ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION(Kingma, Ba, 2015)を読んだので要約およびメモ。
アルゴリズムが何をやっているか知りたかったので、冒頭から5.関連研究までを要約し、筆者の理解と疑問を青色でメモした。
元論文は5章以降、6.実験、7.拡張(AdaMax)、8.結論、...と続く。
一言でいうと
勾配の平均・分散(一次・二次モーメント)から、各パラメータ個別の学習率を計算する最適化手法。Adamの由来はadaptive moment estimationから。
概要(特徴)
- 低次のモーメント（平均とか分散）の適応的推定に基づいた最適化アルゴリズム
- 計算量が少なく、フットプリントも小さい
- パラメータ・データが大量な問題に適している
- 非定常な目的関数に対して、あるいは、ノイジーまたはスパースな勾配の問題に対しても適している
1.Introduction
SGD(確率的勾配降下法)ベースの手法は目的関数がパラメータに関して微分できるなら、全パラメータに関して一次の偏微分を計算するのは関数を評価するのと同じ計算量でできるので、効率が良い。
目的関数は確率的であることがよくあり、（異なるサンプルで評価した部分関数の和など）またdropout(Hinton et al., 2012)のようなそれとは別のノイズを含む場合もある。そのようなノイジーな目的関数用の最適化手法が必要。本論文では高次(higher-order)の最適化手法が不適となる高次元パラメータ空間での最適化に、一次(first-order)の手法に限定してフォーカスする。
スパースな勾配に強いAdaGrad(Duchi et al., 2011)とオンライン・非定常なセッティングで有効なRMSProp (Tieleman & Hinton, 2012)を合わせるように設計されている。他の利点として：
- パラメタ更新の大きさが勾配のリスケーリングに対して変化しない(勾配をリスケールするってどういう場合だろう)
- ステップサイズが近似的にステップサイズハイパーパラメータで抑えられる
- 定常な目的関数を必要としない
- スパースな勾配でも動作する
- ステップサイズアニーリングが自然に実行される(ステップサイズが、学習が進むごとに自動的に小さくなる)
2 アルゴリズム
$f(\theta)$をノイジーな目的関数（パラメータ$\theta$ たちに関して微分可能な確率的スカラー関数）とする。この関数の期待値$E[f(\theta)]$を最小化したい。連続する時間ステップ1,...,Tにおける確率的関数の観測を$f_1(\theta),..., f_{T}(\theta)$と書く。関数の確率的な部分はデータ点のランダムサンプル（ミニバッチ）を評価したとき、または元々の関数のノイズから現れる。勾配（時刻$t$で評価された $f_t$ の$\theta$に関する偏微分のベクトル）のことは$g_t=\nabla_\theta f_t(\theta)$と書く。
アルゴリズムは勾配の指数移動平均($m_t$)と勾配の2乗の指数移動平均($v_t$)を更新する。ハイパーパラメータ$\beta_1と\beta_2\in [0,1)$が移動平均の減衰率をコントロールする。移動平均自体は勾配の一次のモーメント(平均)と二次の生のモーメント(中心化されていない分散)である。これらの移動平均は0(0ベクトル)で初期化されるので、モーメントの推定は0に向かいやすい。とりわけタイムステップの最初の方、特に減衰率が小さいとき(つまり$\beta$たちが1に近いとき)に。
しかし嬉しいことに、これらのバイアス(移動平均が０に向かいやすい)は簡単に対処できる。対処した推定は$\hat{m_t}$と$\hat{v_t}$とする。
アルゴリズム１(Adam)
$g_t^2$は要素ごとの2乗$g_t \odot g_t $を表す。
ベクトル上のすべての操作は要素ごとに行う。
$\beta_1^t, \beta_2^t$は$\beta_1, \beta_2$の$t$乗のこと。
Require:$\quad \alpha \quad$ ステップサイズ
Require:$\quad \beta_1, \beta_2 \in [0,1) \quad$モーメント推定に使う指数減衰率
Require:$\quad f(\theta) \quad$ パラメターを$\theta$とする確率的目的関数
Require:$\quad \theta_0 \quad$ 初期パラメータベクトル
$\quad m_0 \leftarrow 0 \quad$(最初の一次モーメントベクトル)
$\quad v_0 \leftarrow 0 \quad$(最初の二次モーメントベクトル)
$\quad t \leftarrow 0 \quad$(タイムステップ初期化)
$\quad$ while $\;\theta_t$が収束していない do
$\qquad t \leftarrow t+1$
$\qquad g_t \leftarrow \nabla_\theta f_t (\theta_{t-1}) \quad$ 目的関数の時刻tでの勾配
$\qquad m_t \leftarrow \beta_1 \cdot m_{t-1} +(1-\beta_1) \cdot g_t \quad$ 一次のモーメントの推定を更新（バイアスあり）
$\qquad v_t \leftarrow \beta_2 \cdot v_{t-1} + (1-\beta_2) \cdot g_t^2 \quad$ 二次の生のモーメントの推定を更新（バイアスあり）
$\qquad \hat{m_t} \leftarrow \frac{m_t}{(1-\beta_1^t)} \quad$ バイアス修正した一次のモーメントの推定
$\qquad \hat{v_t} \leftarrow \frac{v_t}{(1-\beta_2^t)} \quad$ バイアス修正した二次の生のモーメントの推定
$\qquad \theta_t \leftarrow \theta_{t-1} - \alpha \cdot \frac{\hat{m_t}}{\sqrt{\hat{v_t}+\epsilon}} \quad$ パラメータ更新
$\quad$end while
return $\theta_t$
次に示すのはテスト済みのデフォルト設定。
\alpha=0.001 \\
\beta_1=0.9 \\
\beta_2=0.999 \\
\epsilon=10^{-8}
ちなみに、わかりやすさを犠牲にして計算の次数を変えることでアルゴリズム１の効率性を改善できる。たとえばループ内の最後の３行を次のように変える：
$ \alpha_t = \alpha \cdot \frac{\sqrt{1-\beta_2^t}}{(1-\beta_1^t)} and \theta_{t} \leftarrow \theta_{t-1}- \alpha_t \cdot
\frac{m_t}{(\sqrt{v_t} + \hat{\epsilon)}} $
2.1 更新ルール
ステップサイズの慎重な選択というのが、Adamの更新ルールの重要な性質。$\epsilon=0$と仮定して、時刻tにパラメータ空間で取った有効ステップは$\Delta_t=\alpha \cdot \frac{\hat{m_t}}{\sqrt{\hat{v_t}}} \tag{1}$
有効ステップサイズは２つの上界を持つ。
|\Delta_t| \leq \left\{
\begin{array}{ll}
\alpha \cdot \frac{(1-\beta_1)}{\sqrt(1-\beta_2)} & (1-\beta_1) \gt \sqrt(1-\beta_2) \tag{2} \\
\alpha & otherwise
\end{array}
\right.
$(2)$の最初の場合はスパース性が一番ひどいときに起こる(つまり現在時刻を除くすべての時刻で勾配がずっと0の場合)。なぜ？
あまりスパースではないケースでは、有効ステップサイズはもっと小さくなる。
$(1-\beta_1)=\sqrt(1-\beta_2)$のとき、$(1)$右辺の$|\frac{\hat{m_t}}{\sqrt{\hat{v_t}}}|\lt1$であるので、$|\Delta_t| \lt\alpha$となる（２番めの場合）。
(2)の１番目の式が、$|\Delta_t| \leq \alpha \cdot 1$ となるため。左辺を展開して$| \Delta_t| = | \alpha \cdot \frac{\hat{m_t}}{\sqrt{\hat{v_t}}} |\leq \alpha $が成り立つので、
そのために $| \frac{\hat{m_t}}{\sqrt{\hat{v_t}}}| \lt 1$ となる必要がある。と考えた。
もっと一般的なシナリオでは、$\frac{E[g]}{\sqrt{E[g^2]}} \leq 1$のため、$ \frac{\hat{m_t}}{\sqrt{\hat{v_t}}} \approx \pm{1}$となる。
$\hat{m_t} \approx E[g],
\hat{v_t} \approx E[g^2]$で$\ \frac{E[g]}{\sqrt{E [g^2] }} \approx \pm1$
パラメタ空間での各時刻の有効ステップサイズの大きさはステップサイズの設定$\alpha$(ハイパーパラメータ)で近似的に有界となる。つまり、$ |\Delta_t| \lessapprox \alpha$である。これは、現在のパラメータ値の周辺で、これを超えると現在の勾配の推定が十分な情報を提供できなくなるという信頼区間を作っていると理解できる。これは$\alpha$の正しいスケールを事前に知ることを容易にする。ハイパラの$\alpha$から乖離していればおかしいって判断できる
機械学習モデルについては、たとえば、最適解が高確率でパラメータ空間のset regionにあることを事前にわかっていることがある（パラメータ上の事前分布があるときなど）。
$\alpha$はパラメータ空間でのステップの大きさ（の上界）を設定するものなので、$\theta_0$から一定数のイテレーションで最適解に到達できるような$\alpha$の正しい大きさをのオーダーを推理できることがある。用語を乱用して、比$\frac{m^t}{\sqrt{v^t}}$を信号雑音比(SN比)と呼ぶことにする。 mは勾配の平均、vは分散であった。元々のSN比は信号の分散とノイズの分散を使う
SN比が小さい時、有効ステップサイズは0に近づく。$(|\Delta_t| \leq \alpha \cdot \frac{m^t}{\sqrt{v^t}}$より)
SN比が小さいことは$\hat{m_t}$の方向が真の勾配と一致しているかどうか不確かだから、これは望ましい動作である。(不確かなときは闇雲に進んでほしくない)
たとえば、最適解に近づくにつれてSN比はたいてい０に近づく。その結果パラメタ空間では有効ステップサイズが小さくなる。これは自動アニーリングの一形態である。（最適解（谷底）周辺では勾配が０に近づくからSN比が０に近づく。その時に自動的にステップサイズが小さくなって、そこにとどまる）
有効ステップサイズ$\Delta_t$は勾配のスケールに対して不変である。なぜなら、勾配$g$を$c$でリスケールすると$\hat{m_t}$で$\hat{v_t}$を$c^2$でスケールすることになり、これは結局cがキャンセルアウトする。$\frac{ (c \cdot \hat{m^t})}{(\sqrt{c^2\cdot \hat{v_t}})} = \frac{\hat{m_t}}{\hat{\sqrt{v_t}}} $
3 初期化バイアス補正
2章で述べたように、Adamは初期値バイアス補正項を使う。二次のモーメントの推定に関してその項を導出する。（一次に関しても同様。）
モーメント($m_t, v_t$)を0で初期化しているので、その後も0になりやすいというバイアスがあった。バイアス補正は$1-\beta_x^t$で各モーメントを除することで、0にバイアスしている場合でも($\beta_x$が1に近ければ)大きな値に補正することができる。アルゴリズム1参照。
$g$を確率的目的関数$f$の勾配とする。勾配の二乗の、減衰率$\beta_2$の指数移動平均を使って、その$g$の二次の生のモーメント(中心化されていない分散)を求めたい
$g_1, ..., g_{T}$を連続するタイムステップにおける勾配とする。それぞれが背後に隠された(underlying)勾配の分布に従う。つまり、$g_t\sim p(g_t)$
指数移動平均を$v_0=0$(0ベクトル)で初期化する。まず、タイムステップtにおける指数移動平均の更新
$v_t=\beta_2\cdot v_{t-1}+(1-\beta_2)\cdot g_t^2$
（$g_t^2$は要素ごとの二乗$g_t \odot g_t$を表す）
は以前のすべてのタイムステップの関数
v_t=(1-\beta_2)\sum_{i=1}^t{\beta_2^{t-i}} \cdot g_i^2 \tag{1}
で書ける。この変形がわからない
タイムステップtにおける指数移動平均$E[v_t]$がどのように真の二次モーメント$E[g_t^2]$と関連するか知りたい。なのでその2つの間の不一致を補正する。
$(1)$の両辺の期待値を取って、
\begin{align}
E[v_t]&=E \left[ (1-\beta_2)\sum_{i=1}^{t}\beta_2^{t-i} \cdot g_i^2 \tag{2} \right] \\
&=E[g_t^2] \cdot (1-\beta_2)\sum_{i=1}^{t}\beta_2^{t-i} + \zeta \tag{3} \\
&=E[g_t^2] \cdot (1-\beta_2^t) + \zeta \tag{4} \\
\end{align}
ここでもし真の二次モーメント$E[g_i^2]$が定常であれば、$\zeta=0$である。ここも。
定常でなければ、指数減衰率$\beta_1$は過去すぎる勾配に対して指数移動平均が小さい重みを割り当てるように選ぶ必要があるため、$\zeta$は小さい値を維持する。
残っているのは移動平均を0で初期化したために現れた、$(1-\beta_2^t)$である。
アルゴリズム１では、初期化バイアスを補正するためにこの項で割る操作をした。
この章の最初に書いたこと参照。
スパースな勾配の場合、信頼できる二次モーメント推定のためには小さい$\beta_2$を選んでたくさんの勾配の平均を取る必要がある。
しかしながら、まさにこの小さい$\beta_2$では、初期化バイアス補正が足りないと最初のステップが非常に大きくなるというケースが起こる。ゼロ除算みたいなことが起こる。
4 収束性解析
Zinkevich,2003で提案されたオンライン学習フレームワークを使ってAdamの収束性を解析する。
任意の、未知な(unknown)、凸なコスト関数の系列$f_1(\theta), f_2(\theta), ..., f_T(\theta)$がある。各時刻tで、パラメータ$\theta_t$を予測し、それ以前には未知だったコスト関数$f_t$で評価したい。コスト関数の系列は元々未知であったから、regretを使ってAdamの評価を行う。よく調べていないが、regretという評価方法があるっぽい。似ているがregression（回帰）ではないらしいつまり、以前までのオンライン予測$f_t(\theta)$と、以前までのすべてのステップについての可能な集合$\chi$からの最良の固定点パラメータ$f_t (\theta_t^*)$の誤差すべての和で評価する。具体的には、regretは次のように定義する：
R(T)=\sum_{t=1}^{T}[f_t(\theta_t)-f_t(\theta^*)] \tag{5}
ここで$\theta^*=arg min_{\theta \in \chi }\sum_{t=1}^{T}f(\theta)$である。
誤差関数の評価値を最小にする最適な$\theta$が $\theta^{*}$
Adamが$\mathcal{O}(\sqrt{T})$のregret boundを持つことを示す（証明は付録）。Adamはこの一般化された凸オンライン学習問題(regretで考えている問題のことだろう)の既知の最も良い境界(bound)と同程度の結果であった。
記法を簡単にするためにいくつか定義を用いる。
$g_t \triangleq \nabla f_t(\theta_t)$ およびi番目の要素としての$g_{t,i}$である。
t時刻の勾配ベクトルを$g_t$で表す。さらにそのベクトルのi番目の要素が$g_{t,i}$
時刻tまでのすべての勾配のi番目の要素を含むベクトルを$g_{1:t,i}\in \mathbb{R}^t $と定義する。つまり$g_{1:t,i}=[g_{1,i},g_{2,i},...,g_{t,i}]$である。
また、$\gamma\triangleq \frac{\beta_1^2}{\sqrt{\beta_2}}$と定義する。
次の定理は学習率$\alpha_t$が減衰率$t^{-\frac{1}{2}}$で減衰し、一次モーメントの移動平均係数$\beta_{1,t}$が$\lambda$で指数的に減衰するときに成り立つ。$\lambda$は通常1に近い値（$1-10^{-8}$など）。
定理 4.1.
関数$f_t$が有界な勾配を持ち、すべての$\theta \in R^d$について
|| \nabla f_t(\theta)||_2 \leq G \\\\
|| \nabla f_t(\theta)||_{\infty} \leq G_{\infty}
であり、(勾配の大きさが一定以下に抑えられる)
さらにAdamの生成するいかなる$\theta_t$同士の距離も有界となる、すなわちすべての$m,n \in \bigl\{ 1, ..., T \bigr\} $について
|| \theta_n - \theta_m||_{2} \leq D, \\\\
|| \theta_m - \theta_n||_{\infty} \leq D_{\infty}
が成り立ち、(Adamの生成するパラメータ同士の距離も一定以下に抑えられる)
さらに、$\beta_1, \beta_2 \in [0,1)$が$\frac{\beta_1^2}{\sqrt{\beta_2}} \lt 1$を満たす。(さらにこれも満たすとき、)
$\alpha_t = \frac{\alpha}{\sqrt{t}}, \beta_{1,t}= \beta_1 \lambda^{t-1}, \lambda \in ( 0,1 )$とする。
すべての$T \geq 1$について、Adamは次のことが保証される。
R(T) \leq \frac{D^2}{2 \alpha (1- \beta_1)}
\sum_{i=1}^{d} \sqrt{T \hat{v_{T,i}}} + \frac{\alpha(1+\beta_1)G_{\infty}}{(1-\beta_1)\sqrt{1-\beta_2}(1-\gamma)^2} \sum_{i=1}^{d} ||g_{1:T,i}||_2 + \sum_{i=1}^{d} \frac{D_{\infty}^2 G_{\infty}{\sqrt{1-\beta_2}}}{2\alpha(1-\beta_1)(1-\lambda)^2}
(regretが一定以下になる。)
付録を読んでないので詳細はわからないが、Adamを使えばregretの値が一定以下になることが保証されるらしい。ここでのregretは各時刻でAdamの出力する$\theta$と、最適な$\theta*$を使った場合それぞれの関数の出力の差を時系列で足したものだった。つまり一定までは必ず最適な$\theta$に近づくことができるってこと?Adamすごい。他のオプティマイザの論文読んでないけど。
定理4.1.はデータ特徴量がスパースで、勾配が有界なら、(勾配の要素の)和がその上界よりもずっと小さくなる、つまり
\sum_{i=1}^{d} ||g1:T,i||_2 \ll d G_{\infty} \sqrt{T} \tag{*}
および
\sum_{i=1}^{d} \sqrt{T \hat{v_{T,i}}} \ll d G_{\infty} \sqrt{T}
が成り立つと言っている。この辺は定理4.1の最初の条件から導けそう。特に関数のクラスとデータ特徴量がDuchi et al., 2011の1.2節の形をしているときに成り立つ。未読。
彼らの期待値$E[ \sum_{i=1}^{d} ||g_{1:T,i}||_2]$についての結果はAdamにも当てはまる。
特に、AdamやAdagradのような適応的な手法は、(regret boundが、)非適応的な手法の$\mathcal{O}(\sqrt{dT})$よりも良い$\mathcal{O}(\log d \sqrt{T})$になる。
本解析において、$\beta_{1,t}$を0へと減衰させることは重要であり、従来の経験的発見とも一致している。例えばSutskever et al.,2013は訓練の最後にモメンタムの係数をへらすことが収束を改善すると述べている。
最後に、Adamの平均regretが収束することを示す。
命題4.2
関数$f_t$が有界な勾配を持つ、つまり
||\nabla f_t(\theta)||_2 \leq G \\\\
||\nabla f_t(\theta)||_2{\infty}\leq G_{\infty}
さらに、すべての$\theta \in R^d$と、Adamにより生成されたいかなる$\theta_t$同士についても、すべての$m,n \in \bigl\{ 1, ..., T \bigr\}$についてその距離が有界である、すなわち
||\theta_n - \theta_m||_2 \leq D \\\\
||\theta_m - \theta_n||_{\infty} \leq D_{\infty}
であるとする。
Adamはすべての$T \geq 1$について次のことが保証される
\frac{R(T)}{T} = \mathcal{O}(\frac{1}{\sqrt{T}})
この結果は定理4.1と
\sum_{i=1}^{d} ||g_{1:T,i}||_2 \leq d G_{\infty} \sqrt{T}
を使って得られる。上式は式$(*)$ の $\ll$ を $\leq $としたもの。導出はわからない。
ゆえに、$\lim_{T \to \infty} \frac{R(T)}{T}=0$ である。
命題4.2の保証はregretを全タイムステップ数で割ったregretの平均みたいなものが$\mathcal{O} \frac{1}{\sqrt{T}}$で抑えられて、しかも$T \rightarrow \infty$でそれが０になるって言ってる。何気にすごいこといってる
5 関連研究
この章は少し端折った。Adamの直接の親はRMSPropとAdaGrad。
Sum-of-Functions Optimizer (SFO) (Sohl-Dickstein et al., 2014)はミニバッチに基づく疑似ニュートン法だが、Adamとは異なりデータセットのミニバッチ分割において必要メモリが線形であるという制約があり、GPUのようなメモリに制約のあるデバイスでは適用できない。
natural gradient descent (NGD) (Amari, 1998)同様、Adamはデータのジオメトリに適応する事前条件(preconditioner)を採用しており、$\hat{v_t}$はフィッシャー行列の対角の近似となる(Pascanu & Bengio, 2013)
しかし、AdamのpreconditionerはAdaGradのそれ同様、その適用において、対角フィッシャー行列近似の逆行列の平方根でpreconditioningすることにより、通常のNGDよりも保守的である。
対角フィッシャー行列とかは筆者は理解していない。
RMSProp (Tieleman & Hinton,
2012): Adamと近い手法。モメンタムとの併用が使われることがある(Graves, 2013)。AdamとRMSProp+モメンタムの違いは、後者がリスケールされた勾配の上でモメンタムを使ってパラメータ更新するのに対して、Adamでは勾配の一次・二次のモーメントの移動平均使って直接推定されること。
RMSPropはバイアス修正項がないので、$β_1$が１に近いときに問題になり（スパースな勾配のときに必要。）、このケースではバイアスを修正しないとステップサイズがかなり大きくなり、発散することもある。セクション6.4でも説明する。
AdaGrad(Duchi et al., 2011)
スパースな勾配でうまく動く。基本は$\theta_{t+1}=\frac{\theta_t-α\cdot{g_t}} {\sqrt{\sum_{i=1}^{t}g_t^2}}$で更新する。$\beta_2$を下から無限に１に近づけた時、$lim_{\beta_2\to{1}}\hat{v_t}=t^{-1}\cdot\sum_{i=1}^{t}g_t^2$になる。
補正済み二次モーメント(勾配の分散みたいなもの)が勾配$g_t$の2乗の平均みたいなものになる。ここでは$\beta_2$が1に近づくので、$\hat{v_t}$は$v_t$のゼロ割みたいなことになり、かなり強い補正が効いているんだろう。
AdaGradはAdamの$\beta_1=0$, $(1-\beta_2)$が無限小, $\alpha$を焼きなまし(annealed)版の$\alpha_t=\alpha\cdot t^{-1/2}$に置き換えたものに相当する。つまり
$
\theta_t-\alpha \cdot t^{-1/2} \cdot
\frac{\hat{m_t}}{\sqrt{\lim_{\beta_2\to 1}\hat{v_t}}}=\theta_t-\alpha\cdot t^{-1/2}\cdot \frac{g_t}{\sqrt{t^{-1} \cdot
\sum_{i=1}^t g_t^2}}=\theta_t- \frac{\alpha\cdot g_t}{\sqrt{\sum_{i=1}^t g_t^2}}
$
この式は2.1節でステップサイズの上界を調べたときの$(1)$式に今考えている役者を代入したもの。Adamとの違いは最右辺に移動平均たちが登場せず、そのまま勾配を使っていること
バイアス修正項をなくした場合はこの対応は維持されない。
RMSPropのようにバイアス修正なしでは、$\beta_2$は無限に$1$に近づきバイアスが大きくなり、パラメータ更新が無限に大きくなる。
AdamはRMSPropより安定するようにしたもの。AdaGradに対しては意味的にはどういう関係なんだろう
まとめ
以上が5章までの要約とメモとなる。
筆者の理解でまとめると、Adamは
- パラメータ更新時に、勾配をそのまま使用ではなく、指数移動平均とバイアス補正で調節している。
- そのことでRMSPropより安定している
- パラメータ更新幅について、ハイパラで上界を設定できる。
- 理論的に、最適な場合との差が一定以下に保証されるなどの良い性質がある
本当に理解するには実装するしかない。