Backpropagation vanaf nul: eerst de engine, dan het netwerk

Voordat we de machine bouwen, moet één vraag worden beantwoord, want als het antwoord anders was geweest, was er niets om te bouwen.

De perceptron faalde op XOR omdat één lijn de vier punten niet kan scheiden. De voor de hand liggende oplossing is stapelen: stuur de input door één lineaire laag, en daarna door nog een. Helpt dat?

Nee, en het bewijs is twee regels. Een lineaire laag is $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Voer die aan een andere, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, en substitueer:

De compositie is $W\mathbf{x} + \mathbf{b}$ met $W = W_2W_1$ en $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Een stapel lineaire lagen is één lineaire laag. Tien ervan, duizend ervan: nog steeds één lijn, nog steeds niet in staat om XOR te doen.

Het is de moeite waard om dat te zien gebeuren in plaats van het te geloven:

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

Niet ongeveer gelijk. Bit-voor-bit identiek, omdat het dezelfde rekenkunde is, alleen herschikt.

Diepte levert dus op zichzelf niets op. Wat wel iets oplevert, is een niet-lineaire functie tussen de lagen plaatsen — en dat is de hele reden dat activation functions bestaan. Ze zijn geen biologische versiering of een normalisatietruc. Zonder zo’n functie is de tweede laag decoratie.

Nu de wiskunde, en het is één regel die je al kent, toegepast op een plek die net wat minder vertrouwd is.

De kettingregel voor één variabele zegt dat als $L$ afhangt van $c$ en $c$ afhangt van $x$, dan $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Afgeleiden vermenigvuldigen langs een keten.

Het deel dat hier belangrijk is, is wat er gebeurt wanneer een variabele meer dan één downstream pad voedt. Als $x$ $L$ beïnvloedt via $a$ en ook via $b$, dan tellen de bijdragen op:

Vermenigvuldig langs een pad, sommeer over paden. Dat is heel backpropagation, en elk implementatiedetail in de rest van dit hoofdstuk — inclusief de += in de code en de zero_grad()-aanroep waar iedereen over struikelt die zijn eerste training loop schrijft — is een direct gevolg van dat tweede woord.

Neem een concreet circuit van vijf operaties, met $x = 0.5$ en $y = 1.4$:

Merk op dat $x$ drie keer voorkomt: in $a$, in $b$, en rechtstreeks in $L$. Doe de backward pass op papier, van rechts naar links, beginnend bij $\frac{dL}{dL} = 1$:

Onthoud dat getal. Over een paar pagina’s gaat een programma het produceren zonder dat het hiervan iets is verteld.

Het inzicht dat dit programmeerbaar maakt: elke van die stappen was lokaal. Om een gradient door de vermenigvuldigingsnode te duwen, had je de binnenkomende gradient en de twee opgeslagen inputwaarden nodig — niets over de rest van het circuit. Elke operatie weet hoe hij zichzelf moet differentiëren.

Maak dus een getal dat onthoudt wat het heeft geproduceerd.

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

Vier velden. data is de waarde. grad accumuleert $\frac{\partial L}{\partial \text{self}}$. _prev is de verzameling Values waaruit deze is berekend — de randen van de grafiek. En _backward is een closure die elke operatie installeert: die weet hoe hij de gradient van deze node één stap terug naar zijn inputs moet duwen.

Elke operator volgt dezelfde vorm: bereken de output, noteer de parents, installeer de lokale regel.

    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

Lees de vier _backward-bodies als een tabel en de flowpatronen uit de papieren afleiding staan er meteen:

Elke gebruikt += en nooit =. Dat is de regel „sommeer over paden”, gecodeerd. Een node die twee consumers voedt, wordt twee keer aangeroepen, en de twee bijdragen tellen vanzelf op.

Dan de driver, het enige deel met globale kennis:

    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 produceert een topologische ordening van de grafiek: elke node verschijnt na al zijn inputs. Door die lijst omgekeerd te doorlopen, garandeer je dat wanneer je de _backward van een node aanroept, zijn eigen gradient al compleet is — elke consumer downstream ervan heeft al bijgedragen. Doe je de volgorde verkeerd, dan duw je een half afgemaakte gradient achteruit, wat een verkeerd antwoord oplevert zonder foutmelding.

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. Hetzelfde getal, uit een programma dat de regel voor + kreeg, de regel voor *, de regel voor tanh, en niets over dit circuit.

Twee onafhankelijke controles, omdat „het klopt met wat ik heb afgeleid” een zwakke test is wanneer dezelfde persoon beide deed.

Numerieke differentiatie. Geef de input een duwtje en meet. Het centrale verschil $\frac{L(x+h) - L(x-h)}{2h}$ schat de afgeleide zonder enige calculus:

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

Tegen PyTorch, dat een industriële autodiff-engine heeft, geschreven door mensen die dit voor hun werk doen:

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

Overeenstemming op $2 \times 10^{-16}$, wat machine epsilon is voor een 64-bit float: de twee engines voeren identieke rekenkunde uit. Houd de numerieke check bij de hand — het is de tool om de backward pass van een nieuwe laag te debuggen, en het is de reden dat een verkeerde gradient überhaupt vindbaar is.

Hetzelfde circuit, andere inputs. Zet $x = 2$ en $y = -3$, wat $c = 6$ maakt:

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

De gradient die de $\tanh$-node passeert, viel met een factor 9.945. Alles upstream ervan — in een echt netwerk elke laag ervoor — ontvangt vrijwel niets. De twee paden door het circuit zijn stilgevallen; alleen de directe verbinding die de $\tanh$ overslaat, draagt nog signaal.

Dat is het vanishing gradient-probleem, in één node. Stapel veertig lagen $\tanh$ en vermenigvuldig veertig van zulke factoren met elkaar, en de vroege lagen stoppen volledig met leren. Het is trouwens ook een argument voor skip connections dat je hier in het klein kunt zien: het pad dat de non-lineariteit omzeilde, is het enige dat overleefde.

Elke _backward gebruikt +=. Dat is correct — zo sommeren paden. Maar het heeft een consequentie die iedereen te pakken krijgt: gradients accumuleren ook over aanroepen naar backward() heen. De engine heeft geen idee dat je tweede aanroep een nieuwe training step is in plaats van nog een pad in dezelfde grafiek.

Een training loop moet ze dus wissen:

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

Dit is optimizer.zero_grad() in PyTorch, en het gebruikelijke advies is dat vergeten ervan training breekt. Dus laten we die twee regels verwijderen en kijken hoe kapot het is. Zelfde seeds, alles hetzelfde, 200 stappen XOR:

Bij de kleine learning rates wint de buggy versie elke rij. Hij convergeert wanneer de correcte versie vastloopt.

Dat is geen toeval en het is de moeite waard om te begrijpen, omdat het verklaart waarom deze bug zo moeilijk te vinden is. Als je de gradient nooit wist, dan wordt de parameter bij stap $k$ bijgewerkt met de som van elke gradient die tot dan toe is berekend. Op een loss die grofweg dezelfde kant op blijft wijzen, groeit die som gestaag, en het effect is een learning rate die vanzelf toeneemt. Bij $\eta = 0.05$, waar het correcte algoritme kruipt, ziet de weglopende stapgrootte er precies uit als een oplossing.

Kijk dan naar de onderste drie rijen. Bij $\eta = 0.3$ blaast hetzelfde mechanisme het model uit elkaar — loss 8.0 is wat een model scoort dat is ingestort tot een constante $\pm 1$ — de helft van de 16 die vier maximaal verkeerde antwoorden zouden kosten — — terwijl de correcte versie nu netjes convergeert.

De eerlijke uitspraak is dus niet „roep altijd zero_grad aan of je model traint niet”. Het is: zonder dit voer je geen gradient descent meer uit. Je draait iets waarvan de stapgrootte omhoog drijft met een tempo dat niemand heeft gekozen, en het zal lijken te werken, soms beter dan het echte ding, tot het dat niet meer doet — waarna je de learning rate, de initialisatie of de data de schuld geeft. Dit is de vorm van de ergste bugs in machine learning: ze crashen niet, ze veranderen het algoritme in een ander algoritme dat soms beter scoort.

Nu de engine klaar is, is een neural network nauwelijks nog code. Een neuron is een dot product, een bias en een activatie; een laag is een lijst neuronen; een netwerk is een lijst lagen.

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

Er staat nergens een backward pass in. Geen enkele regel. De Value-klasse weet al hoe hij moet differentiëren wat deze klassen ook bouwen, en dat is precies waarom we hem eerst hebben geschreven: een autodiff-engine weet niet dat hij voor een neural network wordt gebruikt.

Nu het probleem uit Hoofdstuk 1. Twee inputs, twee verborgen units, één output, negen parameters:

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

Vier uit vier. De functie die geen perceptron kan berekenen — in Hoofdstuk 1 bewezen met vier ongelijkheden die eisten dat $b$ zowel positief als negatief was — wordt berekend door negen automatisch gevonden getallen.

Het bevredigende is niet dat het werkt. Het is dat je kunt zien hoe, want met twee verborgen units is de tussenrepresentatie een punt in een vlak en kun je die gewoon printen.

Getraind tot een loss van 0.001241, hier is waar elke input na de verborgen laag terechtkomt, en wat het outputneuron ermee doet:

Kijk naar de eerste en vierde rij. De inputs $(0,0)$ en $(1,1)$ zijn diagonaal tegenoverliggende hoeken van het vierkant — zo ver uit elkaar als twee punten in dit probleem kunnen liggen — en de verborgen laag mapt ze naar $(0.82, -0.85)$ en $(0.84, -0.86)$. Bijna hetzelfde punt. De laag heeft het vlak gevouwen zodat de twee afgewezen hoeken op elkaar landen, en zodra ze op dezelfde plek liggen, scheidt één lijn ze van de andere twee.

En het outputneuron is precies die lijn. Zijn geleerde parameters zijn $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, dus zijn beslissingsgrens is

en dat is een rechte lijn — een perceptron, hetzelfde object uit Hoofdstuk 1, onveranderd. Toen kon hij XOR niet oplossen en nu kan hij dat nog steeds niet. Wat veranderde, is dat hij niet meer naar de input kijkt; hij kijkt naar een ruimte die de eerste laag voor hem heeft gebouwd, waarin het probleem lineair scheidbaar is.

Dat is wat een geleerde representatie is, en het is de moeite waard om precies te zijn, omdat de term in de rest van deze cursus en in de rest van het veld losjes wordt gebruikt. Het is geen compressie, samenvatting of embedding in mystieke zin. Het is een verandering van coördinaten, geleerd in plaats van ontworpen, waarvan de enige taak is om de taak van de volgende laag makkelijk te maken.

Er is hier een theorema, en dat wordt meestal slecht geciteerd.

Cybenko in 1989 en Hornik in 1991 bewezen dat een feedforward-netwerk met één verborgen laag en een geschikte activation function elke continue functie op een compacte verzameling kan benaderen, tot elke nauwkeurigheid die je wilt, mits er genoeg verborgen units zijn.³⁴ Het is een echt en belangrijk resultaat: het zegt dat de architectuur niet de beperking is.

Lees nu wat het weglaat. Het zegt niet hoeveel units — de grens kan astronomisch groot zijn. Het zegt niet dat de gewichten gevonden kunnen worden; het stelt bestaan, en gradient descent vanaf een willekeurige start is geen orakel. En het zegt niets over gedrag op data die je niet hebt gezien, wat de tweede helft van Hoofdstuk 6 is.

De kloof tussen „bestaat” en „vindbaar” is niet academisch. Hier is hetzelfde XOR-probleem, 50 willekeurige initialisaties elk, 1000 stappen, alleen de grootte van de verborgen laag veranderd:

Met de minimaal levensvatbare architectuur komt één run op vier er nooit — hij nestelt zich in een configuratie waar hij niet uit kan afdalen, precies het lokale minimum dat Hoofdstuk 3 liet zien op een eendimensionaal oppervlak. Voeg één unit toe en de mislukkingen verdwijnen bijna, niet omdat het netwerk expressiever werd (twee units zijn al genoeg — 38 runs bewijzen het) maar omdat extra dimensies de afdaling meer richtingen geven om door te ontsnappen.

En dan doet acht units het iets slechter dan vier. Bij een vaste learning rate en een vast stappenbudget is meer capaciteit niet monotoon beter. Iedereen die je vertelt dat de oplossing voor een vastgelopen netwerk altijd een groter netwerk is, extrapoleert vanuit het midden van die tabel.

Dit is dezelfde les als de convergentiestelling in Hoofdstuk 1, en het zal dezelfde les zijn in Hoofdstuk 10 over scaling laws, in de vorm die dat hoofdstuk eraan geeft: een voorspelling van de loss is geen voorspelling van de capability waarvoor je betaalt, en de afstand tussen die twee is waar de engineering leeft.

Je hebt nu een netwerk dat traint. Dat is een kleinere prestatie dan het voelt, omdat het netwerk dat je hebt traint op vier voorbeelden en op dezelfde vier wordt gemeten.

Draai dezelfde code op een echte dataset en er verschijnt een nieuwe reeks problemen, waarvan geen enkele over gradients gaat. De loss daalt een tijdje en stopt dan. Of hij daalt op de trainingsdata en stijgt op al het andere. Of hij beweegt vanaf de eerste stap helemaal niet, en de oorzaak blijkt het bereik van de initiële willekeurige gewichten te zijn. Of de input van één unit is in epoch drie bij elk voorbeeld negatief geworden en sindsdien is die unit dood, stilletjes, terwijl hij een stuk van de capaciteit van het model meeneemt.

Dit zijn geen exotische failures; ze zijn de normale toestand van een netwerk dat net is geschreven, en geen ervan kondigt zichzelf aan. De gradient is correct — je hebt hem tegenover PyTorch tot zestien decimalen gecontroleerd — en het model leert nog steeds niet.

Hoofdstuk 6 gaat daarover: initialisatie, normalisatie, overfitting en regularisatie, en de diagnostische gewoonte om te vragen welke daarvan gebeurt voordat je iets verandert. Het is het verschil tussen een netwerk dat draait en een netwerk dat werkt.

De Value-klasse in dit hoofdstuk stamt rechtstreeks af van Andrej Karpathy’s micrograd, en zijn video The spelled-out intro to neural networks and backpropagation: building micrograd is de beste drie uur die je aan dit materiaal kunt besteden als je het nog een keer door iemand anders uitgelegd wilt krijgen. Zijn post uit 2016 Yes you should understand backprop bepleit waarom je er zelf een moet schrijven en is verplichte literatuur in Stanford’s CS224n. De CS231n-notities over backpropagation (cs231n.github.io/optimization-2) zijn de canonieke behandeling van de flowpatronen die hierboven in de tabel staan. Voor de wiskunde als calculus op een grafiek in plaats van neural-network-folklore is hoofdstuk 5.6 van Mathematics for Machine Learning van Deisenroth, Faisal en Ong ongewoon helder; en de survey Automatic Differentiation in Machine Learning: a Survey van Baydin, Pearlmutter, Radul en Siskind (arXiv:1502.05767) is de referentie voor het veld als geheel, inclusief de hierboven besproken forward/reverse-afweging.