最急降下法

勾配法による連続最適化の基本となる最急降下法について軽く触れる。

反復法

ある連続関数 $f(\bm x)$ を最小化するような問題を考える。

\begin{aligned} \operatorname*{minimize}_{\bm x} \quad f(\bm x) \end{aligned}

これに対して、何らかの反復法により

\{\bm x^i\}_{i=1}^t = \{\bm x^1, \bm x^2, \dots, \bm x^t\}

を生成して、 $f(\bm x)$ の最小値を探すことを考える。

勾配法

各反復ステップにおける更新を、

\begin{aligned} \bm x^{t+1} = \bm x^{t} + \Delta \bm x \end{aligned}

とする。すなわち、次のような更新規則を与えることを考える。

\bm x \gets \bm x + \Delta \bm x

すると、 $\Delta \bm x$ について、

f(\bm x + \Delta \bm x) \lt f(\bm x)

が達成されれば、あとはひたすら $\bm x$ を更新しつづけることで、局所最適解を探すことができる。勾配法では、 $f(\bm x)$ の $\bm x$ による微分に基づいて、これを満たす $\Delta \bm w$ を探しに行く。

目的関数 $f(\bm x)$ は $\bm x$ によって微分可能であるとする。 $f(\bm x)$ を1次の項までテイラー展開する。

\begin{aligned} f(\bm x + \Delta \bm x) \approx f(\bm x) + \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x \end{aligned}

1次の項の係数部分 $\dfrac{\partial f}{\partial \bm x}$ は、 $f(\bm x)$ を $\bm x$ の各成分で微分したものを並べた勾配ベクトルである。上式から、ベクトル $\Delta \bm x$ は1次の項が常に負になるような向きを向いていればよいことがわかる。

\begin{aligned} \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x \lt 0 \end{aligned}

これが達成されるには、 $\Delta \bm x$ が $\dfrac{\partial f}{\partial \bm x}$ と逆向きになっていればよい。すなわち、ある実数 $\eta$ を用いて、次のように定めればよい。

\begin{aligned} \Delta \bm x = - \eta \frac{\partial f (\bm x)}{\partial \bm x} \end{aligned}

こうして得られる次の更新規則に従って局所最適解を探すアルゴリズムを、最急降下法 (steepest descent method) という。

\begin{aligned} \bm x \gets \bm x - \eta \frac{\partial f (\bm x)}{\partial \bm x} \end{aligned}

ここで $\eta$ はステップ幅 (step size) とか学習率 (learning rate) とか呼ばれる実数である。