勾配法について
勾配法の目的
二次関数$f(x)=x^2$を思い浮かべてください。 曲線の形をしていて、曲線が一番低くなっているところ、すなわち最小値が存在します。
その最小値を自動的に求めるアルゴリズムが、勾配法です。
この例では、$x=0$が最小値だと直感的に求めることができるので、 勾配法のありがたみが薄いです。
しかし、勾配法はより複雑な関数にも対応しています。 \[ f(x) = x^3 + 2x^2 + x +1 \] といった三次関数や、さらにもっともっと複雑で、人間にはイメージできない形の関数であっても、 勾配法を使えば最小値を求めることができます。
勾配法の使用例
まずは関数$f(x)=x^2$の最小値を勾配法で求める流れを見ていきましょう。
初期値を決める
初期値として$x=4$を置きます。 この初期値はランダムでかまわないのですが、ここでは4とします。
初期値とはなんの初期値なのでしょうか？ それは、最小値候補の初期値です。
勾配法は最小値の候補値をどんどん更新して、 最終的にもっとも最小値としてふさわしい候補値を得るアルゴリズムです。
なので、最初は暫定的な候補値を置いておきます。 $x=4$が$f(x)=x^2$の最小値ではないのは、わかりきっていることですが、ひとまずはここが最小値の候補値です。
上の図の赤い点が、現在の最小値の候補値です。
これをどんどん真の最小値$x=0$に近づけていきます。
最小値の候補値を更新する
候補値の点について、$f(x)=x^2$の傾きを求めます。
傾きを求めるには微分を行います。 \begin{align} \frac{d}{dx}f(x) &= \frac{d}{dx} x^2 \\ &= 2x \end{align} 微分で得た導関数を、図面にプロットしてみましょう。
緑の直線が、$f(x)=x^2$の導関数、$f'(x)=2x$です。
この直線が0になる値が最小値（極小値）というのは 高校数学の微分でよく知られている話で、 実際に$f'(x)=2x=0$という方程式を解くと、$x=0$と最小値が得られます。
しかしここでは、勾配法のアプローチで解いていきましょう。
勾配法では、この導関数の最小値候補における値、 すなわち$x=4$での値$f'(4)=8$を用いて、最小値候補を更新します。
更新式は \begin{align} x_{new} = x - \alpha f'(x) \end{align} です。αは学習係数と呼ばれる値で、ひとまず$\alpha=0.1$としておきます。
実際に値を代入してみましょう。 \begin{align} x_{new} &= x - \alpha \times f'(x) \\ &= 4 - 0.1 \times 8 \\ &= 3.2 \end{align} これで新しい最小値の候補は$x=3.2$となりました。
もともとの候補値$x=4$と比べると、新しい候補値$x=3.2$は真の最小値$x=0$に近づいていることがわかります。
それでは、この手順を何回か繰り返してみましょう。
次は$x=3.2$が更新前の候補値になります。 導関数上の値は$f'(3.2)=6.4$なので、 \begin{align} x_{new} &= x - \alpha \times f'(x) \\ &= 3.2 - 0.1 \times 6.4 \\ &= 2.56 \end{align} 今度の新たな候補値は$x=2.56$となります。
次の更新では、同様に、 \begin{align} x_{new} &= x - \alpha \times f'(x) \\ &= 2.56 - 0.1 \times 5.12 \\ &= 2.048 \end{align} となります。
上の図を見ると、だんだん候補値の間隔が狭くなってきているのがわかります。
更新値は$f'(x)$に依存しているので、$f'(x)$が少なくなればなるほど、 更新値も少なくなっていきます。
$f'(x)$は0に近づいていくので、どんどん更新値も0に近づいていき、 やがて候補値は更新されなくなります。
累計で20回更新すると、以下のような候補値になります。
20回更新したときの最小値候補は、$x=0.0461...$という値になります。
だいぶ0に近づきました。この繰り返しを何度も繰り返すことで、 より0に近い値を得られます。
このようにして最小値を求めるのが、勾配法のアプローチです。
具体的な使用例がわかったところで、アルゴリズムの説明に入りましょう。