Backpropagation fra bunden: først motoren, så netværket

Før vi bygger maskinen, skal ét spørgsmål afgøres, for hvis svaret gik den anden vej, ville der ikke være noget at bygge.

Perceptronen fejlede på XOR, fordi én linje ikke kan adskille de fire punkter. Den oplagte løsning er at stable: Kør inputtet gennem ét lineært lag og derefter et andet. Hjælper det?

Nej, og beviset er to linjer. Et lineært lag er $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Giv det videre til et andet, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, og indsæt:

Sammensætningen er $W\mathbf{x} + \mathbf{b}$ med $W = W_2W_1$ og $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. En stak lineære lag er ét enkelt lineært lag. Ti af dem, tusind af dem: stadig én linje, stadig ude af stand til at løse XOR.

Det er værd at se det ske i stedet for bare at 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

Ikke omtrent ens. Bit-for-bit identiske, fordi det er den samme aritmetik arrangeret på en anden måde.

Så dybde køber intet i sig selv. Det, der køber noget, er at sætte en ikke-lineær funktion mellem lagene — og det er hele grunden til, at aktiveringsfunktioner findes. De er ikke en biologisk finesse eller et normaliseringstrick. Uden en er det andet lag pynt.

Nu matematikken, og det er én regel, du allerede kender, anvendt et lidt uvant sted.

Kædereglen for én variabel siger, at hvis $L$ afhænger af $c$ og $c$ afhænger af $x$, så er $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Afledte multipliceres langs en kæde.

Det, der betyder noget her, er hvad der sker, når en variabel fodrer mere end én nedstrøms sti. Hvis $x$ påvirker $L$ gennem $a$ og også gennem $b$, lægges bidragene sammen:

Multiplicer langs en sti, summer på tværs af stier. Det er hele backpropagation, og hver implementeringsdetalje i resten af dette kapitel — inklusive += i koden og zero_grad()-kaldet, der fælder alle, der skriver deres første training loop — er en direkte konsekvens af det andet ord.

Tag et konkret kredsløb med fem operationer, med $x = 0.5$ og $y = 1.4$:

Bemærk, at $x$ optræder tre gange: i $a$, i $b$ og direkte i $L$. Lav backward pass på papir, fra højre mod venstre, startende fra $\frac{dL}{dL} = 1$:

Hold fast i det tal. Om få sider vil et program producere det uden at få noget af dette fortalt.

Indsigten, der gør det programmerbart: Hvert eneste af de trin var lokalt. For at skubbe en gradient gennem multiplikationsnoden havde du brug for den indkommende gradient og de to gemte inputværdier — intet om resten af kredsløbet. Hver operation ved, hvordan den differentierer sig selv.

Så lav et tal, der husker, hvad der skabte 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

Fire felter. data er værdien. grad akkumulerer $\frac{\partial L}{\partial \text{self}}$. _prev er mængden af Values, som denne blev beregnet ud fra — grafens kanter. Og _backward er en closure, som hver operation installerer: Den ved, hvordan denne nodes gradient skubbes ét skridt tilbage til dens input.

Hver operator følger samme form: Beregn outputtet, registrer forældrene, installer den 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

Læs de fire _backward-kroppe som en tabel, og flowmønstrene fra papirudledningen står lige der:

Hver eneste bruger += og aldrig =. Det er reglen „summer på tværs af stier“, indkodet. En node, der fodrer to forbrugere, bliver kaldt to gange, og de to bidrag lægger sig sammen af sig selv.

Så driveren, som er den eneste del med nogen global viden:

    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 producerer en topologisk rækkefølge af grafen: Hver node vises efter alle sine input. At gå gennem den liste baglæns garanterer, at når du kalder en nodes _backward, er dens egen gradient allerede komplet — hver forbruger nedstrøms fra den har allerede bidraget. Får du rækkefølgen forkert, skubber du en halvfærdig gradient baglæns, hvilket giver et forkert svar uden fejlmeddelelse.

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. Det samme tal, fra et program, der fik reglen for +, reglen for *, reglen for tanh og intet om dette kredsløb.

To uafhængige tjek, fordi „det matcher det, jeg udledte“ er en svag test, når den samme person gjorde begge dele.

Numerisk differentiering. Skub lidt til inputtet og mål. Den centrerede differens $\frac{L(x+h) - L(x-h)}{2h}$ estimerer den afledte uden calculus overhovedet:

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

Mod PyTorch, som har en industriel autodiff-motor skrevet af folk, der gør dette professionelt:

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

Overensstemmelse ved $2 \times 10^{-16}$, som er machine epsilon for en 64-bit float: De to motorer udfører identisk aritmetik. Hav det numeriske tjek i baglommen — det er værktøjet til at debugge et nyt lags backward pass, og det er grunden til, at en forkert gradient overhovedet kan findes.

Samme kredsløb, andre input. Sæt $x = 2$ og $y = -3$, hvilket 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, der krydsede $\tanh$-noden, faldt med en faktor 9.945. Alt opstrøms for den — i et rigtigt netværk, hvert lag før den — modtager i praksis ingenting. De to stier gennem kredsløbet er blevet tavse; kun den direkte forbindelse, der springer over $\tanh$, bærer stadig signal.

Det er vanishing gradient-problemet i én node. Stabl fyrre lag af $\tanh$ og multiplicer fyrre sådanne faktorer sammen, og de tidlige lag holder helt op med at lære. Det er også, i øvrigt, et argument for skip connections, som du kan se her i miniature: Stien, der omgik ikke-lineariteten, er den eneste, der overlevede.

Hver _backward bruger +=. Det er korrekt — sådan summeres stier. Men det har en konsekvens, der fanger alle: Gradienter akkumuleres også på tværs af kald til backward(). Motoren har ingen idé om, at dit andet kald er et nyt træningstrin og ikke endnu en sti i den samme graf.

Så et training loop skal rydde 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

Dette er optimizer.zero_grad() i PyTorch, og det sædvanlige råd er, at hvis du glemmer det, ødelægger det træningen. Så lad os slette de to linjer og se, hvor ødelagt det er. Samme seeds, samme alt, 200 trin med XOR:

Ved de små læringsrater vinder den fejlbehæftede version hver eneste række. Den konvergerer, når den korrekte version går i stå.

Det er ikke et tilfælde, og det er værd at forstå, fordi det forklarer, hvorfor denne fejl er så svær at fange. Hvis du aldrig rydder gradienten, bliver parameteren ved trin $k$ opdateret med summen af hver gradient beregnet indtil nu. På et loss, der bliver ved med at pege nogenlunde samme vej, vokser den sum støt, og effekten er en læringsrate, der stiger af sig selv. Ved $\eta = 0.05$, hvor den korrekte algoritme kravler, ligner den løbske skridtstørrelse præcis en løsning.

Se så på de nederste tre rækker. Ved $\eta = 0.3$ sprænger den samme mekanisme modellen fra hinanden — loss 8.0 er det, en model kollapset til en konstant $\pm 1$ scorer — halvdelen af de 16, som fire maksimalt forkerte svar ville koste — — mens den korrekte version nu konvergerer rent.

Så den ærlige formulering er ikke „kald altid zero_grad, ellers vil din model ikke træne“. Den er: Uden det kører du ikke gradient descent længere. Du kører noget, hvis skridtstørrelse driver opad med en hastighed, ingen har valgt, og det vil se ud til at virke, nogle gange bedre end den ægte vare, lige indtil det ikke gør — hvorefter du vil give læringsraten, initialiseringen eller dataene skylden. Det er formen på de værste bugs i machine learning: De crasher ikke, de ændrer algoritmen til en anden algoritme, der indimellem scorer bedre.

Når motoren er færdig, er et neural network næsten ingen kode. En neuron er et dot product, en bias og en aktivering; et lag er en liste af neuroner; et netværk er en liste af lag.

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

Der er intet backward pass i noget af det. Ikke én linje. Klassen Value ved allerede, hvordan den differentierer, hvad end disse klasser nu bygger, og det er pointen med at have skrevet den først: En autodiff-motor ved ikke, at den bliver brugt til et neural network.

Nu problemet fra Kapitel 1. To input, to skjulte enheder, ét output, ni parametre:

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

Fire ud af fire. Funktionen, som ingen perceptron kan beregne — bevist i Kapitel 1 med fire uligheder, der krævede, at $b$ var både positiv og negativ — beregnes af ni tal fundet automatisk.

Det tilfredsstillende er ikke, at det virker. Det er at kunne se hvordan, for med to skjulte enheder er den mellemliggende repræsentation et punkt i et plan, og du kan bare printe den.

Trænet til et loss på 0.001241: Her er, hvor hvert input lander efter det skjulte lag, og hvad outputneuronen gør med det:

Se på første og fjerde række. Inputtene $(0,0)$ og $(1,1)$ er diagonalt modsatte hjørner af kvadratet — så langt fra hinanden, som to punkter i dette problem kan være — og det skjulte lag mapper dem til $(0.82, -0.85)$ og $(0.84, -0.86)$. Næsten det samme punkt. Laget har foldet planet, så de to afviste hjørner lander oven på hinanden, og når de først er samme sted, adskiller én linje dem fra de to andre.

Og outputneuronen er præcis den linje. Dens lærte parametre er $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, så dens beslutningsgrænse er

som er en ret linje — en perceptron, det samme objekt fra Kapitel 1, uændret. Den kunne ikke løse XOR dengang, og det kan den ikke nu. Det, der ændrede sig, er, at den ikke længere ser på inputtet; den ser på et rum, det første lag byggede til den, hvor problemet er lineært separabelt.

Det er, hvad en lært repræsentation er, og det er værd at være præcis, fordi udtrykket bliver brugt løst i resten af dette kursus og i resten af feltet. Det er ikke en kompression, et resumé eller en embedding i nogen mystisk forstand. Det er et koordinatskift, lært snarere end designet, hvis eneste opgave er at gøre det næste lags opgave nem.

Der er en sætning her, og den bliver som regel citeret dårligt.

Cybenko i 1989 og Hornik i 1991 beviste, at et feedforward-netværk med ét enkelt skjult lag og en passende aktiveringsfunktion kan approksimere enhver kontinuert funktion på en kompakt mængde, med hvilken som helst nøjagtighed du ønsker, givet nok skjulte enheder.³⁴ Det er et ægte og vigtigt resultat: Det siger, at arkitekturen ikke er begrænsningen.

Læs nu, hvad den udelader. Den siger ikke hvor mange enheder — grænsen kan være astronomisk stor. Den siger ikke, at vægtene kan findes; den hævder eksistens, og gradient descent fra en tilfældig start er ikke et orakel. Og den siger intet om adfærd på data, du ikke har set, hvilket er anden halvdel af Kapitel 6.

Kløften mellem „eksisterer“ og „kan findes“ er ikke akademisk. Her er det samme XOR-problem, 50 tilfældige initialiseringer hver, 1000 trin, kun størrelsen på det skjulte lag ændret:

Med den minimalt levedygtige arkitektur når én kørsel ud af fire aldrig frem — den lander i en konfiguration, den ikke kan bevæge sig ned fra, præcis det lokale minimum, som Kapitel 3 viste på en endimensional overflade. Tilføj én enhed, og fejlene forsvinder næsten, ikke fordi netværket blev mere udtryksfuldt (to enheder er allerede nok — 38 kørsler beviser det), men fordi ekstra dimensioner giver nedstigningen flere retninger at slippe ud gennem.

Og så klarer otte enheder sig en smule dårligere end fire. Ved en fast læringsrate og et fast trinbudget er mere kapacitet ikke monotont bedre. Enhver, der fortæller dig, at løsningen på et fastlåst netværk altid er et større netværk, ekstrapolerer fra midten af den tabel.

Det er den samme lektie som konvergenssætningen i Kapitel 1, og det bliver den samme lektie i Kapitel 10 om scaling laws, i den form det kapitel giver den: En forudsigelse af loss er ikke en forudsigelse af den capability, du betaler for, og afstanden mellem de to er der, engineering bor.

Du har nu et netværk, der træner. Det er en mindre bedrift, end det føles som, fordi det netværk, du har, træner på fire eksempler og bliver målt på de samme fire.

Kør den samme kode på et rigtigt datasæt, og et nyt sæt problemer dukker op, hvor ingen af dem handler om gradienter. Loss falder et stykke tid og stopper så. Eller det falder på træningsdataene og stiger på alt andet. Eller det bevæger sig slet ikke fra første trin, og årsagen viser sig at være intervallet for de tilfældige startvægte. Eller en enheds input drev negativt på hvert eksempel i epoch tre, og den har været død lige siden, lydløst, mens den tog en chunk af modellens kapacitet med sig.

Det er ikke eksotiske fejl; de er normaltilstanden for et netværk, der lige er blevet skrevet, og ingen af dem annoncerer sig selv. Gradienten er korrekt — du tjekkede den mod PyTorch til seksten decimaler — og modellen lærer stadig ikke.

Kapitel 6 handler om det: initialisering, normalisering, overfitting og regularisering, og den diagnostiske vane med at spørge hvilken af dem der sker, før man ændrer noget. Det er forskellen på et netværk, der kører, og et netværk, der virker.

Klassen Value i dette kapitel stammer direkte fra Andrej Karpathys micrograd, og hans video The spelled-out intro to neural networks and backpropagation: building micrograd er de bedste tre timer, du kan bruge på dette materiale, hvis du vil have det forklaret på en anden måde af en anden. Hans indlæg fra 2016 Yes you should understand backprop argumenterer for at skrive en selv og er obligatorisk læsning i Stanfords CS224n. CS231n-noterne om backpropagation (cs231n.github.io/optimization-2) er den kanoniske behandling af de flowmønstre, der er tabuleret ovenfor. For matematikken som calculus på en graf snarere end som neural-network-folklore er kapitel 5.6 af Mathematics for Machine Learning af Deisenroth, Faisal og Ong usædvanligt klart; og Baydin, Pearlmutter, Radul og Siskinds survey Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) er referencen for feltet som helhed, inklusive forward/reverse-afvejningen diskuteret ovenfor.