確率的最適化

確率的最適化

インターネット、センサ技術およびコンピューターの発達により、さまざまな種類のデータが大量に手に入る現在、大量のデータから意味ある情報を取り出すための機械学習技術が注目され、大きく発展している。多種多様なデータが取得可能になったことで様々な問題が解けるようになった一方で、データサイズの肥大化による計算量増大の問題が生じている。

機械学習での確率的最適化とは、ランダムなサンプルを用いた最適化問題の解法のことを指すものとなる。通常の最適化問題では、目的関数を最小化するために、全ての訓練データを使用して最適化する必要があるが、データセットが大規模である場合、これは非常に計算量が大きくなるため、確率的最適化を用いることで、ランダムに選択されたサブセット（ミニバッチ）のデータを使用して最適化を行い、計算量を大幅に削減することができる。また、ランダムに選択されたデータを使用するため、最適化の収束が速くなる場合もある。

確率的最適化手法の代表的なものには、確率的勾配降下法（Stochastic Gradient Descent; SGD）がある。SGDは、最小化する目的関数の勾配の方向に従って、パラメータを更新していくもので、通常の勾配降下法では、全てのデータを使用して勾配を計算しているのに対して、SGDでは、ランダムに選択されたミニバッチに含まれるデータだけを使用して勾配を計算するものとなる。SGDは、ニューラルネットワークの学習において特に効果的であり、現在では機械学習において広く使われている手法となる。

また、SGDには、SGD with MomentumやAdamなどの改良版があり、より高速に収束することが知られており、これらの手法は、学習率の調整やノイズの低減によって、SGDの性能を向上させている。

ここではこれらの機械学習における確率的最適化の諸手法について述べる。

実装

• 機械学習における確率的最適化の概要と実装

確率的最適化は、確率的な要素を含む最適化問題の解法を表し、機械学習での確率的最適化はモデルのパラメータを最適化する際にに広く使用されている手法となる。一般的な最適化問題では、目的関数を最小化または最大化するために、パラメータの最適な値を見つけることが目標であるのに対して、確率的最適化は、目的関数にデータの変動や観測誤差など、さまざまな要因によって引き起こされるノイズやランダム性が含まれる場合に特に有用となる。

確率的最適化では、最適解を見つけるためにランダムな要素や確率的なアルゴリズムが使用される。例えば、機械学習の分野では、ニューラルネットワークの重みやバイアスなどのパラメータを最適化するために確率的最適化手法が頻繁に使用される。代表的な手法であるSGD(Stochastic Gradient Descent)では、データセットのサンプルをランダムに選択し、そのサンプルに基づいてパラメータを更新することで最適化を行うことで、モデルはデータセット全体を使用することなく効率的に学習することができる。

ここでは、SGDとミニバッチ勾配降下法、Adam、遺伝的アルゴリズム、モンテカルロ法でのpythonによる実装とそれらの適用事例として、パラメータチューニング、特徴選択と次元削減、k-meansへの適用実装例について述べている。

理論

• 機械学習プロフェッショナルシリーズ 確率的最適化 読書メモ

教師あり学習や凸解析の復習から、大量データ解析に有用な並列分散確率最適化まで丁寧に解説する。基本技法も新しいトピックも、きちんと理解できる1冊。式の成り立ち、アルゴリズムの意味がわかる。証明を極力略さず示す大規模計算実行までの本当の早道

• 教師あり学習と正則化

機械学習の設定は大きく分けて、教師あり学習と教師なし学習の2つとなる。教師あり学習は画像の判別や遺伝子データからの疾患の予測のように、ある入力x(特徴量)からそれに対応する出力y(ラベル)を予測する問題となる。教師あり学習の代表的な問題として、回帰(regression)と判別(classification)がある。

過学習を避ける方法としては、適切なモデルを選ぶこと以外にも、正則化(regularization)がある。モデルの選択も生息かもどちらもデータにあった適切な複雑さの関係を選ぶという点で、本質的には同じとなる。正則化法はモデルの中で訓練誤差をそのまま最小化するのではなく、その「複雑さ」に応じた罰則を加えて最小化するものとなる。

• 確率的最適化における凸解析の基本事項(1)凸関数と劣微分、双対関数

今回は凸解析の基本事項について述べる。確率的最適化の各種技法は凸解析を基盤として、その上に成り立っている。ここでは、確率的最適化に必要な凸解析の基本事項について述べる。特にアルゴリズムの構成において重要なフェンシェルの双対定理や近接写像、強凸関数と平滑凸関数の導入を行う(凸解析のより詳細についてはロッカーフェラーによる本を最小のこと)。なお、正則化学習法の(確率的でない)最適化法に関しては、”スパース性を用いた機械学習“が参考となる。

• 確率的最適化における凸解析の基本事項(2)フェンシェルの双対定理と近接写像と強凸関数

今回は凸解析の重要な要素であるフェンシェルの双対定理と近接写像と強凸関数について述べる。

• 確率的最適化とオンライン最適化

機械学習における確率的最適化は、主に大規模データでの学習を容易にするために用いられる。現在の機械学習応用では、自然言語・画像・音声など、高次元かつ大量のデータを扱うことが頻繁に要求されている。

学習に必要な最適化に汎用のソルバーをそのままあてはめてしまうと、1回の更新に最低でもサンプルサイズx次元のオーダーがかかってしまうので、データが巨大なときは1回の更新の終了まで長い時間またなければならない。しかも、いつ終わるかの予測が立てづらいという問題もある。

このような問題を解決するために、データを適切に分割し、ランダムにその小さな部分問題を解いていき、結果的にデータ全体を用いた最適化を解いてしまおうというのが確率的最適化のアイデアとなる。確率的最適化には大きく分けて、オンライン型確率的最適化(online stochastic optimization)と、バッチ型確率的最適化(batch stochastic optimization)に分けられる。

• 機械学習のためのオンライン型確率的最適化と確率的勾配降下法

今回はオンライン型確率的最適化の最も基本的なアルゴリズムである確率的勾配降下法(stochastic gradient descent SGD)について述べる。(ネステロフの加速法、凸関数の最適化を勾配法で解く、ラグランジュの未定乗数法、ユークリッドノルム、収束レート、KLダイバージェンス、指数勾配降下法、ニュートン・ラフソン法、ブレグマンダイバージェンス、確率的鏡像降下法、狭義凸関数、リプシッツ連続、損失関数、射影勾配法、SGD、コーシー・シュワルツの不等式、ミニマックス最適、最急降下法)

• 機械学習のためのオンライン型確率的最適化と確率的双対平均化法(SDA)

確率的双対平均化法(stochastic dual averaging ,SDA)は、確率的勾配降下法と並んで重要な最適化技法となる。双対平均化法は、もとは非確率的最適化の文脈でネステロフによって提案されていたが、エンライン型確立的最適化にも変形することができる。確率的勾配降下法の理論解析では\(E_{z_{1:t}}\{||\beta_t-\beta*||^2\}\leq D^2(\forall t\geq 1)\)なる条件が出てきたが、確率的双対平均化法ではこのような条件が必要ない。すなわち、自動的に変数の有界性が保証される。また、L1正則化のようなスパース正則化を用いた時、よりスパースになりやすいという実用上の利点もある。

• 機械学習のためのオンライン型確率的最適化とAdaGrad、ミニマックス最適化

ここでは、AdaGradと呼ばれる、適応的に各座標の更新幅を調整する方法について述べる。スパース正則化のオンライン学習においては出現頻度の低い特徴量がある場合、その特徴量に対応する係数が毎回スパース正則化によって0に潰されてしまうという現象が起きる。勾配降下方の更新式を考えると、L1正則化を使った場合毎回βtはソフト閾値関数を通して得られる。

ここまで述べてきた手法はどれも、一般的には\(O(1/\sqrt{T})\)の収束、今日凸ならO(1/T)の収束を示した。実際にこれらがミニマックス最適(mini-max optimal)という意味で最適であることが示されている。誤解を恐れずに端的に言えば「関数値と勾配を用いたどのような確率的最適化手法」に対しても(定数倍を除いて)負けることはない、という性質を持つ。

• バッチ型確率的最適化 – 確率的双対座標降下法

今回は、バッチ型の確率的最適化での確率的双対座標降下法について述べる。バッチ型確率的最適化はすべてのサンプルがすでに得られている状態で速い収束を達成する方法となる。

• バッチ型確率的最適化 – 確率的分散縮小勾配降下法と確率的平均勾配法

“バッチ型確率的最適化 – 確率的双対座標降下法”では、双対問題を用いることで指数オーダーの収束を実現する各釣り的最適化を構成した。ここでは確率的分散縮小降下法(SVRG)と呼ばれる、指数損失にあいて指数オーダーを達成する方法について述べる。

• オンライン型確率的最適化の分散処理

並列計算と確率的最適化は比較的相性がよく、これまで述べてきた方法を修正することで並列計算が可能となる。ここでは、さまざまな並列計算が可能となる。ここでは、さまざまな状況に対応す手法を列挙する。各種手法の概要は以下のようになる。単純平均、ミニバッチ法、非同期型分散SGD、確率的勾配降下法、分散環境での確率的最適化

• バッチ型確率的最適化の分散処理としての確率的座標降下法

前回まででオンライン型の確率的最適化を主軸にして並列分散計算方法について述べたきた。今回はバッチ型確率的最適化における並列近似誤差について述べる。特にその中でも実装の容易な座標降下法における並列近似誤差について述べ、主問題を扱う方法と双対問題を扱う方法について述べる。