Backpropagation от нулата: първо двигателят, после мрежата

Преди да построим машината, един въпрос трябва да бъде изяснен, защото ако отговорът беше друг, нямаше да има какво да строим.

Perceptron се провали на 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

Не приблизително равни. Идентични бит по бит, защото това е същата аритметика, само пренаредена.

Така че дълбочината сама по себе си не купува нищо. Това, което купува нещо, е поставянето на нелинейна функция между слоевете — и това е цялата причина да съществуват activation functions. Те не са биологична украса или трик за нормализация. Без такава вторият слой е декорация.

Сега математиката, и тя е едно правило, което вече знаете, приложено на малко непознато място.

Верижното правило за една променлива казва, че ако $L$ зависи от $c$ и $c$ зависи от $x$, тогава $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Производните се умножават по веригата.

Частта, която има значение тук, е какво става, когато една променлива захранва повече от един път надолу по веригата. Ако $x$ влияе на $L$ чрез $a$ и също чрез $b$, приносите се събират:

Умножавайте по път, събирайте между пътища. Това е цялото backpropagation, и всеки имплементационен детайл в останалата част от тази глава — включително += в кода и извикването zero_grad(), което препъва всеки, който пише първия си training loop — е пряка последица от тази втора дума.

Вземете конкретна верига от пет операции, с $x = 0.5$ и $y = 1.4$:

Забележете, че $x$ се появява три пъти: в $a$, в $b$ и директно в $L$. Направете backward pass на хартия, отдясно наляво, като започнете от $\frac{dL}{dL} = 1$:

Запомнете това число. След няколко страници програма ще го произведе, без да ѝ е казано нищо от това.

Прозрението, което го прави програмируемо: всяка от тези стъпки беше локална. За да прокарате gradient през възела за умножение, ви трябваха входящият gradient и двете запазени входни стойности — нищо за останалата част от веригата. Всяка операция знае как да диференцира себе си.

Затова направете число, което помни какво го е произвело.

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 е closure, който всяка операция инсталира: той знае как да избута gradient на този възел една стъпка назад към входовете му.

Всеки оператор следва една и съща форма: изчислява изхода, записва родителите, инсталира локалното правило.

    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 като таблица и моделите на потока от извеждането на хартия стоят точно там:

Всяка една използва += и никога =. Това е правилото „събирай между пътищата“, кодирано. Възел, който захранва двама потребители, се извиква два пъти и двата приноса се събират сами.

После driver, който е единствената част с някакво глобално знание:

    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 на възел, неговият собствен gradient вече е пълен — всеки негов downstream потребител вече е допринесъл. Сбъркайте реда и ще изтласкате назад наполовина готов gradient, което дава грешен отговор без съобщение за грешка.

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 engine, написан от хора, които правят това професионално:

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: двата engine изпълняват идентична аритметика. Дръжте числената проверка под ръка — тя е инструментът за debugging на backward pass на нов слой и причината грешен gradient изобщо да може да бъде намерен.

Същата верига, различни входове. Задайте $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

Gradient, който пресича възела $\tanh$, падна с фактор 9 945. Всичко upstream от него — в реална мрежа, всеки слой преди него — получава практически нищо. Двата пътя през веригата са замлъкнали; само директната връзка, която прескача $\tanh$, все още носи сигнал.

Това е проблемът с vanishing gradient в един възел. Подредете четирийсет слоя от $\tanh$ и умножете четирийсет такива фактора, и ранните слоеве спират да учат напълно. Между другото, това е и аргумент за skip connections, който може да се види тук в миниатюра: пътят, който заобиколи нелинейността, е единственият оцелял.

Всеки _backward използва +=. Това е правилно — така се събират пътищата. Но има последствие, което хваща всички: gradients се натрупват и между извикванията на backward(). Engine няма представа, че второто ви извикване е нова training step, а не още един път в същия граф.

Затова training loop трябва да ги изчиства:

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

Това е optimizer.zero_grad() в PyTorch, а обичайният съвет е, че ако го забравите, training се чупи. Нека изтрием тези два реда и видим колко е счупено. Същите seeds, същото всичко, 200 стъпки на XOR:

При малките learning rates buggy версията печели всеки ред. Тя конвергира, когато правилната версия зацикля.

Това не е случайност и си струва да се разбере, защото обяснява защо този bug е толкова труден за улавяне. Ако никога не изчиствате gradient, тогава на стъпка $k$ параметърът се обновява със сумата от всеки gradient, изчислен дотогава. При загуба, която продължава да сочи приблизително в същата посока, тази сума расте стабилно, а ефектът е learning rate, който се увеличава сам. При $\eta = 0.05$, където правилният алгоритъм пълзи, runaway размерът на стъпката изглежда точно като поправка.

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

Така че честното твърдение не е „винаги извиквайте zero_grad, иначе моделът ви няма да се обучи“. То е: без него вече не изпълнявате gradient descent. Изпълнявате нещо, чийто размер на стъпката пълзи нагоре със скорост, която никой не е избрал, и то ще изглежда, че работи — понякога по-добре от истинското нещо — точно докато спре. Тогава ще обвините learning rate, инициализацията или данните. Това е формата на най-лошите bugs в machine learning: те не crash-ват, те променят алгоритъма в различен алгоритъм, който понякога постига по-добър резултат.

След като engine е готов, neural network е почти никакъв код. Невронът е dot product, bias и активация; слой е списък от неврони; мрежа е списък от слоеве.

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()]

Във всичко това няма backward pass. Нито един ред. Класът Value вече знае как да диференцира каквото тези класове построят, и това е смисълът да го напишем първо: autodiff engine не знае, че се използва за neural network.

Сега проблемът от Глава 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

Четири от четири. Функцията, която никой perceptron не може да изчисли — доказано в Глава 1 с четири неравенства, които изискваха $b$ да бъде едновременно положително и отрицателно — се изчислява от девет числа, намерени автоматично.

Удовлетворяващата част не е, че работи. А че можем да видим как, защото с две скрити единици междинното представяне е точка в равнина и можете просто да го отпечатате.

Обучен до loss 0.001241, ето къде попада всеки вход след скрития слой и какво прави изходният неврон с него:

Погледнете първия и четвъртия ред. Входовете $(0,0)$ и $(1,1)$ са диагонално противоположни ъгли на квадрата — толкова далеч един от друг, колкото две точки в този проблем могат да бъдат — а скритият слой ги мапва към $(0.82, -0.85)$ и $(0.84, -0.86)$. Почти една и съща точка. Слоят е сгънал равнината така, че двата отхвърлени ъгъла да попаднат един върху друг, и щом са на едно и също място, една линия ги разделя от другите два.

А изходният неврон е точно тази линия. Научените му параметри са $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, така че неговата decision boundary е

което е права линия — perceptron, същият обект от Глава 1, непроменен. Тогава той не можеше да реши XOR и не може и сега. Това, което се промени, е, че вече не гледа входа; гледа пространство, което първият слой е построил за него, в което проблемът е linearly separable.

Това е научено представяне, и си струва да бъдем точни, защото фразата се използва свободно през останалата част от този курс и през останалата част от областта. То не е компресия, резюме или embedding в някакъв мистичен смисъл. То е промяна на координатите, научена, а не проектирана, чиято единствена работа е да направи работата на следващия слой лесна.

Тук има теорема и тя обикновено се цитира лошо.

Cybenko през 1989 г. и Hornik през 1991 г. доказаха, че feedforward network с един скрит слой и подходяща activation function може да апроксимира всяка непрекъсната функция върху компактен набор до каквато точност искате, ако има достатъчно скрити единици.³⁴ Това е истински и важен резултат: казва, че архитектурата не е ограничението.

Сега прочетете какво пропуска. Не казва колко единици — границата може да е астрономически голяма. Не казва, че теглата могат да бъдат намерени; твърди съществуване, а gradient descent от случаен старт не е оракул. И не казва нищо за поведението върху данни, които не сте виждали, което е втората половина на Глава 6.

Пропастта между „съществува“ и „може да се намери“ не е академична. Ето същия XOR проблем, по 50 случайни инициализации, 1000 стъпки, променен е само размерът на скрития слой:

С минимално жизнеспособната архитектура един от четири run-а така и не стига дотам — установява се в конфигурация, от която не може да слезе, точно локалният минимум, който Глава 3 показа върху едномерна повърхност. Добавете една единица и провалите почти изчезват — не защото мрежата е станала по-изразителна (две единици вече стигат — 38 run-а го доказват), а защото допълнителните измерения дават на descent повече посоки за бягство.

А после осем единици се справят леко по-зле от четири. При фиксиран learning rate и бюджет от стъпки, повече капацитет не е монотонно по-добре. Всеки, който ви казва, че поправката за зациклила мрежа винаги е по-голяма мрежа, екстраполира от средата на тази таблица.

Това е същият урок като теоремата за конвергенция в Глава 1, и ще бъде същият урок в Глава 10 за scaling laws, във формата, която тази глава му дава: прогноза за loss не е прогноза за способността, за която плащате, а разстоянието между двете е мястото, където живее инженерството.

Вече имате мрежа, която се обучава. Това е по-малко постижение, отколкото изглежда, защото мрежата ви се обучава върху четири примера и се измерва върху същите четири.

Пуснете същия код върху реален набор от данни и се появява нов набор от проблеми, нито един от които не е за gradients. Loss намалява известно време и после спира. Или намалява върху training данните и се покачва върху всичко друго. Или изобщо не помръдва от първата стъпка, а причината се оказва диапазонът на началните случайни тегла. Или входът на една единица е дрейфнал отрицателно за всеки пример в епоха три и тя оттогава е мъртва — тихо, вземайки със себе си парче от капацитета на модела.

Това не са екзотични провали; това е нормалното състояние на мрежа, която току-що е написана, и нито един от тях не се обявява сам. Gradient е правилен — сверихте го с 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) са каноничното изложение на моделите на потока, табулирани по-горе. За математиката като смятане върху граф, а не като фолклор на neural network, глава 5.6 от Mathematics for Machine Learning на Deisenroth, Faisal и Ong е необичайно ясна; а обзорът на Baydin, Pearlmutter, Radul и Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) е референцията за областта като цяло, включително компромиса forward/reverse, обсъден по-горе.