📂機械学習

逆伝播アルゴリズム

この文は逆転派アルゴリズムの原理を数学専攻者が理解しやすいように作成された。

表記法

上図のような 人工ニューラルネットワーク が与えられたとする。$\mathbf{x} = (x_{1}, x_{2}, \dots, x_{n_{0}})$は入力^input、 $y_{j}^{l}$は$l$番目の層の$j$ノード、$\hat{\mathbf{y}} = (\hat{y}_{1}, \hat{y}_{2}, \dots, \hat{y}_{\hat{n}})$ドルは出力^outputである。

$L \in \mathbb{N}$は、隠匿層^{hidden layer}の個数であり、$\mathbf{n}=(n_{0}、n_{1}、\dots、n_{L}、\hat{n}) \in \mathbb{N}^{N}=(n)、$の成分は順に入力層、$L$個の隠匿層と出力層のノード数を意味する。 また、便宜上、$0$番目の隠匿層は入力層を意味し、$L+1$番目の隠匿層は出力層を意味するとする。

$w_{ji}^{l}$は、$l$の次の層の$i$のノードとその次の層の$j$のノードを連結する加重値を表す。 すると、各階から次の階への伝播は、以下のGIFのように起こる。

ここで $\phi$ は任意の活性化関数 である。 $l$ 番目の層から次の層の $j$ 番目のノードに伝達される線形結合を $v_{i}^{l}$で表記しよう。

$$ \begin{align*} v_{j}^{l} &= \sum _{i=1}^{n_{l}} w_{ji}^{l}y_{i}^{l} \\ y_{j}^{l+1} &= \phi ( v_{j}^{l} ) = \phi \left( \sum \nolimits_{i=1}^{n_{l}} w_{ji}^{l}y_{i}^{l} \right) \end{align*} $$

これを定理すると次のようになる。

記号	意味
$\mathbf{x}=(x_{1}, x_{2}, \dots, x_{n_{0}})$	入力
$y^{l}_{j}$	$l$ 番目の層の $j$ 番目のノード
$\hat{\mathbf{y}} = (\hat{y}_{1}, \hat{y}_{2}, \dots, \hat{y}_{\hat{n}} )$	出力
$n_{l}$	$l$ 番目の層のノード数
$w_{ji}^{l}$	$l$ 番目の層の $i$ 番目のノードと その次の層の $j$ 番目のノードを接続する重み付け
$\phi$	活性化関数
$v_{j}^{l} = \sum \limits _{i=1} ^{n_{l}} w_{ji}^{l}y_{i}^{l}$	線形結合
$y^{l+1}_{j} = \phi (v_{j}^{l})$	$l$ 番目の階から次の階への 電波

定理

$E = E(\hat{\mathbf{y}})$を微分可能な適切な損失関数とする。 それでは、$E$を最適化する方法は、各層での加重値$w_{ji}^{l}$を次のようにアップデートするものである。

$$ \begin{equation} w_{ji}^{l} \leftarrow w_{ji}^{l} + \alpha \delta^{l}_{j} y_{i}^{l} \label{thm} \end{equation} $$

この時、$\alpha$は学習率で、$\delta_{j}^{l}$ は以下の通りである。

$l=L$の時、

$$ -\delta_{j}^{L} = \phi ^{\prime} (v_{j}^{L}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{j}} $$

$l \in \left\{ 0,\dots, L-1 \right\}$の時、

$$ \delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \sum_{i=1}^{n_{l}} \delta_{i}^{l+1} w_{i j}^{l+1} $$

説明

$(1)$を見てみよう。 $l$番目の層と$l+1$番目の層の間の加重値を更新する時、$l$番目のノードの$y_{j}^{l}$に依存するということですが、各層の出力に応じて最終的に出力$\hat{\mathbf{y}}$が決定されるので当然と見ることができる。 また、$y_{j}^{l}$は$l$番目から$l+1$番目の層に伝播される時の入力と見ることができるが、これは線形回帰モデルでLMS^{Least Mean Squares}で学習する方法と似ている。

$$ \mathbf{w} \leftarrow \mathbf{w} - \alpha (\mathbf{w}^{T}\mathbf{x} - \mathbf{y}) \mathbf{x} $$

一方、各層での出力$y_{j}^{l}$は入力層から出力層として計算される反面、最適化のための$\delta_{j}^{l}$ は次のように出力層から入力層に逆に計算されるため、このような最適化手法を逆伝播アルゴリズム^{back propagation algorithm}という。

$$ \begin{align*} \delta_{j}^{L} &= - \phi ^{\prime} (v_{j}^{L}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{j}} \\ \delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \delta_{j}^{L} w_{ij}^{L} \\ \delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \delta_{i}^{L-1} w_{ij}^{L-1} \\ \delta_{j}^{L-3} &= \phi ^{\prime} (v_{j}^{L-3}) \sum _{i} \delta_{i}^{L-2} w_{ij}^{L-2} \\ &\vdots \\ \delta_{j}^{1} &= \phi ^{\prime} (v_{j}^{1}) \sum _{i} \delta_{i}^{2} w_{ij}^{2} \\ \delta_{j}^{0} &= \phi ^{\prime} (v_{j}^{0}) \sum _{i} \delta_{i}^{1} w_{ij}^{1} \end{align*} $$

証明

入力層から出力層への計算が終わったとする。 加重値を損失関数$E$が減る方向に修正する方法は傾斜下降法を使えば次のようになる。

$$ \begin{equation} w_{ji}^{l} \leftarrow w_{ji}^{l} - \alpha \dfrac{\partial E(\hat{\mathbf{y}})}{\partial w_{ji}^{l} } \label{gradesent} \end{equation} $$

それぞれの$y_{i}^{l}$は与えられた値なので、偏微分部分を計算できる形で解くことができる。 右辺の偏微分は連鎖法則によって次のようになる。

$$ \begin{equation} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial w_{ji}^{l}} = \dfrac{\partial E(\hat{\mathbf{y}}) }{\partial v_{j}^{l}} \dfrac{\partial v_{j}^{l}}{\partial w_{ji}^{l}} = \dfrac{\partial E(\hat{\mathbf{y}})}{\partial v_{j}^{l}} y_{i}^{l} \label{chainrule} \end{equation} $$

$(3)$の右辺の偏微分を$-\delta_{j}^{l}$ とすると、$(2)$ から $(1)$ を得る。

$$ w_{ji}^{l} \leftarrow w_{ji}^{l} + \alpha \delta^{l}_{j} y_{i}^{l} $$

各層で $\delta_{j}^{l}$ を次のように求める。

• $l=L$の場合

  $j \in \left\{ 1, \dots, \hat{n} \right\}$ に対して次が成立する。

  $$ \begin{equation} -\delta_{j}^{L} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L}} = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial \hat{y}_{j}} \dfrac{d \hat{y}_{j}}{d v_{j}^{L}} \label{deltamL} \end{equation} $$

  この時、$\hat{y}_{j} =\phi (v_{j}^{L})$ であるから次を得る。

  $$ -\delta_{j}^{L} (t) =\phi ^{\prime} (v_{j}^{L}(t)) \dfrac{\partial E (\hat{\mathbf{y}})}{\partial \hat{y}_{j}} $$

■

• $l=L-1$の場合

  $j \in \left\{ 1, \dots, n_{L-1} \right\}$については以下の通りである。

  $$ -\delta_{j}^{L-1} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L-1}} = = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial y_{j}^{L}} \dfrac{d y_{j}^{L}}{d v_{j}^{L-1}} $$

  この時$y_{j}^{L} =\phi (v_{j}^{L-1})$ であるので、次を得る。

  $$ -\delta_{j}^{L-1} = = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial y_{j}^{L}} \dfrac{\partial y_{j}^{L}}{\partial v_{j}^{L-1}} = = \phi ^{\prime} (v_{j}^{L-1}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L}} $$

  右辺の偏微分は連鎖法則によって次のように計算される。

  $$ \begin{align*} -\delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L}} \\ \\ &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial y_{j}^{L}} \\ \\ &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \dfrac{\partial v_{i}^{L}}{\partial y_{j}^{L}} \end{align*} $$

  ここで $(4)$ と ${\color{green}v_{i}^{L}=\sum_{j}w_{ij}^{L}y_{j}^{L}}$ により、次を得る。

  $$ \begin{align} && -\delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i=1} {\color{blue}\dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial v_{i}^{L}}} {\color{green} \dfrac{d v_{i}^{L}}{d y_{j^{L}}} } \nonumber \\ && &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} {\color{blue} -\delta_{i}^{L}} {\color{green} w_{ij}^{L} }\nonumber \\ {}\nonumber \\ \implies && \delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \delta_{i}^{L} w_{ij}^{L} \label{deltajL-1} \end{align} $$

■

• $l=L-2$の場合

  $j \in \left\{ 1, \dots, n_{L-2} \right\}$については以下の通りである。

  $$ -\delta_{j}^{L-2} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L-2}} = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial y_{j}^{L-1}} \dfrac{d y_{j}^{L-1}}{d v_{j}^{L-2}} $$

  この時$y_{j}^{L-1} =\phi (v_{j}^{L-2})$ であるから次を得る。

  $$ -\delta_{j}^{L-2} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} \dfrac{d y_{j}^{L-1}}{d v_{j}^{L-2}} = \phi ^{\prime} (v_{j}^{L-2}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} $$

  右辺の偏微分は連鎖法則によって次のように計算される。

  $$ \begin{align*} -\delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \dfrac{\partial v_{i}^{L}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \sum _{k} \dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} \dfrac{\partial y_{k}^{L}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \sum _{k} \dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} \dfrac{d y_{k}^{L}}{d v_{k}^{L-1}} \dfrac{\partial v_{k}^{L-1}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} {\color{blue}\dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}}} {\color{red}\dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} } {\color{green}\dfrac{d y_{k}^{L}}{d v_{k}^{L-1}}} {\color{purple}\dfrac{d v_{k}^{L-1}}{\partial y_{j}^{L-1}}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} {\color{blue} -\delta_{i}^{L}} {\color{red} w_{ik}^{L}} {\color{green} \phi^{\prime}(v_{k}^{L-1})} {\color{purple} w_{kj}^{L-1}} \end{align*} $$

  したがって、次を得る。

  $$ \delta_{j}^{L-2} = -\phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} \delta_{i}^{L} w_{ik}^{L} \phi^{\prime}(v_{k}^{L-1}) w_{kj}^{L-1} $$

  このとき、$(5)$ によって次が成立する。

  $$ \sum _{i} \delta_{i}^{L} w_{ik}^{L} \phi^{\prime}(v_{k}^{L-1}) = \phi^{\prime}(v_{k}^{L-1}) \sum _{i} \delta_{i}^{L} w_{ik}^{L} = \delta_{k}^{L-1} $$

  したがって、次を得る。

  $$ \begin{align*} \delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \delta_{k}^{L-1} w_{kj}^{L-1} \\ \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \delta_{i}^{L-1} w_{ij}^{L-1} \end{align*} $$

■

• 一般化: $l \in \left\{1, \dots, L-1 \right\}$

  上記の結果に基づき、次のように一般化することができる。$j \in \left\{ 1, \dots, n_{l} \right\}$については以下の通りである。

  $$ -\delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{l}} $$

  右辺の偏微分を連鎖法則で解くと次のようになる。

  $$ \begin{align*} &\quad \delta_{j}^{l} \\ &= -\phi ^{\prime} (v_{j}^{l}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{\partial \hat{y}_{i_{(1)}}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{\partial y_{i_{(2)}}^{L}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{\partial y_{i_{(3)}}^{L-1} }{ \partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{d y_{i_{(3)}}^{L-1} }{d v_{i_{(3)}}^{L-2} } \frac{\partial v_{i_{(3)}}^{L-2} }{ \partial y_{j}^{l}} \\ & \quad \vdots \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{d y_{i_{(3)}}^{L-1} }{d v_{i_{(3)}}^{L-2} } \frac{\partial v_{i_{(3)}}^{L-2} }{ \partial y_{i_{(4)}}^{L-2}} \cdots \frac{d y_{i_{(L-l+1)}}^{l+1} }{d v_{i_{(L-l+1)}}^{l} } \frac{\partial v_{i_{(L-l+1)}}^{l} }{ \partial y_{j}^{l}} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} -\delta_{i_{(1)}}^{L} w_{i_{(1)}i_{(2)}}^{L} \phi^{\prime}(v_{i_{(2)}}^{L-1}) w_{i_{(2)} i_{(3)}}^{L-1} \phi^{\prime}( v_{i_{(3)}}^{L-2} ) w_{i_{(3)} i_{(4)}}^{L-2} \cdots \phi^{\prime}(v_{L-l+1}^{l})w_{i_{(L-l+1)} j}^{L} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \delta_{i_{(2)}}^{L-1}w_{i_{(2)} i_{(3)}}^{L-1} \phi^{\prime}( v_{i_{(3)}}^{L-2} ) w_{i_{(3)} i_{(4)}}^{L-2} \cdots \phi^{\prime}(v_{L-l+1}^{l})w_{i_{(L-l+1)} j}^{L} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \delta_{i_{(3)}}^{L-2} w_{i_{(3)} i_{(4)}}^{L-2} \cdots w_{i_{(L-l)} j}^{L} \\ &\quad \vdots \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \delta_{i_{(L-l)}}^{l+1} w_{i_{(l-l)} j}^{l} \end{align*} $$

  したがって、定理すると次のようになる。

  $$ \delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \sum_{i} \delta_{i}^{l+1} w_{ij}^{l+1} $$

  ■