Backpropagation с нуля: сначала движок, потом сеть

Перед тем как строить машину, нужно закрыть один вопрос, потому что при противоположном ответе строить было бы нечего.

Перцептрон провалился на XOR, потому что одна прямая не может разделить четыре точки. Очевидная правка — складывать слои: пропустить вход через один линейный слой, потом через другой. Помогает ли это?

Нет, и доказательство занимает две строки. Линейный слой — это $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Подайте его в другой, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, и подставьте:

Композиция равна $W\mathbf{x} + \mathbf{b}$ с $W = W_2W_1$ и $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Стек линейных слоёв — это один линейный слой. Десять таких, тысяча таких: всё ещё одна прямая, всё ещё неспособная сделать XOR.

Стоит увидеть, как это происходит, а не просто поверить:

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

Не примерно равны. Идентичны бит в бит, потому что это та же арифметика, только переставленная.

Значит, глубина сама по себе ничего не даёт. Что даёт пользу — так это нелинейная функция между слоями; и это вся причина существования функций активации. Это не биологическое украшение и не трюк нормализации. Без неё второй слой — декорация.

Теперь математика, и это одно правило, которое вы уже знаете, просто применённое в чуть непривычном месте.

Цепное правило для одной переменной говорит: если $L$ зависит от $c$, а $c$ зависит от $x$, то $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Производные перемножаются вдоль цепочки.

Здесь важно, что происходит, когда переменная питает больше одного downstream-пути. Если $x$ влияет на $L$ через $a$, а также через $b$, вклады складываются:

Умножать вдоль пути, суммировать между путями. Это весь backpropagation, и каждая деталь реализации в остальной части главы — включая += в коде и вызов zero_grad(), о который спотыкается каждый, кто пишет свой первый цикл обучения, — прямое следствие этого второго слова.

Возьмём конкретную схему из пяти операций, с $x = 0.5$ и $y = 1.4$:

Обратите внимание, что $x$ появляется три раза: в $a$, в $b$ и напрямую в $L$. Сделайте backward pass на бумаге, справа налево, начиная с $\frac{dL}{dL} = 1$:

Запомните это число. Через несколько страниц программа получит его, хотя ей ничего из этого не объясняли.

Идея, которая делает это программируемым: каждый из этих шагов был локальным. Чтобы протолкнуть gradient через узел умножения, вам нужны входящий gradient и два сохранённых значения входов — ничего о всей остальной схеме. Каждая операция знает, как дифференцировать саму себя.

Значит, сделаем число, которое помнит, что его породило.

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

Четыре поля. data — значение. grad накапливает $\frac{\partial L}{\partial \text{self}}$. _prev — множество Value, из которых было вычислено это значение, то есть рёбра графа. А _backward — замыкание, которое устанавливает каждая операция: оно знает, как протолкнуть gradient этого узла на один шаг назад к его входам.

Каждый оператор имеет одну и ту же форму: вычислить выход, записать родителей, установить локальное правило.

    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

Читайте четыре тела _backward как таблицу — и шаблоны потока из бумажного вывода сразу видны:

Каждый из них использует += и никогда =. Это правило «суммировать между путями», закодированное напрямую. Узел, который питает двух потребителей, вызывается дважды, и два вклада складываются сами.

Затем драйвер — единственная часть, которая знает что-то глобальное:

    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 создаёт топологический порядок графа: каждый узел появляется после всех своих входов. Проход по этому списку в обратном порядке гарантирует, что когда вы вызываете _backward узла, его собственный gradient уже полный — каждый downstream-потребитель уже внёс вклад. Ошибитесь с порядком, и вы протолкнёте назад недоделанный gradient, получив неверный ответ без сообщения об ошибке.

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. То же число, от программы, которой сообщили правило для +, правило для *, правило для tanh — и ничего об этой схеме.

Две независимые проверки, потому что «совпадает с тем, что я вывел» — слабый тест, когда и вывод, и код сделал один человек.

Численное дифференцирование. Чуть сдвиньте вход и измерьте. Центральная разность $\frac{L(x+h) - L(x-h)}{2h}$ оценивает производную вообще без матанализа:

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

Против PyTorch, у которого промышленный autodiff-движок, написанный людьми, занимающимися этим профессионально:

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

Совпадение на $2 \times 10^{-16}$, что является машинным эпсилоном для 64-битного float: два движка выполняют идентичную арифметику. Держите численную проверку под рукой — это инструмент для отладки backward pass нового слоя, и именно благодаря ему неверный gradient вообще можно найти.

Та же схема, другие входы. Задайте $x = 2$ и $y = -3$, что даёт $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

Gradient, проходящий через узел $\tanh$, упал в 9 945 раз. Всё, что выше него, — в настоящей сети каждый слой перед ним — получает почти ничего. Два пути через схему замолчали; только прямое соединение, которое обходит $\tanh$, всё ещё несёт сигнал.

Это проблема исчезающего gradient в одном узле. Сложите сорок слоёв $\tanh$ и перемножьте сорок таких факторов, и ранние слои полностью перестанут учиться. Заодно это аргумент в пользу skip connections, который здесь виден в миниатюре: путь, обошедший нелинейность, оказался единственным выжившим.

Каждый _backward использует +=. Это правильно — так суммируются пути. Но у этого есть последствие, которое ловит всех: gradients накапливаются и между вызовами backward() тоже. Движок не знает, что ваш второй вызов — это новый шаг обучения, а не ещё один путь в том же графе.

Поэтому цикл обучения должен их очищать:

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

В PyTorch это optimizer.zero_grad(), и обычный совет звучит так: забыли его — обучение сломалось. Так давайте удалим эти две строки и посмотрим, насколько всё сломано. Те же seed, всё то же самое, 200 шагов XOR:

На малых learning rate багованная версия выигрывает в каждой строке. Она сходится там, где правильная версия застревает.

Это не случайность, и это стоит понять, потому что объясняет, почему этот баг так трудно поймать. Если вы никогда не очищаете gradient, то на шаге $k$ параметр обновляется суммой всех gradients, вычисленных до этого. На loss, который продолжает указывать примерно в ту же сторону, эта сумма устойчиво растёт, и эффект похож на learning rate, который увеличивается сам по себе. При $\eta = 0.05$, где правильный алгоритм ползёт, разгоняющийся размер шага выглядит как исправление.

Теперь посмотрите на нижние три строки. При $\eta = 0.3$ тот же механизм разносит модель — loss 8.0 получает модель, схлопнувшаяся в константу $\pm 1$, то есть половина от 16, которые стоили бы четыре максимально неверных ответа — — тогда как правильная версия теперь сходится чисто.

Так что честная формулировка не «всегда вызывайте zero_grad, иначе модель не будет обучаться». Она такая: без него вы больше не запускаете gradient descent. Вы запускаете что-то, чей размер шага дрейфует вверх со скоростью, которую никто не выбирал, и это будет казаться работающим, иногда лучше настоящего алгоритма, ровно до тех пор, пока не перестанет — и тогда вы будете винить learning rate, инициализацию или данные. Так выглядят худшие баги в machine learning: они не падают, они превращают алгоритм в другой алгоритм, который иногда даёт лучший счёт.

Когда движок готов, нейронная сеть — это совсем немного кода. Нейрон — это скалярное произведение, bias и активация; слой — список нейронов; сеть — список слоёв.

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

Во всём этом нет backward pass. Ни одной строки. Класс Value уже знает, как дифференцировать всё, что эти классы случайно построят, и именно в этом смысл того, что мы сначала написали его: autodiff-движок не знает, что его используют для нейронной сети.

Теперь задача из Главы 1. Два входа, два скрытых units, один выход, девять параметров:

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

Четыре из четырёх. Функция, которую не может вычислить ни один перцептрон, — это было доказано в Главе 1 четырьмя неравенствами, требовавшими, чтобы $b$ был и положительным, и отрицательным, — вычисляется девятью числами, найденными автоматически.

Удовлетворяет не то, что это работает. Удовлетворяет возможность увидеть как, потому что с двумя скрытыми units промежуточное представление — это точка на плоскости, и её можно просто напечатать.

После обучения до loss 0.001241 вот куда каждый вход попадает после скрытого слоя и что с ним делает выходной нейрон:

Посмотрите на первую и четвёртую строки. Входы $(0,0)$ и $(1,1)$ — диагонально противоположные углы квадрата, настолько далёкие друг от друга, насколько две точки в этой задаче вообще могут быть, — а скрытый слой отображает их в $(0.82, -0.85)$ и $(0.84, -0.86)$. Почти в одну и ту же точку. Слой сложил плоскость так, что два отвергнутых угла легли друг на друга, и когда они оказались в одном месте, одна прямая отделила их от двух остальных.

И выходной нейрон — ровно эта прямая. Его выученные параметры: $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, поэтому его граница решения —

то есть прямая линия — перцептрон, тот же объект из Главы 1, без изменений. Тогда он не мог решить XOR и сейчас не может. Изменилось то, что теперь он смотрит не на вход; он смотрит на пространство, которое для него построил первый слой и в котором задача линейно разделима.

Вот что такое выученное представление, и здесь стоит быть точными, потому что дальше в курсе и во всей области эту фразу часто используют расплывчато. Это не сжатие, не summary и не embedding в мистическом смысле. Это смена координат, выученная, а не спроектированная, единственная задача которой — упростить работу следующего слоя.

Здесь есть теорема, и её обычно цитируют плохо.

Цыбенко в 1989 году и Хорник в 1991 году доказали, что feedforward-сеть с одним скрытым слоем и подходящей функцией активации может аппроксимировать любую непрерывную функцию на компактном множестве с любой желаемой точностью, если дать ей достаточно скрытых units.³⁴ Это настоящий и важный результат: он говорит, что архитектура — не ограничение.

Теперь прочитайте, что он опускает. Он не говорит, сколько units нужно: граница может быть астрономически большой. Он не говорит, что веса можно найти; он утверждает существование, а gradient descent из случайного старта — не оракул. И он ничего не говорит о поведении на данных, которых вы не видели, а это вторая половина Главы 6.

Разрыв между «существует» и «можно найти» не академический. Вот та же задача XOR: по 50 случайных инициализаций, 1000 шагов, менялся только размер скрытого слоя:

С минимально жизнеспособной архитектурой один запуск из четырёх так и не доходит — он оседает в конфигурации, из которой не может спуститься, ровно в том локальном минимуме, который Глава 3 показывала на одномерной поверхности. Добавьте один unit, и провалы почти исчезают — не потому, что сеть стала выразительнее (двух units уже достаточно, это доказывают 38 запусков), а потому что дополнительные измерения дают спуску больше направлений для побега.

А затем восемь units работают чуть хуже, чем четыре. При фиксированном learning rate и бюджете шагов большая ёмкость не становится монотонно лучше. Любой, кто говорит вам, что лекарство от застрявшей сети — всегда сеть побольше, экстраполирует из середины этой таблицы.

Это тот же урок, что и теорема сходимости в Главе 1, и это будет тот же урок в Главе 10 о scaling laws в форме, которую даст та глава: предсказание loss — не предсказание способности, за которую вы платите, и именно в расстоянии между ними живёт инженерия.

Теперь у вас есть сеть, которая обучается. Это меньшее достижение, чем кажется, потому что ваша сеть обучается на четырёх примерах и измеряется на тех же четырёх.

Запустите тот же код на реальном датасете, и появится новый набор проблем, ни одна из которых не про gradients. Loss некоторое время падает, а потом останавливается. Или он падает на обучающих данных и растёт на всём остальном. Или не двигается вообще с первого шага, и причиной оказывается диапазон начальных случайных весов. Или вход одного unit на третьей эпохе стал отрицательным на каждом примере, и с тех пор этот unit мёртв — тихо, унося с собой кусок ёмкости модели.

Это не экзотические отказы; это нормальное состояние только что написанной сети, и ни один из них не объявляет о себе. Gradient верный — вы сверили его с PyTorch до шестнадцати знаков после запятой, — а модель всё равно не учится.

Глава 6 об этом: инициализация, нормализация, переобучение и регуляризация, а также диагностическая привычка спрашивать, что именно из этого происходит, прежде чем что-либо менять. Это разница между сетью, которая запускается, и сетью, которая работает.

Класс Value в этой главе напрямую происходит от micrograd Андрея Карпати, а его видео The spelled-out intro to neural networks and backpropagation: building micrograd — лучшие три часа, которые можно потратить на этот материал, если вы хотите услышать второе объяснение от другого человека. Его пост 2016 года Yes you should understand backprop объясняет, почему стоит написать такой движок самостоятельно, и входит в обязательное чтение Stanford CS224n. Заметки CS231n о backpropagation (cs231n.github.io/optimization-2) — каноническое изложение шаблонов потока, сведённых в таблицу выше. Для математики как матанализа на графе, а не фольклора нейронных сетей, глава 5.6 книги Mathematics for Machine Learning Deisenroth, Faisal и Ong необычайно ясна; а обзор Baydin, Pearlmutter, Radul и Siskind Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) — справочник по области в целом, включая компромисс между прямым и обратным режимами, обсуждённый выше.