Backpropagation od nuly: nejdřív engine, potom síť

Než postavíme stroj, je potřeba vyřešit jednu otázku, protože kdyby odpověď byla opačná, nebylo by co stavět.

Perceptron na XOR selhal, protože jedna přímka neumí oddělit čtyři body. Zřejmá oprava je vrstvení: pošlete vstup přes jednu lineární vrstvu a potom přes další. Pomůže to?

Ne, a důkaz má dva řádky. Lineární vrstva je $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Pošlete ji do další, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, a dosaďte:

Kompozice je $W\mathbf{x} + \mathbf{b}$ s $W = W_2W_1$ a $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Stoh lineárních vrstev je jedna lineární vrstva. Deset z nich, tisíc z nich: pořád jedna přímka, pořád neschopná udělat XOR.

Stojí za to se na to podívat, místo abyste tomu jen věřili:

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

Ne přibližně stejné. Identické bit po bitu, protože jde o tutéž aritmetiku jen jinak přeskupenou.

Hloubka sama o sobě tedy nekupuje nic. Něco kupuje až vložení nelineární funkce mezi vrstvy — a to je celý důvod, proč existují aktivační funkce. Nejsou biologickou ozdobou ani normalizačním trikem. Bez nich je druhá vrstva dekorace.

Teď matematika, a je to jedno pravidlo, které už znáte, jen aplikované na trochu méně známém místě.

Řetězové pravidlo pro jednu proměnnou říká, že pokud $L$ závisí na $c$ a $c$ závisí na $x$, pak $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Derivace se podél řetězce násobí.

Tady je důležité, co se stane, když proměnná napájí více než jednu downstream cestu. Pokud $x$ ovlivňuje $L$ přes $a$ a zároveň přes $b$, příspěvky se sčítají:

Násobit podél cesty, sčítat přes cesty. To je celá backpropagation a každý implementační detail ve zbytku této kapitoly — včetně += v kódu a volání zero_grad(), na kterém klopýtne každý, kdo píše svůj první trénovací cyklus — je přímým důsledkem toho druhého slova.

Vezměte konkrétní obvod o pěti operacích, s $x = 0.5$ a $y = 1.4$:

Všimněte si, že $x$ se objevuje třikrát: v $a$, v $b$ a přímo v $L$. Udělejte backward pass na papíře, zprava doleva, od $\frac{dL}{dL} = 1$:

To číslo si zapamatujte. Za pár stránek ho program vyprodukuje, aniž by mu kdokoli cokoli z toho řekl.

Klíčový poznatek, díky kterému je to programovatelné: každý z těch kroků byl lokální. Abyste protlačili gradient přes uzel násobení, potřebovali jste příchozí gradient a dvě uložené vstupní hodnoty — nic o zbytku obvodu. Každá operace ví, jak diferencovat sama sebe.

Takže vytvořte číslo, které si pamatuje, co ho vytvořilo.

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

Čtyři pole. data je hodnota. grad akumuluje $\frac{\partial L}{\partial \text{self}}$. _prev je množina Value, z nichž bylo toto číslo vypočteno — hrany grafu. A _backward je closure, kterou instaluje každá operace: ví, jak posunout gradient tohoto uzlu o jeden krok zpět do jeho vstupů.

Každý operátor má stejný tvar: vypočítá výstup, zaznamená rodiče, nainstaluje lokální pravidlo.

    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

Čtěte čtyři těla _backward jako tabulku a vzorce toku z papírového odvození jsou přímo tam:

Každý z nich používá += a nikdy =. To je zakódované pravidlo „sčítat přes cesty“. Uzel, který napájí dva spotřebitele, se zavolá dvakrát a oba příspěvky se samy sečtou.

Potom driver, jediná část s globální znalostí:

    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 vytváří topologické uspořádání grafu: každý uzel se objeví až po všech svých vstupech. Projít tento seznam pozpátku zaručuje, že když zavoláte _backward uzlu, jeho vlastní gradient je už kompletní — každý downstream spotřebitel už přispěl. Když pořadí spletete, tlačíte dozadu napůl hotový gradient, což vyrobí špatnou odpověď bez chybové hlášky.

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. Stejné číslo, z programu, kterému bylo řečeno pravidlo pro +, pravidlo pro *, pravidlo pro tanh a nic o tomto obvodu.

Dvě nezávislé kontroly, protože „sedí to s tím, co jsem odvodil“ je slabý test, když oboje dělal tentýž člověk.

Numerická diferenciace. Lehce pohněte vstupem a měřte. Centrální diference $\frac{L(x+h) - L(x-h)}{2h}$ odhaduje derivaci úplně bez kalkulu:

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

Proti PyTorch, který má průmyslový autodiff engine napsaný lidmi, kteří se tím živí:

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

Shoda na $2 \times 10^{-16}$, což je machine epsilon pro 64bitový float: oba enginy provádějí identickou aritmetiku. Numerickou kontrolu si nechte po ruce — je to nástroj pro ladění backward pass nové vrstvy a důvod, proč se dá špatný gradient vůbec najít.

Stejný obvod, jiné vstupy. Nastavte $x = 2$ a $y = -3$, čímž vznikne $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 procházející uzlem $\tanh$ klesl faktorem 9 945. Všechno před ním — ve skutečné síti každá vrstva před ním — nedostává v podstatě nic. Dvě cesty obvodem utichly; signál stále nese jen přímé spojení, které $\tanh$ obchází.

To je problém mizejícího gradientu v jednom uzlu. Naskládejte čtyřicet vrstev $\tanh$ a vynásobte čtyřicet takových faktorů dohromady, a rané vrstvy se přestanou učit úplně. Mimochodem je to také argument pro skip connections, který tady vidíte v miniatuře: jediná cesta, která přežila, byla ta, která obešla nelinearitu.

Každé _backward používá +=. To je správně — tak se sčítají cesty. Má to ale důsledek, který nachytá každého: gradienty se akumulují i napříč voláními backward(). Engine netuší, že vaše druhé volání je nový trénovací krok, a ne další cesta ve stejném grafu.

Trénovací smyčka je tedy musí vyčistit:

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

V PyTorch je to optimizer.zero_grad() a obvyklá rada zní, že když na to zapomenete, trénování se rozbije. Tak ty dva řádky smažme a podívejme se, jak moc rozbité to je. Stejné seed, stejné všechno, 200 kroků XOR:

Při malých learning rate buggy verze vyhrává v každém řádku. Konverguje tam, kde se správná verze zasekne.

Není to náhoda a stojí za to tomu rozumět, protože to vysvětluje, proč se tenhle bug tak těžko chytá. Pokud gradient nikdy nevyčistíte, pak se v kroku $k$ parametr aktualizuje součtem všech dosud vypočtených gradientů. Na ztrátě, která pořád míří zhruba stejným směrem, tento součet stabilně roste a efekt je learning rate, který se sám zvyšuje. Při $\eta = 0.05$, kde se správný algoritmus plazí, vypadá rozjetá velikost kroku přesně jako oprava.

Pak se podívejte na spodní tři řádky. Při $\eta = 0.3$ tentýž mechanismus model roztrhá — loss 8.0 je skóre modelu zkolabovaného na konstantu $\pm 1$, polovina z 16, které by stály čtyři maximálně špatné odpovědi — — zatímco správná verze teď konverguje čistě.

Poctivé tvrzení tedy není „vždy volejte zero_grad, jinak se model nebude trénovat“. Je to: bez něj už neběžíte gradient descent. Běží vám něco, čemu velikost kroku ujíždí nahoru tempem, které nikdo nezvolil, a bude to vypadat, že to funguje, někdy lépe než skutečná věc, až do chvíle, kdy ne — a pak budete vinit learning rate, inicializaci nebo data. Tak vypadají nejhorší bugy ve strojovém učení: nespadnou, změní algoritmus na jiný algoritmus, který občas skóruje lépe.

Když je engine hotový, neuronová síť je sotva pár řádků kódu. Neuron je skalární součin, bias a aktivace; vrstva je seznam neuronů; síť je seznam vrstev.

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

V ničem z toho není žádný backward pass. Ani řádek. Třída Value už ví, jak diferencovat cokoli, co tyto třídy náhodou postaví, a to je pointa toho, že jsme ji napsali jako první: autodiff engine neví, že se používá pro neuronovou síť.

Teď problém z kapitoly 1. Dva vstupy, dvě skryté jednotky, jeden výstup, devět parametrů:

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

Čtyři ze čtyř. Funkce, kterou žádný perceptron neumí spočítat — dokázáno v kapitole 1 čtyřmi nerovnostmi, které vyžadovaly, aby $b$ bylo zároveň kladné i záporné — je spočítána devíti čísly nalezenými automaticky.

Uspokojivé není to, že to funguje. Uspokojivé je vidět jak, protože se dvěma skrytými jednotkami je mezireprezentace bod v rovině a můžete ji prostě vypsat.

Natrénováno na loss 0.001241; tady je, kam po skryté vrstvě dopadne každý vstup a co s ním udělá výstupní neuron:

Podívejte se na první a čtvrtý řádek. Vstupy $(0,0)$ a $(1,1)$ jsou protilehlé rohy čtverce — tak daleko od sebe, jak v tomto problému dva body mohou být — a skrytá vrstva je mapuje na $(0.82, -0.85)$ a $(0.84, -0.86)$. Téměř stejný bod. Vrstva přehnula rovinu tak, aby dva odmítnuté rohy dopadly na sebe, a jakmile jsou na stejném místě, jedna přímka je oddělí od zbylých dvou.

A výstupní neuron je přesně ta přímka. Jeho naučené parametry jsou $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, takže jeho rozhodovací hranice je

což je přímka — perceptron, tentýž objekt z kapitoly 1, beze změny. Tehdy XOR vyřešit nemohl a nemůže ho vyřešit ani teď. Změnilo se to, že už se nedívá na vstup; dívá se do prostoru, který pro něj postavila první vrstva a ve kterém je problém lineárně separovatelný.

To je naučená reprezentace a stojí za to být přesný, protože fráze se po zbytek tohoto kurzu i po zbytek oboru používá volně. Není to komprese, shrnutí ani embedding v nějakém mystickém smyslu. Je to změna souřadnic, naučená místo navržené, jejímž jediným úkolem je usnadnit práci další vrstvě.

Tady existuje věta a obvykle se cituje špatně.

Cybenko v roce 1989 a Hornik v roce 1991 dokázali, že feedforward síť s jedinou skrytou vrstvou a vhodnou aktivační funkcí dokáže aproximovat libovolnou spojitou funkci na kompaktní množině s libovolnou přesností, pokud má dost skrytých jednotek.³⁴ Je to skutečný a důležitý výsledek: říká, že omezením není architektura.

Teď si přečtěte, co vynechává. Neříká, kolik jednotek — hranice může být astronomicky velká. Neříká, že váhy lze najít; tvrdí existenci a gradient descent z náhodného startu není orákulum. A neříká nic o chování na datech, která jste neviděli, což je druhá polovina kapitoly 6.

Mezera mezi „existuje“ a „dá se najít“ není akademická. Tady je stejný problém XOR, 50 náhodných inicializací pro každý případ, 1000 kroků, změnila se jen velikost skryté vrstvy:

S minimální životaschopnou architekturou jeden běh ze čtyř nikdy nedorazí do cíle — usadí se v konfiguraci, ze které nedokáže sestoupit, přesně v lokálním minimu, které kapitola 3 ukázala na jednorozměrné ploše. Přidejte jednu jednotku a selhání téměř zmizí, ne proto, že by se síť stala expresivnější (dvě jednotky už stačí — 38 běhů to dokazuje), ale proto, že další dimenze dávají sestupu více směrů, kudy uniknout.

A pak si osm jednotek vede o něco hůř než čtyři. Při pevném learning rate a rozpočtu kroků není větší kapacita monotonně lepší. Kdokoli vám říká, že oprava zaseknuté sítě je vždy větší síť, extrapoluje ze středu té tabulky.

Je to stejná lekce jako věta o konvergenci v kapitole 1 a bude to stejná lekce v kapitole 10 o scaling laws, ve formě, kterou jí tato kapitola dá: predikce ztráty není predikce schopnosti, za kterou platíte, a prostor mezi nimi je místo, kde žije engineering.

Teď máte síť, která se trénuje. Je to menší úspěch, než jak působí, protože síť, kterou máte, se trénuje na čtyřech příkladech a měří se na stejných čtyřech.

Spusťte stejný kód na skutečném datasetu a objeví se nová sada problémů, z nichž žádný není o gradientech. Loss chvíli klesá a pak se zastaví. Nebo klesá na trénovacích datech a roste na všem ostatním. Nebo se od prvního kroku vůbec nehýbe a ukáže se, že příčinou je rozsah počátečních náhodných vah. Nebo se vstup jedné jednotky ve třetí epoše posunul do záporu na každém příkladu a od té doby je mrtvá, tiše, a bere si s sebou kus kapacity modelu.

To nejsou exotická selhání; je to normální stav sítě, která byla právě napsána, a žádné z nich se samo neohlásí. Gradient je správný — ověřili jste ho proti PyTorch na šestnáct desetinných míst — a model se pořád neučí.

Kapitola 6 je o tom: inicializace, normalizace, overfitting a regularizace a diagnostický návyk ptát se, která z těch věcí se děje, než cokoli změníte. Je to rozdíl mezi sítí, která běží, a sítí, která funguje.

Třída Value v této kapitole přímo vychází z micrograd Andreje Karpathyho a jeho video The spelled-out intro to neural networks and backpropagation: building micrograd jsou nejlepší tři hodiny, které můžete tomuto materiálu věnovat, pokud ho chcete slyšet vysvětlený druhým způsobem od někoho jiného. Jeho příspěvek z roku 2016 Yes you should understand backprop argumentuje pro to, abyste si jednu napsali sami, a je povinnou četbou ve Stanfordském CS224n. Poznámky CS231n k backpropagation (cs231n.github.io/optimization-2) jsou kanonickým zpracováním vzorců toku uvedených v tabulce výše. Pro matematiku jako kalkulus na grafu, a ne jako folklór neuronových sítí, je kapitola 5.6 knihy Mathematics for Machine Learning od Deisenrotha, Faisala a Onga neobvykle jasná; a přehled Baydina, Pearlmuttera, Radula a Siskinda Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) je referencí pro celý obor, včetně výše probíraného kompromisu forward/reverse.