勾配降下法のアルゴリズム一覧のメモ

名前のついているアルゴリズムの内容をすぐに思い出せるようにするためのメモである。各アルゴリズムの詳細な厳密な説明にはなっていない。

g(x_t) は x_t における微分（勾配）の値とする。

シンプルな最急降下法

 \displaystyle
x_{t+1} = x_t - \eta g(x_t)

\eta は x2/y の次元を持った値となる。xやyのスケールによっては0.01だとか100だとかぜんぜん違う値にしないとなかなか降下しない。問題によって適切な値にする必要がある。

モメンタム

 \displaystyle
x_{t+1} = x_t + \alpha(x_t - x_{t-1}) - \eta g(x_t)

\alpha は0.9みたいな無次元の値。 \eta の調整が必要なのは最急降下法と同じ。

Nesterov加速法

その地点で勾配を計算するのではなく、次の地点で勾配を計算してから、改めて次の地点を計算する。

 \displaystyle
x_{t+1} = x_t + \alpha(x_t - x_{t-1}) - \eta g(x_t + \alpha(x_t - x_{t-1}))

\alpha は0.9みたいな無次元の値。 \eta の調整が必要なのは最急降下法と同じ。

Adagrad

勾配をこれまでの勾配の合計で割った値で差分を計算する。多次元で軸によって学習率が異なるべき場合にこれで自動で調整できる。勾配の合計というのは実際には勾配の二乗和の平方根を使う。二乗和を使う理由は、勾配の符号が変わったときに打ち消さないようにするためと想像。

 \displaystyle
x_{t+1} = x_t - \eta \frac{g(x_t)}{\sqrt{\displaystyle{\sum_{i=0}^t {g_i}^2}}}

\eta はxの次元を持った値となる。xのスケールによっては0.01だとか100だとかぜんぜん違う値にしないと降下しない。問題によって適切な値にする必要がある。

これまでのすべての g_i を使うため、勾配が極端に大きいところを通過してしまうと、その後はなかなか降下してくれなくなる問題がある。

RMSprop

Adagradとの違いは、勾配の合計ではなく勾配の指数移動平均を使う点。

 \displaystyle
x_{t+1} = x_t - \eta \frac{g(x_t)}{\sqrt{\text{EMA}_i^t({g_i}^2) + \epsilon }}

数式上はEMAの中に隠れてしまっているが、 \eta のほかに指数移動平均を計算する際の係数もハイパーパラメータとして存在する。

\epsilon はゼロで除算しないようにするための微小な値。

Adadelta

RMSpropとの違いは、 \eta の代わりに差分の指数移動平均(EMA)を使う点。

 \displaystyle
x_{t+1} = x_t - \sqrt{\text{EMA}_i^{t-1}(x_{i+1}-x_i)^2 + \epsilon} \frac{g(x_t)}{\sqrt{\text{EMA}_i^t({g_i}^2) + \epsilon}}

2つの指数移動平均を計算する際の係数は同一とする。

次元を持ったパラメータがないため、その調整の手間は省ける。

（最初の差分をどうするかによって降下速度が大きく変わったり、発散してしまったりするような気がするけど、なにか理解が違っているかも・・・）

Adam

(2020/06/26追記)

RMSpropとの違いは、分子にも指数移動平均を使う点。指数移動平均も補正した値を使う。

 \displaystyle
x_{t+1} = x_t - \eta \frac{\hat{\text{EMA}}_i^t(g_i)}{\sqrt{\hat{\text{EMA}}_i^t({g_i}^2) + \epsilon }}

指数移動平均( \text{EMA} )の初期値は0とし、その指数移動平均を補正した値( \hat{\text{EMA}} )を使う。

 \displaystyle
\begin{align}
\text{EMA}_i^t(z_i) &= \beta \, \text{EMA}_i^{t-1}(z_i) + (1-\beta)z_i \\
\text{EMA}_i^0(z_i) &= 0 \\
\hat{\text{EMA}}_i^t(z_i) &= \frac{1}{1 - \beta^t} \text{EMA}_i^t(z_i) \\
\end{align}

自作アルゴリズム

(2020/05/21追記)

私が使っているオリジナルのアルゴリズムを別記事で紹介しました。 suzuki-navi.hatenablog.com