Optimizer : 深層学習における勾配法について

# はじめに
深層学習の勾配法には様々な手法が提唱されています。その中で、どの手法を用いるのが適切であるか自分でもあまり理解できていない部分があり、今回は勾配法の中でも実際に深層学習で主に用いられている手法(SGD, Momentum SGD, AdaGrad, RMSprop, AdaDelta, Adam)について、実装することを前提に調べてまとめてみました。実装フレームワークはChainerを想定しています。

# SGD
SGD(Stochastic Gradient Descent : 確率的勾配降下法)は、Optimizerの中でも初期に提唱された最も基本的なアルゴリズムです。重み$\mathbf{w}$の更新は以下のように行っております。このとき、$E$は誤差関数、$\eta$は学習係数を表しています。

```math
\mathbf{w}^{t + 1} \gets \mathbf{w}^{t} - \eta \frac{\partial E(\mathbf{w}^{t})}{\partial \mathbf{w}^{t}}
```

この手法は、通常の勾配法[1]で起こりうる局所最適解(local optimum)への収束という問題点を、$\mathbf{w}$の更新ごとにランダムにサンプルを選び出すことで解消したものです。また、訓練データにおける冗長性を効率良く学習することができるという利点もあります。
しかし学習係数$\eta$を恣意的に決定する必要があり、一度決めた$\eta$を用いて誤差の最小化を行なっていくことになります。このことから、学習モデルによって最適なパラメータを決めることが難しいという問題があります。

Chainerにおけるデフォルトのパラメータは$\eta = 0.01$となっています。

# Momentum SGD
Momentum SDGは、SGDに慣性項(Momentum)を付与した手法です。
以下の式のように重みの更新を行います。

```math
\mathbf{w}^{t + 1} \gets \mathbf{w}^{t} - \eta \frac{\partial E(\mathbf{w}^{t})}{\partial \mathbf{w}^{t}}　＋ \alpha \Delta \mathbf{w}^{t}
```

このときの$\alpha$は慣性項のパラメータであり、前回の更新量に$\alpha$倍して加算することでパラメータの更新をより慣性的なものにするという狙いがあります。
この手法もハイパーパラメータが２つあり、最適化が難しいという問題があります。

Chainerにおけるデフォルトのパラメータは$\eta = 0.01, \alpha = 0.9$となっています。

# AdaGrad
2011年にJohn Duchiらが提唱した手法[2]であり、学習係数を自動で調整してくれることが強みです。ただし、初期学習係数$\eta_{0}$を決める必要があります。
重みの更新は以下の式のように行います。パラメータ$\epsilon$は、無限大に発散させないように小さな正の定数を設定します。

```math
h_{0} = \epsilon\\
h_{t} = h_{t−１} + \nabla E(\mathbf{w}^{t})^{2}\\
\eta_{t} = \frac{\eta_{0}}{\sqrt{h_{t}}}\\
\mathbf{w}^{t+1} = \mathbf{w}^{t} - \eta_{t} \nabla E(\mathbf{w}^{t})
```

epoch回数を重ねていくごとに計算される学習係数$\eta_{t}$は小さくなっていくことがわかります。また、傾きが小さくなっていくごとに$\eta_{t}$は0に漸近していき収束するであろうことが期待できます。
Chainerにおけるデフォルトのパラメータは$\epsilon = 10^{-8}, \eta_{0} = 0.001$となっています。
またChainerでは、以下のように実装されています。

>$h_{0} = 0$
>$h_{t} = h_{t−１} + \nabla E(\mathbf{w}^{t})^{2}$
>$\eta_{t} = \frac{\eta_{0}}{\sqrt{h_{t}} + \epsilon}$
>$\mathbf{w}^{t+1} = \mathbf{w}^{t} - \eta_{t} \nabla E(\mathbf{w}^{t})$

これは初回の勾配が0の場合におけるゼロ除算を避けるためだと考えられますが、実際の挙動を考えるとこの実装は果たして良いのか少し検討する余地があるかもしれません。。

# RMSprop
2012年にTijmen Tielemanらが提唱した手法[3]であり、AdaGradを改良したアルゴリズムです。勾配の2乗の指数移動平均を取るように変更されています。
重みの更新は以下の式のように行います。

```math
h_{t} = \alpha h_{t−１} + (1 - \alpha) \nabla E(\mathbf{w}^{t})^{2}\\
\eta_{t} = \frac{\eta_{0}}{\sqrt{h_{t}} + \epsilon}\\
\mathbf{w}^{t+1} = \mathbf{w}^{t} - \eta_{t} \nabla E(\mathbf{w}^{t})\\
```

初期値は$h_{0} = 0$です。
$\alpha$によって過去の勾配の影響を抑えると共に、新しい$h_{t}$を優先して反映させるという効果を狙っているのがAdaGradからの最大の変更点です。これにより、AdaGradでは過去の勾配情報を全て均等に考慮して計算が行われていたが、より直近の勾配情報を優先して計算するという改良が実現されています。しかし個人的な所感として、初期学習係数$\eta_{0}$をうまく決定しないとかなりオーダーがずれてしまうような気がします。。もちろんAdaGradでも同じことがいえるのですが。。
Chainerの実装ではデフォルトで$\alpha = 0.99, \epsilon = 10^{-8}, \eta_{0} = 0.01$となっています。

# AdaDelta
2012年にMatthew D. Zeilerが提唱した手法[4]で、AdaGradやRMSPropを改良したものです。RMSpropまでにあった初期学習係数のパラメータ$\eta_{0}$がなくなっている点がポイントです。
以下の式のように重みを更新していきます。パラメータは$\rho = 0.95, \epsilon = 10^{-6}$が論文内で推奨されています。

```math
h_{t} = \rho h_{t−１} + (1 - \rho) \nabla E(\mathbf{w}^{t})^{2}\\
v_{t} = \frac{\sqrt{s_{t} + \epsilon}}{\sqrt{h_{t} + \epsilon}} \nabla E(\mathbf{w}^{t})\\
s_{t+1} = \rho s_{t} + (1 - \rho) v_{t}^{2}\\
\mathbf{w}^{t+1} = \mathbf{w}^{t} - v_{t}
```

初期値は$h_{0} = 0, s_{0} = 0$です。
RMSpropに比べて、$s_{t}$を導入することでより直近の勾配情報を優先して計算することを狙ったアルゴリズムです。初期学習係数を決める必要がなくなったことも大きな改善だと思います。$\epsilon$を変化させてもあまり挙動に影響がない気がするのですが、実際に触った感じだと小さくするほど収束するのに時間がかかるみたいです。もう少し論文を読み込む必要があります。。
Chainerの実装でも推奨パラメータ通りデフォルトで$\rho = 0.95, \epsilon = 10^{-6}$となっています。

# Adam
Adam(Adaptive moment estimation)は2015年にDiederik P. Kingmaらが提唱した手法[5]で、AdaGradやRMSProp,AdaDeltaを改良したものです。
以下の式のように重みを更新していきます。パラメータは$\alpha = 0.001, \beta_{1} = 0.9, \beta_{2} = 0.999, \epsilon = 10^{-8}$が論文内で推奨されています。

```math
m_{t+1} = \beta_{1} m_{t} + (1 - \beta_{1}) \nabla E(\mathbf{w}^{t})\\
v_{t+1} = \beta_{2} v_{t} + (1 - \beta_{2}) \nabla E(\mathbf{w}^{t})^{2}\\
\hat{m} = \frac{m_{t+1}}{1 - \beta_{1}^{t}}\\
\hat{v} = \frac{v_{t+1}}{1 - \beta_{2}^{t}}\\
\mathbf{w}^{t+1} = \mathbf{w}^{t} - \alpha \frac{\hat{m}}{\sqrt{\hat{v}} + \epsilon}
```

初期値は$m_{0} = 0, v_{0} = 0$です。
これまでの手法と比較したときの一番大きな改善点は、移動指数平均を用いた際に生じるバイアス(大きさを変えてしまっていることなど)をそれぞれ$\hat{m}, \hat{v}$で打ち消すことを狙っているという点だと思います。それ以外は特に今までのアルゴリズムからの大きな変更点はなく、AdaGradやRMSprop, AdaDeltaの良い所取りをしたという印象を受けます。現状一番評価されている手法もこのアルゴリズムみたいですね。

Chainerにおける実装は、論文におけるアルゴリズムと多少形が異なっていることが気になります。。
Chainerでの実装パラメータはデフォルトで$\alpha = 0.001, \beta1 = 0.9, \beta2 = 0.999, \epsilon = 10^{-8}$となっていますが、$\alpha$が使われていないことも何が何だか、、
もう少し調べて見る必要があります。。

# まとめ
様々な手法を紹介してみましたが、やっぱりAdamが最強！！って訳でもないみたいで、学習モデルによってはAdaGradの方が高い精度を出すみたいな話も聞いたりします。結局使うOptimizerもモデルごとに最適なものを選ばないといけないってことなんですかね。。まあ少なくともSGDに比べたら精度も収束時間も格段に上がることはわかっているので、次はもう少しこれらのアルゴリズムがそれぞれどのような問題に適しているのかということを理解することが課題だと考えています。
次回はこれらのアルゴリズムを用いた簡単な精度の比較検証を行いたいと思っています。

最後に、間違いや指摘する点が何かありましたらコメントしていただけると助かります。

# 参考文献
[1] [Amari, Shunichi. "A theory of adaptive pattern classifiers." IEEE Transactions on Electronic Computers 3 (1967): 299-307.](http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4039068)
[2] [Duchi, John, Elad Hazan, and Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." Journal of Machine Learning Research 12.Jul (2011): 2121-2159.](http://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf)
[3] Tijmen Tieleman; G. Hinton (2012). Lecture 6.5 - rmsprop, COURSERA: Neural Networks for Machine Learning.
[4] [Zeiler, Matthew D. "ADADELTA: an adaptive learning rate method." arXiv preprint arXiv:1212.5701 (2012).](http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf)
[5] [Kingma, Diederik, and Jimmy Ba. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014).](http://arxiv.org/pdf/1412.6980v8.pdf)