勾配降下法の最適化アルゴリズムを概観する
という神みたいな記事に対して、さらっと読んで最小限のイメージっぽいのをメモ程度にまとめたものです。
上記のリンクの記事を読むととてもわかりやすいかと思います。それを読みつつなるべく要点絞ったものを以下に備忘録として書きました。
一旦公開にしますが、簡単なpythonやC++での実装例なども、追加していきたいと思います。
そもそも勾配降下法とは
特に何かしらの目的関数を最適化(最小化,最大化)する問題を数値解析的に解くことに帰結するような問題に勾配降下法が使われます。なので、微分して0になるような値は何か的なものをプログラムで解くような感じです。
1. 最急降下法(バッチ学習)
仕組みとしては、まず最初にスタート地点を選び、その点での一番降下する傾きが大きいベクトルを利用して次のステップへと更新していく方法です。
みたいなステップで収束を繰り返す処理をしています。(wikipediaより)
$Q_{i}$ は $i$ 番目の訓練データ
2. 確率的勾配効果法(SGD)
$Q(w)$ の勾配は、1つの訓練データから計算した勾配で近似する。
上記の更新を1つ1つの訓練データで行い、訓練データ集合を一周する。収束するまで訓練データ集合を何周もする。一周するたびに訓練データはランダムにシャッフルする。AdaGrad などの適応学習率のアルゴリズムを使用すると収束が速くなる。擬似コードでは、確率的勾配降下法は下記になる。
パラメータ $w$と学習率$\eta$の初期値を選ぶ
$while$ 収束するか所定の反復回数まで反復する $do$
$Q_{i}$（訓練データ）をランダムにシャッフルする
for each i = 1, 2, ..., n do
$w:=w-\eta \nabla Q_{i}(w)$
$w := w - \eta \nabla Q_i(w)$
(wikipediaより)
勾配降下法の最適化アルゴリズム
1. Momentum(慣性)
丘からボールが落ちるのと同じで、転がり落ちる際に勾配の方向に加速して行きます。
今ボールが落ちている方向(慣性)と、勾配方向が同じなら加速、逆なら原則という感じの更新方法。
2. Nesterovの加速勾配降下法
Momentum(慣性)はただのボールでしたが、Nesterovの加速勾配降下法は賢いボールです。
坂道を駆け下りている時に、すごい加速してますが、未来のパラメータの推定位置を計算して(現在のパラメータに関する勾配計算ではなく、次のパラメータの近似値を用いる)、下った先にまた坂があるのなら原則するような感じ。
3. Adagrad
Adagradは情報的に稀なものの比重を大きくして更新を行います。Gt,iiという対角行列の形で、これまでのθiに対する勾配の二乗和を持たせて、一般的な学習率を修正している。Adagradの利点として手動で学習率の調整を行わなくて良い点がある。欠点として過去の勾配が訓練の間増加し続け、学習率が低下してくる。
4. Adadelta
Adagradの発展で、急速かつ単調な学習率の低下を防ぐもの。Queueのような形で過去の勾配を蓄積する領域を一定に制限しています。
ただ、前のタイムスタンプにおける勾配の二乗をw個保持しておくのは非効率なので、代わりに勾配の合計値を過去のタイムスタンプ全ての勾配の二乗を減衰平均化して再帰的に定義。
タイムスタンプt時点においての移動平均は、その時点での勾配と過去の平均にのみ依存することなる。
この時、AdagradでいうGt,iiという対角行列を過去の勾配の二乗の減衰平均で置き換えると、パラメータと単位が一致しなくなる？ので、勾配の二乗の減衰平均ではなく、パラメータ更新の二乗についての減衰平均を用いることにしてるらしい。
更新規則の学習率をRMS(二乗平均平方根)に置換するとAdadeltaの式が導かれる。学習率そのものが式から消えた形となる。
$r_t = \beta r_{t - 1} + (1 - \beta) \nabla Q_i(w) \circ \nabla Q_i(w)$
$v_t = \frac{\sqrt{s_t} + \epsilon}{\sqrt{r_t} + \epsilon} \circ \nabla Q_i(w)$
$s_{t+1} = \beta s_t + (1 - \beta) v_t \circ v_t$
$w_{t+1} = w_t - v_t$
5. RMSprop
Adagradの急速に学習率が低下する問題を解決しようということでAdadeltaと同時期に提案された手法。
内実はAdadeltaの最初のベクトル更新と同じ。
6. Adam
Adaptive Moment Estimationの略で、それぞれのパラメータに対して学習率を計算し適応させていく手法。Adadeltaなどで行われていた勾配の二乗Vtの減衰平均の蓄積に加えて、過去の勾配mtの指数関数的減衰平均を保持しているらしい。少しMomentumに似てる？
mt: 勾配の一次モーメント(平均値)の概算値
vt: 勾配の二次モーメント(分散した平方偏差)の概算値
Adamは他の適応率学習のアルゴリズムと比べて優れている点で実証されたらしい。
図(このセクションは完全に引用)
下記の2つのアニメーション（作者： Alec Radford）は上記の最適化アルゴリズムによる最適化の動きを直感的に示しています。
まとめ(このセクションもほとんど引用)
要約すると、RMSpropは、劇的に減少する学習率に対処するAdagradの拡張だということです。これはAdadeltaと全く同じですが、Adadeltaが分子の書き換えルールにおいてRMSのパラメータの書き換えルールを使うという点が異なっています。Adamは最終的にRMSpropにバイアス補正とMomemtumを加えます。この点においては、RMSprop、Adadelta,、Adamは似た環境下で順調に動く、よく似たアルゴリズムです。Kingmaら14によれば、Adamはバイアス補正によって勾配が少なくなるのに従って最適化を目指すRMSpropよりも、ほんの少し優れているということです。Adamは全般的に最も良い選択かもしれません。
したがって、急速に収束させること、および、深くて複雑なニューラルネットワークを重視するならば、学習率を適応させていく手法から1つを選ぶべきです。
SGDの並列化と分散化
Hogwild!
これに関して @KazukiOsawa がまとめたものがいい感じだと思いました。
Downpour SGD
GoogleにおいてDisbelliefのフレーム(tensorFlowの全身)で使われていたもの。訓練データのサブセットを並列的にモデルのレプリカをいくつも動かして、更新をパラメータサーバーに送るが、それぞれのマシンでやりとりしないので分散や収束の遅延のリスクがある。
SGDのための遅延耐性アルゴリズム
Adagrad
McMahan & Streeter16は、Adagradを並行処理のセッティングまで拡張しました。
TensorFlow
2016/4/13：TensorFlowの分散バージョンがリリースされました。
Elastic Averaging SGD
Zhangらが提唱しているElastic Averaging SGD (EASGD)のabstractを翻訳して要約すると以下のような形になります。
通信制約のもとでの並列コンピューティング環境における深層学習のための確率的最適化問題の研究。
並行処理（ローカルワーカー）間の作業の通信と調整が、パラメータサーバ（マスタ）によって保存された中心変数で計算されるパラメータをリンクする弾性力に基づく新しいアルゴリズムが提案されています。
このアルゴリズムは、ローカルワーカーがより多くの探索を実行することを可能にします。すなわち、アルゴリズムは、ローカルワーカーとマスターとの間の通信量を減らすことによって、ローカル変数が中心変数からさらに変動することを可能にし、経験的に、より多くの探索を可能にすることにより、改善された性能につながる可能性があると言えます。実験では、DOWNPOURや他の一般的なベースライン手法と比較して新しいアルゴリズムが深いアーキテクチャのトレーニングを加速し、さらに通信効率が非常に良いことが実証されています。
SGD最適化の更なる戦略
シャッフルとカリキュラム学習
最適化アルゴリズムに偏りを与えてしまうかもしれないため、通常は、学習モデルに訓練例を意味ある順で提供するのは避けようとします。そのため、エポックごとに訓練データをシャッフルすると良い場合が多いらしい。
逆に、この意味ある順を確立する方法をカリキュラム学習と言う。
バッチ正規化
学習を促進するために、一般的に、パラメータの初期値を平均0・分散1に初期化することによって正規化します。訓練が進み、パラメータを異なる範囲に更新するにつれ、この正規化は失われます。その結果、ネットワークが深くなっていくと、訓練速度が落ち、変化の幅が大きくなります。バッチ正規化は、ミニバッチごとに再び正規化を行い、加えて、この処理によって変化が逆伝搬されます。正規化をモデルアーキテクチャの一部とすることにより、学習率を上げ、初期化パラメータにあまり注意を払わずに済みます。
早期終了
訓練中、検証用データセットの誤差を常に監視し、検証の誤差が十分に改善に結び付かない場合は、ある程度粘り強く対応した上で、終了すべきです。
勾配ノイズ
このノイズを付加することにより、ネットワークの不十分な初期化に対するロバスト性が向上し、特に深く複雑なネットワークを訓練するのに役立つことを示しています。付加されたノイズによって、モデルが新しい極小値から抜け出したり見つけたりする機会を増やす可能性がある。