Backpropagation з нуля: спершу рушій, потім мережа

Перш ніж будувати машину, треба закрити одне питання, бо якби відповідь була іншою, будувати було б нічого.

Перцептрон провалився на XOR, бо одна пряма не може розділити чотири точки. Очевидне виправлення — скласти шари: пропустити вхід через один лінійний шар, потім через інший. Це допоможе?

Ні, і доказ займає два рядки. Лінійний шар — це $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Подайте його в інший, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, і підставте:

Композиція — це $W\mathbf{x} + \mathbf{b}$ з $W = W_2W_1$ і $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Стек лінійних шарів — це один лінійний шар. Десять таких, тисяча таких: усе ще одна пряма, усе ще нездатна розвʼязати XOR.

Краще побачити, як це відбувається, ніж просто повірити:

import numpy as np
rng = np.random.default_rng(0)
W1, b1 = rng.normal(size=(3, 2)), rng.normal(size=3)
W2, b2 = rng.normal(size=(1, 3)), rng.normal(size=1)
x = rng.normal(size=2)

two_layers = W2 @ (W1 @ x + b1) + b2
one_layer  = (W2 @ W1) @ x + (W2 @ b1 + b2)
print(two_layers[0], one_layer[0], abs(two_layers[0] - one_layer[0]))

-4.612963371048  -4.612963371048  0.00e+00

Не приблизно рівні. Ідентичні біт у біт, бо це та сама арифметика, лише переставлена.

Отже, глибина сама по собі нічого не дає. Щось дає вставлення нелінійної функції між шарами — і саме тому існують функції активації. Це не біологічна прикраса й не трюк нормалізації. Без неї другий шар — декорація.

Тепер математика, і це одне правило, яке ви вже знаєте, застосоване в трохи незвичному місці.

Ланцюгове правило для однієї змінної каже: якщо $L$ залежить від $c$, а $c$ залежить від $x$, тоді $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Похідні множаться уздовж ланцюга.

Тут важлива частина — що відбувається, коли змінна живить більше ніж один подальший шлях. Якщо $x$ впливає на $L$ через $a$ і також через $b$, внески додаються:

Множте вздовж шляху, підсумовуйте між шляхами. Це і є весь backpropagation, і кожна деталь реалізації в решті розділу — включно з += у коді та викликом zero_grad(), на якому спотикається кожен, хто пише свій перший цикл навчання, — є прямим наслідком цього другого слова.

Візьмімо конкретну схему з пʼяти операцій, де $x = 0.5$ і $y = 1.4$:

Зверніть увагу, що $x$ зʼявляється тричі: у $a$, у $b$ і безпосередньо в $L$. Виконайте зворотний прохід на папері, справа наліво, починаючи з $\frac{dL}{dL} = 1$:

Запамʼятайте це число. За кілька сторінок програма видасть його, хоча їй нічого з цього не розповідали.

Інсайт, який робить це програмованим: кожен із цих кроків був локальним. Щоб проштовхнути градієнт через вузол множення, потрібні вхідний градієнт і два збережені вхідні значення — нічого про решту схеми. Кожна операція знає, як диференціювати саму себе.

Тож зробімо число, яке памʼятає, що його породило.

class Value:
    """A number that remembers where it came from."""

    def __init__(self, data, _children=(), _op=""):
        self.data = data
        self.grad = 0.0
        self._backward = lambda: None
        self._prev = set(_children)      
        self._op = _op

Чотири поля. data — значення. grad накопичує $\frac{\partial L}{\partial \text{self}}$. _prev — множина Value, з яких було обчислено це значення, тобто ребра графа. А _backward — замикання, яке встановлює кожна операція: воно знає, як проштовхнути градієнт цього вузла на один крок назад до його входів.

Кожен оператор має ту саму форму: обчислити вихід, записати батьків, встановити локальне правило.

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data + other.data, (self, other), "+")

        def _backward():
            self.grad += out.grad       
            other.grad += out.grad      

        out._backward = _backward
        return out

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data * other.data, (self, other), "*")

        def _backward():
            self.grad += other.data * out.grad   
            other.grad += self.data * out.grad   

        out._backward = _backward
        return out

    def tanh(self):
        t = math.tanh(self.data)
        out = Value(t, (self,), "tanh")

        def _backward():
            self.grad += (1 - t * t) * out.grad

        out._backward = _backward
        return out

    def relu(self):
        out = Value(self.data if self.data > 0 else 0.0, (self,), "relu")

        def _backward():
            self.grad += (1.0 if out.data > 0 else 0.0) * out.grad

        out._backward = _backward
        return out

Прочитайте чотири тіла _backward як таблицю, і патерни потоку з паперового виведення будуть прямо перед вами:

Кожна з них використовує += і ніколи =. Це правило «підсумовувати між шляхами», закодоване. Вузол, який живить двох споживачів, викликається двічі, і два внески додаються самі.

Потім драйвер — єдина частина з глобальним знанням:

    def backward(self):
        order, seen = [], set()

        def build(v):
            if v in seen:
                return
            seen.add(v)
            for child in v._prev:
                build(child)
            order.append(v)

        build(self)
        self.grad = 1.0
        for v in reversed(order):       
            v._backward()               

build створює топологічне впорядкування графа: кожен вузол зʼявляється після всіх своїх входів. Прохід цим списком у зворотному напрямку гарантує, що коли ви викликаєте _backward вузла, його власний градієнт уже повний — кожен downstream-споживач уже зробив внесок. Помиліться з порядком, і ви проштовхнете назад напівготовий градієнт, що дасть неправильну відповідь без жодного повідомлення про помилку.

x = Value(0.5)
y = Value(1.4)
a = x * y
b = x + y
c = a * b
d = c.tanh()
L = d + x
L.backward()
print(x.grad, y.grad)

forward:  a=0.7000  b=1.9000  c=1.3300  d=0.8692  L=1.3692
backward: dL/dd=1.0000  dL/dc=0.2444  dL/da=0.4644  dL/db=0.1711
          dL/dx=1.8212   dL/dy=0.4033

1.8212. Те саме число, від програми, якій повідомили правило для +, правило для *, правило для tanh — і нічого про цю схему.

Дві незалежні перевірки, бо «збігається з тим, що я вивів» — слабкий тест, коли обидві частини робила та сама людина.

Чисельне диференціювання. Трохи зсуньте вхід і виміряйте. Центральна різниця $\frac{L(x+h) - L(x-h)}{2h}$ оцінює похідну без жодного математичного аналізу:

dL/dx:  analytic=1.821202805  numeric=1.821202805  |diff|=1.80e-10
dL/dy:  analytic=0.403269235  numeric=0.403269235  |diff|=7.64e-12

Проти PyTorch, у якого є промисловий autodiff-рушій, написаний людьми, які роблять це професійно:

torch dL/dx=1.821202805316   ours=1.821202805316   |diff|=2.22e-16
torch dL/dy=0.403269234753   ours=0.403269234753   |diff|=1.11e-16

Збіг на рівні $2 \times 10^{-16}$, тобто machine epsilon для 64-бітного float: два рушії виконують ідентичну арифметику. Тримайте чисельну перевірку під рукою — це інструмент для налагодження зворотного проходу нового шару, і саме завдяки йому неправильний градієнт узагалі можна знайти.

Та сама схема, інші входи. Задайте $x = 2$ і $y = -3$, що робить $c = 6$:

x=0.5, y=1.4:  dL/dc = 0.244400     three paths into x:  0.6501 + 0.1711 + 1.0000 = 1.8212
x=2.0, y=-3.0: dL/dc = 0.000025     three paths into x:  0.0001 + -0.0001 + 1.0000 = 0.9999

Градієнт, який перетинає вузол $\tanh$, впав у 9 945 разів. Усе upstream від нього — у реальній мережі кожен шар перед ним — фактично не отримує нічого. Два шляхи через схему замовкли; сигнал усе ще несе лише пряме зʼєднання, яке обходить $\tanh$.

Це проблема зникаючого градієнта в одному вузлі. Складіть сорок шарів $\tanh$ і перемножте сорок таких множників, і ранні шари повністю перестануть навчатися. До речі, це також аргумент на користь skip connections, який тут видно в мініатюрі: шлях, що обійшов нелінійність, — єдиний, який вижив.

Кожен _backward використовує +=. Це правильно — саме так шляхи підсумовуються. Але з цього випливає наслідок, на який натрапляють усі: градієнти накопичуються і між викликами backward() теж. Рушій не має уявлення, що ваш другий виклик — це новий крок навчання, а не ще один шлях у тому самому графі.

Тож цикл навчання має очищати їх:

for step in range(steps):
    ys = [model(x) for x, _ in DATA]
    loss = sum((yp - yt) ** 2 for yp, (_, yt) in zip(ys, DATA))

    for p in model.parameters():   
        p.grad = 0.0

    loss.backward()
    for p in model.parameters():
        p.data -= lr * p.grad

У PyTorch це optimizer.zero_grad(), і звична порада каже, що якщо забути його, навчання зламається. Тож видалімо ці два рядки й подивімося, наскільки воно зламане. Ті самі seeds, усе те саме, 200 кроків XOR:

На малих learning rate версія з багом перемагає в кожному рядку. Вона сходиться тоді, коли правильна версія застрягає.

Це не випадковість, і це варто зрозуміти, бо саме тому цей баг так важко зловити. Якщо ви ніколи не очищаєте градієнт, то на кроці $k$ параметр оновлюється сумою всіх градієнтів, обчислених дотепер. На втраті, яка продовжує вказувати приблизно в той самий бік, ця сума стабільно зростає, і ефект схожий на learning rate, що збільшується сам собою. При $\eta = 0.05$, коли правильний алгоритм повзе, неконтрольований розмір кроку виглядає саме як виправлення.

Потім подивіться на три нижні рядки. При $\eta = 0.3$ той самий механізм розносить модель — loss 8.0 отримує модель, що схлопнулася до сталої $\pm 1$, це половина від 16, які коштували б чотири максимально неправильні відповіді — — тоді як правильна версія тепер сходиться чисто.

Отже, чесне твердження не «завжди викликайте zero_grad, інакше модель не навчатиметься». Воно таке: без цього ви більше не запускаєте gradient descent. Ви запускаєте щось, чий розмір кроку дрейфує вгору зі швидкістю, яку ніхто не обирав, і це здаватиметься робочим — іноді кращим за справжній алгоритм — аж доки перестане. І тоді ви звинуватите learning rate, ініціалізацію або дані. Саме так виглядають найгірші баги в machine learning: вони не падають, вони перетворюють алгоритм на інший алгоритм, який іноді показує кращий результат.

Коли рушій готовий, нейронна мережа — це зовсім небагато коду. Нейрон — це dot product, bias і activation; шар — список нейронів; мережа — список шарів.

class Neuron:
    def __init__(self, nin):
        self.w = [Value(random.uniform(-1, 1)) for _ in range(nin)]
        self.b = Value(0.0)

    def __call__(self, x):
        act = sum((wi * xi for wi, xi in zip(self.w, x)), self.b)
        return act.tanh()

    def parameters(self):
        return self.w + [self.b]


class Layer:
    def __init__(self, nin, nout):
        self.neurons = [Neuron(nin) for _ in range(nout)]

    def __call__(self, x):
        out = [n(x) for n in self.neurons]
        return out[0] if len(out) == 1 else out

    def parameters(self):
        return [p for n in self.neurons for p in n.parameters()]


class MLP:
    def __init__(self, nin, nouts):
        sizes = [nin] + nouts
        self.layers = [Layer(sizes[i], sizes[i + 1]) for i in range(len(nouts))]

    def __call__(self, x):
        for layer in self.layers:
            x = layer(x)
        return x

    def parameters(self):
        return [p for layer in self.layers for p in layer.parameters()]

У всьому цьому немає зворотного проходу. Жодного рядка. Клас Value уже знає, як диференціювати все, що ці класи випадково побудують, і саме в цьому сенс того, що ми спершу написали його: autodiff-рушій не знає, що його використовують для нейронної мережі.

Тепер задача з Розділу 1. Два входи, два приховані вузли, один вихід, девʼять параметрів:

step   1: loss 4.156690
step  10: loss 4.005572
step  50: loss 3.996708
step 100: loss 3.510700
step 200: loss 0.038597

[0, 0] -> -0.9081  (target -1)  ok
[0, 1] -> +0.8934  (target +1)  ok
[1, 0] -> +0.8906  (target +1)  ok
[1, 1] -> -0.9207  (target -1)  ok

Чотири з чотирьох. Функцію, яку не може обчислити жоден перцептрон — у Розділі 1 це було доведено чотирма нерівностями, які вимагали, щоб $b$ було водночас додатним і відʼємним, — обчислено девʼятьма числами, знайденими автоматично.

Приємна частина не в тому, що це працює. А в тому, що можна побачити як, бо з двома прихованими вузлами проміжне представлення — це точка на площині, і її можна просто надрукувати.

Після навчання до втрати 0.001241 ось куди потрапляє кожен вхід після прихованого шару і що з ним робить вихідний нейрон:

Подивіться на перший і четвертий рядки. Входи $(0,0)$ і $(1,1)$ — діагонально протилежні кути квадрата, настільки далекі один від одного, наскільки взагалі можуть бути дві точки в цій задачі, — а прихований шар відображає їх у $(0.82, -0.85)$ і $(0.84, -0.86)$. Майже в ту саму точку. Шар склав площину так, що два відхилені кути лягли один на одного, і коли вони опинилися в одному місці, одна пряма відділяє їх від двох інших.

І вихідний нейрон — саме ця пряма. Його вивчені параметри — $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, тож його межа рішення така:

Це пряма лінія — перцептрон, той самий обʼєкт із Розділу 1, без змін. Тоді він не міг розвʼязати XOR і зараз не може. Змінилося те, що він більше не дивиться на вхід; він дивиться на простір, який перший шар побудував для нього, і в цьому просторі задача лінійно роздільна.

Саме це і є вивчене представлення, і варто бути точними, бо цю фразу в решті курсу й у решті галузі вживають вільно. Це не стиснення, не резюме й не embedding у якомусь містичному сенсі. Це зміна координат, вивчена, а не спроєктована, чия єдина робота — полегшити роботу наступного шару.

Тут є теорема, і її зазвичай цитують погано.

Cybenko у 1989 році та Hornik у 1991 році довели, що feedforward-мережа з одним прихованим шаром і відповідною функцією активації може апроксимувати будь-яку неперервну функцію на компактній множині з будь-якою бажаною точністю, якщо має достатньо прихованих вузлів.³⁴ Це справжній і важливий результат: він каже, що архітектура не є обмеженням.

Тепер прочитайте, що він пропускає. Він не каже, скільки вузлів — межа може бути астрономічно великою. Він не каже, що ваги можна знайти; він стверджує існування, а gradient descent з випадкового старту — не оракул. І він нічого не каже про поведінку на даних, яких ви не бачили, а це друга половина Розділу 6.

Розрив між «існує» і «можна знайти» не академічний. Ось та сама задача XOR: по 50 випадкових ініціалізацій, 1000 кроків, змінювався лише розмір прихованого шару:

З мінімально життєздатною архітектурою один запуск із чотирьох так і не доходить — він осідає в конфігурацію, з якої не може спуститися, рівно той локальний мінімум, який Розділ 3 показав на одновимірній поверхні. Додайте один вузол — і відмови майже зникають, не тому що мережа стала виразнішою (двох вузлів уже достатньо — 38 запусків це доводять), а тому що додаткові виміри дають спуску більше напрямків для втечі.

А потім вісім вузлів працюють трохи гірше, ніж чотири. За фіксованого learning rate і бюджету кроків більша місткість не є монотонно кращою. Будь-хто, хто каже вам, що виправлення для застряглої мережі — це завжди більша мережа, екстраполює з середини цієї таблиці.

Це той самий урок, що й теорема збіжності в Розділі 1, і це буде той самий урок у Розділі 10 про scaling laws, у формі, яку дає той розділ: прогноз втрати — це не прогноз здатності, за яку ви платите, а відстань між ними — саме там живе інженерія.

Тепер у вас є мережа, яка навчається. Це менше досягнення, ніж здається, бо ваша мережа навчається на чотирьох прикладах і вимірюється на тих самих чотирьох.

Запустіть той самий код на справжньому наборі даних, і зʼявиться новий набір проблем, жодна з яких не про градієнти. Втрата якийсь час зменшується, а потім зупиняється. Або вона зменшується на тренувальних даних і зростає на всьому іншому. Або не рухається взагалі з першого кроку, і причиною виявляється діапазон початкових випадкових ваг. Або вхід одного вузла став відʼємним на кожному прикладі в третю епоху, і відтоді він мертвий — мовчки, забравши із собою шматок місткості моделі.

Це не екзотичні відмови; це нормальний стан мережі, яку щойно написали, і жодна з них не оголошує про себе. Градієнт правильний — ви звірили його з PyTorch до шістнадцяти десяткових знаків — а модель усе одно не навчається.

Розділ 6 саме про це: ініціалізація, нормалізація, overfitting і regularisation, а також діагностична звичка питати, що саме з цього відбувається, перш ніж щось змінювати. Це різниця між мережею, яка запускається, і мережею, яка працює.

Клас Value у цьому розділі напряму походить від micrograd Andrej Karpathy, а його відео The spelled-out intro to neural networks and backpropagation: building micrograd — найкращі три години, які ви можете витратити на цей матеріал, якщо хочете почути пояснення вдруге від когось іншого. Його пост 2016 року Yes you should understand backprop доводить, чому варто написати такий рушій самостійно, і входить до обовʼязкового читання в Stanford CS224n. Нотатки CS231n про backpropagation (cs231n.github.io/optimization-2) — канонічний виклад патернів потоку, зведених у таблицю вище. Для математики як математичного аналізу на графі, а не як фольклору нейронних мереж, розділ 5.6 книги Mathematics for Machine Learning Deisenroth, Faisal і Ong незвично ясний; а огляд Baydin, Pearlmutter, Radul і Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) — головна довідка для всієї галузі, включно з компромісом між прямим і зворотним режимами, обговореним вище.