こんにちは（＾ω＾）

この記事は、勾配降下法を最適化するアルゴリズムを、
２つのベンチマーク関数を使って比較し、まとめたものです。

計算の経過をみるために、
最適化するベンチマーク関数は２変数関数に限定し、
３次元グラフに計算の経過をプロットし記事に載せています。

ニューラルネットワークの学習を行うときなどには
最適化するパラメータは膨大な数となるため、
今回の比較で得た各アルゴリズムの良し悪しは実際の学習には適用できないと思います。
あくまで参考程度にしていただければ幸いです。

勾配降下法がよくわからないという方はこちらを参考にしてみてください
勾配降下法って？ - スラきちの野望

またここで使用しているアルゴリズムは以下のサイトを参考にさせていただきました
勾配降下法の最適化アルゴリズムを概観する | コンピュータサイエンス | POSTD

使用した最適化アルゴリズム

最急降下法　( $x_{t+1}=x_t - \eta \nabla_{x_t} f(x_t)$ )
Momentum　(γ=0.9)
NAG　(γ=0.9)
Adagrad
Adadelta　(γ=0.9)
RMSprop　(γ=0.9)
Adam　( $B_1$ =0.9, $B_2$ =0.999)

ベンチマーク関数

以下の２つの関数を使用しています

Ackley関数

式：
　 $f(x_1, x_2)=20-20 exp(-0.2 \sqrt{\frac{1}{2}({x_1}^2 + {x_2}^2)}) + e$
　　　　　　　 $- exp(\frac{1}{2}(cos(2\pi x_1) + cos(2\pi x_2)))$

最適解：
　 $f_{min}(0,0) = 0$

初期値：
　 $(20.0, 20.0)$

勾配：
　 $\frac{\partial f}{\partial x_1} = \frac{(2.82843{x_1}exp(-0.141424 \sqrt{{x_1}^2 + {x_2}^2}))} {\sqrt{{x_1}^2 + {x_2}^2}} + \pi sin(2\pi{x_1})exp(\frac{1}{2}(cos(2 \pi {x_1}) + cos(2 \pi {x_2})))$
　 $\frac{\partial f}{\partial x_2} = \frac{(2.82843{x_2}exp(-0.141424 \sqrt{{x_1}^2 + {x_2}^2}))} {\sqrt{{x_1}^2 + {x_2}^2}} + \pi sin(2\pi{x_2})exp(\frac{1}{2}(cos(2 \pi {x_1}) + cos(2 \pi {x_2})))$
　※~~面倒だったので~~勾配はWoframeAlphaさんを使って求めました

f:id:CAPsp:20171014164945p:plain

Rosenbrock関数

式：
　 $f(x_1, x_2)=100(x_2-{x_1}^2)^2 + (x_1 - 1)^2$

最適解：
　 $f_{min}(1,1) = 0$

初期値：
　 $(5.0, 5.0)$

勾配：
　 $\frac{\partial f}{\partial x_1} = -400x_1(x_2 - {x_1}^2) + 2x_1 - 2$
　 $\frac{\partial f}{\partial x_2} = 200(x_2 - {x_1}^2)$ f:id:CAPsp:20171014185504p:plain

以下のサイトにベンチマーク関数のまとめが載ってあります
最適化アルゴリズムを評価するベンチマーク関数まとめ - Qiita

比較結果

学習率は0.1として、
初期値から各アルゴリズムを使って最小値を求めます。

最小値の座標と計算中の座標との大きさが1未満になったときに収束したとする場合、
10000回タイムステップを進めたときの結果は

	Ackley関数	Rosenbrock関数
最急降下法	収束せず	計算途中でオーバーフロー
Momentum	142ステップで収束	計算途中でオーバーフロー
NAG	1569ステップで収束	計算途中でオーバーフロー
Adagrad	収束せず	収束せず
Adadelta	収束せず	収束せず
RMSprop	収束せず	129ステップで収束
Adam	収束せず	8714ステップで収束

なお、学習率をいろいろ変えて試してみたところ、学習率0.4付近だとRmspropと再急降下法がAckley関数の収束に成功していました。
その他は収束が早くなったり遅くなったりはありましたが、新たに収束に成功しているものはありませんでした。

経過のプロット

赤：最急降下法
青：Momentum
緑：NAG
黒：Adagrad
白：Adadelta
ピンク：RMSprop
黄色：Adam

Ackley function

f:id:CAPsp:20171014184309g:plain

収束しているNAGとMomentumは、しっかりと最小値に移動している様子が見れると思います。

Rosenbrock function

f:id:CAPsp:20171014184735g:plain
NAGがどっかに飛んでいってるのはなんでなんですかね（＾ω＾）

まとめ

なんとも言えない結果になってしまいました、
全体的にみればRMSpropが良いっちゃ良いです。

収束していないものの多くはタイムステップを進めても座標がほとんど変化していなかったので、局所解に陥ってしまったのだと思います。

そういった状況にならないためには、適切な学習率やパラメータを設定する必要があると思うのですが、いろんなサイトを回ってもそれの確かめ方はわかりませんでした。

現状試行錯誤するしかないのでしょうかね？

ここまで記事を見てくださってありがとうございました！

スラきちの野望

技術系で紹介したいこととか、遊んだゲームなどを載せていくブログです。

勾配降下法に使われる最適化アルゴリズムを比較する簡単な実験をしてみた

目次