Backpropagationをスクラッチから：エンジン、そしてネットワークへ

機械を作る前に、1つの問いを片づける必要があります。もし答えが逆なら、作るものなど何もないからです。

perceptronがXORで失敗したのは、1本の直線では4点を分離できないからでした。明らかな修正は、積み重ねることです。入力を1つのlinear layerに通し、さらに別のlinear layerに通す。これは役に立つでしょうか。

いいえ。証明は2行です。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です。 10個でも、1000個でも同じです。やはり1本の直線であり、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単位で完全に同一です。同じ算術を並べ替えただけだからです。

つまり、depthだけでは何も得られません。価値を生むのは、layerの間にnonlinear functionを置くことです。これこそがactivation functionが存在する理由のすべてです。生物学的な飾りでも、normalisationの小技でもありません。それがなければ、2つ目のlayerはただの装飾です。

次は数学です。とはいえ、すでに知っている1つのruleを、少し見慣れない場所に適用するだけです。

1変数のchain ruleは、$L$が$c$に依存し、$c$が$x$に依存するなら、$\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$だと言います。chainに沿ってderivativeは掛け合わされます。

ここで重要なのは、あるvariableが下流の複数のpathへ流れ込むと何が起きるかです。$x$が$a$を通じて$L$に影響し、さらに$b$を通じても影響するなら、それぞれの寄与は足し合わされます。

pathに沿って掛け、pathをまたいで足す。これがbackpropagationのすべてです。この章の残りに出てくる実装上の細部はすべて、コード内の+=も、初めてtraining loopを書く人が必ずつまずくzero_grad()呼び出しも含めて、その2語目の直接の帰結です。

$x = 0.5$と$y = 1.4$を持つ、5つのoperationからなる具体的なcircuitを考えます。

$x$が3回現れることに注意してください。$a$の中、$b$の中、そして$L$の中に直接現れます。$\frac{dL}{dL} = 1$から始めて、右から左へ、紙の上でbackward passを行います。

この数を覚えておいてください。数ページ後、プログラムが、ここまでのどれも教えられずにこれを出します。

これをプログラム可能にする洞察は、上のすべてのstepがlocalだったことです。multiplication nodeを通じてgradientを押し戻すには、入力gradientと、保存された2つの入力値だけが必要でした。circuitの残りについては何もいりません。各operationは、自分自身をどう微分するかを知っています。

そこで、自分を何が生み出したかを覚えているnumberを作ります。

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

4つのfieldがあります。dataは値です。gradは$\frac{\partial L}{\partial \text{self}}$をaccumulateします。_prevは、この値が計算される元になったValueたちのset、つまりgraphのedgeです。そして_backwardは各operationがinstallするclosureです。このnodeのgradientを、1step戻して入力へ押し戻す方法を知っています。

どのoperatorも同じ形です。出力を計算し、parentを記録し、local ruleをinstallします。

    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

4つの_backward bodyをtableとして読むと、紙の上で導いたflow patternがそのままそこにあります。

どれも+=を使い、=は決して使いません。これが「pathをまたいで足す」ruleをcode化したものです。2つのconsumerへ流れ込むnodeは2回呼ばれ、その2つの寄与は自然に足し合わされます。

次に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がすでに完成していることが保証されます。下流のすべてのconsumerがすでに寄与しているからです。順序を間違えると、未完成のgradientを後ろへ押し戻すことになり、error messageなしで間違った答えが出ます。

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については何も教えられていません。

独立したcheckを2つ行います。「自分で導いたものと一致した」は、導いたのも同じ人なら弱いtestだからです。

Numerical differentiation。 inputを少し動かして測ります。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との比較。 これは、この仕事を本職にしている人たちが書いた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です。2つのengineは同一の算術を実行しています。numerical checkを手元に置いておいてください。新しいlayerのbackward passをdebugする道具であり、間違ったgradientを見つけられる理由そのものです。

同じcircuit、異なるinputです。$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分の1に落ちました。その上流にあるすべて、実際のnetworkならその前のすべてのlayerは、実質的に何も受け取りません。circuitを通る2つのpathは沈黙しました。$\tanh$をskipする直接接続だけが、まだsignalを運んでいます。

これがvanishing gradient problemを1つのnodeで見たものです。$\tanh$のlayerを40個積み、そのようなfactorを40個掛け合わせれば、初期のlayerは完全に学習を止めます。ついでに言えば、これはskip connectionの主張をミニチュアで見せてもいます。nonlinearityを迂回したpathだけが生き残ったからです。

すべての_backwardは+=を使います。それは正しいことです。pathがsumされる仕組みだからです。しかし、その結果として誰もが引っかかることが起きます。gradientはbackward()へのcallをまたいでもaccumulateします。engineには、2回目のcallが同じgraph内の別pathではなく、新しいtraining stepであることは分かりません。

だからtraining loopでは、それをclearする必要があります。

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が壊れる、というものです。ではその2行を削除して、どれほど壊れるか見てみましょう。同じseed、同じすべて、XORを200stepです。

小さいlearning rateでは、bugのあるversionが全行で勝っています。正しいversionが停滞するところでconvergeします。

これは偶然ではなく、理解する価値があります。このbugが見つけにくい理由を説明してくれるからです。gradientをclearしない場合、step $k$でのparameter更新は、それまでに計算されたすべてのgradientの合計になります。lossがおおむね同じ向きを指し続けるなら、その合計は着実に大きくなり、learning rateが勝手に増えていくのと同じ効果になります。正しいalgorithmが這うように進む$\eta = 0.05$では、暴走するstep sizeがまさに修正のように見えます。

次に下の3行を見てください。$\eta = 0.3$では、同じ仕組みがmodelを吹き飛ばします。loss 8.0は、modelがconstant $\pm 1$にcollapseしたときのscoreです。4つの答えが最大限に間違ったときの16の半分です。一方で、正しいversionはここで綺麗にconvergeします。

したがって正直な言い方は、「必ずzero_gradを呼ばないとmodelはtrainしない」ではありません。こうです。それなしでは、もうgradient descentを実行していません。 誰も選んでいない速度でstep sizeが上向きにdriftする何かを実行しています。そしてそれは、うまくいくように見え、ときには本物よりよく見えることさえあります。うまくいかなくなるその瞬間までは。そのときあなたはlearning rate、initialisation、dataのどれかを責めるでしょう。machine learningで最悪のbugはこういう形をしています。crashしません。algorithmを別のalgorithmに変え、しかもたまにより高いscoreを出すのです。

engineができれば、neural networkはごくわずかなcodeです。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がありません。1行もありません。Value classは、これらのclassがたまたま構築するものを微分する方法をすでに知っています。これこそ、先にそれを書いた理由です。autodiff engineは、自分がneural networkに使われていることを知りません。

では第1章の問題です。2入力、2 hidden unit、1出力、9 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

4つ中4つです。perceptronには計算できない関数、第1章で$b$が正であり負でもなければならないという4つの不等式によって証明した関数が、自動的に見つかった9つの数によって計算されました。

満足すべきところは、動いたことではありません。どう動いたかを見られることです。hidden unitが2つなら、intermediate representationは平面上の点であり、ただprintできます。

loss 0.001241までtrainしたとき、各inputがhidden layerの後にどこへ着地し、output neuronがそれに何をするかは次の通りです。

1行目と4行目を見てください。input $(0,0)$と$(1,1)$は正方形の対角のcornerで、この問題で2点が取り得る最大距離だけ離れています。それなのにhidden layerは、それらを$(0.82, -0.85)$と$(0.84, -0.86)$へmapします。ほとんど同じ点です。 layerは平面を折りたたみ、rejectされる2つのcornerを互いの上に着地させました。いったん同じ場所に来れば、1本の直線でそれらを他の2つから分離できます。

そしてoutput neuronは、まさにその直線です。学習されたparameterは$\mathbf{w} = (-3.1153,\ +3.0893)$、$b = +2.7697$なので、そのdecision boundaryは

というstraight lineです。第1章と同じperceptronであり、同じ物体で、何も変わっていません。当時XORを解けなかったし、今もそのままでは解けません。変わったのは、もはやinputを見ていないことです。1つ目のlayerが作ったspaceを見ており、そのspaceでは問題がlinearly separableになっています。

これがlearned representationです。このphraseはこのコースの残りでも、この分野全体でもゆるく使われるので、正確にしておく価値があります。これはcompressionでもsummaryでも、神秘的な意味でのembeddingでもありません。設計されたのではなく学習された座標変換であり、その唯一の仕事は、次のlayerの仕事を簡単にすることです。

ここには定理があります。そしてたいてい、よくない引用をされます。

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上での振る舞いについては何も言っていません。これは第6章の後半です。

「存在する」と「見つけられる」の間のgapは、学術的な細部ではありません。同じXOR問題で、各50回のrandom initialisation、1000 step、hidden layer sizeだけを変えた結果がこちらです。

最小限のviable architectureでは、4回に1回は到達しません。第3章で1次元surface上に示したlocal minimumそのもの、つまり抜け出せないconfigurationに落ち着きます。1 unit足すと失敗はほぼ消えます。networkの表現力が増したからではありません（2 unitで十分です。38回のrunがそれを証明しています）。余分なdimensionが、descentに抜け道となる方向をより多く与えるからです。

そして8 unitは4 unitよりわずかに悪くなります。固定されたlearning rateとstep budgetでは、capacityを増やせば単調によくなるわけではありません。詰まったnetworkの修正は常に大きなnetworkだと言う人は、このtableの真ん中から外挿しているだけです。

これは第1章のconvergence theoremと同じlessonです。そして第10章のscaling lawでも、その章の形で同じlessonになります。lossの予測は、あなたが対価を払っているcapabilityの予測ではありません。その2つの距離にengineeringがあります。

これで、trainするnetworkを手に入れました。これは感じるほど大きな達成ではありません。あなたのnetworkは4つのexampleでtrainされ、同じ4つで測られているからです。

同じcodeを実際のdatasetで走らせると、新しい問題が現れます。そのどれもgradientそのものの問題ではありません。lossがしばらく下がってから止まる。あるいはtraining dataでは下がり、それ以外では上がる。あるいは最初のstepからまったく動かず、原因は初期random weightのrangeだったと判明する。あるいは3 epoch目に、あるunitのinputがすべてのexampleで負にdriftし、それ以来ずっと静かにdeadで、model capacityの一部を道連れにしている。

これらは珍しい失敗ではありません。書いたばかりのnetworkの通常状態です。そして、そのどれも自分から名乗り出ません。gradientは正しい。PyTorchと16桁まで照合しました。それでもmodelは学習しません。

第6章はその話です。initialisation、normalisation、overfitting、regularisation、そして何かを変える前にどれが起きているのかを問う診断の習慣についてです。走るnetworkと、働くnetworkの違いです。

この章のValue classは、Andrej Karpathyのmicrogradを直接の源流としています。彼のvideo The spelled-out intro to neural networks and backpropagation: building micrograd は、この題材を別の人からもう一度説明してもらいたいなら、費やす価値のある最高の3時間です。2016年のpost Yes you should understand backprop は、自分で1つ書くべき理由を論じており、StanfordのCS224nの指定読書になっています。backpropagationに関するCS231n notes（cs231n.github.io/optimization-2）は、上でtable化したflow patternのcanonicalな解説です。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です。