Backpropagation från grunden: först motorn, sedan nätverket

Innan vi bygger maskinen måste en fråga avgöras, för om svaret hade gått åt andra hållet skulle det inte finnas något att bygga.

Perceptronen misslyckades med XOR eftersom en linje inte kan separera de fyra punkterna. Den uppenbara lösningen är att stapla: kör indata genom ett linjärt lager och sedan ett till. Hjälper det?

Nej, och beviset är två rader. Ett linjärt lager är $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Mata det till ett annat, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, och sätt in:

Sammansättningen är $W\mathbf{x} + \mathbf{b}$ med $W = W_2W_1$ och $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. En stapel av linjära lager är ett enda linjärt lager. Tio av dem, tusen av dem: fortfarande en linje, fortfarande oförmögen att göra XOR.

Det är värt att se det hända i stället för att bara tro på det:

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

Inte ungefär lika. Bit-för-bit identiska, eftersom det är samma aritmetik omarrangerad.

Så djup köper ingenting i sig. Det som köper något är att lägga en icke-linjär funktion mellan lagren — och det är hela skälet till att aktiveringsfunktioner finns. De är inte en biologisk utsmyckning eller ett normaliseringstrick. Utan en sådan är det andra lagret dekoration.

Nu matematiken, och det är en regel du redan kan, tillämpad på en plats som är lite ovan.

Kedjeregeln för en variabel säger att om $L$ beror på $c$ och $c$ beror på $x$, då $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Derivator multipliceras längs en kedja.

Den del som spelar roll här är vad som händer när en variabel matar mer än en väg nedströms. Om $x$ påverkar $L$ genom $a$ och också genom $b$, adderas bidragen:

Multiplicera längs en väg, summera över vägar. Det är hela backpropagation, och varje implementationsdetalj i resten av kapitlet — inklusive += i koden och zero_grad()-anropet som fäller alla som skriver sin första träningsloop — är en direkt konsekvens av det andra ordet.

Ta en konkret krets med fem operationer, med $x = 0.5$ och $y = 1.4$:

Notera att $x$ förekommer tre gånger: i $a$, i $b$ och direkt i $L$. Gör backward pass på papper, från höger till vänster, med start från $\frac{dL}{dL} = 1$:

Håll fast vid det talet. Om några sidor kommer ett program att producera det utan att få veta något av detta.

Insikten som gör det programmerbart: vart och ett av dessa steg var lokalt. För att skicka en gradient genom multiplikationsnoden behövde du den inkommande gradienten och de två lagrade indatavärdena — ingenting om resten av kretsen. Varje operation vet hur den ska derivera sig själv.

Så skapa ett tal som minns vad som producerade det.

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

Fyra fält. data är värdet. grad ackumulerar $\frac{\partial L}{\partial \text{self}}$. _prev är mängden Value som detta beräknades från — grafens kanter. Och _backward är en closure som varje operation installerar: den vet hur den ska skicka den här nodens gradient ett steg tillbaka till dess indata.

Varje operator följer samma form: beräkna utdata, registrera föräldrarna, installera den lokala regeln.

    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

Läs de fyra _backward-kropparna som en tabell, så ligger flödesmönstren från pappershärledningen precis där:

Varenda en använder += och aldrig =. Det är regeln ”summera över vägar”, kodad. En nod som matar två konsumenter anropas två gånger, och de två bidragen adderas av sig själva.

Sedan drivern, som är den enda delen med någon global kunskap:

    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 producerar en topologisk ordning av grafen: varje nod visas efter alla sina indata. Att gå genom listan baklänges garanterar att när du anropar en nods _backward är dess egen gradient redan komplett — varje konsument nedströms har redan bidragit. Får du ordningen fel skickar du en halvfärdig gradient bakåt, vilket ger ett felaktigt svar utan felmeddelande.

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. Samma tal, från ett program som fick regeln för +, regeln för *, regeln för tanh och ingenting om just den här kretsen.

Två oberoende kontroller, eftersom ”det matchar det jag härledde” är ett svagt test när samma person gjorde båda.

Numerisk derivering. Knuffa på indatat och mät. Den centrerade differensen $\frac{L(x+h) - L(x-h)}{2h}$ uppskattar derivatan utan någon kalkyl alls:

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

Mot PyTorch, som har en industriell autodiff-motor skriven av människor som gör detta på heltid:

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

Överensstämmelse vid $2 \times 10^{-16}$, vilket är maskinepsilon för ett 64-bitars flyttal: de två motorerna utför identisk aritmetik. Behåll den numeriska kontrollen i bakfickan — det är verktyget för att felsöka ett nytt lagers backward pass, och det är skälet till att en felaktig gradient går att hitta över huvud taget.

Samma krets, andra indata. Sätt $x = 2$ och $y = -3$, vilket gör $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

Gradienten som korsar $\tanh$-noden föll med en faktor på 9 945. Allt uppströms om den — i ett verkligt nätverk, varje lager före den — får i princip ingenting. De två vägarna genom kretsen har tystnat; bara den direkta kopplingen som hoppar över $\tanh$ bär fortfarande signal.

Det är problemet med vanishing gradient, i en nod. Stapla fyrtio lager av $\tanh$ och multiplicera ihop fyrtio sådana faktorer, så slutar de tidiga lagren att lära sig helt. Det är också, för övrigt, ett argument för skip connections som du kan se här i miniatyr: vägen som gick förbi icke-linjäriteten är den enda som överlevde.

Varje _backward använder +=. Det är korrekt — det är så vägar summeras. Men det får en konsekvens som fäller alla: gradienter ackumuleras även över anrop till backward(). Motorn har ingen aning om att ditt andra anrop är ett nytt träningssteg snarare än ännu en väg i samma graf.

Så en träningsloop måste rensa dem:

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

Detta är optimizer.zero_grad() i PyTorch, och det vanliga rådet är att om du glömmer det går träningen sönder. Så låt oss ta bort de två raderna och se hur trasigt det blir. Samma seeds, samma allt, 200 steg av XOR:

Vid de små learning rate-värdena vinner den buggiga versionen på varje rad. Den konvergerar när den korrekta versionen fastnar.

Det är ingen tillfällighet och det är värt att förstå, eftersom det förklarar varför den här buggen är så svår att fånga. Om du aldrig rensar gradienten uppdateras parametern vid steg $k$ med summan av varje gradient som beräknats hittills. På en förlust som fortsätter peka ungefär åt samma håll växer den summan stadigt, och effekten blir en learning rate som ökar av sig själv. Vid $\eta = 0.05$, där den korrekta algoritmen kryper fram, ser den skenande steglängden exakt ut som en lösning.

Titta sedan på de tre nedersta raderna. Vid $\eta = 0.3$ spränger samma mekanism modellen — loss 8.0 är vad en modell som kollapsat till en konstant $\pm 1$ får — hälften av de 16 som fyra maximalt felaktiga svar skulle kosta — — medan den korrekta versionen nu konvergerar rent.

Så det ärliga påståendet är inte ”anropa alltid zero_grad annars tränar inte modellen”. Det är: utan det kör du inte gradient descent längre. Du kör något vars steglängd driver uppåt i en takt som ingen valt, och det kommer att verka fungera, ibland bättre än det riktiga, ända tills det inte gör det — då kommer du att skylla på learning rate, initieringen eller datan. Det här är formen på de värsta buggarna i machine learning: de kraschar inte, de ändrar algoritmen till en annan algoritm som ibland får bättre resultat.

Med motorn klar är ett neuralt nätverk knappt någon kod alls. En neuron är en skalärprodukt, en bias och en aktivering; ett lager är en lista av neuroner; ett nätverk är en lista av lager.

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

Det finns inget backward pass i något av detta. Inte en rad. Klassen Value vet redan hur den ska derivera vad dessa klasser än råkar bygga, vilket är poängen med att ha skrivit den först: en autodiff-motor vet inte att den används för ett neuralt nätverk.

Nu problemet från Kapitel 1. Två indata, två dolda enheter, en utdata, nio parametrar:

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

Fyra av fyra. Funktionen som ingen perceptron kan beräkna — bevisad i Kapitel 1 med fyra olikheter som krävde att $b$ skulle vara både positiv och negativ — beräknas av nio tal som hittats automatiskt.

Det tillfredsställande är inte att det fungerar. Det är att kunna se hur, för med två dolda enheter är den mellanliggande representationen en punkt i ett plan och du kan bara skriva ut den.

Tränad till en loss på 0.001241, här är var varje indata hamnar efter det dolda lagret, och vad utdataneuronen gör med den:

Titta på första och fjärde raden. Indata $(0,0)$ och $(1,1)$ är diagonalt motsatta hörn av kvadraten — så långt ifrån varandra som två punkter i detta problem kan vara — och det dolda lagret mappar dem till $(0.82, -0.85)$ och $(0.84, -0.86)$. Nästan samma punkt. Lagret har vikt planet så att de två avvisade hörnen hamnar ovanpå varandra, och när de väl är på samma plats separerar en linje dem från de andra två.

Och utdataneuronen är exakt den linjen. Dess inlärda parametrar är $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, så dess beslutsgräns är

vilket är en rät linje — en perceptron, samma objekt från Kapitel 1, oförändrad. Den kunde inte lösa XOR då och kan inte nu. Det som ändrades är att den inte längre tittar på indatat; den tittar på ett rum som det första lagret byggde åt den, där problemet är linjärt separerbart.

Det är vad en inlärd representation är, och det är värt att vara precis eftersom frasen används löst under resten av kursen, och i resten av fältet. Det är inte en komprimering, en sammanfattning eller en embedding i någon mystisk mening. Det är ett koordinatbyte, inlärt snarare än designat, vars enda jobb är att göra nästa lagers jobb enkelt.

Det finns en sats här, och den citeras vanligtvis illa.

Cybenko 1989 och Hornik 1991 bevisade att ett feedforward-nätverk med ett enda dolt lager och en lämplig aktiveringsfunktion kan approximera vilken kontinuerlig funktion som helst på en kompakt mängd, med vilken noggrannhet du vill, givet tillräckligt många dolda enheter.³⁴ Det är ett äkta och viktigt resultat: det säger att arkitekturen inte är begränsningen.

Läs nu vad det utelämnar. Det säger inte hur många enheter — gränsen kan vara astronomiskt stor. Det säger inte att vikterna kan hittas; det hävdar existens, och gradient descent från en slumpmässig start är inget orakel. Och det säger ingenting om beteende på data du inte har sett, vilket är den andra halvan av Kapitel 6.

Gapet mellan ”finns” och ”går att hitta” är inte akademiskt. Här är samma XOR-problem, 50 slumpmässiga initieringar vardera, 1000 steg, endast storleken på det dolda lagret ändrad:

Med den minsta livskraftiga arkitekturen kommer en körning av fyra aldrig fram — den landar i en konfiguration den inte kan ta sig ned från, exakt det lokala minimum som Kapitel 3 visade på en endimensionell yta. Lägg till en enhet och felen försvinner nästan, inte för att nätverket blev mer uttrycksfullt (två enheter räcker redan — 38 körningar bevisar det) utan för att extra dimensioner ger nedstigningen fler riktningar att fly genom.

Och sedan går åtta enheter något sämre än fyra. Vid fast learning rate och stegbudget är mer kapacitet inte monotont bättre. Den som säger att lösningen för ett nätverk som fastnat alltid är ett större nätverk extrapolerar från mitten av den tabellen.

Det här är samma lärdom som konvergenssatsen i Kapitel 1, och det kommer att vara samma lärdom i Kapitel 10 om scaling laws, i den form det kapitlet ger den: en förutsägelse av förlusten är inte en förutsägelse av den förmåga du betalar för, och avståndet mellan de två är där ingenjörsarbetet bor.

Du har nu ett nätverk som tränar. Det är en mindre prestation än det känns som, eftersom nätverket du har tränar på fyra exempel och mäts på samma fyra.

Kör samma kod på ett verkligt dataset och en ny uppsättning problem dyker upp, varav inget handlar om gradienter. Förlusten går ned ett tag och stannar sedan. Eller så går den ned på träningsdatan och upp på allt annat. Eller så rör den sig inte alls från första steget, och orsaken visar sig vara intervallet för de initiala slumpmässiga vikterna. Eller så drev en enhets indata negativt på varje exempel i epok tre och den har varit död sedan dess, tyst, och tagit en bit av modellens kapacitet med sig.

Detta är inte exotiska fel; de är normaltillståndet för ett nätverk som just har skrivits, och inget av dem tillkännager sig. Gradienten är korrekt — du kontrollerade den mot PyTorch till sexton decimaler — och modellen lär sig ändå inte.

Kapitel 6 handlar om det: initiering, normalisering, overfitting och regularisation, och den diagnostiska vanan att fråga vilket av dem som händer innan du ändrar något. Det är skillnaden mellan ett nätverk som kör och ett nätverk som fungerar.

Klassen Value i det här kapitlet härstammar direkt från Andrej Karpathys micrograd, och hans video The spelled-out intro to neural networks and backpropagation: building micrograd är de bästa tre timmar du kan lägga på detta material om du vill få det förklarat på ett annat sätt av någon annan. Hans inlägg från 2016, Yes you should understand backprop, argumenterar för att skriva en själv och är obligatorisk läsning i Stanfords CS224n. CS231n-anteckningarna om backpropagation (cs231n.github.io/optimization-2) är den kanoniska behandlingen av flödesmönstren som tabellerats ovan. För matematiken som kalkyl på en graf snarare än som neural-network-folklore är kapitel 5.6 i Mathematics for Machine Learning av Deisenroth, Faisal och Ong ovanligt tydligt; och Baydin, Pearlmutter, Radul och Siskinds översikt Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) är referensen för fältet som helhet, inklusive forward/reverse-avvägningen som diskuterats ovan.