Machine Learning

Stanford Univ, Coursera


Neural Networks: Learning

Cost Function

Neural Network の Cost Function
$\displaystyle L = \mbox{レイヤの総数}$
$\displaystyle s_l = \mbox{レイヤ$l$ のユニット数 (常時1のバイアスユニットは含まない)}$
$\displaystyle K = \mbox{クラスの数}$

$\displaystyle h_{\Theta}(x) \in \boldsymbol{R}^{K}$
$\displaystyle (h_{\Theta}(x))_{i} = \mbox{$i$-th output}$

$\displaystyle \begin{eqnarray} J(\Theta) & = & -\frac{1}{m} \sum_{i=1}^{m} \sum_{k=1}^{K} ( y_k^{(i)} \log (h_{\Theta}(x^{(i)}))_{k} + (1 - y_k^{(i)}) \log (1 - (h_{\Theta}(x^{(i)}))_{k} ) ) + \frac{\lambda}{2m} \sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}} ({\Theta_{ji}^{(l)}})^2 \end{eqnarray} $

式の中の $\displaystyle \sum_{k=1}^K$ の部分は、最終出力のノード数 ( $K$クラスなので $K$ 個) の回数だけループするためである。

式の中で最後に加算している部分は、レイヤ $l$ に含まれる $i$ 番目のノードから、レイヤ $l+1$ に含まれる $j$ 番目のノードへの重み $\Theta_{ji}^{(l)}$ に関する正則化(regularization)の和である。


Backpropagation

$J(\Theta)$ を最小化するのが目的である。そのためには $\frac{\partial}{\partial \Theta_{ji}^{(l)}} J(\Theta)$を計算する必要がある。
Neural Network における Backpropagation アルゴリズム
training set: $(x^{(1)}, y^{(1)})$, $(x^{(2)}, y^{(2)})$, $\cdots$, $(x^{(m)}, y^{(m)})$

${\triangle}_{ij}^{(l)} = \boldsymbol{0}$    // for all $l$, $i$, $j$
for $i=1$ to $m$      // 変数 $i$ はデータセット番号
   $\boldsymbol{a}^{(1)} = x^{(i)}$      // 最初のレイヤは入力そのもの
   for $l=2$ to $L$      // 各レイヤについて
     $a^{(l)} = g( {\Theta}^{(l-1)} a^{(l-1)} )$    // forward propagation を行って $a^{(l)}$ を求める
   ${\delta}^{(L)} = a^{(L)} - y^{(i)}$      // 最終結果と $y^{(L)}$ の誤差を求める
   for $l=L-1$ to $2$ // 後から前に向かってレイヤ2まで誤差を求める。${\delta}^{(1)}$ はall 0
     ${\delta}^{(l)} = (({\Theta}^{(l)})^T \delta^{(l+1)}) g'(a^{(l)})$    // [Note 1] [Note 2]参照
   ${\triangle}_{ij}^{(l)} = {\triangle}_{ij}^{(l)} + \boldsymbol{a}_{j}^{(l)} \boldsymbol{\delta}_i^{(l+1)}$      // ベクトル計算では $\boldsymbol{\triangle}^{(l)} = \boldsymbol{\delta}^{(l+1)} (\boldsymbol{a}^{(l)})^T$

$\displaystyle D_{ij}^{(l)} = \frac{1}{m} {\triangle}_{ij}^{(l)} + \lambda {\Theta}_{ij}^{(l)}$    if $j \neq 0$      // [Note 3]参照
$\displaystyle D_{ij}^{(l)} = \frac{1}{m} {\triangle}_{ij}^{(l)}$        if $j=0$
  

[Note 1] sigmoid 関数の式は $\displaystyle g(x) = \frac{1}{1+e^{-x}} = (1+e^{-x})^{-1}$ .
微分を計算すると
$\displaystyle \begin{eqnarray} g'(x) &=& -(1+e^{-x})^{-2} (- e^{-x}) \\ &=& \frac{e^{-x}}{(1+e^{-x})^2} \end{eqnarray} $
ここで
$\displaystyle \begin{eqnarray} g(x) (1-g(x)) &=& \frac{1}{1+e^{-x}} (1 - \frac{1}{1+e^{-x}}) \\ &=& \frac{1}{1+e^{-x}} (1 - \frac{e^{-x}}{1+e^{-x}}) \\ &=& \frac{e^{-x}}{1+e^{-1}} \end{eqnarray} $
したがってsigmoid関数では $g'(x) = g(x) (1-g(x))$ が成り立つ。 そもそもactivation関数にsigmoid 関数を使うのは微分を簡単に計算できるからである。
よって $g'(a^{(l)}) = g(a^{(l)}) (1-g(a^{(l)}))$ を計算すればよい。

[Note 2] $y = f(x)$ という関数を考える。$x=x_0$ のときの$y$の値は $y_0 = f(x_0)$ で計算できる。 もしも$x$が $x=x_0$ の近くで少しだけ変動すると $y$は $\displaystyle \frac{d y}{d x}|_{x=x_0}$ だけ影響を受けることを意味する。 これは $y$ を$\delta$だけ変化させたければ $x$ を $\delta \displaystyle \frac{d y}{d x}|_{x=x_0}$ だけ変化させればよいことを意味する。

$y = f(x_1, x_2, \cdots , x_n) = f(\boldsymbol{x})$ という多変数関数を考える。 $\boldsymbol{x}=\boldsymbol{x}_0=(x_{01}, x_{02}, \cdots , x_{0j}, \cdots, x_{0n})$ のときの$y$の値は $y_0 = f(\boldsymbol{x}_0)$ で計算できる。 もしも $\boldsymbol{x}$ の中の $x_{j}$が$x_{0j}$の近くで少しだけ変動すると $y$は $\displaystyle \frac{\partial y}{\partial x_{j}}|_{x_j=x_{0j}}$ だけ影響を受けること意味する。 これは $y$ を$\delta$だけ変化させたければ $x_j$ に関しては $\delta \displaystyle \frac{\partial y}{\partial x_{j}}|_{\boldsymbol{x}=\boldsymbol{x}_0}$ だけ変化させればよいことを意味する。

レイヤ $l$ のノード$j$からレヤ$l+1$のノード$i$へのリンクの重みを${\theta}_{ij}$と表すことにする。 レイヤ $l$ からレイヤ $l+1$ へのforward propagation で $a_j^{(l)}$ が $a_i^{(l+1)}$ に与える影響 $\displaystyle \frac{\partial a_i^{(l+1)}}{\partial a_j^{(l)}}$ を計算してみると
$\displaystyle \begin{eqnarray} z_i^{(l+1)} & = & \cdots + {\theta}_{ij}^{(l)} a_j^{(l)} + \cdots \\ a_i^{(l+1)} & = & g(z_i^{(l+1)}) \\ \frac{\partial a_i^{(l+1)}}{\partial z_i^{(l+1)}} & = & a_i^{(l+1)} (1 - a_i^{(l+1)}) \\ \frac{\partial z_i^{(l+1)}}{\partial a_j^{(l)}} & = & {\theta}_{ij}^{(l)} \\ \therefore \frac{\partial a_i^{(l+1)}}{\partial a_j^{(l)}} & = & {\theta}_{ij}^{(l)} a_i^{(l+1)} (1 - a_i^{(l+1)}) \\ \end{eqnarray} $

back propagationにおいて、レイヤ$l$のノード$j$がレイヤ$l+1$のノード$i$から影響を受ける誤差 ${\delta}_{ij}$ は
$\displaystyle \begin{eqnarray} {\delta}_{ij} & = & {\delta}_i^{(l+1)} \frac{\partial a_i^{(l+1)}}{\partial a_j^{(l)}} \\ & = & {\delta}_i^{(l+1)} \frac{\partial a_i^{(l+1)}}{\partial z_i^{(l)}} \frac{\partial z_i^{(l+1)}}{\partial a_j^{(l)}} \\ & = & {\delta}_i^{(l+1)} a_i^{(l+1)} (1 - a_i^{(l+1)}) {\theta}_{ij}^{(l)} \\ \therefore {\delta}_j^{(l)} & = & \sum_{i} {\delta}_{ji}^{(l)} \\ & = & \sum_{i} {\theta}_{ij}^{(l)} {\delta}_i^{(l+1)} a_i^{(l+1)} (1 - a_i^{(l+1)}) \end{eqnarray} $

[Note 3] $D$ は値を積算するのに用いられている。意味は $\displaystyle \frac{\partial}{\partial {\Theta}_{ij}^{(l)}} J(\Theta) = D_{ij}^{(l)}$


Backpropagation Intuition

個人的な感想だが、この説明はよくないと思う。上記の [Note 2] の方が理解しやすいと思う。


5-1 test

advanced 最適化手法(fminunc, conjugate gradient, BFGS, L-BFGS など)の一つを用いて、 $\Theta$の関数として $J(\Theta)$ を最小化する。 計算すべきは?

5-2 test

2個のtraining example ($x^{(1)}$, $y^{(1)}$), ($x^{(2)}$, $y^{(2)}$) を考える。 gradient を計算する正しい一連の操作はどれか?
Yoshihisa Nitta

http://nw.tsuda.ac.jp/