最急降下法

関数 $f$ が微分可能であるとき、${\min }_{x}f(x)$ となる $x$ を求める手法。

アルゴリズム

1. $t=0,x^0$ をランダムに初期化する
2. $x^{t+1}\leftarrow x^t-\eta \frac{\text{d}}{\text{d}x}f(x^t)$
3. $t\leftarrow t+1$
4. $\left|x^{t+1}-x^t\right|<ϵ$ を満たすまで繰り返す

傾きが$0$と見做せるまで移動し続けることで最小値を見つける。 $f$ の形によっては局所解に収束することがあるので、初期値の値を変えながら複数回試すことで結果が改善することがある。 また、微分を解析的に計算するために絶対値ではなく二乗を使う。

最小二乗法を使わない理由

最小二乗法を使うには、$\frac{\text{d}f}{\text{d}x}=0$ が解析的に解ける必要がある。 線形モデルでは当然解けるが、多くの機械学習モデルでは解けない。

確率的勾配降下法

SGD: stochastic gradient descent method。

ナイーブな最急降下法は全事例の訓練誤差総和についての勾配を計算するが、計算量はサンプル数$N$について$\mathrm{O}(N)$となる。 SGDは、ランダムに選んだ1つの事例の訓練誤差について勾配を計算する。

勾配は近似的だが、更新あたりの計算量はサンプル数$N$について$\mathrm{O}(1)$。 訓練誤差が単調減少しないなど、最適化の過程は不安定になる。

ミニバッチSGD

全データから比較的少数のデータをランダムに選んだ集合であるミニバッチを作成する。 ランダムに選んだミニバッチの予測誤差について勾配計算を行う。

更新あたりの計算量はミニバッチサイズに比例するが、SGDほど更新過程が不安定ではなくなる。 バッチごとに独立に勾配を計算できるので並列化できるという嬉しさもある。

これらは1ステップあたりの計算量を減らすが、全体として計算量が減ることや計算時間が短くなることを保証するものではない。