Friday, February 6, 2015

Step by Step Neural Network: Mathematical Foundation

Let's derive the formula for optimising parameters of a single hidden layer neural network.
ここでは隠れ層一つのニューラルネットワークを最適化する式を導出する。



Forward Pass

Let column vector $\mathbf{x}$ denote the input to the network. In the hidden layer, this vector firstly gets linearly transformed with weight matrix $W_1$ and bias vector $\mathbf{b_1}$. By letting $\mathbf{p}$ denote the resulting vector, this transformation can be written as follow.

列ベクトル $\mathbf{x}$ でネットワークへの入力を表すとする。このベクトルは隠れ層でまず、重み行列$W_1$とバイアスベクトル$\mathbf{b_1}$によって線形に変換される。変換後のベクトルを$\mathbf{p}$と書くと、変換は次のように表される。

$$ \mathbf{p} = \mathbf{b_1} + W_1 \mathbf{x}$$

Next, each element of $\mathbf{p}$ is separately passed to the activation function. The popular choices for the activation function are hyperbolic tangent function and sigmoid function. By letting $\mathbf{y}$ denote the resulting vector and $\phi(\cdot)$, the activation function, this process be written as follow.

次に$\mathbf{p}$の各要素が個別に活性化関数に渡される。活性化関数には双曲線正接関数とシグモイド関数がよく使われる。活性化関数を $\phi(\cdot)$、活性化関数からの出力を $\mathbf{y}$と書くとこの処理は以下のように書ける。

$$ \mathbf{y} = \phi(\mathbf{p}) $$

$\mathbf{y}$ is the output from the hidden layer and further passed to the outer layer. The same procedure as $\mathbf{x}$ is applied to $\mathbf{y}$ in the output layer. That is,

$\mathbf{y}$ は隠れ層からの出力であり、出力層へと渡される。出力層では$\mathbf{x}$ と同様の処理が行われる。すなわち、

$$ \begin{align*} \mathbf{q} &= \mathbf{b_2} + W_2\mathbf{y}\\  \mathbf{z} &= h(\mathbf{q}) \end{align*}$$

where $\mathbf{b_2}$ and $W_2$ is bias vector and weight matrix of output layer respectively, $h$ is the output function and $\mathbf{z}$ is the output of the network. The choice of the output function depends on the problem domain. The error of this output can be evaluated using an appropriate error function, given a correct output $\mathbf{t}$.  Table.1 show the activation functions used for the different types of task and their error functions. These are explained in detail in Bishop's PRML section 5.2.

ここで$\mathbf{b_2}$ および $W_2$ はそれぞれ出力層のバイアスベクトル及び重み行列であり、$h$ は出力関数、$\mathbf{z}$ はネットワークの出力である。この出力関数はネットワークの解こうとする問題の種類に依る。このネットワーク出力と、正しい信号 $\mathbf{t}$ との誤差は出力関数に対応する適当な誤差関数にを用いることで評価できる。Table.1 に課題別の活性化関数と誤差関数を示す。詳しい説明は Bishop の PRML 5.2 章を参照のこと。

Task Type Activation Function $\mathbf{h}(\mathbf{q})$ Error Function $E(\mathbf{z}, \mathbf{t})$
Regression
(Single or multiple output)
$\mathbf{h}(\mathbf{q}) = \mathbf{q}$
Squared Error
$E(\mathbf{z}, \mathbf{t})=\frac{1}{2}{||\mathbf{z}-\mathbf{t}||}^2$
Binary classification
(Single output)
Sigmoid function
$h(q) = \frac{1}{1+exp(-q)}$
Cross Entropy
$E(z, t)=-t\ln z - (1-t)\ln (1-z)$
Multi-class classification
(Multiple output using 1-of-K coding)
Softmax function
$\mathbf{h}(\mathbf{q}) = \{\frac{exp(q_i)}{\sum_j exp(q_j)}\}$
Cross Entropy
$E(\mathbf{z}, \mathbf{t})=-\sum_i t_i \ln z_i$
Table.1 The choice of activation function and error function for different type of tasks

Error-propagation

Once the error is evaluated, it is back-propagated through the network. By applying the chain-rule, we can derive the gradient of the error with respect to the weight parameters. In the followings, $I, J, K$ denotes the size of $\mathbf{x}, \mathbf{y}, \mathbf{z}$ respectively, so that the size of matrices $W_1, \mathbf{b_1}, W_2$ and $\mathbf{b_2}$ becomes $J \times I, J \times 1, K \times J$ and $K \times 1$ respectively.

誤差を求めたら、それをネットワーク内に逆伝搬させる。連鎖律を当てはめることで各重みパラメーター毎の誤差の変化を求めることが出来る。以下では$I, J, K$ はそれぞれ $\mathbf{x}, \mathbf{y}, \mathbf{z}$ の大きさを表す。従って行列 $W_1, \mathbf{b_1}, W_2$ および $\mathbf{b_2}$ の大きさはそれぞれ $J \times I, J \times 1, K \times J, K \times 1$ となる。

$$\begin{align*} \frac{\partial E}{\partial w_{2kj}} &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \frac{\partial z_\hat{k}}{\partial w_{2kj}} \\ &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}} {\partial w_{2kj}} \\ \frac{\partial E}{\partial b_{2k}} &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}} {\partial b_{2k}} \\ \frac{\partial E}{\partial w_{1ji}} &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \frac{\partial z_\hat{k}}{\partial w_{1ji}} \\  &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}}{\partial w_{1ji}} \\ &=  \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \sum_\hat{j} \frac{\partial q_\tilde{k}}{\partial y_\hat{j}} \frac{\partial y_\hat{j}}{\partial w_{1ji}} \\ &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \sum_\hat{j} \frac{\partial q_\tilde{k}}{\partial y_\hat{j}} \frac{\partial y_\hat{j}}{\partial p_\hat{j}} \frac{\partial p_\hat{j}}{\partial w_{1ji}} \\ \frac{\partial E}{\partial b_{1j}} &=  \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \sum_\hat{j} \frac{\partial q_\tilde{k}}{\partial y_\hat{j}} \frac{\partial y_\hat{j}}{\partial p_\hat{j}} \frac{\partial p_\hat{j}}{\partial b_{1j}} \end{align*}$$

Each term can be derived separately. $\delta$ in the followings is Kronecker's delta.
それぞれの項は個別に計算できる。以下では $\delta$ はクロネッカーのデルタを表す。

$$\frac{\partial p_\hat{j}}{\partial w_{1ji}} = \delta_{\hat{j}j}x_i, \ \ \ \ \ \ \ \ \ \frac{\partial q_\tilde{k}}{\partial y_\hat{j}} = w_{2\tilde{k}\hat{j}}, \ \ \ \ \ \ \ \ \ \frac{\partial q_\tilde{k}}{\partial w_{2kj}} = \delta_{\tilde{k}k} y_j $$

If $\phi(\cdot)$ is sigmoid function,
$\phi(\cdot)$ がシグモイド関数なら
$$\frac{\partial y_\hat{j}}{\partial p_\hat{j}} = y_\hat{j}(1-y_\hat{j})$$

If $\phi(\cdot)$ is hyperbolic tangent function, 
$\phi(\cdot)$ が双曲正接関数なら
$$\frac{\partial y_\hat{j}}{\partial p_\hat{j}} = 1-{y_\hat{j}}^2$$
となり、

For regression,
回帰問題なら
$$ \begin{align*} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} &= 1 \\ \\ \frac{\partial E}{\partial z_\hat{k}} &= z_\hat{k}- t_\hat{k} \end{align*}$$
For binary classification,
二値分類問題なら
$$ \begin{align*} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} &= z(1-z) \\ \\ \frac{\partial E}{\partial z_\hat{k}} &= -\frac{t}{z}+\frac{1-t}{1-z} \end{align*}$$
For multiclass classification,
多クラス分類問題ならば
$$ \begin{align*} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} &= \delta_{\hat{k}\tilde{k}}z_\hat{k}-z_\hat{k}z_\tilde{k} \\ \\ \frac{\partial E}{\partial z_\hat{k}} &= -\frac{t_\hat{k}}{z_\hat{k}} \end{align*}$$
となる。

Gradient of Error for multi-class classification problem 

For multi-class classification with sigmoid activation function, the partial derivatives of the error function turns to
隠れ層の活性化関数にシグモイド関数を用いた多クラス分類問題の場合、誤差関数の偏微係数は次のようになる。

$$\begin{align*} \frac{\partial E}{\partial w_{2kj}} &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}} {w_{2kj}} \\ &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \delta_{\tilde{k}k} y_j \\ &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} \frac{\partial z_\hat{k}}{\partial q_k} y_j  \\ &= \sum_\hat{k}\frac{\partial E}{\partial z_\hat{k}} (\delta_{\hat{k}k}z_\hat{k}-z_\hat{k}z_k) y_j \\ &= \sum_\hat{k} -\frac{t_\hat{k}}{z_\hat{k}} (\delta_{\hat{k}k}z_\hat{k}-z_\hat{k}z_k) y_j \\ &= \sum_\hat{k}- (\delta_{\hat{k}k}t_\hat{k}-t_\hat{k}z_k) y_j \\ &= -(t_k - z_k \sum_\hat{k} t_\hat{k}) y_j  \\ &=  -(t_k - z_k) y_j  \\ \\  \frac{\partial E}{\partial b_{2k}} &=  -(t_k - z_k) \\ \\ \frac{\partial E}{\partial w_{1ji}} &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \sum_\hat{j} \frac{\partial q_\tilde{k}}{\partial y_\hat{j}} \frac{\partial y_\hat{j}}{\partial p_\hat{j}} \frac{\partial p_\hat{j}}{\partial w_{1ji}} \\ &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}}{\partial y_j} \frac{\partial y_j}{\partial p_j} x_i \\ &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} \frac{\partial q_\tilde{k}}{\partial y_j} y_j(1-y_j) x_i  \\ &= \sum_\hat{k} \frac{\partial E}{\partial z_\hat{k}} \sum_\tilde{k} \frac{\partial z_\hat{k}}{\partial q_\tilde{k}} w_{\tilde{k}j} y_j(1-y_j) x_i \\ &= \sum_\hat{k} -\frac{t_\hat{k}}{z_\hat{k}} \sum_\tilde{k} (\delta_{\hat{k}\tilde{k}}z_\hat{k}-z_\hat{k}z_\tilde{k}) w_{\tilde{k}j} y_j(1-y_j) x_i \\ &= \sum_\hat{k} -t_\hat{k} \sum_\tilde{k} (\delta_{\hat{k}\tilde{k}}-z_\tilde{k}) w_{\tilde{k}j} y_j(1-y_j) x_i \\ &= (\sum_\hat{k}\sum_\tilde{k} -t_\hat{k}\delta_{\hat{k}\tilde{k}}w_{\tilde{k}j} +\sum_\hat{k}\sum_\tilde{k} t_\hat{k}z_\tilde{k}w_{\tilde{k}j} ) y_j(1-y_j) x_i \\ &= (\sum_\hat{k} -t_\hat{k}w_{\hat{k}j} +\sum_\tilde{k}z_\tilde{k}w_{\tilde{k}j} ) y_j(1-y_j) x_i \\ &= \sum_k (-t_k+z_k)w_{2kj}  y_j(1-y_j) x_i \\ \\ \frac{\partial E}{\partial b_{j}} &=\sum_k (-t_k+z_k)w_{2kj}  y_j(1-y_j) \end{align*}$$

By letting $\frac{\partial E}{\partial W_2}, \frac{\partial E}{\partial \mathbf{b_2}}, \frac{\partial E}{\partial W_1}$ and $\frac{\partial E}{\partial \mathbf{b_1}}$ denote the matrices of which element is the gradient of E w.r.t. the corresponding weight parameter, these matrices can be written simply as follow.

$\frac{\partial E}{\partial W_2}, \frac{\partial E}{\partial \mathbf{b_2}}, \frac{\partial E}{\partial W_1}$ と $\frac{\partial E}{\partial \mathbf{b_1}}$を各成分が、対応する重み成分による $E$ の変微係数となる行列とすると、これらの行列は以下のように簡単に計算できる。

$$\begin{align*} \frac{\partial E}{\partial \mathbf{b_2}} &= (\mathbf{z}-\mathbf{t}) \\ \\  \frac{\partial E}{\partial W_2} &= (\mathbf{z}-\mathbf{t}) \mathbf{y}^T \\ \\ \frac{\partial E}{\partial \mathbf{b_1}} &= \{(W_2^T (\mathbf{z}-\mathbf{t})) * \mathbf{y} * (1-\mathbf{y}) \}\\ \\ \frac{\partial E}{\partial W_1} &= \{(W_2^T (\mathbf{z}-\mathbf{t}) )* \mathbf{y} * (1-\mathbf{y}) \}  \mathbf{x}^T\end{align*}$$
where * is element-wise multiplication. 
但し * は成分毎の掛け算を表す。

By rewriting these equations as following, the notion of error-propagation becomes more clear.
これらの式は次のように書き直すことに依って誤差伝搬の意味がより明確になる。

$$\begin{align*} \mathbf{error} &= \mathbf{z}-\mathbf{t} \\ \\ \frac{\partial E}{\partial \mathbf{b_2}} &= \mathbf{error} \\ \\  \frac{\partial E}{\partial W_2} &= \mathbf{error} \  \cdot \ \mathbf{y}^T \\ \\ \mathbf{error} &\leftarrow \{(W_2^T \mathbf{error}) * \mathbf{y} * (1-\mathbf{y}) \} \\ \\ \frac{\partial E}{\partial \mathbf{b_1}} &= \mathbf{error} \\ \\ \frac{\partial E}{\partial W_1} &= \mathbf{error} \ \cdot \ \mathbf{x}^T\end{align*}$$

The equation $ \mathbf{error} \leftarrow \{(W_2^T \mathbf{error}) * \mathbf{y} * (1-\mathbf{y}) \} $ can be interpreted as follows. The error in the output layer $\mathbf{error}$ is $K$ dimensional column vector. By multiplying by $W_2^T$ , this vector becomes $J$ dimension and is projected back to the output space of the hidden layer. $\mathbf{y} * (1-\mathbf{y})$ is the derivative of sigmoid function. So multiplying this transpose the error vector into the variables space of the internal of the hidden layer. Therefore, now the error derivatives $ \frac{\partial E}{\partial \mathbf{b_1}} $ and $ \frac{\partial E}{\partial W_1} $ can be computed with simple arithmetic in this space.

$\mathbf{error} \leftarrow \{(W_2^T \mathbf{error}) * \mathbf{y} * (1-\mathbf{y}) \} $ は、次のように解釈できる。出力層での誤差 $\mathbf{error}$ は $K$ 次元のベクトルで表現されている。これに $W_2^T$ を掛けると、このベクトルの次元は $J$ となり、隠れ層からの出力空間へ投影される。$\mathbf{y} * (1-\mathbf{y})$ はシグモイド関数の導関数であるのでこれを掛けることで、誤差は隠れ層内部の変数と同じ空間で表現されることになる。これによって  $ \frac{\partial E}{\partial \mathbf{b_1}} $ および$ \frac{\partial E}{\partial W_1} $ の変化量を算出することが出来る。

Parameter Update

Once the parameters $W_1, \mathbf{b_1}, W_2$ and $\mathbf{b_2}$ are initialised, they can be iteratively optimised with the following equations.
$W_1, \mathbf{b_1}, W_2 \mathbf{b_2}$ を初期化した後、次のように更新することで、反復的に最適化することが出来る。

$$\begin{align*}W_1 &\leftarrow W_1 - \alpha \frac{\partial E}{\partial W_1} \\ \\ \mathbf{b_1} &\leftarrow \mathbf{b_1} - \alpha \frac{\partial E}{\partial \mathbf{b_1}} \\ \\ W_2 &\leftarrow W_2 - \alpha \frac{\partial E}{\partial W_2}  \\ \\ \mathbf{b_2} &\leftarrow \mathbf{b_2} - \alpha \frac{\partial E}{\partial \mathbf{b_2}} \end{align*}$$

where $\alpha$ is learning rate.
但し $\alpha$ は学習率を表す。

No comments:

Post a Comment