//---はじめに---
こんにちは。Machine Learning Advent Calendar 2013の11日目を担当することになりました@vaaaaanquishです。今回は大学で研究している進捗としてstochastic average gradient(SAG)についてまとめていきたいと思います。「前年度も誰かがやってたような･･･」と思った方はきっと記憶違いです。よろしくお願いします。
//---SAG---
SAGはNIPS2012で発表*1されたオンラインアルゴリズム最適化手法の一つです。その名の通り更新時に確率的勾配の「Average」を取るアルゴリズムです。このような平均化されたアルゴリズムは、averaged stochastic gradient descent*2やSample Average Approximation*3のように昔から数多くの研究が行われていました(図書館で論文を読みあさっている時に偶然知りました)。今回紹介するSAGでは、ある条件の下で計算のコストが定数オーダーで線形収束する事の証明が成されています。要するにとても早いです。とてもすごい。
//---SGとFG---
NIPS2012の論文では、IntroductionとしてStochastic Gradient(SG)とFull Gradient(FG)の比較を行っています。なぜなら、SAGが実質これら２つの良いとこ取りのようなアルゴリズムであるからです。
FGは損失関数の和等を最小にしたい時、有限のサンプルの平均から最適化します。所謂「バッチアルゴリズム」です。FGはそのアルゴリズム上、凸な問題と一定のステップサイズを考えた時、k回の更新によってで線形収束します(
<1)。しかしながら、全てのサンプルを見る為に、毎回計算にかかるコストが一定で大きいというデメリットがあります。
それに対してSGは、サンプルの中から一様に(確率的に)データを選び更新を行う「オンラインアルゴリズム」です。こちらは全てのデータを見る訳ではないので計算コストが小さくなります。収束もFGのようにはいかずともが期待できます。
SAGは、より強い仮定のもとで、これらFGの収束とSGの計算コストを最適に取り込み、より高速な最適解への収束を可能にしたアルゴリズムです。
//---The SAG method---
SAGの反復は以下のようにして行われます。
上式のは有限のデータ、
はランダムな訓練例です。一見上の式だけ見るとFGのように見えますが、実際はオンラインアルゴリズムのようにランダムな訓練例によって更新されます。しかし、更新の際に使うGradientは、その時点までに見てきたデータを復元し、その平均を用います。
つまり、ランダムに選ばれた訓練例を記憶しておいて、それらの平均を取って更新に利用すれば、回数を重ねる毎に見るサンプルデータが増え、徐々にFGで得られるようなFullGradientに近似されるといった考え方になります。
実装の際には、｢現在の(平均化された)Gradient｣に加えて｢今まで見たデータを復元出来る情報｣を保持しておく必要があります。これは、同じ次元のベクトルとして保存しておけば良いので、やたらメモリを食う等という事もありません。さらに、最初の数回SGを回すと高い収束率を維持することが出来ます[要出典]。
//---強い仮定---
SAGは、どんな最適化問題に対しても良い性能を発揮する事が保証されている訳でもありません。主な条件としては「問題がStrongly Convex(強凸)」「二回微分可能である(≒リプシッツ連続)」があります。前者は機会学習等では満たされない条件ですが、正則化項の追加によってほとんどの問題で解決する事が可能でしょう。後者は簡単な話急傾斜になるような問題で無い事が求められます。
//---Results---
以下は論文内での実験の結果です。
見て分かるように、SAGの良い収束速度を示しています(自分が実装した訳ではないので一概には言えませんが)。Objective mlnus OptimumもTest Logistic Lossもどちらも成果を出しているという事で素晴らしいですね。問題によっては、SGの倍以上の性能を出せるというならば、色々な所で実装される日も近いのではないでしょうか。
//---SAGとこれから---
そもそも今平均化されたオンラインアルゴリズムが話題となる理由として、深層学習等の学習器の発展があると考えています。私もニューラルネットを学び、DeepLearningを知り、応用を考えてこのようなアルゴリズムを勉強し始めました。様々な最適化問題に簡単に実装出来るようになる事がこのアルゴリズムの発展にも繋がると考えています。さらには、他のFOBOSのようなオンラインアルゴリズムでも似たような平均化手法が使えたり、もしかしたらSAGが非効率になるような物も見つかるのかも･･･。楽しみですね。私自身実装して実験している最中ですが、気になったという方は一度試してみてはいかがでしょうか。
(「勉強会で証明を解説します」という時は連絡してくれると嬉しいです///)
//---おわりに---
以上で私のMachine Learning Advent Calendar 2013記事を終了します。ほぼ「卒論に向けてのメモ」状態で申し訳ない気持ちでいっPythonです。内容の薄い記事ですが、このような機会を提供してくれたnaoya_tさん、紹介して頂いたkazoo04さんに感謝しております。今後大学院で学会等にも発表者として参加出来るよう精進して行きたいと思います。先輩方の意見と記事を楽しみに残り少ない2013年を過ごしたいと思います。少し早いですが、良いお年を。
//---参考---
