読者です 読者をやめる 読者になる 読者になる

【Deep Learning】計算グラフによる誤差逆伝播法(Back propagation)の理解

機械学習

背景

  • ニューラルネットの重みなどのパラメータ決定を勾配法で行う
  • 勾配法の計算の際に損失関数の微分が必要
  • 微分計算の高速化が求められる.
  • その高速化のために誤差逆伝播法を用いるのが一般的
  • その誤差逆伝播法を数式ではなく,計算グラフから理解してみる.

計算グラフとは

複雑な処理からなる計算を可視化する方法として,計算グラフ(Computational graph)がある.

例えば,{e = (a + b)*(b + 1)}という数式を考える.
3つの演算からなり,加算が2つで乗算が1つ.
この式を計算グラフ化すると下図のようになる.

f:id:yusuke_ujitoko:20161231102417p:plain:w500

この式の値をもとめるには,入力変数に特定の値を代入して,ノードを順に計算していく.
たとえば,{a = 2}{b = 3}とすると, 式の値は20になる.

f:id:yusuke_ujitoko:20161231102756p:plain:w500

計算グラフの自動微分

アルゴリズムで定義された関数を解析し,微分を計算するアルゴリズムを導出する技術のことを自動微分(Automatic differentiation)という.

計算グラフを使ってその自動微分を計算してみよう.
たとえば上図で,a方向のeの微分や,b方向のeの微分は何だろう.

計算グラフを見ると,直接接続されているノード間では,微分を計算できそうだ.
たとえば,a方向のcの微分や,b方向のcの微分などだ.
これらを図に加えると以下のようになる.

f:id:yusuke_ujitoko:20161231225452p:plain:w500

では,直接接続されていないノード間の微分はどう求めるのか?
たとえばaはどうeに影響するのかを追ってみると,
aは1変化したら,上図からcは1変化する.
cが1変化すると,上図からeはd変化する.
結果的に,aが1変化するとeはd変化することになる.

あるノードからあるノードへの微分を求めるときには,道筋の微分係数を合計する.
例えばbに対するeの微分係数は,b→c→eとb→d→eの2つの道筋を考えて, {} $$ \frac{\partial e}{\partial b} = 1 * d + 1 * e $$ となる.

この方法は直観的であり,自動微分の中でもforward-modeと呼ばれる方法だ.
でもニューラルネットの場合,後述するreverse-modeの方が適している.

forward-mode自動微分とreverse-mode自動微分

計算グラフから微分を導く方法には2種類ある.
forward-mode とreverse-modeだ.

どちらも基本原理は連鎖律を用いた微分の分解である.
たとえば,シンプルな合成関数である{
y =
g(h(x)) =
g(w)
} に対して連鎖律を適用すると,以下を得る. {} $$ \frac{dy}{dx} = \frac{dy}{dw} \frac{dw}{dx} $$

forward-modeは連鎖律を内側から外側に計算し,
reverse-modeは連鎖律を外側から内側に計算する.

forward-mode自動微分

forward-modeでは,最初に微分を行う入力変数を決めて,全ての中間変数の微分を計算していく.

下図の {a}{b}{c}{d}{e}の5つの変数の入力変数{b}に対する微分を計算すると,

f:id:yusuke_ujitoko:20161231102417p:plain:w500

以下のようになる.

f:id:yusuke_ujitoko:20161231234352p:plain:w500
  • {
\frac{\partial a}{\partial b} =
0
}

  • {
\frac{\partial b}{\partial b} =
1
}

  • {
\frac{\partial c}{\partial b} =
\frac{\partial (a + b)}{\partial b} =
1
}

  • {
\frac{\partial d}{\partial b} =
\frac{\partial (b + 1)}{\partial b} =
1
}

  • {
\frac{\partial e}{\partial b} =
\frac{\partial (c \cdot d)}{\partial b} =
\frac{\partial c}{\partial b} \cdot d + c \cdot \frac{\partial e}{\partial b} =
d + c
}

{\frac{\partial e}{\partial e}}の計算をするときに,既に算出した下流の{\frac{\partial e}{\partial c}}{\frac{\partial e}{\partial d}}を利用している.

このように,下流の計算で上流の結果を利用するのが,forward-modeの特徴となる.
出力変数が多いときにはこのforward-modeを使うのが計算量で有利.

reverse-mode自動微分

reverse-modeでは,1つの出力変数について,全ての中間変数に対する微分を計算していく.
例を考えてみる.
出力変数のeについて,各中間変数に対する微分を計算してみる.
reverse-modeでは計算グラフの後ろ側から計算していくイメージだ.

f:id:yusuke_ujitoko:20161231234829p:plain:w500
  • {
\frac{\partial e}{\partial e} =
1
}

  • {
\frac{\partial e}{\partial d} =
c
}

  • {
\frac{\partial e}{\partial c} =
d
}

  • {
\frac{\partial e}{\partial b} =
\frac{\partial e}{\partial d} \frac{\partial d}{\partial b} + \frac{\partial e}{\partial c} \frac{\partial c}{\partial b}=
c \cdot \frac{\partial (b + 1)}{\partial b} + d \cdot \frac{\partial (a + b)}{\partial b}=
c + d
}

  • {
\frac{\partial e}{\partial a} =
\frac{\partial e}{\partial c} \frac{\partial c}{\partial a} =
d \cdot \frac{\partial (a + b)}{\partial a} =
d
}

{\frac{\partial e}{\partial a}}{\frac{\partial e}{\partial b}}の計算をするときに,既に算出した下流の{\frac{\partial e}{\partial c}}{\frac{\partial e}{\partial d}}を利用している.

このように,上流の計算で下流の結果を利用するのが,reverse-modeの特徴となる.
したがって,入力変数が多いときにはこのreverse-modeを使うのが計算量で有利と言える.

ニューラルネットの場合, 微分を得たい入力変数は高次元で,出力変数はスカラーであるので, reverse-modeを利用する.

なお誤差逆伝播法はこのreverse-modeの1例である. これ以降はreverse-modeに限定して話を進める.

参考