勾配法 (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$ $\nabla_{x} f (x) = 0$ を解くことで最適解が求まる（ $f({\bold x})$ $f (x)$ の極値を求める）ので，
更新式 ${\bold x}^{new} = {\bold x}^{old} - H_{{ \bold x}^{old}}^{-1} \nabla_{{\bold x}} f({\bold x}^{old})$ $x^{n e w} = x^{o l d} - H_{x^{o l d}}^{- 1} \nabla_{x} f (x^{o l d})$ で $f({\bold x})$ $f (x)$ を最大化できる
- $H_{{\bold x}}$ はヘッセ行列
- ヘッセ行列と勾配ベクトル( $\nabla$ )を用いる
特徴
- 必ず収束するとは限らない（が大抵収束する．反復回数に上限を設けたほうがよい）