確率的最適化 ４章

背景

研究で確率的最適化の研究をすることになりまして。

鈴木大慈先生の「確率的最適化」を読むことになりました。

個人的に４章の内容が重くて尚且つ重要だと感じたので備忘録的な感じで書き連ねていきたいと思います。

４章の話をする前に確率的最適化が何かというお気持ちの部分についておさらいしていこうと思います。

A.大規模データでの学習を容易にするために用いられることが多い。

確率的最適化の１番のメリットは計算量が少なく最適解に向かうことができる点です。

他にもオンライン学習ができるということや局所解にはまりにくいといった恩恵もありますが今回の主題は凸最適かを問題としているため割愛します。

具体的には最急降下法とSGD（確率的勾配降下法）が比較されることが多いです。例えば私たちが持っているサンプル数がNだとした時

最急降下法では毎回の勾配の計算にO(N)の計算量がかかるのに対してSGDはO(1)で計算することができます。これはNが大きくなればとてつもない差になるでしょう。

A.はい。早いです。ですが、、、

最急降下法はある条件下（強凸かつ平滑）において指数的なオーダーで収束することが知られています。しかし実際には機械学習においてよく確率的最適化が用いられます。その理由は確率的最適化を学習手法としてみなした時十分な性能を示すからです。

学習の目的は訓練誤差を最小化することではなく汎化誤差を最小化することが目的なのです。

最急降下法がいかに訓練誤差を早く収束させようとしても汎化誤差が大きくなってしまうのでは意味がないのです。訓練誤差は必ずしも完全に最適化する必要はないのです。

ある程度の最適化がうまくいってるならば最適化の誤差はデータのばらつき（ノイズ）によって埋もれてしまうことが多いです。

確率的勾配降下法の学習の進み方の例

最急降下法の学習の進み方の例

確率的最適化では逐次的にサンプルを使います。ここではこの逐次的に使うサンプル数は1とします。

時刻tで使われているサンプルを\(z_t\)とします。時刻tといういう形をしてますが単純に使ったサンプルの個数と考えて問題ないです。

教師あり学習では\(z_t\)は(\(x_t\),\(y_t\))というような特徴量とラベルの組みです。

また確率的最適化では重要な仮定として\(z_t\)は確率分布Pから独立同一に発生していると仮定します。\(z_t\sim P\)という形でこのことを書き表します。

現在執筆中です。。。