なぜ誤差逆伝播法は逆方向に進むのか

バックプロパゲーションが後方に進む理由

ニューラルネットワークの学習に使用されるアルゴリズムであるバックプロパゲーション（誤差逆伝播法）(Rumelhart et al., 1986)の一般的な説明は、各ノードの誤差を後方に伝播させるというものです。しかし、私がこのアルゴリズムを初めて学んだとき、直接的な答えが見つからない疑問がありました。なぜ後方に進む必要があるのだろうか？ ニューラルネットワークは複合関数に過ぎず、連鎖律を用いて複合関数の導関数を計算する方法はわかっています。なぜ順伝播で勾配を計算しないのでしょうか？この疑問に答えることで、バックプロパゲーションへの理解が深まることがわかりました。

読者はニューラルネットワークと勾配降下法を大まかに理解しており、バックプロパゲーションにもある程度精通していると仮定します。まず、いくつかの有用な概念と記法を用いてバックプロパゲーションのセットアップを行い、その後、順伝播アルゴリズムがなぜ最適ではないのかを説明します。

セットアップ

バックプロパゲーションの目標は、ニューラルネットワーク $f$ のすべての重み $\theta_i$ について効率的に $\partial f / \partial \theta_i$ を計算することであることを思い出してください。問題を整理するために、任意の重み $\theta_1$ と $f$ の中のあるノード $v$ について考えてみましょう。

［画像: ニューラルネットワークの計算グラフの一部を示す図。ノードvは、重みθ1、θ2、...、θnと入力t1、t2、...、tnに接続されている。］

明確にするために、ノード $v$ は、入力の重み付き和を活性化関数 $\sigma$ を通した後のノードの出力値を指します。つまり：

\begin{aligned}
u &= \theta_1 t_1 + \theta_2 t_2 + \dots + \theta_n t_n \ v &= \sigma(u)\end{aligned}

典型的な図では、$u$、$\sigma$、$v$ はすべて単一のノードとして表され、破線で示されることに注意してください。私の考えでは、バックプロパゲーションを理解するために必要な最も重要な観察はこれです：$\partial f / \partial \theta_1$ の計算の大部分は、連鎖律のおかげで、各ノードで局所的に行うことができます。

$\frac{\partial f}{\partial \theta_1} = \frac{\partial f}{\partial v} \frac{\partial v}{\partial u} \frac{\partial u}{\partial \theta_1}$

$\partial v / \partial u$ は解析的に計算できます。これは $\sigma$ の定義に依存するだけです。また、$\partial u / \partial \theta_1 = t_1$ であることもわかっています。したがって、各ノード $v$ で、$\partial f / \partial v$ がわかっていれば、$\partial f / \partial \theta_1$ を計算できます。

$\partial f / \partial v$ を計算する上での課題は、下流のノードが $v$ の値に依存することです。幸いなことに、多変数連鎖律が答えを提供します。各 $w_j$ が $v$ の単一変数関数 $w_j(v)$ であるような多変数関数 $g(w_1, w_2, \dots, w_m)$ が与えられた場合、多変数連鎖律は次のように述べています。

$\frac{\partial g}{\partial v} = \frac{\partial}{\partial v} g(w_1(v), w_2(v), \dots, w_m(v)) = \sum_j \frac{\partial g}{\partial w_j} \frac{\partial w_j}{\partial v}$

したがって、任意の重み $\theta_i$ について $\partial f / \partial \theta_i$ を計算できるため、順伝播でバックプロパゲーションを実装しようとするために必要な仕組みが整っています。どのようなことが起こるか見てみましょう。

繰り返し現れる項

任意の重み $\theta_i$ の偏導関数 $\partial f / \partial \theta_i$ を計算できる順伝播アルゴリズムを求めます。上記の議論から、ノード $v$ において、これは次と同等であることが示されました。

$\frac{\partial f}{\partial \theta_i} = \frac{\partial f}{\partial v} \frac{\partial v}{\partial \theta_i}$

表記を簡単にするために、中間変数 $u$ は省略しました。順伝播アルゴリズムを設計するために、重要な事実を形式化しましょう。ノード $b$ がノード $a$ に依存する有向計算グラフにおいて、ノード $b$ の任意の時点で $\partial b / \partial a$ を計算することは不可能です。

［画像: 計算グラフの一部を示す図。ノードbはノードaに依存している。］

この主張は明白であるはずです。もし計算グラフが関数 $f(a) = b$ を表すなら、$f$、したがって $b$ にアクセスせずに $f'(a)$ を計算することは不可能です。

私たちのセットアップでは、ノード $v$ に依存するすべての下流ノード $w_j$ について、$\partial w_j / \partial v$ をノード $v$ で計算することは不可能です。したがって、$\partial f / \partial v$ を計算するために、多変数連鎖律を用いて項を分解し、$\partial f / \partial \theta_i$ を計算するために必要な他の項を $v$ に依存する各ノード $w_j$ に順伝播させる必要があります。

$\frac{\partial f}{\partial \theta_i} = \Big( \sum_j \frac{\partial f}{\partial w_j} \underbrace{\frac{\partial w_j}{\partial v}}_{\text{ $w_j$ で計算}} \Big) \overbrace{\frac{\partial v}{\partial \theta_i}}_{\text{順伝播させる}}$

このようなアルゴリズムは計算量が爆発することがわかります。なぜなら、同じメッセージを何度も順伝播させているからです。例えば、$\theta_i$ と同じ層にある別の重み $\theta_k$ について $\partial f / \partial \theta_i$ と $\partial f / \partial \theta_k$ を計算したい場合、$\partial v / \partial \theta_i$ と $\partial v / \partial \theta_k$ を別々に計算する必要がありますが、他のすべての項は繰り返し現れます。

\begin{aligned}
\frac{\partial f}{\partial \theta_i} = \overbrace{ \Big( \sum_j \Big( \sum_k \frac{\partial f}{\partial z_k} \frac{\partial z_k}{\partial w_j} \Big) \frac{\partial w_j}{\partial v} \Big)}_{\text{繰り返し現れる項}} \color{#11accd}{ \frac{\partial v}{\partial \theta_i} } \ \frac{\partial f}{\partial \theta_k} = \Big( \sum_j \Big( \sum_k \frac{\partial f}{\partial z_k} \frac{\partial z_k}{\partial w_j} \Big) \frac{\partial w_j}{\partial v} \Big) \color{#bc2612}{ \frac{\partial v}{\partial \theta_k} }
\end{aligned}

繰り返し現れる項のメッセージパッシングの図を以下に示します。

［画像: 計算グラフの一部を示す図。ノードvから下流のノードへのメッセージパッシングと、繰り返し現れる項の計算パスが示されている。］

この図こそが、バックプロパゲーションが後方に進む理由を理解する鍵だと私は思います。これが重要な洞察です。もし下流の項、例えば $\partial w_j / \partial v$ にすでにアクセスできていれば、それらの項をノード $v$ に後方にメッセージパッシングして $\partial f / \partial v$ を計算できます。各ノードは自身の局所的な項を渡すだけなので、後方パスはノード数に対して線形時間で実行できます。

後方パス

有向非巡回グラフで導関数を計算しようとすることから、バックプロパゲーションに至る方法が明確になったことを願っています。ノード $a$ に依存するノード $b$ が与えられた場合、$\partial b / \partial a$ を単純に $a$ に後方へメッセージパッシングします。多変数連鎖律はバックプロパゲーションの正当性を証明するのに役立ちます。下流の重み $w_j$ を持つノード $v$ について、もし $v$ が後方へ伝播するメッセージを単純に合計するなら、望ましい導関数を計算します。

$\frac{\partial f}{\partial v} = \sum_j \frac{\partial f}{\partial w_j} \frac{\partial w_j}{\partial v}$

バックプロパゲーションが解決する主要な計算問題を理解すれば、誤差を後方に伝播させるという標準的な説明がより理にかなってくると思います。このプロセスは、一種のクレジット割り当て問題の解決策と見なすことができます。各ノードは、上流の隣接ノードに何が間違っていたかを伝えます。しかし、アルゴリズムがこのようになっている理由は、ナイーブな順伝播ソリューションではノード数に対して二次的な実行時間になるためです。