Backpropagation from scratch: 엔진부터, 그다음 신경망

기계를 만들기 전에 먼저 정리해야 할 질문이 하나 있습니다. 답이 반대였다면 만들 것도 없었을 것이기 때문입니다.

perceptron은 XOR에서 실패했습니다. 하나의 직선으로 네 점을 분리할 수 없기 때문입니다. 뻔한 해결책은 쌓는 것입니다. 입력을 하나의 linear layer에 통과시키고, 그다음 또 하나의 linear layer에 통과시킵니다. 도움이 될까요?

아니요. 증명은 두 줄이면 됩니다. linear layer는 $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$입니다. 이를 또 다른 layer, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$에 넣고 대입하면 다음과 같습니다.

이 합성은 $W = W_2W_1$와 $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$를 갖는 $W\mathbf{x} + \mathbf{b}$입니다. linear layer를 쌓아도 결국 하나의 linear layer입니다. 열 개를 쌓아도, 천 개를 쌓아도 여전히 하나의 직선이고, 여전히 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

대략 같은 것이 아닙니다. bit 단위로 완전히 동일합니다. 같은 산술을 재배열했을 뿐이기 때문입니다.

따라서 깊이 자체는 아무것도 사 주지 않습니다. 무언가를 가능하게 하는 것은 layer 사이에 nonlinear function을 넣는 것이며, activation function이 존재하는 이유가 바로 이것입니다. 그것들은 생물학적 장식도, normalisation 요령도 아닙니다. activation function이 없으면 두 번째 layer는 장식입니다.

이제 수학입니다. 이미 알고 있는 규칙 하나를 조금 낯선 곳에 적용할 뿐입니다.

단일 변수 chain rule은 $L$가 $c$에 의존하고 $c$가 $x$에 의존한다면 $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$라고 말합니다. 미분은 chain을 따라 곱해집니다.

여기서 중요한 부분은 어떤 변수가 downstream 경로를 둘 이상 먹여 살릴 때 일어나는 일입니다. $x$가 $a$를 통해 $L$에 영향을 주고, 동시에 $b$를 통해서도 영향을 준다면, 기여분은 더해집니다.

경로를 따라 곱하고, 경로들 사이에서는 합합니다. 이것이 backpropagation의 전부입니다. 이 챕터의 나머지 모든 구현 세부사항 — 코드의 +=와, 첫 training loop를 쓰는 모든 사람을 넘어뜨리는 zero_grad() 호출까지 — 은 그 두 번째 단어의 직접적인 결과입니다.

$x = 0.5$와 $y = 1.4$를 갖는 다섯 operation짜리 구체적인 circuit을 봅시다.

$x$가 세 번 등장한다는 점에 주목하세요. $a$ 안에, $b$ 안에, 그리고 $L$ 안에 직접 등장합니다. $\frac{dL}{dL} = 1$에서 시작해 오른쪽에서 왼쪽으로 backward pass를 종이에 해 봅시다.

그 숫자를 기억해 두세요. 몇 페이지 뒤에 프로그램이 이 내용을 전혀 지시받지 않고 그 숫자를 만들어낼 것입니다.

이를 프로그램으로 만들 수 있게 해 주는 통찰은 이것입니다. 위의 모든 단계는 local했습니다. multiplication node를 통해 gradient를 밀어 넣으려면 들어온 gradient와 저장해 둔 두 입력값만 있으면 됐습니다. circuit의 나머지에 대해서는 아무것도 필요하지 않았습니다. 각 operation은 자신을 어떻게 differentiate할지 알고 있습니다.

그러니 자신을 무엇이 만들었는지 기억하는 숫자를 만듭시다.

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들의 집합, 즉 graph의 edge입니다. 그리고 _backward는 각 operation이 설치하는 closure입니다. 이 node의 gradient를 입력들로 한 단계 뒤로 밀어 넣는 방법을 알고 있습니다.

모든 operator는 같은 형태를 따릅니다. 출력을 계산하고, parent를 기록하고, local rule을 설치합니다.

    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 본문을 표처럼 읽으면, 종이 derivation에서 본 흐름 패턴이 바로 거기에 놓여 있습니다.

이 모든 것은 +=를 사용하고 절대 =를 사용하지 않습니다. 그것이 “경로들 사이에서는 합한다”는 규칙의 인코딩입니다. 두 consumer를 먹이는 node는 두 번 호출되고, 두 기여분은 저절로 더해집니다.

그다음은 driver입니다. 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는 graph의 topological ordering을 만듭니다. 모든 node가 자신의 모든 입력 뒤에 등장합니다. 이 list를 역순으로 걸으면 어떤 node의 _backward를 호출할 때 그 node 자신의 gradient가 이미 완성되어 있음을 보장합니다. downstream의 모든 consumer가 이미 기여했기 때문입니다. 순서를 틀리면 반쯤 완성된 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. 같은 숫자입니다. 이 프로그램은 +의 rule, *의 rule, tanh의 rule만 들었고, 이 circuit에 대해서는 아무것도 듣지 않았습니다.

독립적인 확인을 두 개 더 합니다. “내가 유도한 것과 맞다”는 같은 사람이 둘 다 했을 때 약한 test이기 때문입니다.

Numerical differentiation. 입력을 살짝 밀고 측정합니다. centred difference $\frac{L(x+h) - L(x-h)}{2h}$는 미적분을 전혀 쓰지 않고 derivative를 추정합니다.

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와 대조. PyTorch에는 이 일을 직업으로 하는 사람들이 작성한 industrial autodiff engine이 있습니다.

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-bit float의 machine epsilon입니다. 두 engine은 동일한 산술을 수행하고 있습니다. numerical check를 주머니에 넣어 두세요. 새 layer의 backward pass를 debug할 때 쓰는 tool이며, 잘못된 gradient를 찾아낼 수 있게 해 주는 이유입니다.

같은 circuit, 다른 입력입니다. $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

$\tanh$ node를 가로지르는 gradient가 9,945배 줄었습니다. 그 위쪽에 있는 모든 것 — 실제 network라면 그 앞의 모든 layer — 은 사실상 아무것도 받지 못합니다. circuit을 지나는 두 경로는 조용해졌고, $\tanh$를 건너뛰는 직접 연결만 아직 signal을 운반합니다.

이것이 한 node 안의 vanishing gradient problem입니다. $\tanh$ layer를 40개 쌓고 이런 factor 40개를 곱하면 초기 layer들은 완전히 학습을 멈춥니다. 덧붙여, 여기서 축소판으로 볼 수 있는 skip connection의 논거이기도 합니다. nonlinearity를 우회한 경로만 살아남았기 때문입니다.

모든 _backward는 +=를 사용합니다. 이것은 맞습니다. 경로들이 합쳐지는 방식이기 때문입니다. 하지만 모두를 잡는 결과가 하나 있습니다. gradient는 backward() 호출들 사이에서도 누적됩니다. engine은 두 번째 호출이 같은 graph의 또 다른 경로가 아니라 새로운 training step이라는 사실을 알 방법이 없습니다.

그래서 training loop는 그것들을 지워야 합니다.

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()이고, 흔한 조언은 이를 잊으면 training이 망가진다는 것입니다. 그러니 그 두 줄을 지우고 얼마나 망가지는지 봅시다. 같은 seed, 같은 모든 조건, XOR 200 step입니다.

작은 learning rate에서는 buggy version이 모든 row에서 이깁니다. 올바른 version이 멈출 때 수렴합니다.

우연이 아니며, 이해할 가치가 있습니다. 이 bug가 잡기 어려운 이유를 설명하기 때문입니다. gradient를 절대 지우지 않으면 step $k$에서 parameter는 지금까지 계산된 모든 gradient의 합으로 update됩니다. loss가 대체로 같은 방향을 계속 가리키고 있으면 그 합은 꾸준히 커지고, effect는 learning rate가 저절로 증가하는 것처럼 보입니다. 올바른 알고리즘이 기어가는 $\eta = 0.05$에서는 폭주하는 step size가 정확히 해결책처럼 보입니다.

그다음 아래 세 row를 보세요. $\eta = 0.3$에서는 같은 메커니즘이 모델을 산산조각 냅니다. loss 8.0은 모델이 constant $\pm 1$로 collapse했을 때의 점수입니다. 네 개의 답이 모두 최대한 틀렸을 때 비용인 16의 절반입니다. 반면 올바른 version은 이제 깔끔하게 수렴합니다.

그러므로 정직한 말은 “항상 zero_grad를 호출하지 않으면 model이 train되지 않는다”가 아닙니다. 정확히는 이렇습니다. 그것이 없으면 더 이상 gradient descent를 실행하는 것이 아닙니다. 누구도 선택하지 않은 속도로 step size가 위로 drift하는 무언가를 실행하는 것입니다. 그리고 그것은 작동하는 것처럼 보일 것이고, 때로는 진짜보다 더 잘 작동하는 것처럼 보일 것입니다. 어느 순간 그렇지 않을 때까지 말입니다. 그때 여러분은 learning rate, initialisation, data를 탓하게 됩니다. 이것이 machine learning에서 최악의 bug가 띠는 모양입니다. crash하지 않고, 알고리즘을 가끔 더 높은 점수를 내는 다른 알고리즘으로 바꿔 버립니다.

engine이 끝나면 neural network는 코드가 거의 필요 없습니다. neuron은 dot product, bias, activation입니다. layer는 neuron의 list이고, network는 layer의 list입니다.

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 class는 이미 이 class들이 우연히 만들게 되는 무엇이든 differentiate하는 방법을 알고 있습니다. 그것을 먼저 작성한 이유가 바로 이것입니다. autodiff engine은 자신이 neural network에 쓰이고 있다는 사실을 모릅니다.

이제 Chapter 1의 문제입니다. 입력 둘, hidden unit 둘, 출력 하나, parameter 아홉 개입니다.

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

네 개 중 네 개입니다. 어떤 perceptron도 계산할 수 없는 함수 — Chapter 1에서 네 개의 부등식이 $b$가 양수이면서 동시에 음수여야 한다고 요구함으로써 증명했던 그 함수 — 가 자동으로 찾은 아홉 개의 숫자로 계산됩니다.

만족스러운 부분은 작동한다는 사실이 아닙니다. 어떻게 작동하는지 볼 수 있다는 점입니다. hidden unit이 두 개라서 intermediate representation이 평면 위의 점이고, 그냥 출력해 볼 수 있기 때문입니다.

loss 0.001241까지 training한 뒤, 각 입력이 hidden layer 뒤에서 어디에 놓이는지, 그리고 output neuron이 그것으로 무엇을 하는지는 다음과 같습니다.

첫 번째와 네 번째 row를 보세요. 입력 $(0,0)$와 $(1,1)$은 정사각형의 대각선 반대쪽 corner입니다. 이 문제에서 두 점이 가질 수 있는 가장 먼 거리입니다. 그런데 hidden layer는 그것들을 $(0.82, -0.85)$와 $(0.84, -0.86)$로 보냅니다. 거의 같은 점입니다. 이 layer는 평면을 접어서 거부되어야 할 두 corner가 서로 위에 놓이게 만들었고, 일단 같은 장소에 있으면 하나의 직선이 그것들을 다른 두 점과 분리합니다.

그리고 output neuron이 바로 그 직선입니다. 학습된 parameter는 $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$이므로 decision boundary는

입니다. 즉 직선입니다. Chapter 1의 그 perceptron과 같은 객체이고, 변하지 않았습니다. 그때는 XOR을 풀 수 없었고 지금도 풀 수 없습니다. 달라진 것은 더 이상 입력을 보고 있지 않다는 점입니다. 첫 번째 layer가 자신을 위해 만든 공간을 보고 있고, 그 공간에서는 문제가 linearly separable합니다.

이것이 learned representation입니다. 정확히 말할 가치가 있습니다. 이 표현은 이 과정의 나머지에서도, 이 분야의 나머지에서도 느슨하게 쓰이기 때문입니다. 그것은 compression도, summary도, 어떤 신비로운 의미의 embedding도 아닙니다. 설계된 것이 아니라 학습된 좌표 변화이며, 유일한 역할은 다음 layer의 일을 쉽게 만드는 것입니다.

여기에는 theorem이 하나 있고, 보통은 잘못 인용됩니다.

1989년 Cybenko와 1991년 Hornik은 hidden layer가 하나이고 적절한 activation function을 가진 feedforward network가 충분한 hidden unit이 주어지면 compact set 위의 임의의 continuous function을 원하는 정확도로 approximate할 수 있음을 증명했습니다.³⁴ 이는 진짜이며 중요한 결과입니다. architecture가 한계가 아니라는 뜻이기 때문입니다.

이제 무엇이 빠져 있는지 읽어 보세요. unit이 얼마나 필요한지는 말하지 않습니다. bound는 천문학적으로 클 수 있습니다. weight를 찾을 수 있다고 말하지도 않습니다. 존재를 주장할 뿐이고, random start에서의 gradient descent는 oracle이 아닙니다. 또한 보지 못한 data에서 어떻게 행동하는지에 대해서도 아무 말이 없습니다. 그것은 Chapter 6의 후반부입니다.

“존재한다”와 “찾을 수 있다” 사이의 간극은 학문적인 문제가 아닙니다. 같은 XOR 문제에서 random initialisation을 각각 50번, 1000 step씩 실행하고 hidden layer size만 바꾼 결과입니다.

최소 viable architecture에서는 네 번 중 한 번은 끝내 도달하지 못합니다. Chapter 3에서 one-dimensional surface 위에서 보여 준 local minimum과 정확히 같은, 더 내려갈 수 없는 configuration에 안착합니다. unit 하나를 추가하면 실패가 거의 사라집니다. network가 더 expressive해졌기 때문이 아닙니다. unit 두 개로 이미 충분하다는 것은 38번의 run이 증명합니다. extra dimension이 descent가 빠져나갈 방향을 더 많이 주기 때문입니다.

그리고 unit 여덟 개는 네 개보다 약간 나쁩니다. 고정된 learning rate와 step budget에서는 capacity가 많아진다고 단조롭게 좋아지지 않습니다. 멈춘 network의 해결책이 항상 더 큰 network라고 말하는 사람은 저 표의 중간에서 extrapolate하고 있는 것입니다.

이는 Chapter 1의 convergence theorem과 같은 lesson이며, Chapter 10에서 scaling law를 다룰 때도 그 챕터의 형태로 다시 나올 lesson입니다. loss에 대한 prediction은 여러분이 비용을 지불하는 capability에 대한 prediction이 아니며, 둘 사이의 거리가 engineering이 자리하는 곳입니다.

이제 training되는 network가 있습니다. 느낌만큼 큰 성취는 아닙니다. 이 network는 네 개의 예제로 training되고 같은 네 개로 측정되기 때문입니다.

같은 코드를 실제 dataset에 실행하면 새로운 문제들이 나타납니다. 그중 어느 것도 gradient에 관한 문제가 아닙니다. loss가 한동안 내려가다가 멈춥니다. 또는 training data에서는 내려가고 나머지 모든 것에서는 올라갑니다. 또는 첫 step부터 전혀 움직이지 않고, 원인은 초기 random weight의 범위로 밝혀집니다. 또는 어떤 unit의 입력이 세 번째 epoch의 모든 예제에서 음수로 drift했고, 그 이후 조용히 죽은 채 model capacity의 한 chunk를 함께 가져갔습니다.

이것들은 이국적인 failure가 아닙니다. 막 작성된 network의 정상 상태이며, 그 어느 것도 스스로를 알리지 않습니다. gradient는 정확합니다. PyTorch와 16자리 decimal place까지 확인했습니다. 그런데도 model은 여전히 학습하지 않습니다.

Chapter 6은 바로 그것에 관한 것입니다. initialisation, normalisation, overfitting과 regularisation, 그리고 무엇이든 바꾸기 전에 그중 어느 것이 일어나고 있는지 묻는 diagnostic habit입니다. 실행되는 network와 작동하는 network의 차이입니다.

이 챕터의 Value class는 Andrej Karpathy의 micrograd에서 직접 이어집니다. 그의 영상 The spelled-out intro to neural networks and backpropagation: building micrograd는 이 material을 다른 사람에게 또 다른 방식으로 설명받고 싶을 때 쓸 수 있는 최고의 세 시간입니다. 그의 2016년 글 Yes you should understand backprop은 직접 하나를 작성해야 하는 이유를 주장하며 Stanford CS224n의 assigned reading입니다. backpropagation에 관한 CS231n notes(cs231n.github.io/optimization-2)는 위에서 표로 정리한 flow pattern의 canonical treatment입니다. neural-network folklore이 아니라 graph 위의 calculus로서 수학을 보고 싶다면 Deisenroth, Faisal, Ong의 Mathematics for Machine Learning 5.6장이 유난히 명확합니다. 그리고 Baydin, Pearlmutter, Radul, Siskind의 survey Automatic Differentiation in Machine Learning: a Survey(arXiv:1502.05767)는 위에서 논의한 forward/reverse trade-off를 포함해 이 분야 전체에 대한 reference입니다.