最適化アルゴリズムの更新式まとめ

最適化アルゴリズムの更新式

理論は置いておいて、各アルゴリズムをパッと見れるようにまとめてみた。
ちゃんとした理論はわかりやすいページがいいっぱいあるので。

勾配降下法

勾配降下法による更新式を下記とした場合の更新式。
全ての式は、ここから始まった。
要するに、重み w を求めたい。

w_{t+1} =  w_t - \eta \nabla E(w_t)

\Delta w_t =  - \eta \nabla E(w_t)

モメンタム

前回の重みを考慮した計算。
過去の勾配の指数関数的減衰平均。

V_t = \mu V_{t-1} - \epsilon \nabla E \\
w^{(t+1)} = w^{(t)} + V_t

NAG (Nesterovの加速勾配法)

モーメンタム係数$\mu$で勾配の振動を抑制している

\Delta w_t = \mu\Delta w_{t-1} -(1-\mu) \eta \nabla  E(w_t + \mu w_{t-1})

AdaGrad

パラメータが100個、200個あった時に全てのパラメータについて同じ学習率で良いか？というと、そうではない。
軸方向に更新量を変えていく。

NAGは勾配の１次の情報を使っているが、AdaGrad は2次の情報を使っている。

\Delta w_t = - \frac {\eta}{\sqrt{\sum_{k=1}^t( \nabla E (w_k)_i)^2}} \nabla E(w_t)_i

RMSProp

AdaGrad だと最初に大きな更新をすると、その後、一気に更新量が少なくなる。0になると0から戻らないので、それを回避。

指数的な移動平均 $v_{i,t}$を適用。

v_{i,t} = \rho v_{i,t-1} + (1 - \rho)( \Delta E(w_t)_i)^2 \\

\Delta w_{t(i)} = - \frac{\eta}{\sqrt{v_{i,t}} + \epsilon} \nabla E(w_t)_i

AdaDelta

ニュートン法を勾配降下法で近似。
ロバストな学習率を実現

他と比べて学習率 $\eta$を含まない。
また、AdaDelta だけ左辺と右辺の単位が同じ。

u_{i,t} = \rho u_{i,t-1} + (1-\rho)(\Delta w_{i(t)})^2\\

v_{i,t} = \rho v_{i,t-1} + (1 - \rho)( \Delta E(w_t)_i )^2 \\

\Delta w_{t(i)} = - \frac{\sqrt{u_{i,t-1} + \epsilon}} {\sqrt {u_{i,t} +\epsilon}} \nabla E (w_t)_i

比較

それぞれの最適化アルゴリズムについて、違いがわかるように表にしてみた。
ちょっと表にするとブラウザの横幅大きくしないと見にくいかも。。。

アルゴリズム	重みの計算式	各パラメータ	改善点
勾配降下法	$w_{t+1} = w_t - \eta \nabla E$		学習率が固定。
モメンタム	$w_{t+1} = w_t + V_t $	$V_t= \mu V_{t-1} - \epsilon \nabla E$	勾配の振動を抑制。
NAG (Nesterovの加速勾配法)	$w_{t+1} = w_t + V_t $	$V_t= \mu V_{t-1} - \epsilon \nabla E(w-V_{t-1})$	勾配の振動を抑制・変化の加速。
AdaGrad	$w_{t+1} = w_t - \epsilon \frac{1}{\sqrt{h_t} + \theta } \nabla E $	$h_0 = \theta$ $h_t = h_{t-1} +( \nabla E)^2 $	パラメータ方向に応じて学習率を補正。勾配が大きいと学習率を大きくする。
RMSProp	$w_{t+1} = w_t - \epsilon \frac{1}{\sqrt{h_t} + \theta } \nabla E $	$h_t = \alpha h_{t-1} + (1- \alpha) (\nabla E)^2 $	AdaGradの単調な学習率低下を改善。
AdaDelta	$w_{t+1} = w_t - \frac { \sqrt {s_{t-1} + \epsilon}} {\sqrt{h_t + \epsilon}}$	$h_t = \alpha h_{t-1} + (1- \alpha) (\nabla E)^2$ $s_{t} = \alpha s_{t-1} +(1-\alpha) V_{t-1}^2 $ $ V_t = \frac { \sqrt {s_{t-1} + \epsilon}} {\sqrt{h_t + \epsilon}} $	ニュートン法を購買降下方で近似。ロバストな学習率を実現。
Adam	$w_{t+1} = w_t - \beta \frac{V_t}{\sqrt{h_t + \epsilon}}$	$V_t = \mu V_{t-1} - \epsilon \nabla E$ $h_t = \alpha h_{t-1} + (1-\alpha) (\nabla E)^2 $	AdaGradとRMSPropを合わせたような感じ。