Backpropagation da zero: prima il motore, poi la rete

Prima di costruire la macchina, bisogna chiudere una domanda, perché se la risposta fosse diversa non ci sarebbe nulla da costruire.

Il perceptron ha fallito su XOR perché una sola retta non può separare i quattro punti. La correzione ovvia è impilare: fai passare l’input attraverso uno strato lineare, poi un altro. Aiuta?

No, e la dimostrazione sta in due righe. Uno strato lineare è $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Dallo in pasto a un altro, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, e sostituisci:

La composizione è $W\mathbf{x} + \mathbf{b}$ con $W = W_2W_1$ e $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Una pila di strati lineari è un singolo strato lineare. Dieci, mille: sempre una sola retta, ancora incapace di fare XOR.

Vale la pena vederlo succedere, invece di crederci sulla parola:

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

Non approssimativamente uguali. Identici bit per bit, perché è la stessa aritmetica riordinata.

Quindi la profondità, da sola, non compra nulla. Quello che compra qualcosa è mettere una funzione non lineare tra gli strati — ed è l’intera ragione per cui esistono le funzioni di attivazione. Non sono un vezzo biologico o un trucco di normalizzazione. Senza una di loro, il secondo strato è decorazione.

Ora la matematica, ed è una regola che conosci già applicata in un punto appena meno familiare.

La regola della catena a una variabile dice che se $L$ dipende da $c$ e $c$ dipende da $x$, allora $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Le derivate si moltiplicano lungo una catena.

La parte che conta qui è cosa succede quando una variabile alimenta più di un percorso a valle. Se $x$ influenza $L$ tramite $a$ e anche tramite $b$, i contributi si sommano:

Moltiplica lungo un percorso, somma tra i percorsi. Questa è tutta la backpropagation, e ogni dettaglio implementativo nel resto di questo capitolo — incluso il += nel codice e la chiamata zero_grad() che fa inciampare chiunque scriva il suo primo loop di training — è una conseguenza diretta di quella seconda parola.

Prendi un circuito concreto di cinque operazioni, con $x = 0.5$ e $y = 1.4$:

Nota che $x$ appare tre volte: in $a$, in $b$ e direttamente in $L$. Fai il backward pass su carta, da destra a sinistra, partendo da $\frac{dL}{dL} = 1$:

Tieni a mente quel numero. Tra qualche pagina un programma lo produrrà senza che gli venga detto nulla di tutto questo.

L’intuizione che lo rende programmabile: ognuno di quei passaggi era locale. Per spingere un gradiente attraverso il nodo di moltiplicazione, ti servivano il gradiente in ingresso e i due valori di input salvati — niente del resto del circuito. Ogni operazione sa come differenziare sé stessa.

Quindi crea un numero che ricordi cosa l’ha prodotto.

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

Quattro campi. data è il valore. grad accumula $\frac{\partial L}{\partial \text{self}}$. _prev è l’insieme dei Value da cui questo è stato calcolato — gli archi del grafo. E _backward è una closure che ogni operazione installa: sa come spingere il gradiente di questo nodo un passo indietro verso i suoi input.

Ogni operatore segue la stessa forma: calcola l’output, registra i genitori, installa la regola locale.

    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

Leggi i quattro corpi _backward come una tabella e gli schemi di flusso della derivazione su carta sono proprio lì:

Ognuno usa += e mai =. Questa è la regola «somma tra i percorsi», codificata. Un nodo che alimenta due consumatori viene chiamato due volte, e i due contributi si sommano da soli.

Poi il driver, che è l’unica parte con una qualsiasi conoscenza globale:

    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 produce un ordinamento topologico del grafo: ogni nodo appare dopo tutti i suoi input. Percorrere quella lista al contrario garantisce che, quando chiami il _backward di un nodo, il suo gradiente sia già completo: ogni consumatore a valle ha già contribuito. Sbaglia l’ordine e spingi all’indietro un gradiente mezzo finito, ottenendo una risposta sbagliata senza nessun messaggio di errore.

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. Lo stesso numero, da un programma a cui è stata detta la regola per +, la regola per *, la regola per tanh, e nulla su questo circuito.

Due controlli indipendenti, perché «corrisponde a ciò che ho derivato» è un test debole quando la stessa persona ha fatto entrambe le cose.

Differenziazione numerica. Sposta leggermente l’input e misura. La differenza centrata $\frac{L(x+h) - L(x-h)}{2h}$ stima la derivata senza alcun calcolo simbolico:

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

Contro PyTorch, che ha un motore autodiff industriale scritto da persone che lo fanno di mestiere:

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

Accordo a $2 \times 10^{-16}$, che è l’epsilon macchina per un float a 64 bit: i due motori stanno eseguendo aritmetica identica. Tieni in tasca il controllo numerico: è lo strumento per fare debug del backward pass di un nuovo layer, ed è il motivo per cui un gradiente sbagliato è trovabile.

Lo stesso circuito, input diversi. Imposta $x = 2$ e $y = -3$, il che rende $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

Il gradiente che attraversa il nodo $\tanh$ è caduto di un fattore 9.945. Tutto ciò che sta a monte — in una rete reale, ogni layer prima di quel punto — riceve sostanzialmente nulla. I due percorsi attraverso il circuito sono diventati silenziosi; solo la connessione diretta che salta $\tanh$ porta ancora segnale.

Questo è il problema del gradiente che svanisce, in un solo nodo. Impila quaranta layer di $\tanh$ e moltiplica quaranta fattori del genere, e i primi layer smettono del tutto di imparare. È anche, incidentalmente, un argomento a favore delle skip connection che puoi vedere qui in miniatura: il percorso che ha bypassato la non linearità è l’unico sopravvissuto.

Ogni _backward usa +=. È corretto: è così che i percorsi si sommano. Ma ha una conseguenza che prende tutti in contropiede: i gradienti si accumulano anche tra chiamate a backward(). Il motore non ha idea che la tua seconda chiamata sia un nuovo step di training invece di un altro percorso nello stesso grafo.

Quindi un loop di training deve azzerarli:

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

Questo è optimizer.zero_grad() in PyTorch, e il consiglio abituale è che dimenticarlo rompe il training. Allora cancelliamo quelle due righe e vediamo quanto è rotto. Stessi seed, stesso tutto, 200 step di XOR:

Ai learning rate piccoli, la versione con bug vince ogni singola riga. Converge quando la versione corretta si blocca.

Non è un caso, e vale la pena capirlo, perché spiega perché questo bug è così difficile da cogliere. Se non azzeri mai il gradiente, allora allo step $k$ il parametro viene aggiornato dalla somma di ogni gradiente calcolato fino a quel momento. Su una loss che continua a puntare più o meno nella stessa direzione, quella somma cresce costantemente, e l’effetto è un learning rate che aumenta da solo. A $\eta = 0.05$, dove l’algoritmo corretto avanza a fatica, la dimensione del passo fuori controllo sembra esattamente una soluzione.

Poi guarda le tre righe in fondo. A $\eta = 0.3$ lo stesso meccanismo manda in pezzi il modello: loss 8.0 è il punteggio di un modello collassato a una costante $\pm 1$ — metà dei 16 che costerebbero quattro risposte massimamente sbagliate — — mentre la versione corretta ora converge in modo pulito.

Quindi la formulazione onesta non è «chiama sempre zero_grad o il tuo modello non farà training». È: senza, non stai più eseguendo gradient descent. Stai eseguendo qualcosa la cui dimensione del passo deriva verso l’alto a una velocità che nessuno ha scelto, e sembrerà funzionare, a volte meglio della cosa vera, fino al momento in cui non funzionerà più — e a quel punto darai la colpa al learning rate, all’inizializzazione o ai dati. Questa è la forma dei bug peggiori nel machine learning: non fanno crash, cambiano l’algoritmo in un algoritmo diverso che ogni tanto ottiene risultati migliori.

Con il motore pronto, una rete neurale è pochissimo codice. Un neurone è un prodotto scalare, un bias e un’attivazione; un layer è una lista di neuroni; una rete è una lista di layer.

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

Non c’è backward pass in nulla di tutto questo. Nemmeno una riga. La classe Value sa già differenziare qualsiasi cosa queste classi si trovino a costruire, ed è questo il punto di averla scritta per prima: un motore autodiff non sa di essere usato per una rete neurale.

Ora il problema del Capitolo 1. Due input, due unità nascoste, un output, nove parametri:

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

Quattro su quattro. La funzione che nessun perceptron può calcolare — dimostrato nel Capitolo 1 con quattro disuguaglianze che richiedevano che $b$ fosse sia positivo sia negativo — viene calcolata da nove numeri trovati automaticamente.

La parte soddisfacente non è che funzioni. È poter vedere come, perché con due unità nascoste la rappresentazione intermedia è un punto in un piano e puoi semplicemente stamparla.

Addestrata fino a una loss di 0.001241, ecco dove finisce ogni input dopo il layer nascosto, e cosa ne fa il neurone di output:

Guarda la prima e la quarta riga. Gli input $(0,0)$ e $(1,1)$ sono angoli diagonalmente opposti del quadrato — tanto lontani quanto possono esserlo due punti in questo problema — e il layer nascosto li mappa in $(0.82, -0.85)$ e $(0.84, -0.86)$. Quasi lo stesso punto. Il layer ha ripiegato il piano in modo che i due angoli rifiutati finiscano uno sopra l’altro, e una volta che sono nello stesso posto, una sola retta li separa dagli altri due.

E il neurone di output è esattamente quella retta. I suoi parametri appresi sono $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, quindi il suo confine decisionale è

che è una retta: un perceptron, lo stesso oggetto del Capitolo 1, invariato. Allora non poteva risolvere XOR e non può farlo ora. Ciò che è cambiato è che non sta più guardando l’input; sta guardando uno spazio che il primo layer ha costruito per lui, in cui il problema è linearmente separabile.

Questo è ciò che è una rappresentazione appresa, e vale la pena essere precisi perché l’espressione verrà usata con leggerezza per il resto di questo corso, e per il resto del campo. Non è una compressione, un riassunto o un embedding in senso mistico. È un cambio di coordinate, appreso invece che progettato, il cui unico compito è rendere facile il lavoro del layer successivo.

Qui c’è un teorema, e di solito viene citato male.

Cybenko nel 1989 e Hornik nel 1991 dimostrarono che una rete feedforward con un singolo layer nascosto e una funzione di attivazione adatta può approssimare qualsiasi funzione continua su un insieme compatto, con la precisione che vuoi, dato un numero sufficiente di unità nascoste.³⁴ È un risultato autentico e importante: dice che l’architettura non è il limite.

Ora leggi cosa omette. Non dice quante unità: il limite può essere astronomicamente grande. Non dice che i pesi possano essere trovati; afferma l’esistenza, e gradient descent da un punto di partenza casuale non è un oracolo. E non dice nulla sul comportamento su dati che non hai visto, che è la seconda metà del Capitolo 6.

Il divario tra «esiste» e «trovabile» non è accademico. Ecco lo stesso problema XOR, 50 inizializzazioni casuali ciascuna, 1000 step, con solo la dimensione del layer nascosto cambiata:

Con l’architettura minima praticabile, una run su quattro non ci arriva mai: si assesta in una configurazione da cui non riesce a scendere, esattamente il minimo locale che il Capitolo 3 ha mostrato su una superficie unidimensionale. Aggiungi un’unità e i fallimenti quasi scompaiono, non perché la rete sia diventata più espressiva (due unità bastano già: 38 run lo dimostrano) ma perché dimensioni extra danno alla discesa più direzioni attraverso cui scappare.

E poi otto unità va leggermente peggio di quattro. A learning rate e budget di step fissi, più capacità non è monotonicamente meglio. Chiunque ti dica che la soluzione per una rete bloccata è sempre una rete più grande sta estrapolando dal centro di quella tabella.

È la stessa lezione del teorema di convergenza nel Capitolo 1, e sarà la stessa lezione nel Capitolo 10 sulle scaling law, nella forma che quel capitolo le dà: una previsione della loss non è una previsione della capability per cui stai pagando, e la distanza tra le due è il luogo in cui vive l’ingegneria.

Ora hai una rete che si addestra. È un risultato più piccolo di quanto sembri, perché la rete che hai si addestra su quattro esempi e viene misurata sugli stessi quattro.

Esegui lo stesso codice su un dataset reale e appare una nuova serie di problemi, nessuno dei quali riguarda i gradienti. La loss scende per un po’ e poi si ferma. Oppure scende sui dati di training e sale su tutto il resto. Oppure non si muove affatto dal primo step, e la causa si rivela essere l’intervallo dei pesi casuali iniziali. Oppure l’input di un’unità è scivolato in negativo su ogni esempio nell’epoca tre ed è rimasto morto da allora, in silenzio, portandosi via un pezzo della capacità del modello.

Non sono fallimenti esotici; sono la condizione normale di una rete appena scritta, e nessuno di loro si annuncia. Il gradiente è corretto — l’hai confrontato con PyTorch fino a sedici cifre decimali — e il modello comunque non impara.

Il Capitolo 6 parla di questo: inizializzazione, normalizzazione, overfitting e regolarizzazione, e dell’abitudine diagnostica di chiedersi quale di queste cose stia succedendo prima di cambiare qualsiasi cosa. È la differenza tra una rete che gira e una rete che funziona.

La classe Value in questo capitolo discende direttamente da micrograd di Andrej Karpathy, e il suo video The spelled-out intro to neural networks and backpropagation: building micrograd è il miglior modo di spendere tre ore su questo materiale se vuoi sentirlo spiegare in un secondo modo da qualcun altro. Il suo post del 2016 Yes you should understand backprop argomenta perché dovresti scriverne una tu stesso ed è lettura assegnata nel CS224n di Stanford. Le note di CS231n sulla backpropagation (cs231n.github.io/optimization-2) sono il trattamento canonico degli schemi di flusso tabulati sopra. Per la matematica come calcolo su un grafo invece che come folklore delle reti neurali, il capitolo 5.6 di Mathematics for Machine Learning di Deisenroth, Faisal e Ong è insolitamente chiaro; e la survey di Baydin, Pearlmutter, Radul e Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) è il riferimento per l’intero campo, incluso il compromesso forward/reverse discusso sopra.