More than 5 years have passed since last update.

最急降下法とニュートン法を用いた最適化

Last updated at 2017-09-29Posted at 2017-09-29

自主学習まとめ. 自分にわかりやすく書いてます...
[番号]は文末に引用元を表記. 番号が振られていない引用は全体を通して参照.
変なことを書いてる可能性あり...

0. イントロダクション

機械学習とはデータからパターンを学ぶことであり, 具体的には教師あり学習においては, コスト関数の曲線の極小値を見つけることである. 多くの問題は次のステップで解く.

トレーニングデータセットを表すモデルを定義する
コスト関数を定義する
2. コスト関数に使う損失関数を決定する
コストが最小になるように最適化する

ステップからわかる通り, これらは三つは密接に関連している. ここではコスト関数の極小値を求める方法について紹介する.

1. コスト関数

本題に入る前に整理するために, コスト関数の定義に立ち帰ろう. コスト関数とは目的関数の一種で, 計算で算出した結果と実際の結果との差を示す. 即ち, この差が小さいほど, 誤差が小さく精度が高いといえる. コスト関数の極小値の見つけ方に入る前に,目的関数, コスト関数, 損失関数について図1にまとめた.

図1 目的関数・コスト関数・損失関数の関係
(参考：Objective function, cost function, loss function: are they the same thing?)

コスト関数の多くは二乗誤差などの統計モデルに由来する. これらのコスト関数は通常凸関数の損失関数で定義される. 簡単のために, 損失関数$L$が誤差平方和のコスト関数$J(\theta)$を考える.

J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_\theta(x^i)-y^i)^2\tag{1}

式(1)に見るように, コスト関数$J$は微分可能な下に凸関数であり, 極小値を求めることができる. 降下法とはコスト関数の微分（傾き）情報を用いることで, 各反復において必ず極小値に近づいていく方法である. 重要となるのは探索方向とステップサイズで, 探索方向の種類として最急降下法, ニュートン法, 準ニュートン法がある.

2. 最急降下法（勾配降下法） Gradient Descent, Steepest Descent

コスト関数$J$を最適化するために最もよく使われるアルゴリズムが最急降下法（勾配降下法）である. 一次微分を利用する方法である.

図1 左：グラフ全体が既知　右：一部のみわかる

図1にコスト関数の例を示した. 横軸が重み$\theta$で縦軸がコスト関数$J(\theta )$である. 図右のように,グラフ全体が既知の時は極小値が点Aであると簡単にわかるが, 左のように一部しかわからないようなときはどうすればいいか. 前提知識として極小値では偏微分（＝コスト関数の傾き$\nabla _\theta J(\theta)$）の結果が0となる. そこで限りなく偏微分の結果が0になった点が解である. なお, 図は１次元であるが実際は多次元のため, 傾きの方向が非常に大切になる.

2.0.1 アルゴリズム

点Bで$\theta$について偏微分を行う
傾きが負であると得られる
下に凸のグラフなので, 傾きを0にするために点Bよりも重み$\theta$が大きい点Cで偏微分を行う
傾きが正であるとえられる
次に$\theta _B <\theta <\theta _C$で偏微分を行う
これを繰り返し次々に新しい点で偏微分を行う
偏微分の結果が0に近くなったら終わり

このときのステップ（BとCの幅）を学習率$\eta>0$という.

2.0.2 ステップサイズ＝学習率を決定する

$\eta$が小さすぎると全然収束せず, 大きすぎると最適解を飛び越える可能性がある（図2）.

図2 左：$\eta$が小さすぎるとき右：$\eta$が大きすぎ最初とは別の極小値をもつ値の偏微分を見ているとき

最適な学習率$\eta $を求める問題を直線探索という.
勾配を計算するのに使うデータ量の違いにより, 次の勾配降下法がある.

2.1 バッチ勾配降下法 batch gradient descent

一般的な最急降下法（勾配降下法）のことをバッチ勾配降下法と呼ぶ. バッチとは「ひとかたまり」を意味し, 一度にトレーニングセットのデータ全体の重さ$\theta$を計算し, コスト関数$J(\theta)$の勾配を計算する. ステップ数が進むにつれて, 重さ$\theta$も次のように変化する. ここで$\tau $はステップの繰り返しの回数である.

\theta ^{\tau +1}=\theta ^\tau -\eta \nabla J(\theta ^\tau)\tag{2}

バッチ勾配降下法の問題点は, 全データを計算して重み$\theta $を変更していくため収束が遅く, データ量が多いと計算量が莫大になることである. ここで勾配方向は$-\nabla J(\theta ^\tau)$が勾配方向である.

2.2 確率的勾配降下法 stochastic gradient descent, SGD

上述したバッチ勾配降下法の問題点を解決する手法として, トレーニングデータセットの中からランダムに選択した異なったデータに対して, パフォーマンスの結果を比較しするアルゴリズムである確率的勾配降下法が開発された. これは, 逐次的勾配降下法 (iterative gradient descent)とも呼ばれる.

2.2.1 数学的背景

ここで実際の結果と計算結果との誤差をコストを定義すると

cost(\theta, (x^i, y^i))=\frac{1}{2}(h_\theta(x^i)-y^i)^2\tag{3}

このコストを用いてコスト関数は,

\begin{align}
J(\theta)&=\frac{1}{2}\sum_{i=1}^m cost(\theta, (x^i, y^i))\tag{4}\\
&=\frac{1}{2}\sum _{i=1}^m J_m(\theta)\tag{5}
\end{align}

となる. ここで, 重み$\theta$は

\theta ^{\tau +1}=\theta ^\tau -\eta \nabla J_m(\theta ^\tau)\tag{6}

であり, バッチ勾配降下法の式(2)と全く同じであるが, データが1点だけであることに注目したい. つまり, バッチ勾配降下法はイテレーションが進むにつれコスト関数は小さくなったが, 確率的勾配降下法では1つのデータ点対してフィットするように重み$\theta$を変更するため単調減少とは限らない. つまりバッチ勾配降下法では極小値に到達するが, 確率的勾配降下法では極小値付近で解が収束する.

この数式のアルゴリズムを次の節に言葉でまとめた.

2.2.2 アルゴリズム

データをランダムにシャッフルする
$i=1$として$\theta_0$を計算, 更新する
$\theta_n$まで繰り返す ($\theta_j:=\theta_j-\eta(h_\theta x^i-y^i)x_j^i$)
2-3を$i=m$まで繰り返す

2.2.3 オンライン勾配降下法 online gradient descent

オンライン学習 (online learning)
オンライン学習ではwebを通して新たなトレーニングセットが来た時に, そのデータセットを使って重み$\theta$を更新する方法である. 確率的勾配降下法に非常によく似ているが, 確率的勾配降下法では固定されたデータセットに対して一つ一つ取り出して学習させるのに対し, オンライン学習はユーザーアクション等からひとつだけトレーニングサンプルとして取り出して学習させ, 学習が終わるとデータは破棄される. これはユーザーの嗜好の変化に適応できるという利点がある.

2.3 ミニバッチ勾配降下法 mini-batch gradient descent

重み$\theta$の更新のために, バッチ勾配降下法では全データを計算し, 確率的勾配降下法では1データサンプルを計算した. この折衷案としてデータサンプルサイズをミニバッチサイズ$b$とした勾配降下法がミニバッチ勾配降下法である. 確率的勾配降下法はデータ数分のforループで計算を回すが, ミニバッチ勾配降下法は取り出した$b$個のデータサンプルをベクトルに格納するため計算も早い. 典型的なバッチサイズは10であり, 一般的には$2\leq b\leq 100$の値をとる$^{[1]}$. 各勾配降下法について表1にまとめた.

表1 勾配降下法

	バッチ勾配降下法	確率的勾配降下法	ミニバッチ勾配降下法
重さ$\theta$の更新に必要なデータ数	全データ	1	1<b<全て
計算コスト	高	低	低

2.3.1 数学的背景

ミニバッチサイズ$b(1<b<all)$とすると,

\theta ^{\tau +1}=\theta ^\tau -\eta \frac{1}{b}\sum_{k=0}^{b-1}\nabla J_k(\theta ^\tau)\tag{6}

3. 最急降下法以外の最適解を探すアルゴリズム

最急降下法はジグザグに動きながら最適解に近づくので収束速度が遅く効率が悪い. そこで別の方法で最適解を探す.

3.1 ニュートン法　Newton method

最急降下法でうまくいかないとき, 一次微分の情報に加え, 二次微分の情報であるヘッセ行列$H$を用いる方法がニュートン法である. 最急降下法に比べて, 効率よく最適解に到達することができる.

3.1.1 数学的背景

最適化したい関数$f: \mathbb{R}\mapsto \mathbb{R}$を仮定し, $f(\theta)=0$となる$\theta$を求める. ここで$\theta \in \mathbb{R}$とする. まず$\theta$に近い値$\theta_0$をとり, 関数$f(\theta)$上の点$(\theta_0, f(\theta_0))$における接線を引く. 接線が$\theta$軸と交わる点の$\theta$座標を$\theta_1$とする. このとき$\theta$のまわりで二次のテーラー展開をすると,

f(\theta)=f(\theta_0)+f'(\theta_0)(\theta-\theta_0)+O((\theta-\theta_0)^2)

このとき(右辺)=0の解は,

\theta=\theta_0-\frac{f(\theta_0)}{f'(\theta_0)}

$\tau$をiterationの回数として一般化すると

\begin{align}
\theta_{\tau+1}&=\theta_\tau-\frac{f(\theta_\tau)}{f'(\theta_\tau)}\\
\theta &:= \theta - \frac{f(\theta)}{f'(\theta)} \tag{4}
\end{align}

関数$f$を損失関数$l$とし, 切片を含めた$n+1\times n+1$のヘッセ行列$H$を用いると, 式(4)は

\begin{align}
\theta &:=\theta-H^{-1}\nabla _\theta l(\theta)\\
&:=\theta-H^{-1}g(\theta)\tag{5}
\end{align}

となる. ここで$l(\theta)$の$\theta$についての偏微分を$g(\theta)=\nabla_\theta l(\theta)$とした. この$g(\theta)$が探索方向である. 誤差の最大値を$\epsilon$とし, $|\theta_\tau-\theta_{\tau-1}|\lt \epsilon$となる値$\theta_\tau$が近似解となる. まとめると,

3.1.2 アルゴリズム

予想される真の解$\theta$に近いと思われる値$\theta_0$を初期値として入力
$\theta_1=\theta_0-\frac{f(\theta_0)}{f'(\theta_0)}$を求める
$|\theta_1-\theta_0|\lt \epsilon$となるか確認
4. ならなければ1$\tau_1$の値を入力して2にもどる
5. なったらそれが答えで終了

ニュートン法は最急降下法よりも少ない回数で早く収束するが, ヘッセ行列の逆行列を繰り返しのたびに計算しなければならず計算コストが高い. そのため次元$n$が大きくなりすぎると実用的ではない (scipy lecture noteによると$n>250^{[2]}$).

3.2 準ニュートン法　quasi-Newton method\

追記予定

3.3 共役勾配法 conjugate gradient method