ニューラルネットワークと逆伝播：連鎖律を計算グラフの上で逆向きに走らせる

0. この記事の要点

ニューラルネットワークは、数百万、ときには数千億もの調整つまみ（パラメータ）を持つ大きな計算式です。学習とは、出力の誤りが減る方向へ、すべてのつまみを少しずつ回すことです。そのためには「各つまみを少し回すと誤りがどれだけ変わるか」を全部知る必要があります。つまみを 1 つずつ試していては時間が足りません。この記事では、それを順伝播 1 回分ほどの手間でまとめて求める逆伝播の仕組みと、それが正しい理由を学びます。

• ニューラルネットワークとは、アフィン変換（一次式 $W\boldsymbol{z}+\boldsymbol{b}$ の形の変換）$\boldsymbol{z} \mapsto W\boldsymbol{z} + \boldsymbol{b}$ と成分ごとの非線形関数 $\sigma$ を交互に合成しただけの関数です。損失もその先に合成されるので、全体は 1 つの合成関数になります。
• 合成関数の微分は、ヤコビ行列の積 $J_{\mathcal{L}}J_{L}\cdots J_{1}$ です。逆伝播とは、この積を左から掛けるという、ただそれだけの計算順序の指定です。
• 出力がスカラーのとき、左端は行ベクトルです。行ベクトルに行列を掛け続ければ計算はずっと「ベクトル×行列」で済み、右から掛ける場合の「行列×行列」より、層の幅を $n$ として $n$ 倍ほど安くなります。
• 一般の計算グラフに対して、随伴変数 $\bar v_k$ の漸化式 $\bar v_k = \sum_{m} \bar v_m \,\partial \varphi_m/\partial v_k$ が本当に偏微分を与えることを証明します（定理 4.3）。随伴変数とは、出力の変化率を出力側から順に集めていく量のことです。多層ネットワークの逆伝播はその特別な場合です。
• 逆伝播 1 回の計算量は順伝播 1 回の定数倍です。パラメータ数が $P$ のとき、数値微分なら $P$ に比例する回数の順伝播が要るので、実用規模では 10 万倍以上の差がつきます。

この記事で使う事前知識

• ヤコビ行列: 多変数の写像を各変数で偏微分して並べた行列。1 変数の導関数の多変数版にあたる。第 2 節で定義を確認します。
• 全微分可能: 点の近くで写像を一次式でよく近似できる、という性質。→ 全微分可能性の定義
• 勾配降下法: 勾配の逆向きにパラメータを少しずつ動かして、損失を減らす方法。→ 勾配降下法
• 方向微分: ある方向に進んだときの関数の変化率。→ 方向微分
• シグモイド関数: 実数を 0 と 1 の間に押し込む滑らかな関数 $1/(1+e^{-t})$。→ シグモイド関数

1. 動機：連鎖律を「知っている」ことと「安く計算できる」ことは別

勾配降下法では、パラメータ $\boldsymbol{\theta}$ を $\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\, \nabla E(\boldsymbol{\theta})$ で更新しました（定義 4.1［勾配降下法］）。この式は勾配 $\nabla E(\boldsymbol{\theta})$ が手に入ることを前提にしています。線形回帰やロジスティック回帰では、勾配を紙の上で 1 行に書き下せました（定理 5.1［ロジスティック回帰］）。ところが層を重ねたニューラルネットワークでは、$E$ を $\boldsymbol{\theta}$ の式として展開すると人間が読めない大きさになります。しかもパラメータ数 $P$ は、小さなモデルでも $10^5$、現代の大規模モデルでは $10^{11}$ を超えます。

一番素朴な手は差分近似です。$i$ 番目のパラメータについて

$$\frac{\partial E}{\partial \theta_i} \approx \frac{E(\boldsymbol{\theta} + h\boldsymbol{e}_i) - E(\boldsymbol{\theta} - h\boldsymbol{e}_i)}{2h}$$

と計算すれば、微分の公式を一切知らなくても勾配が得られます。しかしこれには $E$ の評価が $2P$ 回必要です。$P = 10^5$ でも 20 万回、$P = 10^{11}$ なら話になりません。さらに、差分近似には打ち切り誤差と丸め誤差のせめぎ合いがあり、精度も限られます（演習 9.4）。

一方、ニューラルネットワークは合成関数です。合成関数の微分法（連鎖律）を使えば、微分は原理的には求まります。ではなぜ「逆伝播」という名前のアルゴリズムがわざわざ必要なのでしょうか。答えは計算の順序にあります。層が $L$ 個あるとき、連鎖律は

$$\nabla E^{\mathsf{T}} = J_{\mathcal{L}}\, J_{L}\, J_{L-1} \cdots J_{1}$$

というヤコビ行列の積を与えます（$J_{\mathcal{L}}$ は損失のヤコビ行列で $1 \times n_L$、$J_k$ は第 $k$ 層のヤコビ行列で $n_k \times n_{k-1}$）。行列の積は結合法則を満たすので、どの順で掛けても答えは同じです。しかしコストは同じではありません。すべての層幅を $n$ とすると、

掛ける順序	途中の形	1 回の積のコスト	全体
右から（$J_2J_1$ から）	$n \times n$ 行列	$n^3$	$O(Ln^3)$
左から（$J_{\mathcal{L}} J_L$ から）	$1 \times n$ 行ベクトル	$n^2$	$O(Ln^2)$

逆伝播とは、この表の下の行、すなわち左から掛けるという選択のことです。出力がスカラー（損失は 1 つの実数）だから左端が行ベクトルになり、行ベクトルのまま右へ右へと押し込んでいける。この非対称性が、深層学習を計算可能にしている唯一といってよい仕掛けです。

歴史的には、この「逆向きの微分」は 1970 年に Linnainmaa が丸め誤差の解析のために定式化し（学位論文。雑誌論文は 1976 年で、[1] はこちら）、1974 年に Werbos が学習アルゴリズムとして提案し、1986 年の Rumelhart・Hinton・Williams の論文（[2]）で機械学習の標準手法として広まりました。計算量の一般論としては、Baur と Strassen が 1983 年に「勾配の計算コストは関数値の計算コストの定数倍で抑えられる」ことを証明しています（[3]）。

ノート

この記事で「逆伝播」と呼ぶものは、自動微分（algorithmic differentiation）のリバースモードをニューラルネットワークに適用したものです。PyTorch や JAX が内部でやっているのは、まさに 定理 4.3 の漸化式です。

2. 準備：記号と、ネットワークの定式化

記号を固定します。ベクトルはすべて列ベクトルとし、$\boldsymbol{u} \in \mathbb{R}^n$ に対して

• $\nabla_{\boldsymbol{u}} E := \left(\dfrac{\partial E}{\partial u_1}, \ldots, \dfrac{\partial E}{\partial u_n}\right)^{\mathsf{T}} \in \mathbb{R}^n$（勾配は列ベクトル）
• $\boldsymbol{f} : \mathbb{R}^n \to \mathbb{R}^m$ のヤコビ行列は $\big(J_{\boldsymbol{f}}(\boldsymbol{x})\big)_{ij} = \dfrac{\partial f_i}{\partial x_j}(\boldsymbol{x}) \in \mathbb{R}^{m \times n}$
• アダマール積（成分ごとの積）を $(\boldsymbol{u} \odot \boldsymbol{v})_i = u_i v_i$ と書く
• 1 変数関数 $\sigma$ をベクトルに施すときは成分ごととし、$\sigma(\boldsymbol{z}) := (\sigma(z_1), \ldots, \sigma(z_n))^{\mathsf{T}}$、$\sigma'(\boldsymbol{z}) := (\sigma'(z_1), \ldots, \sigma'(z_n))^{\mathsf{T}}$ と書く

とします。

定義 2.1（多層パーセプトロン）↗

$L \ge 1$、$n_0, n_1, \ldots, n_L \in \mathbb{N}$ とする。各 $\ell = 1, \ldots, L$ について行列 $W^{(\ell)} \in \mathbb{R}^{n_\ell \times n_{\ell-1}}$、ベクトル $\boldsymbol{b}^{(\ell)} \in \mathbb{R}^{n_\ell}$、および $C^1$ 級の 1 変数関数 $\sigma^{(\ell)} : \mathbb{R} \to \mathbb{R}$（活性化関数）が与えられているとする。入力 $\boldsymbol{x} \in \mathbb{R}^{n_0}$ に対し $\boldsymbol{a}^{(0)} := \boldsymbol{x}$ と置き、$\ell = 1, \ldots, L$ の順に

$$\boldsymbol{z}^{(\ell)} := W^{(\ell)} \boldsymbol{a}^{(\ell-1)} + \boldsymbol{b}^{(\ell)}, \qquad \boldsymbol{a}^{(\ell)} := \sigma^{(\ell)}\!\left(\boldsymbol{z}^{(\ell)}\right)$$

で定まる $\boldsymbol{a}^{(L)} \in \mathbb{R}^{n_L}$ を出力とする写像を、$L$ 層の多層パーセプトロンという。$\boldsymbol{z}^{(\ell)}$ を第 $\ell$ 層の前活性、$\boldsymbol{a}^{(\ell)}$ を活性と呼ぶ。パラメータの全体を $\boldsymbol{\theta} = \big(W^{(1)}, \boldsymbol{b}^{(1)}, \ldots, W^{(L)}, \boldsymbol{b}^{(L)}\big)$ と書く。

さらに正解 $\boldsymbol{y}$ に対する $C^1$ 級の損失関数 $\mathcal{L}(\cdot, \boldsymbol{y}) : \mathbb{R}^{n_L} \to \mathbb{R}$ を与え、$E := \mathcal{L}\!\left(\boldsymbol{a}^{(L)}, \boldsymbol{y}\right)$ と置く。

活性化関数 $\sigma^{(\ell)}$ を恒等写像にしてしまうと、ネットワーク全体は $W^{(L)}\cdots W^{(1)}\boldsymbol{x} + (\text{定数})$ というアフィン写像に潰れ、1 層と表現力が変わりません。層を重ねる意味は非線形性にあります。逆にいえば、$\sigma$ が入るせいで $E$ を $\boldsymbol{\theta}$ の閉じた式に展開できなくなり、連鎖律が必要になるのです。

例 2.2（ニューロン 1 個の場合の手計算）

$n_0 = n_1 = 1$、$L = 1$、$\sigma$ をシグモイド関数 $\sigma(t) = 1/(1+e^{-t})$、損失を $\ell(a, y) = \tfrac12 (a-y)^2$ とします。パラメータは実数 $w, b$ の 2 つで、

$$z = wx + b, \qquad a = \sigma(z), \qquad E = \tfrac12 (a - y)^2 .$$

1 変数の連鎖律（定理 7.2［導関数の定義と基本的な微分法］）を 2 回使います。まず $\dfrac{\partial E}{\partial a} = a - y$、次に $\dfrac{da}{dz} = \sigma'(z)$、最後に $\dfrac{\partial z}{\partial w} = x$、$\dfrac{\partial z}{\partial b} = 1$ です。したがって

$$\frac{\partial E}{\partial w} = (a-y)\,\sigma'(z)\, x, \qquad \frac{\partial E}{\partial b} = (a-y)\,\sigma'(z).$$

ここで $\delta := (a-y)\sigma'(z) = \dfrac{\partial E}{\partial z}$ と置くと、$\partial E/\partial w = \delta x$、$\partial E/\partial b = \delta$ と書けます。つまり「前活性についての微分 $\delta$」さえ手に入れば、パラメータの微分は $\delta$ に入力を掛けるだけです。この $\delta$ が、以下で $\boldsymbol{\delta}^{(\ell)}$ として一般化されるものです。

なお $\sigma' = \sigma(1-\sigma)$ なので（演習 9.1）、$x = 2$、$w = 1$、$b = -1$、$y = 0$ なら $z = 1$、$a = \sigma(1) = 0.7311$、$\sigma'(z) = 0.7311 \times 0.2689 = 0.1966$ となり、$\delta = 0.7311 \times 0.1966 = 0.1437$、$\partial E/\partial w = 0.2875$、$\partial E/\partial b = 0.1437$ です。

3. 多変数の連鎖律

逆伝播のすべては、次の定理から出ます。仮定を省かずに述べます。

定理 3.1（連鎖律）✓

$U \subset \mathbb{R}^n$、$V \subset \mathbb{R}^m$ を開集合とし、写像 $\boldsymbol{g} : U \to \mathbb{R}^m$ が $\boldsymbol{g}(U) \subset V$ を満たすとする。$\boldsymbol{g}$ が点 $\boldsymbol{a} \in U$ で全微分可能、$\boldsymbol{f} : V \to \mathbb{R}^p$ が点 $\boldsymbol{b} := \boldsymbol{g}(\boldsymbol{a})$ で全微分可能とする。このとき合成 $\boldsymbol{f} \circ \boldsymbol{g} : U \to \mathbb{R}^p$ は $\boldsymbol{a}$ で全微分可能で

$$J_{\boldsymbol{f} \circ \boldsymbol{g}}(\boldsymbol{a}) = J_{\boldsymbol{f}}(\boldsymbol{b})\, J_{\boldsymbol{g}}(\boldsymbol{a}) .$$

成分で書けば、$i = 1,\ldots,p$、$j = 1,\ldots,n$ について

$$\frac{\partial (f \circ g)_i}{\partial x_j}(\boldsymbol{a}) = \sum_{k=1}^{m} \frac{\partial f_i}{\partial y_k}(\boldsymbol{b}) \, \frac{\partial g_k}{\partial x_j}(\boldsymbol{a}) .$$

次の証明は、「合成した関数の誤差は、内側の誤差と外側の誤差を足したものにすぎず、どちらも $\boldsymbol{h}$ より速く $0$ に近づく」ことを、$\varepsilon$ を使って丁寧に確かめるものです。イプシロンの議論に慣れていなければ、結論の式だけ受け取って次の節へ進んでも、以降は読めます。

証明（定理 3.1）

$A := J_{\boldsymbol{f}}(\boldsymbol{b})$、$B := J_{\boldsymbol{g}}(\boldsymbol{a})$ と置きます。行列の作用素ノルムを $\|A\| := \sup_{\|\boldsymbol{h}\|=1}\|A\boldsymbol{h}\|$ とすると、$\|A\boldsymbol{h}\| \le \|A\|\,\|\boldsymbol{h}\|$ が成り立ちます。

$\boldsymbol{g}$ の $\boldsymbol{a}$ における全微分可能性（定義 9.1［多変数関数の微分と偏微分］）とは、$\boldsymbol{h}$ が十分小さいとき

$$\boldsymbol{g}(\boldsymbol{a}+\boldsymbol{h}) = \boldsymbol{b} + B\boldsymbol{h} + \boldsymbol{r}(\boldsymbol{h}), \qquad \frac{\|\boldsymbol{r}(\boldsymbol{h})\|}{\|\boldsymbol{h}\|} \xrightarrow[\boldsymbol{h} \to \boldsymbol{0}]{} 0$$

と書けることです。同様に $\boldsymbol{f}$ について、$\boldsymbol{k}$ が十分小さいとき

$$\boldsymbol{f}(\boldsymbol{b}+\boldsymbol{k}) = \boldsymbol{f}(\boldsymbol{b}) + A\boldsymbol{k} + \boldsymbol{s}(\boldsymbol{k}), \qquad \frac{\|\boldsymbol{s}(\boldsymbol{k})\|}{\|\boldsymbol{k}\|} \xrightarrow[\boldsymbol{k} \to \boldsymbol{0}]{} 0$$

であり、$\boldsymbol{s}(\boldsymbol{0}) = \boldsymbol{0}$ と定めておきます。$U$ が開集合なので $\|\boldsymbol{h}\|$ が小さければ $\boldsymbol{a}+\boldsymbol{h} \in U$ であり、$\boldsymbol{k}(\boldsymbol{h}) := B\boldsymbol{h} + \boldsymbol{r}(\boldsymbol{h}) = \boldsymbol{g}(\boldsymbol{a}+\boldsymbol{h}) - \boldsymbol{b}$ と置けます。2 つの展開を繋ぐと

$$\boldsymbol{f}(\boldsymbol{g}(\boldsymbol{a}+\boldsymbol{h})) = \boldsymbol{f}(\boldsymbol{b}) + A\big(B\boldsymbol{h} + \boldsymbol{r}(\boldsymbol{h})\big) + \boldsymbol{s}(\boldsymbol{k}(\boldsymbol{h})) = \boldsymbol{f}(\boldsymbol{b}) + AB\boldsymbol{h} + \underbrace{A\boldsymbol{r}(\boldsymbol{h}) + \boldsymbol{s}(\boldsymbol{k}(\boldsymbol{h}))}_{=: \boldsymbol{\rho}(\boldsymbol{h})} .$$

あとは $\|\boldsymbol{\rho}(\boldsymbol{h})\| / \|\boldsymbol{h}\| \to 0$ を示せば、定義より $\boldsymbol{f}\circ\boldsymbol{g}$ は $\boldsymbol{a}$ で全微分可能でヤコビ行列が $AB$ だと結論できます。

第 1 項は $\|A\boldsymbol{r}(\boldsymbol{h})\| \le \|A\|\,\|\boldsymbol{r}(\boldsymbol{h})\|$ であり、$\|\boldsymbol{r}(\boldsymbol{h})\|/\|\boldsymbol{h}\| \to 0$ なので $\|A\boldsymbol{r}(\boldsymbol{h})\|/\|\boldsymbol{h}\| \to 0$ です。

第 2 項を評価します。まず $\|\boldsymbol{r}(\boldsymbol{h})\| \le \|\boldsymbol{h}\|$ となるほど $\|\boldsymbol{h}\|$ を小さく取れば

$$\|\boldsymbol{k}(\boldsymbol{h})\| \le \|B\|\,\|\boldsymbol{h}\| + \|\boldsymbol{r}(\boldsymbol{h})\| \le (\|B\|+1)\,\|\boldsymbol{h}\|$$

です。$C := \|B\|+1 > 0$ と置きます。任意に $\varepsilon > 0$ を取ります。$\boldsymbol{s}$ の性質から、ある $\eta > 0$ があって $\|\boldsymbol{k}\| < \eta$ ならば $\|\boldsymbol{s}(\boldsymbol{k})\| \le (\varepsilon/C)\|\boldsymbol{k}\|$ です（$\boldsymbol{k}=\boldsymbol{0}$ のときも $\boldsymbol{s}(\boldsymbol{0})=\boldsymbol{0}$ より成立）。そこで $\|\boldsymbol{h}\| < \eta / C$ かつ上の評価が使えるほど $\|\boldsymbol{h}\|$ を小さく取れば $\|\boldsymbol{k}(\boldsymbol{h})\| \le C\|\boldsymbol{h}\| < \eta$ となり、

$$\|\boldsymbol{s}(\boldsymbol{k}(\boldsymbol{h}))\| \le \frac{\varepsilon}{C}\,\|\boldsymbol{k}(\boldsymbol{h})\| \le \frac{\varepsilon}{C}\cdot C\|\boldsymbol{h}\| = \varepsilon\|\boldsymbol{h}\|$$

が従います。$\varepsilon$ は任意だったので $\|\boldsymbol{s}(\boldsymbol{k}(\boldsymbol{h}))\|/\|\boldsymbol{h}\| \to 0$ です。以上で $\|\boldsymbol{\rho}(\boldsymbol{h})\|/\|\boldsymbol{h}\| \to 0$ が示されました。成分表示は行列積 $AB$ の $(i,j)$ 成分を書き下したものです。

∎

注意 3.2

出力がスカラー（$p = 1$）のとき、定理 3.1 のヤコビ行列は $1 \times n$ の行ベクトル、すなわち勾配の転置です。両辺を転置すると

$$\nabla_{\boldsymbol{x}} (f \circ \boldsymbol{g}) = J_{\boldsymbol{g}}(\boldsymbol{a})^{\mathsf{T}} \, \nabla_{\boldsymbol{y}} f$$

となります。勾配は、ヤコビ行列の転置を掛けることで、出力側から入力側へ運ばれる。この 1 行が逆伝播の正体です。実装では $J$ を明示的に作らず、「ベクトルにヤコビ行列の転置を掛ける」操作（vector-Jacobian product）だけを層ごとに用意します。

4. 計算グラフと随伴変数

ネットワークを層の列として見る代わりに、スカラー変数の有向非巡回グラフとして見ると、逆伝播の正しさをいちどきに証明できます。分岐（同じ値が複数の場所で使われる）や重み共有も、この見方なら追加の議論なしに扱えます。

定義 4.1（計算グラフ）↗

$1 \le n < N$ とする。変数 $v_1, \ldots, v_N$ に対し、各 $k = n+1, \ldots, N$ について空でない親集合 $\mathrm{Pa}(k) \subset \{1, \ldots, k-1\}$ と、$\mathbb{R}^{|\mathrm{Pa}(k)|}$ の開集合上で定義された $C^1$ 級関数 $\varphi_k$ が与えられているとする。入力 $(v_1, \ldots, v_n)$ を与えると、$k = n+1, \ldots, N$ の順に

$$v_k = \varphi_k\big((v_j)_{j \in \mathrm{Pa}(k)}\big)$$

によってすべての $v_k$ が定まる。この組を計算グラフと呼び、$v_N$ を出力（スカラー）と呼ぶ。入力から出力を返す写像を $F(v_1, \ldots, v_n) := v_N$ と書く。

添字が親より大きいという条件 $\mathrm{Pa}(k) \subset \{1,\ldots,k-1\}$ は、グラフに閉路がなく、$1, 2, \ldots, N$ という順番がトポロジカル順序（どの変数も、その材料となる変数より後に並ぶ順番）になっていることを意味します。実際のプログラムは演算を 1 つずつ順に実行するので、この条件は自動的に満たされます。

2 層ネットワークの計算グラフ。パラメータも入力ノードとして扱う。損失 E が唯一の出力ノード。

次の随伴変数 $\bar v_k$ は、一言でいえば「$v_k$ を少し動かしたとき、出力 $v_N$ がどれだけ動くか」を表す量です。出力から入力へ向かって、後ろの変数の値を使って前の変数の値を決めていくので、添字の大きい順に定めます。

定義 4.2（随伴変数）↗

定義 4.1 の計算グラフと、入力の値 $(v_1,\ldots,v_n)$ を 1 つ固定する。随伴変数 $\bar v_N, \bar v_{N-1}, \ldots, \bar v_1$ を、添字の大きい順に

$$\bar v_N := 1, \qquad \bar v_k := \sum_{m \,:\, k \in \mathrm{Pa}(m)} \bar v_m \, \frac{\partial \varphi_m}{\partial v_k} \quad (k = N-1, \ldots, 1)$$

で定める。ここで偏微分は、$\varphi_m$ の引数のうち $v_k$ に対応するものについての偏微分を、固定した入力から定まる値の組で評価したものとする。

和が意味を持つことを確かめておきます。$k \in \mathrm{Pa}(m)$ ならば $k < m$ ですから、$\bar v_k$ の右辺に現れる $\bar v_m$ はすべて添字が $k$ より大きく、すでに計算済みです。また $k$ が誰の親でもなければ和は空で $\bar v_k = 0$ になります。

定理 4.3（逆伝播（リバースモード自動微分）の正当性）✓

定義 4.1 の計算グラフを考え、入力の値 $(v_1,\ldots,v_n)$ を、以降に現れるすべての $\varphi_k$ の評価がその定義域の内点で行われるように固定する。このとき 定義 4.2 の随伴変数について

$$\bar v_j = \frac{\partial F}{\partial v_j}(v_1, \ldots, v_n) \qquad (j = 1, \ldots, n)$$

が成り立つ。

証明の方針は次のとおりです。「変数を $k$ 個まで計算した途中の状態から、出力までを計算する関数」$\Phi_k$ を考えます。$k$ を 1 つ減らすたびに連鎖律を 1 回使って偏微分の関係式を作り、それを $k$ について足し合わせると、途中の項が打ち消し合って随伴変数の漸化式だけが残ります。

証明（定理 4.3）

途中状態から出力への写像を用意します。 各 $k = n, n+1, \ldots, N$ に対し、$\Phi_k : \mathbb{R}^k \supset D_k \to \mathbb{R}$ を次で定めます。引数 $(u_1, \ldots, u_k)$ を受け取り、$m = k+1, \ldots, N$ の順に $u_m := \varphi_m\big((u_j)_{j \in \mathrm{Pa}(m)}\big)$ を計算し、$u_N$ を返す。定義域 $D_k$ は、この計算が定義される点の集合の、着目点を含む開近傍とします。各 $\varphi_m$ は $C^1$ 級で、$C^1$ 級写像の合成は 定理 3.1 より $C^1$ 級なので、$\Phi_k$ も着目点の近傍で $C^1$ 級です。

定義から $\Phi_n = F$、また $\Phi_N(u_1,\ldots,u_N) = u_N$ です。以下、偏微分はすべて着目点 $(v_1, \ldots, v_k)$ で評価するものとし、

$$g_k^{(j)} := \frac{\partial \Phi_k}{\partial u_j}(v_1, \ldots, v_k) \qquad (j \le k)$$

と書きます。$\Phi_N(u_1,\ldots,u_N)=u_N$ から、ただちに

$$g_N^{(N)} = 1, \qquad g_N^{(j)} = 0 \quad (j < N)$$

がわかります。以下これを基点の式と呼びます。

1 段だけ状態を減らす関係式。 $k = n+1, \ldots, N$ を固定します。$\Phi_{k-1}$ の計算手順の最初の一歩は $u_k = \varphi_k\big((u_j)_{j\in\mathrm{Pa}(k)}\big)$ を作ることで、その後は $\Phi_k$ の手順とまったく同じです。よって $(u_1,\ldots,u_{k-1})$ が着目点の近くにあるとき

$$\Phi_{k-1}(u_1, \ldots, u_{k-1}) = \Phi_k\Big(u_1, \ldots, u_{k-1}, \; \varphi_k\big((u_j)_{j \in \mathrm{Pa}(k)}\big)\Big)$$

が恒等的に成り立ちます。右辺を $\boldsymbol{u} \mapsto (u_1,\ldots,u_{k-1},\varphi_k(\cdots))$ と $\Phi_k$ の合成と見て 定理 3.1 を適用すると、$j \le k-1$ について

$$g_{k-1}^{(j)} = g_k^{(j)} + g_k^{(k)} \, \frac{\partial \varphi_k}{\partial v_j}$$

を得ます。以下これを1 段落としの式と呼びます。ただし $j \notin \mathrm{Pa}(k)$ のときは $\partial \varphi_k / \partial v_j := 0$ と約束します（$\varphi_k$ はその変数を含まないので、内側の写像の第 $k$ 成分の $u_j$ による偏微分が実際に $0$ になります）。第 1 項は内側の写像の第 $j$ 成分（恒等写像）からの寄与、第 2 項は第 $k$ 成分からの寄与です。

降順の帰納法で $g_m^{(m)} = \bar v_m$ を示します。 $m = N$ のときは基点の式と $\bar v_N = 1$ より成立します。$k < N$ とし、$m > k$ なるすべての $m$ で $g_m^{(m)} = \bar v_m$ が成り立つと仮定します。1 段落としの式を $j = k$ に対して $k' = k+1, k+2, \ldots, N$ と適用して足し合わせると、左辺は望遠鏡的に消えて

$$g_k^{(k)} - g_N^{(k)} = \sum_{m = k+1}^{N} g_m^{(m)} \, \frac{\partial \varphi_m}{\partial v_k}$$

となります。$k < N$ なので基点の式より $g_N^{(k)} = 0$ です。帰納法の仮定 $g_m^{(m)} = \bar v_m$ と、$k \notin \mathrm{Pa}(m)$ の項が $0$ であることを使うと

$$g_k^{(k)} = \sum_{m = k+1}^{N} \bar v_m \, \frac{\partial \varphi_m}{\partial v_k} = \sum_{m \,:\, k \in \mathrm{Pa}(m)} \bar v_m \, \frac{\partial \varphi_m}{\partial v_k} = \bar v_k$$

となり（最後の等号は 定義 4.2）、$m = k$ でも主張が成り立ちます。$k > n$ の範囲でこの帰納法が回ります。

入力ノードへの結論。 $j \le n$ を固定します。上とまったく同じ計算を $j$ に対して行います。1 段落としの式を $k' = n+1, \ldots, N$ と適用して足すと

$$g_n^{(j)} - g_N^{(j)} = \sum_{m=n+1}^{N} g_m^{(m)} \, \frac{\partial \varphi_m}{\partial v_j} .$$

$j \le n < N$ より基点の式から $g_N^{(j)} = 0$、また $m > n$ では上で示した $g_m^{(m)} = \bar v_m$ が使えるので

$$\frac{\partial F}{\partial v_j} = g_n^{(j)} = \sum_{m \,:\, j \in \mathrm{Pa}(m)} \bar v_m \, \frac{\partial \varphi_m}{\partial v_j} = \bar v_j$$

を得ます。最初の等号は $\Phi_n = F$ から、最後の等号は 定義 4.2 の定義式そのものです。

∎

証明を振り返ると、逆伝播が使っているのは 定理 3.1 と、トポロジカル順序の逆順に走査すれば必要な量がすべて確定済みであるという順序の事実だけです。ネットワークの形（層状か、分岐があるか、重みを共有しているか）は一切使っていません。だから同じアルゴリズムが畳み込みでも再帰型でも Transformer でも動きます。

例 4.4（分岐のある小さなグラフを手で逆向きに回す）

$f(x, y) = xy + \sin(xy)$ を計算グラフにします。$v_1 = x$、$v_2 = y$ を入力とし、

$$v_3 = \varphi_3(v_1,v_2) = v_1 v_2, \qquad v_4 = \varphi_4(v_3) = \sin v_3, \qquad v_5 = \varphi_5(v_3, v_4) = v_3 + v_4$$

とします。$\mathrm{Pa}(3) = \{1,2\}$、$\mathrm{Pa}(4)=\{3\}$、$\mathrm{Pa}(5)=\{3,4\}$ です。$v_3$ は $v_4$ と $v_5$ の両方の親になっている（分岐している）点が要です。

$x = 1$、$y = \pi/3$ とすると順伝播は $v_3 = \pi/3$、$v_4 = \sin(\pi/3) = \sqrt{3}/2$、$v_5 = \pi/3 + \sqrt{3}/2$ です。定義 4.2 に従って添字の大きい順に随伴変数を計算します。

$$\begin{aligned} \bar v_5 &= 1, \\ \bar v_4 &= \bar v_5 \frac{\partial \varphi_5}{\partial v_4} = 1 \cdot 1 = 1, \\ \bar v_3 &= \bar v_4 \frac{\partial \varphi_4}{\partial v_3} + \bar v_5 \frac{\partial \varphi_5}{\partial v_3} = 1 \cdot \cos v_3 + 1 \cdot 1 = \cos\frac{\pi}{3} + 1 = \frac{3}{2}, \\ \bar v_1 &= \bar v_3 \frac{\partial \varphi_3}{\partial v_1} = \frac{3}{2} \cdot v_2 = \frac{3}{2}\cdot\frac{\pi}{3} = \frac{\pi}{2}, \\ \bar v_2 &= \bar v_3 \frac{\partial \varphi_3}{\partial v_2} = \frac{3}{2} \cdot v_1 = \frac{3}{2}. \end{aligned}$$

直接微分して確かめます。$\partial f/\partial x = y + y\cos(xy) = y\,(1+\cos xy)$ に $x=1$、$y=\pi/3$ を入れると $(\pi/3)(1+1/2) = \pi/2$ で $\bar v_1$ と一致します。$\partial f/\partial y = x(1+\cos xy) = 1 \cdot (3/2) = 3/2$ で $\bar v_2$ とも一致します。

分岐ノード $v_3$ のところで和が現れたことに注意してください。同じ中間値が下流の複数箇所で使われるとき、随伴変数はそれぞれの経路からの寄与を足し合わせます。定理 4.3 の証明で $\mathrm{Pa}(m)$ 全体にわたる和を取ったのは、まさにこのためです。

5. 多層ネットワークの逆伝播公式

定理 4.3 を 定義 2.1 のネットワークに適用すると、教科書でおなじみの 4 本の式が出ます。

系 5.1（逆伝播の漸化式）✓

定義 2.1 の設定の下で、入力 $\boldsymbol{x}$ と正解 $\boldsymbol{y}$ を固定し、順伝播で $\boldsymbol{z}^{(\ell)}, \boldsymbol{a}^{(\ell)}$ をすべて計算しておく。$\boldsymbol{\delta}^{(\ell)} := \nabla_{\boldsymbol{z}^{(\ell)}} E \in \mathbb{R}^{n_\ell}$ と定めると、次が成り立つ。

$$\begin{aligned} &\text{(i)} && \boldsymbol{\delta}^{(L)} = \sigma^{(L)\prime}\!\big(\boldsymbol{z}^{(L)}\big) \odot \nabla_{\boldsymbol{a}^{(L)}} E, \\[2pt] &\text{(ii)} && \boldsymbol{\delta}^{(\ell)} = \sigma^{(\ell)\prime}\!\big(\boldsymbol{z}^{(\ell)}\big) \odot \Big( W^{(\ell+1)\mathsf{T}} \boldsymbol{\delta}^{(\ell+1)} \Big) \qquad (\ell = L-1, L-2, \ldots, 1), \\[2pt] &\text{(iii)} && \nabla_{W^{(\ell)}} E = \boldsymbol{\delta}^{(\ell)} \big(\boldsymbol{a}^{(\ell-1)}\big)^{\mathsf{T}}, \qquad \nabla_{\boldsymbol{b}^{(\ell)}} E = \boldsymbol{\delta}^{(\ell)} \qquad (\ell = 1, \ldots, L), \\[2pt] &\text{(iv)} && \nabla_{\boldsymbol{x}} E = W^{(1)\mathsf{T}} \boldsymbol{\delta}^{(1)} . \end{aligned}$$

ここで (iii) の左辺は $\big(\nabla_{W^{(\ell)}} E\big)_{pq} = \partial E / \partial W^{(\ell)}_{pq}$ を成分とする $n_\ell \times n_{\ell-1}$ 行列である。

次の証明では、定理 4.3 の漸化式を各ノードに書き下すだけです。(ii) に転置が現れるのは、$\boldsymbol{z}^{(\ell+1)}$ の各成分の勾配を、$W^{(\ell+1)}$ の係数の重みをつけて $\boldsymbol{a}^{(\ell)}$ の成分へ足し戻すためです。順伝播では行列 $W$ で前へ運び、逆伝播では同じ重みで逆向きに運ぶので、$W$ の行と列が入れ替わります。

証明（系 5.1）

スカラー変数 $x_j$、$W^{(\ell)}_{pq}$、$b^{(\ell)}_p$、$z^{(\ell)}_i$、$a^{(\ell)}_i$、$E$ を並べ、$x_j$ と $W^{(\ell)}_{pq}$ と $b^{(\ell)}_p$ と $y$ の成分を入力ノード、$E$ を出力ノードとする計算グラフを作ります。トポロジカル順序は $\boldsymbol{z}^{(1)}, \boldsymbol{a}^{(1)}, \boldsymbol{z}^{(2)}, \ldots$ の順に取れます。各ノードの生成規則と親は

$$z^{(\ell)}_i = \sum_{q=1}^{n_{\ell-1}} W^{(\ell)}_{iq} a^{(\ell-1)}_q + b^{(\ell)}_i, \qquad a^{(\ell)}_i = \sigma^{(\ell)}\big(z^{(\ell)}_i\big), \qquad E = \mathcal{L}\big(\boldsymbol{a}^{(L)}, \boldsymbol{y}\big)$$

です。定理 4.3 の証明中で示したとおり、入力ノードだけでなく中間ノードについても $\bar v_k = g_k^{(k)}$ が成り立ち、これは「その変数を微小に動かしたときの $E$ の変化率」に他なりません。$\bar z^{(\ell)}_i$ は定義より $\partial E/\partial z^{(\ell)}_i = \delta^{(\ell)}_i$ です。以下、定義 4.2 の漸化式を各ノードに書き下します。

(i) 最終層。 $a^{(L)}_i$ の子は $E$ だけなので $\bar a^{(L)}_i = \bar E \cdot \partial \mathcal{L} / \partial a^{(L)}_i = \big(\nabla_{\boldsymbol{a}^{(L)}} E\big)_i$（$\bar E = 1$）。次に $z^{(L)}_i$ の子は $a^{(L)}_i$ ただ 1 つで（活性化は成分ごとなので $z^{(L)}_i$ は他の $a^{(L)}_{i'}$ に影響しません）、$\partial a^{(L)}_i/\partial z^{(L)}_i = \sigma^{(L)\prime}(z^{(L)}_i)$ ですから

$$\delta^{(L)}_i = \bar z^{(L)}_i = \sigma^{(L)\prime}\big(z^{(L)}_i\big)\,\big(\nabla_{\boldsymbol{a}^{(L)}} E\big)_i .$$

成分ごとの積なので、これはアダマール積で (i) と書けます。

(ii) 中間層。 $\ell < L$ のとき、$a^{(\ell)}_j$ の子は $z^{(\ell+1)}_1, \ldots, z^{(\ell+1)}_{n_{\ell+1}}$ です。$\partial z^{(\ell+1)}_i / \partial a^{(\ell)}_j = W^{(\ell+1)}_{ij}$ なので

$$\bar a^{(\ell)}_j = \sum_{i=1}^{n_{\ell+1}} \bar z^{(\ell+1)}_i W^{(\ell+1)}_{ij} = \sum_{i} W^{(\ell+1)}_{ij}\,\delta^{(\ell+1)}_i = \Big(W^{(\ell+1)\mathsf{T}} \boldsymbol{\delta}^{(\ell+1)}\Big)_j .$$

添字の位置に注意してください。$W^{(\ell+1)}_{ij}$ の $i$ について和を取るので、現れるのは転置です。続いて $z^{(\ell)}_j$ の子は $a^{(\ell)}_j$ だけなので $\delta^{(\ell)}_j = \bar z^{(\ell)}_j = \sigma^{(\ell)\prime}(z^{(\ell)}_j)\,\bar a^{(\ell)}_j$ となり、(ii) を得ます。

(iii) パラメータ。 $W^{(\ell)}_{pq}$ が現れるのは $z^{(\ell)}_p$ の式の中だけです（$i \ne p$ の $z^{(\ell)}_i$ の式には $W^{(\ell)}_{iq}$ しか現れません）。したがって子は $z^{(\ell)}_p$ 一つで、$\partial z^{(\ell)}_p / \partial W^{(\ell)}_{pq} = a^{(\ell-1)}_q$ ですから

$$\frac{\partial E}{\partial W^{(\ell)}_{pq}} = \bar W^{(\ell)}_{pq} = \delta^{(\ell)}_p \, a^{(\ell-1)}_q .$$

これは外積 $\boldsymbol{\delta}^{(\ell)} (\boldsymbol{a}^{(\ell-1)})^{\mathsf{T}}$ の $(p,q)$ 成分です。同様に $b^{(\ell)}_p$ の子は $z^{(\ell)}_p$ だけで $\partial z^{(\ell)}_p/\partial b^{(\ell)}_p = 1$ なので $\partial E/\partial b^{(\ell)}_p = \delta^{(\ell)}_p$ です。

(iv) 入力。 $x_j = a^{(0)}_j$ の子は $z^{(1)}_1, \ldots, z^{(1)}_{n_1}$ で、(ii) の計算と同じ形になり $\nabla_{\boldsymbol{x}} E = W^{(1)\mathsf{T}}\boldsymbol{\delta}^{(1)}$ です。

∎

(iii) が実務上いちばん大事な式です。あるパラメータの勾配は「その層の $\delta$」と「その層への入力」の外積だけで決まります。例 2.2 で見た $\partial E/\partial w = \delta x$ の一般化になっています。(iv) は学習には不要ですが、入力に関する勾配は敵対的サンプルの生成や特徴の可視化に使われます。

順伝播は値を左から右へ運び（実線）、逆伝播は随伴変数を右から左へ運ぶ（破線）。走るのは同じグラフで、向きだけが逆になる。

アルゴリズムとしてまとめると次のようになります。

1. 順伝播：$\boldsymbol{a}^{(0)} = \boldsymbol{x}$ から始め、$\ell = 1, \ldots, L$ の順に $\boldsymbol{z}^{(\ell)}, \boldsymbol{a}^{(\ell)}$ を計算し、すべて保存する。
2. 出力層の $\delta$：系 5.1 (i) で $\boldsymbol{\delta}^{(L)}$ を作る。
3. 逆伝播：$\ell = L, L-1, \ldots, 1$ の順に、(iii) で $\nabla_{W^{(\ell)}}E$ と $\nabla_{\boldsymbol{b}^{(\ell)}}E$ を確定させ、$\ell > 1$ なら (ii) で $\boldsymbol{\delta}^{(\ell-1)}$ を作る。

手順 1 で $\boldsymbol{a}^{(\ell)}$ と $\boldsymbol{z}^{(\ell)}$ を保存するところが重要です。(ii) と (iii) はどちらも順伝播時の値を必要とするので、逆伝播は順伝播の記録なしには走りません。これが深層学習のメモリ消費の主因です。

import numpy as np

def sigmoid(z):
    return 1.0 / (1.0 + np.exp(-z))

def forward(Ws, bs, x):
    """順伝播。前活性 zs と活性 a を層ごとに保存して返す。出力層は恒等活性。"""
    a, zs = [x], []
    L = len(Ws)
    for l, (W, b) in enumerate(zip(Ws, bs)):
        z = W @ a[-1] + b
        zs.append(z)
        a.append(sigmoid(z) if l < L - 1 else z)
    return zs, a

def backward(Ws, zs, a, y):
    """二乗誤差 E = |a_L - y|^2 / 2 に対する逆伝播。dW[l], db[l] を返す。"""
    L = len(Ws)
    dWs, dbs = [None] * L, [None] * L
    delta = a[-1] - y                          # 系 (i)：出力層は恒等活性
    for l in range(L - 1, -1, -1):
        dWs[l] = np.outer(delta, a[l])         # 系 (iii)
        dbs[l] = delta
        if l > 0:                              # 系 (ii)
            s = sigmoid(zs[l - 1])
            delta = s * (1.0 - s) * (Ws[l].T @ delta)
    return dWs, dbs

例 5.2（2-2-1 ネットワークの数値計算を最後まで）

$L = 2$、$n_0 = n_1 = 2$、$n_2 = 1$ とします。第 1 層の活性化はシグモイド、第 2 層は恒等写像、損失は $E = \tfrac12 (a^{(2)} - y)^2$ とし、

$$W^{(1)} = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}, \quad \boldsymbol{b}^{(1)} = \begin{pmatrix} 1 \\ -1 \end{pmatrix}, \quad W^{(2)} = \begin{pmatrix} 2 & -3 \end{pmatrix}, \quad b^{(2)} = 1, \quad \boldsymbol{x} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}, \quad y = 1$$

とします。以下、小数第 4 位まで書きます。

順伝播。

$$\boldsymbol{z}^{(1)} = \begin{pmatrix} 1\cdot 1 + (-1)\cdot 2 + 1 \\ 0\cdot 1 + 1\cdot 2 - 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \qquad \boldsymbol{a}^{(1)} = \begin{pmatrix} \sigma(0) \\ \sigma(1) \end{pmatrix} = \begin{pmatrix} 0.5000 \\ 0.7311 \end{pmatrix}$$$$z^{(2)} = 2(0.5000) - 3(0.7311) + 1 = 1 - 2.1932 + 1 = -0.1932, \qquad a^{(2)} = z^{(2)} = -0.1932$$$$E = \tfrac12 (-0.1932 - 1)^2 = \tfrac12 (1.1932)^2 = \tfrac12 (1.4237) = 0.7118$$

逆伝播。 第 2 層の活性化は恒等なので $\sigma^{(2)\prime} \equiv 1$、また $\nabla_{a^{(2)}}E = a^{(2)} - y$ です。系 5.1 (i) より

$$\delta^{(2)} = 1 \cdot (-0.1932 - 1) = -1.1932 .$$

(iii) から第 2 層のパラメータの勾配が出ます。

$$\nabla_{W^{(2)}}E = \delta^{(2)}\big(\boldsymbol{a}^{(1)}\big)^{\mathsf{T}} = -1.1932\,(0.5000,\; 0.7311) = (-0.5966,\; -0.8723), \qquad \frac{\partial E}{\partial b^{(2)}} = -1.1932 .$$

(ii) で $\boldsymbol{\delta}^{(1)}$ に降ります。まず

$$W^{(2)\mathsf{T}}\delta^{(2)} = \begin{pmatrix} 2 \\ -3 \end{pmatrix}(-1.1932) = \begin{pmatrix} -2.3864 \\ 3.5795 \end{pmatrix},$$

次に $\sigma' = \sigma(1-\sigma)$ から

$$\sigma'\big(\boldsymbol{z}^{(1)}\big) = \begin{pmatrix} 0.5000 \times 0.5000 \\ 0.7311 \times 0.2689 \end{pmatrix} = \begin{pmatrix} 0.2500 \\ 0.1966 \end{pmatrix},$$

よってアダマール積を取って

$$\boldsymbol{\delta}^{(1)} = \begin{pmatrix} 0.2500 \times (-2.3864) \\ 0.1966 \times 3.5795 \end{pmatrix} = \begin{pmatrix} -0.5966 \\ 0.7038 \end{pmatrix} .$$

最後に (iii) を $\ell = 1$ で使います。$\boldsymbol{a}^{(0)} = \boldsymbol{x} = (1, 2)^{\mathsf{T}}$ なので

$$\nabla_{W^{(1)}}E = \begin{pmatrix} -0.5966 \\ 0.7038 \end{pmatrix} (1,\; 2) = \begin{pmatrix} -0.5966 & -1.1932 \\ 0.7038 & 1.4076 \end{pmatrix}, \qquad \nabla_{\boldsymbol{b}^{(1)}}E = \begin{pmatrix} -0.5966 \\ 0.7038 \end{pmatrix}.$$

検算。 $W^{(1)}_{22}$ について直接微分してみます。$W^{(1)}_{22}$ は $z^{(1)}_2$ にしか現れず、$z^{(1)}_2 = W^{(1)}_{21}x_1 + W^{(1)}_{22}x_2 + b^{(1)}_2$、$a^{(1)}_2 = \sigma(z^{(1)}_2)$、$z^{(2)} = 2a^{(1)}_1 - 3a^{(1)}_2 + 1$、$E = \tfrac12(z^{(2)}-y)^2$ なので、1 変数の連鎖律を繋ぐと

$$\frac{\partial E}{\partial W^{(1)}_{22}} = (z^{(2)}-y)\cdot(-3)\cdot \sigma'\big(z^{(1)}_2\big)\cdot x_2 = (-1.1932)(-3)(0.1966)(2) = 1.4076$$

となり、上の行列の $(2,2)$ 成分と一致します。同様に $b^{(1)}_1$ については $(z^{(2)}-y)\cdot 2 \cdot \sigma'(z^{(1)}_1) = (-1.1932)(2)(0.2500) = -0.5966$ で、$\nabla_{\boldsymbol{b}^{(1)}}E$ の第 1 成分と一致します。

注意 5.3

実際によく使われる ReLU $\sigma(t) = \max(t, 0)$ は $t = 0$ で微分可能でないので、定義 2.1 の「$C^1$ 級」という仮定を満たしません。実装では $\sigma'(0)$ を $0$（または $1$）と決め打ちします。これは数学的には劣微分から 1 つ選んでいることに相当します。$t = 0$ ちょうどが起きる確率は測度ゼロで、実務上はまず問題になりません。ただし「勾配」と呼んでいるものが真の勾配とは限らないことは意識しておいてください。

6. なぜ安いのか：計算量

定理 4.3 は「正しい」ことしか言っていません。逆伝播の値打ちは「安い」ことにあります。それを見積もります。

命題 6.1（逆伝播 1 回は順伝播 1 回の定数倍）✓

定義 4.1 の計算グラフについて、辺数を $M := \sum_{k > n} |\mathrm{Pa}(k)|$ とする。各 $k$ について、値 $\varphi_k$ の評価と、すべての偏微分 $\partial \varphi_k / \partial v_j$（$j \in \mathrm{Pa}(k)$）の評価が、それぞれ $|\mathrm{Pa}(k)|$ に比例する演算回数でできると仮定する。このとき

$$\text{順伝播の計算量} = O(N + M), \qquad \text{逆伝播の計算量} = O(N + M)$$

であり、後者 1 回で $n$ 個の偏微分 $\partial F/\partial v_1, \ldots, \partial F/\partial v_n$ がすべて得られる。一方、差分近似で同じ $n$ 個を得るには順伝播が $n$ 回以上必要で、計算量は $\Omega\big(n(N+M)\big)$ となる。

なお、$O(\cdot)$ は「高々この程度の手間」、$\Omega(\cdot)$ は「少なくともこの程度の手間」を表す記号です。逆伝播は 1 回の走査で全部の偏微分が出るのに対し、差分近似は変数を 1 つずつ動かして調べるため、変数の個数だけ順伝播が要る、というのが次の証明の骨子です。

証明（命題 6.1）

順伝播はノード $k = n+1, \ldots, N$ を順に 1 回ずつ処理し、各ノードで $O(|\mathrm{Pa}(k)|)$ の演算を行います。合計は $\sum_{k>n} O(|\mathrm{Pa}(k)|) = O(M)$、ノードの読み書きに $O(N)$ かかるので $O(N+M)$ です。

逆伝播は次のように実装します。長さ $N$ の配列 $\bar v$ を $\bar v_N = 1$、それ以外 $0$ で初期化します（$O(N)$）。次に $m = N, N-1, \ldots, n+1$ の順に、各 $j \in \mathrm{Pa}(m)$ について

$$\bar v_j \mathrel{+}= \bar v_m \cdot \frac{\partial \varphi_m}{\partial v_j}$$

と加算します。この二重ループが触れる回数は辺の総数 $M$ に等しく、各回の仕事は偏微分 1 個の評価と積和で $O(1)$ ですから、合計 $O(N+M)$ です。

この手続きが 定義 4.2 の定義と一致することを確かめます。$m$ を降順に処理するので、添字 $j$ の枠に加算が行われるのは $j \in \mathrm{Pa}(m)$ なる $m$ すべてについてであり、加算が終わった時点の値は $\sum_{m : j \in \mathrm{Pa}(m)} \bar v_m \,\partial\varphi_m/\partial v_j$ です。しかも $j$ の枠が読み出される（すなわち $m = j$ の番が来る）のは、$j$ より大きい添字の処理がすべて終わった後なので、そのとき $\bar v_j$ はすでに確定しています。よって 定義 4.2 と同じ値が得られ、定理 4.3 より $j \le n$ でそれは $\partial F/\partial v_j$ です。

差分近似については、$\partial F/\partial v_j$ を得るには少なくとも $v_j$ を動かした $F$ の評価が 1 回必要で、$j$ ごとに別の評価が要ります。$F$ の 1 回の評価が順伝播 1 回、すなわち $\Theta(N+M)$ なので、全体で $\Omega(n(N+M))$ です。

∎

定義 2.1 のネットワークでは、辺数の主要項は $M \approx \sum_{\ell} n_\ell n_{\ell-1}$ で、これはパラメータ数 $P = \sum_\ell (n_\ell n_{\ell-1} + n_\ell)$ とほぼ同じです。したがって逆伝播は $\Theta(P)$、差分近似は $\Theta(P^2)$ になります。$P$ が大きいほど差は開きます。

例 6.2（784-256-128-10 のネットワークでの見積もり）

手書き数字認識でよく使われるサイズを取ります。$n_0 = 784$、$n_1 = 256$、$n_2 = 128$、$n_3 = 10$ の 3 層ネットワークです。パラメータ数は

$$P = (784 \cdot 256 + 256) + (256 \cdot 128 + 128) + (128 \cdot 10 + 10) = 200960 + 32896 + 1290 = 235146$$

です。順伝播 1 回の積和回数は行列ベクトル積が支配的で

$$784 \cdot 256 + 256 \cdot 128 + 128 \cdot 10 = 200704 + 32768 + 1280 = 234752 \approx 2.3 \times 10^5$$

回です。命題 6.1 より逆伝播も同じオーダーで、実際 (ii) の $W^{\mathsf{T}}\boldsymbol{\delta}$ と (iii) の外積がそれぞれ順伝播と同じ回数の積和なので、勾配計算全体でおよそ $3 \times 2.3\times10^5 \approx 7\times10^5$ 回です。

一方、中心差分で全パラメータの勾配を出すには $2P = 470292$ 回の順伝播が要るので

$$470292 \times 2.34752\times10^5 \approx 1.1 \times 10^{11}$$

回の積和になります。比を取ると $1.1\times10^{11} / 7\times10^5 \approx 1.6 \times 10^5$、およそ 16 万倍です。逆伝播で 1 秒の学習ステップが、差分近似では 2 日近くかかる計算になります。しかもこれは小さいネットワークでの話で、$P$ が $10^9$ の規模になれば比はさらに $4$ 桁開きます。

注意 6.3

連鎖律の積 $J_{\mathcal{L}} J_L \cdots J_1$ を右から掛ける計算も、それ自体は正当なアルゴリズムで、フォワードモード自動微分と呼ばれます。こちらは 1 回の走査で「入力方向 $\boldsymbol{u}$ に沿った方向微分」$J\boldsymbol{u}$ を返すので、勾配全体を得るには $n$ 回走らせる必要があります。逆に、出力が多くて入力が少ない状況（$n$ が小さく $p$ が大きい）ではフォワードモードのほうが安上がりです。深層学習ではスカラーの損失を大量のパラメータで微分するので、リバースモード一択になります。

注意 6.4

命題 6.1 は時間の話で、空間については別の見積もりが要ります。逆伝播は順伝播で作った中間値を保持しなければならないので、メモリは深さに比例して増えます。これを緩和するのが再計算（gradient checkpointing） で、中間値を間引いて保存し、逆伝播中に必要になった区間だけ順伝播をやり直します。$L$ 段の連鎖に対して $O(\sqrt{L})$ のメモリと $O(L)$ の追加計算で済ませられます。詳しくは Griewank と Walther の教科書（[4]）を参照してください。

7. 出力層と損失を組にする：ソフトマックスと交差エントロピー

系 5.1 (i)(ii) は活性化関数が成分ごとであることを使いました。多クラス分類で使うソフトマックス関数はそうではありません。その場合は 注意 3.2 に戻り、ヤコビ行列の転置を掛ける一般形

$$\boldsymbol{\delta}^{(L)} = J_{\sigma^{(L)}}\big(\boldsymbol{z}^{(L)}\big)^{\mathsf{T}} \, \nabla_{\boldsymbol{a}^{(L)}} E$$

を使います。ソフトマックスと交差エントロピー（2 クラスの場合が 定義 4.1［ロジスティック回帰］）を組にすると、この積が劇的に簡単になります。

命題 7.1（ソフトマックス＋交差エントロピーの勾配）✓

$\boldsymbol{z} \in \mathbb{R}^n$ に対しソフトマックスを

$$a_i = \mathrm{softmax}(\boldsymbol{z})_i := \frac{e^{z_i}}{\sum_{k=1}^{n} e^{z_k}} \qquad (i = 1, \ldots, n)$$

で定める。$\boldsymbol{y} \in \mathbb{R}^n$ が $y_i \ge 0$ かつ $\sum_{i=1}^n y_i = 1$ を満たすとし、交差エントロピー損失を $E := -\sum_{i=1}^n y_i \log a_i$ とする。このとき

$$\nabla_{\boldsymbol{z}} E = \boldsymbol{a} - \boldsymbol{y}$$

が成り立つ。またソフトマックスのヤコビ行列は $J = \mathrm{diag}(\boldsymbol{a}) - \boldsymbol{a}\boldsymbol{a}^{\mathsf{T}}$ である。

証明（命題 7.1）

$S := \sum_{k=1}^n e^{z_k}$ と置きます。$e^{z_k} > 0$ より $S > 0$、したがって $a_i > 0$ で $\log a_i$ は定義され、$\boldsymbol{z} \mapsto \boldsymbol{a}$ は $C^\infty$ 級です。

まず $\log a_i = z_i - \log S$ です。$\dfrac{\partial S}{\partial z_j} = e^{z_j}$ なので $\dfrac{\partial \log S}{\partial z_j} = \dfrac{e^{z_j}}{S} = a_j$ であり、

$$\frac{\partial \log a_i}{\partial z_j} = \frac{\partial z_i}{\partial z_j} - a_j = \begin{cases} 1 - a_j & (i = j) \\ -a_j & (i \ne j) \end{cases}$$

を得ます。以下 $[i=j]$ は $i=j$ のとき $1$、$i \ne j$ のとき $0$ を表す記法とし、上の場合分けを $\partial \log a_i/\partial z_j = [i=j]-a_j$ と一つにまとめます。これに $a_i$ を掛ければ $\dfrac{\partial a_i}{\partial z_j} = a_i\big([i=j] - a_j\big)$、すなわち行列で $J = \mathrm{diag}(\boldsymbol{a}) - \boldsymbol{a}\boldsymbol{a}^{\mathsf{T}}$ です。

損失の勾配は、$J$ を経由せずに直接計算するほうが早く済みます。$E = -\sum_i y_i \log a_i = -\sum_i y_i (z_i - \log S)$ を $z_j$ で偏微分すると、第 1 項からは $-y_j$、第 2 項からは $\big(\sum_i y_i\big)\dfrac{\partial \log S}{\partial z_j}$ が出ます。仮定 $\sum_i y_i = 1$ と、上で求めた $\partial \log S/\partial z_j = a_j$ を使えば

$$\frac{\partial E}{\partial z_j} = -y_j + 1 \cdot a_j = a_j - y_j$$

となり、主張が従います。

念のため、注意 3.2 の一般形からも同じ答えになることを確かめます。$\nabla_{\boldsymbol{a}}E$ の第 $i$ 成分は $-y_i/a_i$ なので、$J$ が対称であることに注意して

$$\big(J^{\mathsf{T}}\nabla_{\boldsymbol{a}}E\big)_j = \sum_i J_{ij}\left(-\frac{y_i}{a_i}\right) = \sum_i a_i\big([i=j]-a_j\big)\left(-\frac{y_i}{a_i}\right) = -y_j + a_j\sum_i y_i = a_j - y_j$$

で一致します。

∎

出力層でソフトマックスを使うとき、実装では $\boldsymbol{\delta}^{(L)} = \boldsymbol{a}^{(L)} - \boldsymbol{y}$ と 1 行で書きます。ヤコビ行列 $J$（$n \times n$）を作らずに済むので、クラス数が大きいときの節約は大きくなります。なお $\boldsymbol{y}$ が one-hot（正解クラス $c$ で $y_c = 1$、他は $0$）のときも仮定 $\sum_i y_i = 1$ は満たされるので、この命題がそのまま使えます。

注意

ソフトマックスをそのまま計算すると $e^{z_i}$ が容易にあふれます。実装では $\max_k z_k$ を全成分から引いてから指数を取ります。ソフトマックスは $\boldsymbol{z}$ に定数ベクトルを足しても値が変わらない（演習 9.3）ので、この操作は結果を変えません。

8. 深さの代償：勾配消失

逆伝播は「安い」ですが「よく効く」とは限りません。系 5.1 (ii) を $\ell$ から $L$ まで繰り返すと、$\boldsymbol{\delta}^{(\ell)}$ は $L-\ell$ 個の行列と $L-\ell$ 個の対角行列の積になります。積の各因子が $1$ より小さいと、積は指数的に小さくなります。

命題 8.1（勾配の大きさの指数的な上界）✓

定義 2.1 の設定に加え、ある定数 $c > 0$、$w > 0$ が存在して、すべての $\ell$ とすべての $t \in \mathbb{R}$ について $|\sigma^{(\ell)\prime}(t)| \le c$、かつ作用素ノルムについて $\|W^{(\ell)}\|_2 \le w$ が成り立つとする。このとき任意の $\ell = 1, \ldots, L$ について

$$\big\|\boldsymbol{\delta}^{(\ell)}\big\|_2 \le (cw)^{\,L-\ell}\,\big\|\boldsymbol{\delta}^{(L)}\big\|_2, \qquad \big\|\nabla_{W^{(\ell)}}E\big\|_F \le (cw)^{\,L-\ell}\,\big\|\boldsymbol{\delta}^{(L)}\big\|_2\,\big\|\boldsymbol{a}^{(\ell-1)}\big\|_2$$

が成り立つ（$\|\cdot\|_F$ はフロベニウスノルム）。とくに $\sigma$ がシグモイド関数のときは $c = 1/4$ が取れるので、$w < 4$ ならば $\ell$ が小さくなるにつれて勾配は指数的に $0$ へ近づく。

証明のねらいは、(ii) の 1 段ごとに $\boldsymbol{\delta}$ の長さが高々 $cw$ 倍にしかならないことを示し、それを $L-\ell$ 回繰り返すことです。ここで作用素ノルム $\|W\|_2$ は、$W$ がベクトルを引き伸ばす最大の倍率のことで、特異値分解（行列を回転・拡大縮小・回転の積に分けること）を使うと最大の特異値に等しいことが見えます。フロベニウスノルムは、行列の全成分の 2 乗和の平方根です。

証明（命題 8.1）

系 5.1 (ii) は、$D^{(\ell)} := \mathrm{diag}\big(\sigma^{(\ell)\prime}(z^{(\ell)}_1), \ldots, \sigma^{(\ell)\prime}(z^{(\ell)}_{n_\ell})\big)$ と置けば

$$\boldsymbol{\delta}^{(\ell)} = D^{(\ell)}\, W^{(\ell+1)\mathsf{T}}\, \boldsymbol{\delta}^{(\ell+1)}$$

と書き直せます（アダマール積は対角行列を左から掛けることと同じです）。

まず $\|D^{(\ell)}\|_2 \le c$ を示します。任意の $\boldsymbol{u}$ について

$$\big\|D^{(\ell)}\boldsymbol{u}\big\|_2^2 = \sum_{j} \sigma^{(\ell)\prime}\big(z^{(\ell)}_j\big)^2 u_j^2 \le c^2 \sum_j u_j^2 = c^2\|\boldsymbol{u}\|_2^2$$

なので、作用素ノルムの定義から従います。次に $\|W^{\mathsf{T}}\|_2 = \|W\|_2$ です。実際、特異値分解 $W = U\Sigma V^{\mathsf{T}}$（$U, V$ は直交行列）を取ると $W^{\mathsf{T}} = V\Sigma U^{\mathsf{T}}$ で、作用素ノルムは最大特異値に等しく、$W$ と $W^{\mathsf{T}}$ は特異値を共有します（スペクトル定理、とくに 定理 4.2［スペクトル定理］ を参照）。よって $\|W^{(\ell+1)\mathsf{T}}\|_2 \le w$ です。

作用素ノルムの劣乗法性 $\|AB\|_2 \le \|A\|_2\|B\|_2$ を使うと

$$\big\|\boldsymbol{\delta}^{(\ell)}\big\|_2 \le \big\|D^{(\ell)}\big\|_2 \big\|W^{(\ell+1)\mathsf{T}}\big\|_2 \big\|\boldsymbol{\delta}^{(\ell+1)}\big\|_2 \le cw\,\big\|\boldsymbol{\delta}^{(\ell+1)}\big\|_2$$

となり、$\ell$ についての降順の帰納法で $\|\boldsymbol{\delta}^{(\ell)}\|_2 \le (cw)^{L-\ell}\|\boldsymbol{\delta}^{(L)}\|_2$ を得ます。

第 2 の不等式は 系 5.1 (iii) からです。外積のフロベニウスノルムは

$$\big\|\boldsymbol{u}\boldsymbol{v}^{\mathsf{T}}\big\|_F^2 = \sum_{p,q} u_p^2 v_q^2 = \Big(\sum_p u_p^2\Big)\Big(\sum_q v_q^2\Big) = \|\boldsymbol{u}\|_2^2\|\boldsymbol{v}\|_2^2$$

なので、$\|\nabla_{W^{(\ell)}}E\|_F = \|\boldsymbol{\delta}^{(\ell)}\|_2\|\boldsymbol{a}^{(\ell-1)}\|_2$ に第 1 の不等式を代入すればよいです。

最後にシグモイドの場合です。$\sigma' = \sigma(1-\sigma)$（演習 9.1）で $s := \sigma(t) \in (0,1)$ と置くと $\tfrac14 - s(1-s) = s^2 - s + \tfrac14 = (s - \tfrac12)^2 \ge 0$ なので $\sigma'(t) \le 1/4$ です。したがって $c = 1/4$ が取れます。

∎

$cw < 1$ のとき、たとえば $cw = 0.5$ で $L - \ell = 20$ なら係数は $0.5^{20} \approx 10^{-6}$ です。入力に近い層のパラメータはほとんど更新されなくなります。これが勾配消失です。逆に $cw > 1$ なら勾配は指数的に増大し、勾配爆発が起きます。

命題 8.1 は上界なので、勾配が必ず消えることを主張してはいません。しかし「何が効いているか」ははっきり読み取れます。$c$（活性化関数の傾きの上限）と $w$（重みの作用素ノルム）の積が $1$ から離れると危ない、ということです。実際の対策はこの読みに沿っています。$c$ を上げるために飽和しない ReLU 系を使う、$w$ を $1$ の近くに保つように初期化を設計する（層の入出力幅に応じて分散を決める Glorot らの初期化）、恒等写像の経路を足して積の因子に $1$ を混ぜる残差接続、前活性のスケールを揃える正規化層、といったものです。詳しくは Goodfellow らの教科書（[5]）の第 8 章を参照してください。

9. 演習

演習 9.1易

シグモイド関数 $\sigma(t) = \dfrac{1}{1+e^{-t}}$ について、次を示してください。

1. $\sigma'(t) = \sigma(t)\big(1 - \sigma(t)\big)$。
2. $\displaystyle\max_{t \in \mathbb{R}} \sigma'(t) = \frac14$ であり、最大値は $t = 0$ でのみ取られる。

解答

1. $\sigma(t) = (1+e^{-t})^{-1}$ を商の微分法（あるいは合成関数の微分法）で微分します。

$$\sigma'(t) = -\,(1+e^{-t})^{-2}\cdot \frac{d}{dt}\big(1+e^{-t}\big) = -\,(1+e^{-t})^{-2}\cdot(-e^{-t}) = \frac{e^{-t}}{(1+e^{-t})^{2}} .$$

ここで $\dfrac{e^{-t}}{1+e^{-t}} = \dfrac{(1+e^{-t}) - 1}{1+e^{-t}} = 1 - \sigma(t)$ なので

$$\sigma'(t) = \frac{1}{1+e^{-t}}\cdot\frac{e^{-t}}{1+e^{-t}} = \sigma(t)\big(1-\sigma(t)\big)$$

を得ます。

2. $s := \sigma(t)$ と置きます。$\sigma$ は $\mathbb{R}$ から開区間 $(0,1)$ の上への狭義単調増加な全単射なので、$t$ を動かすことは $s$ を $(0,1)$ で動かすことと同じです。$s(1-s)$ を評価すると

$$\frac14 - s(1-s) = s^2 - s + \frac14 = \left(s - \frac12\right)^2 \ge 0$$

なので $\sigma'(t) = s(1-s) \le 1/4$ であり、等号は $s = 1/2$ のとき、すなわち $\sigma(t) = 1/2$ すなわち $t = 0$ のときに限ります。$\sigma(0) = 1/2$ なので最大値 $1/4$ は実際に達成されます。

この $1/4$ が 命題 8.1 の定数 $c$ です。シグモイドを重ねると勾配が最低でも 4 分の 1 ずつ縮む、というのがこの計算の意味です。

演習 9.2標準

再帰型ネットワーク（RNN）では、同じ重み行列が各時刻で使い回されます。$\boldsymbol{h}^{(0)} \in \mathbb{R}^{d}$ を固定された初期状態、$\boldsymbol{x}^{(1)}, \ldots, \boldsymbol{x}^{(T)}$ を入力列とし、$C^1$ 級の成分ごとの活性化 $\sigma$ に対して

$$\boldsymbol{z}^{(t)} = W \boldsymbol{h}^{(t-1)} + U\boldsymbol{x}^{(t)} + \boldsymbol{b}, \qquad \boldsymbol{h}^{(t)} = \sigma\big(\boldsymbol{z}^{(t)}\big) \qquad (t = 1, \ldots, T)$$

と定めます。損失 $E$ は $\boldsymbol{h}^{(1)}, \ldots, \boldsymbol{h}^{(T)}$ の $C^1$ 級関数とします。$\boldsymbol{\delta}^{(t)} := \nabla_{\boldsymbol{z}^{(t)}} E$ と置くとき

$$\nabla_W E = \sum_{t=1}^{T} \boldsymbol{\delta}^{(t)} \big(\boldsymbol{h}^{(t-1)}\big)^{\mathsf{T}}$$

を 定理 4.3 から導いてください。

解答

スカラー変数を並べた計算グラフを作ります。入力ノードは $W_{pq}$、$U_{pq}$、$b_p$、$\boldsymbol{x}^{(t)}$ と $\boldsymbol{h}^{(0)}$ の成分、中間ノードは $z^{(t)}_i$ と $h^{(t)}_i$、出力ノードは $E$ です。トポロジカル順序は時刻の順に取れます。

$W_{pq}$ がどのノードの式に現れるかを数えます。$z^{(t)}_i = \sum_q W_{iq}h^{(t-1)}_q + \sum_q U_{iq}x^{(t)}_q + b_i$ なので、$W_{pq}$ が現れるのは $i = p$ のときだけ、すなわち

$$z^{(1)}_p,\ z^{(2)}_p,\ \ldots,\ z^{(T)}_p$$

の $T$ 個です。ここが要点で、同じパラメータが $T$ 個の子を持つ、つまり 例 4.4 の $v_3$ と同じ分岐ノードになっています。

局所偏微分は $\dfrac{\partial z^{(t)}_p}{\partial W_{pq}} = h^{(t-1)}_q$ です（$\boldsymbol{h}^{(t-1)}$ はグラフ上の別のノードであって、$W$ の関数として展開する必要はありません。これが計算グラフで考える利点です）。定義 4.2 の漸化式を $W_{pq}$ に適用すると、子の全体にわたる和として

$$\bar W_{pq} = \sum_{t=1}^{T} \bar z^{(t)}_p \cdot \frac{\partial z^{(t)}_p}{\partial W_{pq}} = \sum_{t=1}^{T} \delta^{(t)}_p\, h^{(t-1)}_q$$

が得られます。$W_{pq}$ は入力ノードなので 定理 4.3 より $\bar W_{pq} = \partial E/\partial W_{pq}$ であり、これを行列としてまとめれば $\nabla_W E = \sum_t \boldsymbol{\delta}^{(t)}(\boldsymbol{h}^{(t-1)})^{\mathsf{T}}$ です。

一般に、重みを共有したら勾配は各出現箇所の寄与の和になるというのがここでの教訓です。畳み込み層で 1 つのフィルタ係数の勾配が全位置にわたる和になるのも、まったく同じ理由です。

演習 9.3標準

命題 7.1 のソフトマックスのヤコビ行列 $J = \mathrm{diag}(\boldsymbol{a}) - \boldsymbol{a}\boldsymbol{a}^{\mathsf{T}}$ について、次を示してください。$\boldsymbol{1} := (1, \ldots, 1)^{\mathsf{T}}$ とします。

1. $J\boldsymbol{1} = \boldsymbol{0}$。これはソフトマックスのどんな性質を表していますか。
2. 任意の $\boldsymbol{u} \in \mathbb{R}^n$ に対して $\boldsymbol{u}^{\mathsf{T}} J \boldsymbol{u} \ge 0$、すなわち $J$ は半正定値。

解答

1. $\mathrm{diag}(\boldsymbol{a})\boldsymbol{1} = \boldsymbol{a}$ です。また $\boldsymbol{a}^{\mathsf{T}}\boldsymbol{1} = \sum_i a_i = 1$（ソフトマックスの定義から分子の総和が分母に等しい）なので $\boldsymbol{a}\boldsymbol{a}^{\mathsf{T}}\boldsymbol{1} = \boldsymbol{a}(\boldsymbol{a}^{\mathsf{T}}\boldsymbol{1}) = \boldsymbol{a}$ です。差を取って $J\boldsymbol{1} = \boldsymbol{a} - \boldsymbol{a} = \boldsymbol{0}$ を得ます。

意味はシフト不変性です。$\boldsymbol{1}$ 方向の方向微分が $\boldsymbol{0}$ ということは、$\boldsymbol{z}$ に定数ベクトル $t\boldsymbol{1}$ を足しても 1 次の変化がないということです。実際、定義に戻れば

$$\mathrm{softmax}(\boldsymbol{z} + t\boldsymbol{1})_i = \frac{e^{z_i + t}}{\sum_k e^{z_k+t}} = \frac{e^t e^{z_i}}{e^t \sum_k e^{z_k}} = \mathrm{softmax}(\boldsymbol{z})_i$$

で、厳密に不変です。数値計算で $\max_k z_k$ を引いてよいのはこの等式によります。

2. 成分で書くと

$$\boldsymbol{u}^{\mathsf{T}} J \boldsymbol{u} = \sum_i a_i u_i^2 - \Big(\sum_i a_i u_i\Big)^2 .$$

$a_i > 0$、$\sum_i a_i = 1$ なので、$\boldsymbol{a}$ を $\{1,\ldots,n\}$ 上の確率分布と見て、$U$ をその分布に従い値 $u_i$ を確率 $a_i$ で取る確率変数とすれば、右辺は $\mathbb{E}[U^2] - (\mathbb{E}[U])^2 = \mathrm{Var}(U) \ge 0$ です。

確率を持ち出さずに示すこともできます。$m := \sum_i a_i u_i$ と置くと

$$\sum_i a_i (u_i - m)^2 = \sum_i a_i u_i^2 - 2m\sum_i a_i u_i + m^2 \sum_i a_i = \sum_i a_i u_i^2 - 2m^2 + m^2 = \boldsymbol{u}^{\mathsf{T}} J \boldsymbol{u}$$

であり、左辺は非負の項の和なので非負です。ついでに、等号成立は全部の $u_i$ が等しいとき、すなわち $\boldsymbol{u} \in \mathrm{span}\{\boldsymbol{1}\}$ のときに限ることもわかり、1 の結果と整合します。

演習 9.4難

逆伝播の実装が正しいかを確かめるには、数値微分と突き合わせるのが定石です（gradient check）。1 変数の $C^3$ 級関数 $f$ について中心差分

$$D_h f(x) := \frac{f(x+h) - f(x-h)}{2h}$$

を考えます。$M_3 := \max_{|\xi - x| \le h} |f'''(\xi)|$ とし、$f$ の値の計算には相対誤差 $\epsilon$ 程度の丸め誤差が乗るとします（倍精度なら $\epsilon \approx 1.1 \times 10^{-16}$）。

1. 打ち切り誤差が $\big|D_h f(x) - f'(x)\big| \le \dfrac{M_3}{6}h^2$ で抑えられることを示してください。
2. 丸め誤差の寄与を $\dfrac{\epsilon |f(x)|}{h}$ と見積もり、両者の和を最小にする $h$ と、そのときの誤差の大きさを求めてください。$|f(x)| = M_3 = 1$、$\epsilon = 1.1\times10^{-16}$ で数値を出してください。

解答

1. テイラーの定理（定理 5.3［平均値の定理とテイラーの定理］、ラグランジュの剰余項付き、3 次まで）を $x$ のまわりで使います。ある $\xi_+ \in (x, x+h)$、$\xi_- \in (x-h, x)$ があって

$$f(x+h) = f(x) + hf'(x) + \frac{h^2}{2}f''(x) + \frac{h^3}{6}f'''(\xi_+), \qquad f(x-h) = f(x) - hf'(x) + \frac{h^2}{2}f''(x) - \frac{h^3}{6}f'''(\xi_-)$$

です。辺々引くと $f(x)$ の項と $f''$ の項が消えて

$$f(x+h) - f(x-h) = 2hf'(x) + \frac{h^3}{6}\big(f'''(\xi_+) + f'''(\xi_-)\big),$$

両辺を $2h$ で割ると

$$D_h f(x) - f'(x) = \frac{h^2}{12}\big(f'''(\xi_+) + f'''(\xi_-)\big) .$$

三角不等式と $|f'''(\xi_\pm)| \le M_3$ から $\big|D_hf(x) - f'(x)\big| \le \dfrac{h^2}{12}\cdot 2M_3 = \dfrac{M_3}{6}h^2$ です。$f''$ の項が打ち消し合うのが中心差分の利点で、前進差分 $\big(f(x+h)-f(x)\big)/h$ なら誤差は $O(h)$ にしかなりません。

2. $f(x\pm h)$ の計算値はそれぞれ $\epsilon|f|$ 程度の絶対誤差を持ちます。分子で最大 $2\epsilon|f|$、$2h$ で割って $\dfrac{\epsilon|f(x)|}{h}$ です。誤差の総和を

$$g(h) = \frac{M_3}{6}h^2 + \frac{\epsilon|f(x)|}{h} \qquad (h > 0)$$

と置きます。$g'(h) = \dfrac{M_3}{3}h - \dfrac{\epsilon|f(x)|}{h^2}$ で、$g'(h) = 0$ は $h^3 = \dfrac{3\epsilon|f(x)|}{M_3}$ と同値です。$g''(h) = \dfrac{M_3}{3} + \dfrac{2\epsilon|f|}{h^3} > 0$ なので、この停留点

$$h^{*} = \left(\frac{3\epsilon|f(x)|}{M_3}\right)^{1/3}$$

が最小点です。$|f| = M_3 = 1$、$\epsilon = 1.1\times10^{-16}$ を入れると $h^{*} = (3.3\times10^{-16})^{1/3} \approx 6.9\times10^{-6}$ です。このとき

$$g(h^{*}) = \frac{1}{6}(6.9\times10^{-6})^2 + \frac{1.1\times10^{-16}}{6.9\times10^{-6}} \approx 7.9\times10^{-12} + 1.6\times10^{-11} \approx 2.4\times10^{-11}$$

となります。つまり中心差分では $10^{-11}$ 程度の精度が限界で、$h$ をこれ以上小さくすると丸め誤差でかえって悪化します。

実務上の指針もここから出ます。gradient check では $h \approx 10^{-5}$ 前後を使い、逆伝播の値との相対差が $10^{-7}$ 程度なら合格、$10^{-3}$ を超えたら実装を疑う、という判定が使われます。命題 6.1 のとおりこのチェックは高価なので、パラメータを数個だけ抜き取って行います。

参考文献

• S. Linnainmaa, “Taylor expansion of the accumulated rounding error”, BIT Numerical Mathematics 16 (1976), 146–160. DOI: 10.1007/BF01931367 — リバースモード自動微分の最初の定式化。
• D. E. Rumelhart, G. E. Hinton, R. J. Williams, “Learning representations by back-propagating errors”, Nature 323 (1986), 533–536. DOI: 10.1038/323533a0 — 逆伝播をニューラルネットワークの学習として提示した論文。
• W. Baur, V. Strassen, “The complexity of partial derivatives”, Theoretical Computer Science 22 (1983), 317–330. DOI: 10.1016/0304-3975(83)90110-X — 勾配の計算コストが関数値の計算コストの定数倍で済むことの証明。
• A. Griewank, A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed., SIAM, 2008 — 第 3 章（リバースモード）と、checkpointing を扱う章。
• I. Goodfellow, Y. Bengio, A. Courville, Deep Learning, MIT Press, 2016 — 第 6 章 6.5 節（Back-Propagation and Other Differentiation Algorithms）、第 8 章（最適化の困難）。
• W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill, 1976 — 第 9 章（多変数関数の微分、連鎖律）。

Appendix: ミニバッチのテンソル形式

1 サンプルずつではなく、$B$ 個まとめて処理する形に書き直します。 実装では入力を列に並べた行列 $A^{(0)} = X \in \mathbb{R}^{n_0 \times B}$ を使い、

$$Z^{(\ell)} = W^{(\ell)} A^{(\ell-1)} + \boldsymbol{b}^{(\ell)}\boldsymbol{1}_B^{\mathsf{T}}, \qquad A^{(\ell)} = \sigma^{(\ell)}\big(Z^{(\ell)}\big)$$

とします（$\boldsymbol{1}_B \in \mathbb{R}^B$ は全成分 $1$ のベクトルで、第 2 項はバイアスを全列に複製する操作です）。損失はサンプルごとの損失の和 $E = \sum_{s=1}^{B} E_s$ とします。

勾配は「サンプルごとの外積の和」になります。 $\Delta^{(\ell)} \in \mathbb{R}^{n_\ell \times B}$ を、第 $s$ 列がサンプル $s$ に対する $\boldsymbol{\delta}^{(\ell)}$ である行列とします。$E$ が和の形なので、系 5.1 (iii) をサンプルごとに適用して足し合わせると

$$\nabla_{W^{(\ell)}} E = \sum_{s=1}^{B} \boldsymbol{\delta}^{(\ell)}_s \big(\boldsymbol{a}^{(\ell-1)}_s\big)^{\mathsf{T}} = \Delta^{(\ell)} \big(A^{(\ell-1)}\big)^{\mathsf{T}}, \qquad \nabla_{\boldsymbol{b}^{(\ell)}} E = \sum_{s=1}^{B}\boldsymbol{\delta}^{(\ell)}_s = \Delta^{(\ell)}\boldsymbol{1}_B$$

が得られます。中央の等号は「行列の積は列ベクトルの外積の和に分解できる」という行列の積（定義 4.1［行列と連立一次方程式］）の基本性質です。$\Delta$ の漸化式も列ごとに同じ式なので、そのまま行列形になります。

$$\Delta^{(\ell)} = \sigma^{(\ell)\prime}\big(Z^{(\ell)}\big) \odot \Big( W^{(\ell+1)\mathsf{T}} \Delta^{(\ell+1)} \Big)$$

ここで $\odot$ は行列の成分ごとの積です。ミニバッチ化によってループが行列積 1 回に置き換わり、GPU の演算器を埋められるようになります。深層学習の実装がほぼすべて行列積の羅列になっているのは、この書き換えの結果です。