Backpropagation des de zero: primer el motor, després la xarxa

Abans de construir la màquina, cal resoldre una pregunta, perquè si la resposta fos l’altra no hi hauria res a construir.

El perceptró va fallar amb XOR perquè una línia no pot separar els quatre punts. La solució òbvia és apilar: passa l’entrada per una capa lineal, després per una altra. Això ajuda?

No, i la demostració són dues línies. Una capa lineal és $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Dona-la a una altra, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, i substitueix:

La composició és $W\mathbf{x} + \mathbf{b}$ amb $W = W_2W_1$ i $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Una pila de capes lineals és una sola capa lineal. Deu capes, mil capes: continua sent una línia, continua sense poder fer XOR.

Val la pena veure-ho passar en lloc de creure-s’ho:

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

No aproximadament iguals. Idèntics bit a bit, perquè és la mateixa aritmètica reordenada.

Per tant, la profunditat no aporta res per si sola. El que aporta alguna cosa és posar una funció no lineal entre les capes — i aquesta és tota la raó per la qual existeixen les funcions d’activació. No són un floriment biològic ni un truc de normalització. Sense una, la segona capa és decoració.

Ara les matemàtiques, i és una sola regla que ja coneixes aplicada en un lloc una mica menys familiar.

La regla de la cadena d’una sola variable diu que si $L$ depèn de $c$ i $c$ depèn de $x$, aleshores $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Les derivades es multipliquen al llarg d’una cadena.

La part que importa aquí és què passa quan una variable alimenta més d’un camí downstream. Si $x$ influeix en $L$ a través de $a$ i també a través de $b$, les contribucions se sumen:

Multiplica al llarg d’un camí, suma entre camins. Això és tot el backpropagation, i cada detall d’implementació de la resta d’aquest capítol — incloent-hi el += del codi i la crida zero_grad() que fa ensopegar tothom quan escriu el seu primer bucle d’entrenament — és una conseqüència directa d’aquesta segona paraula.

Agafa un circuit concret de cinc operacions, amb $x = 0.5$ i $y = 1.4$:

Fixa’t que $x$ apareix tres vegades: a $a$, a $b$, i directament a $L$. Fes el backward pass en paper, de dreta a esquerra, començant per $\frac{dL}{dL} = 1$:

Retén aquest nombre. D’aquí a unes pàgines, un programa el produirà sense que li hàgim dit res de tot això.

La intuïció que ho fa programable: cadascun d’aquells passos era local. Per empènyer un gradient a través del node de multiplicació, necessitaves el gradient entrant i els dos valors d’entrada emmagatzemats — res sobre la resta del circuit. Cada operació sap com diferenciar-se a si mateixa.

Així que fes un nombre que recordi què l’ha produït.

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

Quatre camps. data és el valor. grad acumula $\frac{\partial L}{\partial \text{self}}$. _prev és el conjunt de Value dels quals s’ha calculat aquest — les arestes del graf. I _backward és una clausura que instal·la cada operació: sap com empènyer el gradient d’aquest node un pas enrere cap a les seves entrades.

Cada operador segueix la mateixa forma: calcula la sortida, registra els pares, instal·la la regla local.

    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

Llegeix els quatre cossos _backward com una taula i veuràs els patrons de flux de la derivació en paper just aquí:

Tots i cadascun fan servir += i mai =. Aquesta és la regla de "sumar entre camins", codificada. Un node que alimenta dos consumidors és cridat dues vegades, i les dues contribucions se sumen soles.

Després ve el controlador, que és l’única part amb coneixement global:

    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 produeix un ordenament topològic del graf: cada node apareix després de totes les seves entrades. Recórrer aquesta llista en ordre invers garanteix que, quan crides el _backward d’un node, el seu propi gradient ja és complet: tots els consumidors downstream ja hi han contribuït. Si t’equivoques d’ordre, empenys enrere un gradient a mig fer, cosa que produeix una resposta incorrecta sense cap missatge d’error.

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. El mateix nombre, d’un programa al qual se li va dir la regla de +, la regla de *, la regla de tanh, i res sobre aquest circuit.

Dues comprovacions independents, perquè "coincideix amb el que he derivat" és una prova feble quan la mateixa persona ha fet totes dues coses.

Diferenciació numèrica. Mou una mica l’entrada i mesura. La diferència centrada $\frac{L(x+h) - L(x-h)}{2h}$ estima la derivada sense cap càlcul diferencial:

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

Contra PyTorch, que té un motor d’autodiff industrial escrit per gent que s’hi dedica professionalment:

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

Coincidència a $2 \times 10^{-16}$, que és l’èpsilon de màquina per a un float de 64 bits: els dos motors fan aritmètica idèntica. Guarda’t la comprovació numèrica a la butxaca: és l’eina per depurar el backward pass d’una capa nova, i és la raó per la qual un gradient erroni es pot trobar.

El mateix circuit, entrades diferents. Posa $x = 2$ i $y = -3$, cosa que fa $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

El gradient que travessa el node $\tanh$ ha caigut per un factor de 9.945. Tot el que queda upstream — en una xarxa real, cada capa anterior — rep essencialment res. Els dos camins pel circuit han quedat en silenci; només la connexió directa que salta $\tanh$ encara porta senyal.

Aquest és el problema del gradient que s’esvaeix, en un sol node. Apila quaranta capes de $\tanh$ i multiplica quaranta factors així, i les capes inicials deixen d’aprendre del tot. També és, incidentalment, un argument a favor de les connexions de salt que aquí pots veure en miniatura: el camí que va esquivar la no-linealitat és l’únic que va sobreviure.

Cada _backward fa servir +=. Això és correcte: és com se sumen els camins. Però té una conseqüència que atrapa tothom: els gradients també s’acumulen entre crides a backward(). El motor no té manera de saber que la teva segona crida és un nou pas d’entrenament i no un altre camí del mateix graf.

Per tant, un bucle d’entrenament els ha de netejar:

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

Això és optimizer.zero_grad() a PyTorch, i el consell habitual és que oblidar-ho trenca l’entrenament. Així que eliminem aquestes dues línies i mirem fins a quin punt es trenca. Les mateixes llavors, tot igual, 200 passos de XOR:

Amb learning rates petits, la versió amb bug guanya totes les files. Convergeix quan la versió correcta s’encalla.

Això no és una casualitat i val la pena entendre-ho, perquè explica per què aquest bug és tan difícil de detectar. Si mai neteges el gradient, llavors al pas $k$ el paràmetre s’actualitza amb la suma de tots els gradients calculats fins ara. En una pèrdua que continua apuntant aproximadament en la mateixa direcció, aquesta suma creix de manera constant, i l’efecte és un learning rate que augmenta tot sol. A $\eta = 0.05$, quan l’algoritme correcte s’arrossega, la mida de pas desbocada sembla exactament una solució.

Després mira les tres files de sota. A $\eta = 0.3$ el mateix mecanisme fa esclatar el model: pèrdua 8.0 és el que obté un model col·lapsat a una constant $\pm 1$ — la meitat dels 16 que costarien quatre respostes màximament incorrectes — — mentre que la versió correcta ara convergeix netament.

Per tant, l’afirmació honesta no és "crida sempre zero_grad o el teu model no entrenarà". És: sense això, ja no estàs fent gradient descent. Estàs executant una cosa la mida de pas de la qual deriva cap amunt a un ritme que ningú ha triat, i semblarà funcionar, de vegades millor que l’autèntica, fins just abans de deixar de fer-ho; llavors culparàs el learning rate, la inicialització o les dades. Aquesta és la forma dels pitjors bugs en machine learning: no fallen, canvien l’algoritme per un algoritme diferent que de vegades treu millor puntuació.

Amb el motor acabat, una xarxa neuronal és ben poc codi. Una neurona és un producte escalar, un biaix i una activació; una capa és una llista de neurones; una xarxa és una llista de capes.

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

No hi ha cap backward pass en res d’això. Ni una línia. La classe Value ja sap com diferenciar qualsevol cosa que aquestes classes construeixin, que és precisament el motiu d’haver-la escrit primer: un motor d’autodiff no sap que s’està fent servir per a una xarxa neuronal.

Ara, el problema del Capítol 1. Dues entrades, dues unitats ocultes, una sortida, nou paràmetres:

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

Quatre de quatre. La funció que cap perceptró pot calcular — demostrat al Capítol 1 amb quatre desigualtats que exigien que $b$ fos alhora positiu i negatiu — és calculada per nou nombres trobats automàticament.

La part satisfactòria no és que funcioni. És poder veure com, perquè amb dues unitats ocultes la representació intermèdia és un punt en un pla i simplement pots imprimir-la.

Entrenada fins a una pèrdua de 0.001241, aquí és on cau cada entrada després de la capa oculta, i què en fa la neurona de sortida:

Mira la primera i la quarta files. Les entrades $(0,0)$ i $(1,1)$ són cantonades oposades en diagonal del quadrat — tan allunyades com poden estar dos punts en aquest problema — i la capa oculta les mapeja a $(0.82, -0.85)$ i $(0.84, -0.86)$. Gairebé el mateix punt. La capa ha plegat el pla perquè les dues cantonades rebutjades caiguin l’una sobre l’altra, i un cop són al mateix lloc, una línia les separa de les altres dues.

I la neurona de sortida és exactament aquesta línia. Els seus paràmetres apresos són $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, així que la seva frontera de decisió és

que és una línia recta: un perceptró, el mateix objecte del Capítol 1, sense canvis. Aleshores no podia resoldre XOR i ara tampoc. El que ha canviat és que ja no mira l’entrada; mira un espai que la primera capa li ha construït, en el qual el problema és linealment separable.

Això és una representació apresa, i val la pena ser precisos perquè la frase s’usa de manera laxa durant la resta d’aquest curs, i en la resta del camp. No és una compressió, un resum ni un embedding en cap sentit místic. És un canvi de coordenades, après en lloc de dissenyat, l’única feina del qual és facilitar la feina de la capa següent.

Aquí hi ha un teorema, i normalment se cita malament.

Cybenko el 1989 i Hornik el 1991 van demostrar que una xarxa feedforward amb una sola capa oculta i una funció d’activació adequada pot aproximar qualsevol funció contínua en un conjunt compacte, amb qualsevol precisió que vulguis, si té prou unitats ocultes.³⁴ És un resultat real i important: diu que l’arquitectura no és la limitació.

Ara llegeix què omet. No diu quantes unitats: la cota pot ser astronòmicament gran. No diu que els pesos es puguin trobar; afirma existència, i gradient descent des d’un inici aleatori no és un oracle. I no diu res sobre el comportament en dades que no has vist, que és la segona meitat del Capítol 6.

La distància entre "existeix" i "es pot trobar" no és acadèmica. Aquí tens el mateix problema XOR, 50 inicialitzacions aleatòries cadascuna, 1000 passos, canviant només la mida de la capa oculta:

Amb l’arquitectura mínima viable, una execució de cada quatre no hi arriba mai: s’assenta en una configuració de la qual no pot baixar, exactament el mínim local que el Capítol 3 va mostrar en una superfície unidimensional. Afegeix una unitat i les fallades gairebé desapareixen, no perquè la xarxa s’hagi tornat més expressiva (dues unitats ja n’hi ha prou: 38 execucions ho demostren), sinó perquè dimensions extra donen al descens més direccions per on escapar.

I després vuit unitats van una mica pitjor que quatre. Amb un learning rate i un pressupost de passos fixos, més capacitat no és monòtonament millor. Qualsevol que et digui que la solució per a una xarxa encallada sempre és una xarxa més gran està extrapolant des del mig d’aquesta taula.

És la mateixa lliçó que el teorema de convergència del Capítol 1, i serà la mateixa lliçó al Capítol 10 sobre les lleis d’escalat, en la forma que li dona aquell capítol: una predicció de la pèrdua no és una predicció de la capacitat per la qual estàs pagant, i la distància entre totes dues és on viu l’enginyeria.

Ara tens una xarxa que entrena. És un assoliment més petit del que sembla, perquè la xarxa que tens entrena amb quatre exemples i es mesura amb els mateixos quatre.

Executa el mateix codi en un dataset real i apareix un nou conjunt de problemes, cap dels quals va de gradients. La pèrdua baixa una estona i després s’atura. O baixa en les dades d’entrenament i puja en tota la resta. O no es mou gens des del primer pas, i la causa resulta ser el rang dels pesos aleatoris inicials. O l’entrada d’una unitat va derivar cap a negativa en tots els exemples a l’època tres i ha estat morta des de llavors, en silenci, enduent-se un tros de la capacitat del model.

Aquestes no són fallades exòtiques; són l’estat normal d’una xarxa que s’acaba d’escriure, i cap d’elles s’anuncia. El gradient és correcte — l’has comprovat contra PyTorch fins a setze decimals — i el model continua sense aprendre.

El Capítol 6 va d’això: inicialització, normalització, overfitting i regularització, i l’hàbit diagnòstic de preguntar quin d’aquests fenòmens està passant abans de canviar res. És la diferència entre una xarxa que s’executa i una xarxa que funciona.

La classe Value d’aquest capítol descendeix directament de micrograd d’Andrej Karpathy, i el seu vídeo The spelled-out intro to neural networks and backpropagation: building micrograd és les millors tres hores que pots dedicar a aquest material si vols que algú altre te l’expliqui d’una segona manera. El seu article de 2016 Yes you should understand backprop defensa que n’escriguis un tu mateix i és lectura assignada al CS224n de Stanford. Les notes del CS231n sobre backpropagation (cs231n.github.io/optimization-2) són el tractament canònic dels patrons de flux tabulats més amunt. Per a les matemàtiques com a càlcul sobre un graf i no com a folklore de xarxes neuronals, el capítol 5.6 de Mathematics for Machine Learning de Deisenroth, Faisal i Ong és inusualment clar; i l’estudi de Baydin, Pearlmutter, Radul i Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) és la referència per al camp en conjunt, inclòs el compromís forward/reverse comentat més amunt.