勾配法 (Gradient method)

最急勾配法

目的関数$f$が最も減少する方向に進む場合，最急降下法とよぶ
手順
1. $\bold{x}$の初期値を決める
2. 更新式${\bold x}^{new} = {\bold x}^{old} + \eta \nabla_{{\bold x}} f({\bold x}^{old})$を用いて${\bold x}$を更新する．
  目的関数を$\bold{x}$で微分したものに${\bold x}^{old}$を代入した第2項が，傾きが最も急な方向をあらわす． $\eta$は学習率．
3. 目的関数の値の変化が一定値以下になるまで2を繰り返す
特徴
- 傾き（一階微分）のみしか見ないので手法として簡便で計算も速い
- 局所解に陥りやすい

コンセプト
- $f(x) = 0$になるような値$x$を探すとき，$(x^{old}, f(x^{old}))$における$f$の接線$l$の切片（$y=0$となる点）$x^{new} = x^{old} - \frac{x^{old}}{f'(x^{old})}$は，$x^{old}$より真の値$x$に近くなる．
  これを，値の変化が一定値以下になるまで繰り返すことで$x$の近似値を得られる．
- 接線を一次近似式，接線のx切片を一次近似式の零点と考えることにより，高次元関数の場合に一般化できる．
  - $f({\bold x}) = 0$となる$\bold{x}$を求める更新式は${\bold x}^{new} = {\bold x}^{old} - \left( \partial f ({\bold x}^{old}) \right)^{-1} f({\bold x}^{old})$
  - $\partial f ({\bold x}^{old})$はヤコビ行列
最適化においては$\nabla_{{\bold x}} f({\bold x}) = 0$を解くことで最適解が求まる（$f({\bold x})$の極値を求める）ので，
更新式${\bold x}^{new} = {\bold x}^{old} - H_{{ \bold x}^{old}}^{-1} \nabla_{{\bold x}} f({\bold x}^{old})$で$f({\bold x})$を最大化できる
- $H_{{\bold x}}$はヘッセ行列
- ヘッセ行列と勾配ベクトル($\nabla$)を用いる
特徴
- 必ず収束するとは限らない（が大抵収束する．反復回数に上限を設けたほうがよい）