最適化手法について—SGDからYellowFinまで— | moskomule log

最適化手法について—SGDからYellowFinまで—

はじめに

前回の記事に,「ベンチマーク函数があるよ」というフィードバックを頂きました.test functions for optimizationというWikipediaの記事にまとまっていたので,今回はこちらにあるRosenbrock function($f_{R}=100(y-x^2)^2+(x-1)^2$,大域解$f_{R}(1,1)=0$)を使います.Rosenbrock函数には大域解を含む広い濠があって大域解が見つけにくいのが特徴です.

一般に勾配法の更新方法はバッチ更新と呼ばれます.つまり勾配降下法であれば学習事例$n=1,2,\ldots,N$に対して個々の誤差函数$E_n$の和

\[E(x)=\sum_n E_n(x)\]

について$x\gets x-\alpha\nabla E$と更新していました.

確率的な(stochastic)では$n\in\{1,\ldots,N\}$を乱択して,または逐次的な(online)勾配降下法では$n=1,2,\ldots,$によって$x\gets x-\alpha\nabla E_n(x)$により更新を行います.

また,ディープラーニングの文脈では$B\subset\{1,\ldots,N\}$によって$x\gets x-\frac{\alpha}{|B|}\sum_{i\in B}\nabla E_i(x)$を更新するミニバッチ更新がしばしば用いられます.ミニバッチの大きさ$|B|$は32,64,128などがよく用いられるように思われます.この大きさが大きいほど計算は速くなりますが,あまり大きくない方が汎化性能が上がるという話もあります1

今回紹介する手法は主にディープラーニングの文脈で用いられるため,ミニバッチ更新を行うことでよりよい性能が出せる可能性がありますが,記事中では可視化の都合もあり$x\gets x-\alpha d$によって更新を行います.

なお,表記にはこの記事特有のものも含まれていますので,その点にはお気をつけ下さい.

SGD(Stochastic Gradient Descent)

基本的に勾配降下法と同一で,以下により更新を行います.

\[x_{k+1}=x_{k}-\alpha_k\nabla f(x_{k})\]

$\alpha$の調整には段階的に$\alpha$を小さくするstep decay,$\alpha_k=\alpha_0 e^{-rk}$とするexponential decay,$\alpha_k=\frac{\alpha_0}{1+rk}$とする1/k decayなどの手法がありますが,職人の勘による調整法も多いようです.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からのSGDによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Momentum

SGDは$\nabla f(x)$が0に近い時に更新ができなくなるという問題がありました.Momentum法では

\[\begin{aligned} v_{k+1} &= \mu v_k-\alpha\nabla f(x_k)~,v_0=0 \cr\cr x_{k+1} &= x_k+v_{k+1} \end{aligned}\]

によって更新を行うことでこの問題を解決しています.またSGDは各点の勾配変化に敏感でしたが,以前の状態を引き継ぐ慣性力のようなmomentum term$v$を用いることで些細な変化に対しての感度を低下させているとみることもできます.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からのmomentumつきのSGDによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Nestrov Accelerated Gradient

Momentum法を改良し,$v_{k+1}$の更新に$x_k$よりも$x_{k+1}$に近いと期待される$x_k+\mu v_k$を用いたのがNestrov Accelerated Gradientです.

\[\begin{aligned} v_{k+1} &= \mu v_k-\alpha\nabla f(x_k+\mu v_k)~,v_0=0 \cr\cr x_{k+1} &= x_k+v_{k+1} \end{aligned}\]

clminのdocでは$x_k+\mu v_k$を$x_{k+\frac12}$と表記しており,$x_k$と$x_{k+1}$の間の点であることが分かりやすいです.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からのNestrovのmomentumつきのSGDによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Adaptive Learning Rate

momentum法と異なり,学習率を自動調整することを目指したのがAdaptive Learning Rateを用いた手法です.

前回紹介した手法にはline search methodなど学習率$\alpha$を最適化する方法が含まれていました.それらの手法では,何度も$f(x_k+\alpha_k d_k)$を更新して適当な$\alpha$を求めます.

特にディープラーニングなどパラメータ数が多い場合にはこの計算はコストが大きく,$\alpha$を求めるためだけに何度も繰り返したくはありません.そのためadaptive learning rateを用いる手法においては,そのような手法は用いていません.

Adagrad

Adagrad2は過去の勾配の自乗$(\nabla f(x))^2$を累積し,これを用いて学習率を適応させていきます.

\[\begin{aligned} g_{k+1} &= g_k + (\nabla f(x_k))^2,~g_0=0 \cr\cr x_{k+1} &= x_k - \alpha (g_{k+1}+\epsilon)^{-\frac12}\odot\nabla f(x_k) \end{aligned}\]

ただし,$\epsilon=\varepsilon\mathbf{1}$,$(g_{k+1}+\epsilon)^{-\frac12}$は第$i$成分が$(g_{k+1}^{(i)}+\varepsilon)^{-1}$であるようなベクトルで,$\odot$は要素積です.$\varepsilon$は分母が0となるのを防ぐためにあり,$10^{-8}$程度です.$|\nabla f(x_k)|$が大きい要素に対しては学習率を下げ,逆に小さい要素に対しては学習率を上げています.

$(g_{k+1}+\epsilon)^{-\frac12}$は$f$の$x_{k}$でのHessianの逆行列 $(\nabla^2 f(x_k))^{-1}$を近似していて,理想的にはNewton法に近くなることが期待されます.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からのAdagradによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

RMSProp

Adagradの弱点として,$g_k$が$k$とともに単調に増加していく,つまり学習率$\alpha (g_{k}+\epsilon)^{-\frac12}$は単調減少で,一度小さくなった学習率は大きくならないという問題点がありました.RMSProp3では過去の勾配を適当な割合で「忘れる」ことでこの問題に対応しています.つまり$\gamma$(0.9程度)を用いて

\[\begin{aligned} g_{k+1} &= \gamma g_k + (1-\gamma)(\nabla f(x_k))^2,~g_0=0 \cr\cr x_{k+1} &= x_t - \alpha (g_{k+1}+\epsilon)^{-\frac12}\odot\nabla f(x_k) \end{aligned}\]

としています.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からのRMSPropによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Adadelta

Adadelta4もRMSProp同様,Adagradの学習率の単調減少に対応しています.RMSPropと異なり,過去の勾配だけでなく, 過去の学習ステップも使います.

\[\begin{aligned} g_{k+1} &= \gamma g_k + (1-\gamma)(\nabla f(x_k))^2,~g_0=0 \cr\cr x_{k+1} &= x_k - \alpha (g_{k+1}+\epsilon)^{-\frac12}\odot\nabla f(x_k)\odot(s_k+\epsilon)^{\frac12} \cr\cr s_{k+1} &= (1-\gamma)(x_{k+1}-x_k)^2+\gamma s_k,~s_0=0 \end{aligned}\]

ただし例によって$(s_k+\epsilon)^{\frac12}$は第$i$成分が$\sqrt{s_k^{(i)}+\varepsilon}$であるようなベクトル, $(x_{k+1}-x_k)^2=(x_{k+1}-x_k)\odot (x_{k+1}-x_k)$とします.$s_0=0$とするためか,$\varepsilon$を小さくしすぎない方がよいようで,climinでは$10^{-4}$となっています.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からAdadeltaによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Adam

Adam(adaptive moment estimation)5では勾配と勾配の2乗の指数移動平均(exponential moving average, EMA)をもちいることで,勾配の1次モーメント($m$ 平均)と0周りの2次モーメント($v$ 0周りの分散)を推定しています.指数移動平均は時系列データの文脈で使われる言葉で,Googleで調べるとFX系のページが出てきました.

\[\begin{aligned} m_{k+1} &= \beta_1 m_{k}+(1-\beta_1)\nabla f(x_k),~m_0=0 \cr\cr v_{k+1} &= \beta_2 v_{k}+(1-\beta_2)(\nabla f(x_k))^2,~v_0=0 \end{aligned}\]

ただし,$k$が小さいと初期値($m_0=v_0=0$)の影響を強く受けるため

\[\begin{aligned} \hat{m}_{k} &= \frac{m_k}{1-\beta_1^k} \cr\cr \hat{v}_{k} &= \frac{v_k}{1-\beta_2^k} \end{aligned}\]

によって補正を行い,以下によって更新します.

\[x_{k+1}=x_k-\alpha((\hat{v}_{k+1})^{\frac12}+\epsilon)^{-1}\odot\hat{m}_{k+1}\]

論文中では$\beta_1=0.9,\beta_2=0.999$が用いられています.SGDなどと比較して早く収束するため,ディープラーニングのoptimizerとしては多く用いられているように思われます.

初期位置(-0.7, -0.7),(0, 2.5),(-1, 2)からAdamによる1000ステップの移動の軌跡.黄色の点が大域解(1,1).

Adamax

Adamの2次モーメントを拡張し,

\[v_{k+1} = (\beta_2^p v_{k}+(1-\beta_2^p)|\nabla f(x_k)|^p)^{\frac{1}{p}}\]

とします.この$p\to\infty$の,Maxノルムを用いるのがAdamaxで5のExtensionsに挙げられています.

Eve

Eve6はAdamに目的函数の増減に伴うフィードバックを加えています.

\[\begin{aligned} r_k &= \begin{cases} \frac{f_{k-1}-f_{k}}{f_{k}} ~ ~\text{if}~ f_{k-1}\geq f_{k}\cr\cr \frac{f_{k}-f_{k-1}}{f_{k-1}} ~ ~\text{otherwise} \end{cases} \cr\cr d_{k+1} &= \beta_3 d_k+(1-\beta_3)r_k \cr\cr \end{aligned}\]

ただし,$f_k=f(x_k)$です.実際には$\kappa<r_k<K$と範囲を限定し,$f_k$の代わりに,$f$を近似する滑らかな列$\hat{f}_k$を使うなどの工夫がされています.

YellowFin

YellowFin7はほかの方法が学習率の自動調整を行うのに対し,momentum termの$\mu$も調整しようという試みです. momentum tunerのtunerとtuna(マグロ)をかけてYellowfin(キハダマグロ)と名づけられているようです.

YellowFinでは学習率$\alpha$とmomentum項の係数$\mu$を与えます.ハイパーパラメータは共通の$\beta$を用います.

\[\begin{aligned} \alpha_{k+1} &= \beta\alpha_{k}+(1-\beta)\hat{a}_{k+1} \cr\cr \mu_{k+1} &= \beta\mu_{k}+(1-\beta)\hat{m}_{k+1} \end{aligned}\]

ただし,$\hat{a}_{k+1},\hat{m_{k+1}}$は$(\nabla f(x)$と$\beta)$によって定まる曲率の範囲$(h^{\min}_{k+1},h^{\max}_{k+1})$,勾配の分散$V_{k+1}$,最適解までの距離$D_{k+1}$から以下によって得ます.簡単のために下付文字の${}_k$は省略します.

\[\begin{aligned} \hat{m},\hat{a} &= \mathop{\mathrm{argmin}}\limits_{m} mD^2 + a^2V \cr\cr s.t. \space\space m &\geq(\frac{\sqrt{h_{\max}/h_{\min}}-1}{\sqrt{h_{\max}/h_{\min}}+1})^2 \cr\cr a &= \frac{(1-\sqrt{m})^2}{h_{\min}} \end{aligned}\]

ここで$f(x)$を(局所的には)$\frac12hx^2+V$という形であると仮定しているので,「最適解までの距離」というものが出てきます.

公式のブログが充実しているので此方をご覧下さい.Adamと比較してより早く収束すると述べられています.

手法の比較

2層の畳み込み層+2層の全結合層のCNNでMNISTを分類した際の学習データの損失,検証データの損失および正答率の20エポックにわたる変動をまとめました.値は3回の実験の平均値です.計算資源の都合でSGD,momentumつきSGD,Adagrad,Adadelta,Adamのみを扱っています.

SGDおよびmomentumつきSGDの学習率は$10^{-3}$,momentumつきSGDのmomentumは$0.9$を用いてい,それ以外はPyTorchの初期値であるAdadelta(lr=1.0),Adagrad(lr=0.01),Adam(lr=0.001)を使いました.

学習データでの損失の変動

検証データでの損失の変動

検証データでの正答率の変動

検証データでのSGD以外の正答率の変動

今回の結果からはSGD以外の性能に大きな際は見られないものの,強いて言えばAdadeltaが安定していそうです.

この比較については,データやアーキテクチャを変更して,今後さらに検証してみたいと考えています.また今回はRMSPropが異常に大きな損失を返すなど,問題があったのでこの点も確認をしてみます.

まとめ

このようにSGDからさまざまな更新手法が発展してきましたが,最近ではAdamをはじめとする勾配に適応する手法では十分な汎化性能が得られない,SGDに立ち返るべきという研究8もあります.一方で問題によって適当なoptimizerが異なることも知られており(),とりあえずAdam,ではいけなくて,optimizerの選択の重要性が分かってきたと言うことかもしれません.銀の弾丸は存在しないのでしょうが,今後も引き続き注目していきたいです.

今回の記事を執筆するに当たってはほかに9,10を参考にしました.


  1. Hoffer, E. (2017). Train longer , generalize better : closing the generalization gap in large batch training of neural networks, 1–13. [return]
  2. Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. [return]
  3. これといった初出はないようです.G.HintonのCouseraの授業やTronto大学での授業に出てきたようです. [return]
  4. Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. arXiv, 6. Retrieved from http://arxiv.org/abs/1212.5701 [return]
  5. Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations 2015, 1–15. [return]
  6. Koushik, J., & Hayashi, H. (2016). Improving Stochastic Gradient Descent with Feedback. Arxiv, 1–8. Retrieved from http://arxiv.org/abs/1611.01505 [return]
  7. Zhang, J., Mitliagkas, I., & Ré, C. (2017). YellowFin and the Art of Momentum Tuning. arXiv, 1–21. Retrieved from http://arxiv.org/abs/1706.03471 [return]
  8. Wilson, A. C., Roelofs, R., Stern, M., Srebro, N., & Recht, B. (2017). The Marginal Value of Adaptive Gradient Methods in Machine Learning. arXiv, 1–14. Retrieved from http://arxiv.org/abs/1705.08292 [return]
  9. Sebastian Ruder (2016). An overview of gradient descent optimisation algorithms. arXiv preprint arXiv:1609.04747. [return]
  10. Stanford大学 “CS231n: Convolutional Neural Networks for Visual Recognition” [return]
comments powered by Disqus