Backpropagation do zero: primeiro o motor, depois a rede

Antes de construir a máquina, é preciso resolver uma pergunta, porque se a resposta fosse a outra não haveria nada para construir.

O perceptron falhou no XOR porque uma linha não consegue separar os quatro pontos. A correção óbvia é empilhar: passar a entrada por uma camada linear e depois por outra. Isso ajuda?

Não, e a prova tem duas linhas. Uma camada linear é $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Alimente outra com ela, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, e substitua:

A composição é $W\mathbf{x} + \mathbf{b}$ com $W = W_2W_1$ e $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Uma pilha de camadas lineares é uma única camada linear. Dez delas, mil delas: continua a ser uma linha, continua sem conseguir fazer XOR.

Vale a pena ver isso acontecer em vez de apenas acreditar:

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

Não são aproximadamente iguais. São idênticas bit a bit, porque é a mesma aritmética rearranjada.

Portanto, a profundidade por si só não compra nada. O que compra alguma coisa é colocar uma função não linear entre as camadas — e essa é toda a razão pela qual existem funções de ativação. Não são um floreado biológico nem um truque de normalização. Sem uma, a segunda camada é decoração.

Agora a matemática, e é uma regra que já conhece aplicada num sítio ligeiramente pouco familiar.

A regra da cadeia de uma variável diz que, se $L$ depende de $c$ e $c$ depende de $x$, então $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. As derivadas multiplicam-se ao longo de uma cadeia.

A parte que interessa aqui é o que acontece quando uma variável alimenta mais do que um caminho a jusante. Se $x$ influencia $L$ através de $a$ e também através de $b$, as contribuições somam-se:

Multiplicar ao longo de um caminho, somar entre caminhos. Isso é todo o backpropagation, e cada detalhe de implementação no resto deste capítulo — incluindo o += no código e a chamada zero_grad() que atrapalha todos os que escrevem o seu primeiro ciclo de treino — é uma consequência direta dessa segunda palavra.

Pegue num circuito concreto de cinco operações, com $x = 0.5$ e $y = 1.4$:

Repare que $x$ aparece três vezes: em $a$, em $b$ e diretamente em $L$. Faça a passagem backward no papel, da direita para a esquerda, começando em $\frac{dL}{dL} = 1$:

Guarde esse número. Daqui a poucas páginas, um programa vai produzi-lo sem que lhe seja dito nada disto.

A ideia que torna isto programável: todos esses passos foram locais. Para empurrar um gradiente pelo nó de multiplicação, precisava do gradiente recebido e dos dois valores de entrada guardados — nada sobre o resto do circuito. Cada operação sabe como se diferenciar a si própria.

Portanto, crie um número que se lembra do que o produziu.

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

Quatro campos. data é o valor. grad acumula $\frac{\partial L}{\partial \text{self}}$. _prev é o conjunto de Values a partir dos quais este foi calculado — as arestas do grafo. E _backward é uma closure que cada operação instala: sabe como empurrar o gradiente deste nó um passo para trás, para as suas entradas.

Cada operador segue a mesma forma: calcular a saída, registar os pais, instalar a regra 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

Leia os quatro corpos _backward como uma tabela e os padrões de fluxo da derivação no papel estão logo ali:

Cada uma usa += e nunca =. Essa é a regra de «somar entre caminhos», codificada. Um nó que alimenta dois consumidores é chamado duas vezes, e as duas contribuições somam-se por si.

Depois vem o controlador, que é a única parte com algum conhecimento 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 produz uma ordenação topológica do grafo: cada nó aparece depois de todas as suas entradas. Percorrer essa lista ao contrário garante que, quando chama o _backward de um nó, o seu próprio gradiente já está completo — todos os consumidores a jusante já contribuíram. Se errar a ordem, empurra para trás um gradiente meio acabado, o que produz uma resposta errada sem mensagem de erro.

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. O mesmo número, vindo de um programa a que foi dita a regra para +, a regra para *, a regra para tanh, e nada sobre este circuito.

Duas verificações independentes, porque «bate certo com o que derivei» é um teste fraco quando a mesma pessoa fez as duas coisas.

Diferenciação numérica. Dê um pequeno empurrão à entrada e meça. A diferença centrada $\frac{L(x+h) - L(x-h)}{2h}$ estima a derivada sem cálculo algum:

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 tem um motor autodiff industrial escrito por pessoas que fazem isto profissionalmente:

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

Concordância em $2 \times 10^{-16}$, que é o épsilon de máquina para um float de 64 bits: os dois motores estão a realizar aritmética idêntica. Guarde a verificação numérica — é a ferramenta para depurar a passagem backward de uma nova camada, e é a razão pela qual um gradiente errado é encontrável.

O mesmo circuito, entradas diferentes. Defina $x = 2$ e $y = -3$, o que torna $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

O gradiente que atravessa o nó $\tanh$ caiu por um fator de 9.945. Tudo a montante dele — numa rede real, todas as camadas antes dele — recebe praticamente nada. Os dois caminhos pelo circuito ficaram silenciosos; só a ligação direta que salta o $\tanh$ ainda transporta sinal.

Esse é o problema do gradiente que desaparece, num único nó. Empilhe quarenta camadas de $\tanh$ e multiplique quarenta fatores desses, e as camadas iniciais deixam de aprender por completo. É também, incidentalmente, um argumento a favor de ligações de salto que consegue ver aqui em miniatura: o caminho que contornou a não linearidade é o único que sobreviveu.

Cada _backward usa +=. Isso está correto — é assim que os caminhos somam. Mas tem uma consequência que apanha toda a gente: os gradientes acumulam também entre chamadas a backward(). O motor não faz ideia de que a sua segunda chamada é um novo passo de treino em vez de outro caminho no mesmo grafo.

Por isso, um ciclo de treino tem de os limpar:

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

Isto é optimizer.zero_grad() em PyTorch, e o conselho habitual é que esquecê-lo estraga o treino. Portanto, vamos apagar essas duas linhas e ver quão estragado fica. Mesmas seeds, tudo igual, 200 passos de XOR:

Com learning rates pequenos, a versão com bug ganha em todas as linhas. Converge quando a versão correta fica bloqueada.

Isso não é acaso e vale a pena perceber, porque explica por que este bug é tão difícil de apanhar. Se nunca limpar o gradiente, então no passo $k$ o parâmetro é atualizado pela soma de todos os gradientes calculados até então. Numa perda que continua a apontar mais ou menos na mesma direção, essa soma cresce de forma constante, e o efeito é uma learning rate que aumenta sozinha. Em $\eta = 0.05$, onde o algoritmo correto se arrasta, o tamanho de passo descontrolado parece exatamente uma correção.

Depois olhe para as três linhas de baixo. Em $\eta = 0.3$, o mesmo mecanismo desfaz o modelo — perda 8.0 é o que obtém um modelo colapsado para uma constante $\pm 1$ — metade dos 16 que quatro respostas maximamente erradas custariam — enquanto a versão correta agora converge limpidamente.

Portanto, a afirmação honesta não é «chame sempre zero_grad ou o seu modelo não treina». É: sem isso, já não está a executar gradient descent. Está a executar algo cujo tamanho de passo deriva para cima a uma taxa que ninguém escolheu, e vai parecer funcionar, às vezes melhor do que a coisa real, até ao momento em que deixa de funcionar — e aí culpará a learning rate, a inicialização ou os dados. Esta é a forma dos piores bugs em machine learning: não rebentam, mudam o algoritmo para um algoritmo diferente que ocasionalmente pontua melhor.

Com o motor terminado, uma rede neuronal quase não exige código. Um neurónio é um produto escalar, um viés e uma ativação; uma camada é uma lista de neurónios; uma rede é uma lista de camadas.

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

Não há passagem backward em nada disso. Nem uma linha. A classe Value já sabe diferenciar seja o que for que estas classes construam, que é o objetivo de a termos escrito primeiro: um motor autodiff não sabe que está a ser usado para uma rede neuronal.

Agora o problema do capítulo 1. Duas entradas, duas unidades ocultas, uma saída, nove parâmetros:

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

Quatro em quatro. A função que nenhum perceptron consegue calcular — provado no capítulo 1 por quatro desigualdades que exigiam que $b$ fosse simultaneamente positivo e negativo — é calculada por nove números encontrados automaticamente.

A parte satisfatória não é funcionar. É conseguir ver como, porque com duas unidades ocultas a representação intermédia é um ponto num plano e pode simplesmente imprimi-la.

Treinada até uma perda de 0.001241, eis onde cada entrada aterra depois da camada oculta, e o que o neurónio de saída faz com ela:

Olhe para a primeira e a quarta linhas. As entradas $(0,0)$ e $(1,1)$ são cantos diagonalmente opostos do quadrado — tão afastados quanto dois pontos neste problema conseguem estar — e a camada oculta mapeia-os para $(0.82, -0.85)$ e $(0.84, -0.86)$. Quase o mesmo ponto. A camada dobrou o plano de modo que os dois cantos rejeitados aterram um em cima do outro e, depois de estarem no mesmo lugar, uma linha separa-os dos outros dois.

E o neurónio de saída é exatamente essa linha. Os seus parâmetros aprendidos são $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, por isso a sua fronteira de decisão é

que é uma linha reta — um perceptron, o mesmo objeto do capítulo 1, inalterado. Não conseguia resolver XOR antes e não consegue agora. O que mudou é que já não está a olhar para a entrada; está a olhar para um espaço que a primeira camada construiu para ele, no qual o problema é linearmente separável.

Isso é uma representação aprendida, e vale a pena ser preciso porque a expressão é usada de forma solta no resto deste curso, e no resto da área. Não é uma compressão, um resumo nem um embedding em qualquer sentido místico. É uma mudança de coordenadas, aprendida em vez de desenhada, cujo único trabalho é tornar fácil o trabalho da camada seguinte.

Há aqui um teorema, e costuma ser mal citado.

Cybenko em 1989 e Hornik em 1991 provaram que uma rede feedforward com uma única camada oculta e uma função de ativação adequada consegue aproximar qualquer função contínua num conjunto compacto, com a precisão que quiser, desde que tenha unidades ocultas suficientes.³⁴ É um resultado genuíno e importante: diz que a arquitetura não é a limitação.

Agora leia o que omite. Não diz quantas unidades — o limite pode ser astronomicamente grande. Não diz que os pesos podem ser encontrados; afirma existência, e gradient descent a partir de um início aleatório não é um oráculo. E não diz nada sobre o comportamento em dados que não viu, que é a segunda metade do capítulo 6.

A distância entre «existe» e «é encontrável» não é académica. Eis o mesmo problema XOR, 50 inicializações aleatórias cada, 1000 passos, mudando apenas o tamanho da camada oculta:

Com a arquitetura mínima viável, uma execução em quatro nunca lá chega — assenta numa configuração da qual não consegue descer, exatamente o mínimo local que o capítulo 3 mostrou numa superfície unidimensional. Acrescente uma unidade e as falhas quase desaparecem, não porque a rede se tornou mais expressiva (duas unidades já bastam — 38 execuções provam-no), mas porque dimensões extra dão à descida mais direções por onde escapar.

E depois oito unidades saem ligeiramente pior do que quatro. Com uma learning rate e um orçamento de passos fixos, mais capacidade não é monotonicamente melhor. Quem lhe disser que a correção para uma rede bloqueada é sempre uma rede maior está a extrapolar a partir do meio dessa tabela.

É a mesma lição do teorema da convergência no capítulo 1, e será a mesma lição no capítulo 10 sobre leis de escala, na forma que esse capítulo lhe dá: uma previsão da perda não é uma previsão da capacidade pela qual está a pagar, e a distância entre as duas é onde vive a engenharia.

Agora tem uma rede que treina. É uma conquista menor do que parece, porque a rede que tem treina em quatro exemplos e é medida nos mesmos quatro.

Execute o mesmo código num conjunto de dados real e aparece um novo conjunto de problemas, nenhum deles sobre gradientes. A perda desce durante algum tempo e depois para. Ou desce nos dados de treino e sobe em tudo o resto. Ou não se mexe desde o primeiro passo, e a causa acaba por ser o intervalo dos pesos aleatórios iniciais. Ou a entrada de uma unidade ficou negativa em todos os exemplos na época três e está morta desde então, silenciosamente, levando consigo uma parte da capacidade do modelo.

Estas não são falhas exóticas; são a condição normal de uma rede acabada de escrever, e nenhuma delas se anuncia. O gradiente está correto — comparou-o com PyTorch a dezasseis casas decimais — e o modelo continua sem aprender.

O capítulo 6 é sobre isso: inicialização, normalização, overfitting e regularização, e o hábito diagnóstico de perguntar qual destas coisas está a acontecer antes de mudar seja o que for. É a diferença entre uma rede que corre e uma rede que funciona.

A classe Value neste capítulo descende diretamente do micrograd de Andrej Karpathy, e o vídeo dele The spelled-out intro to neural networks and backpropagation: building micrograd é as melhores três horas que pode gastar neste material se quiser vê-lo explicado de outra forma por outra pessoa. O seu artigo de 2016 Yes you should understand backprop defende o caso de escrever uma por si próprio e é leitura obrigatória no CS224n de Stanford. As notas de CS231n sobre backpropagation (cs231n.github.io/optimization-2) são o tratamento canónico dos padrões de fluxo tabelados acima. Para a matemática como cálculo num grafo, e não como folclore de redes neuronais, o capítulo 5.6 de Mathematics for Machine Learning de Deisenroth, Faisal e Ong é invulgarmente claro; e o estudo de Baydin, Pearlmutter, Radul e Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) é a referência para a área como um todo, incluindo o trade-off forward/inverso discutido acima.