最急降下法

前回までに、機械学習のアルゴリズムの一つ「線形回帰」、そしてその求め方「最小二乗法」について説明しました。今回は最小二乗法での最小値の求め方である「最急降下法」について説明します。

 

 

前回説明した多次元での最小値の求め方についてです。この方法は線形回帰以外でも機械学習では様々な場所で使用しています。また、ここでは説明を簡潔にするため、下記のθ0,θ1についてのパラメータにしていますが、これはθの数がいくつあっても利用することができます。

$$J(θ_0, θ_1) = \frac { 1 }{ 2m } \sum _{ i=1 }^{ m } ((θ_0+θ_1x^{(i)}) – y^{(i)} )^2$$

 

最急降下法(gradient descent)

まず最初にθ0,θ1の値を適当に決めます。これは

$$θ_0 = 0,   θ_1 = 0$$

でも構いません。その後、少しずつそれぞれのθの値を変えていき、J関数の最小値を求めていきます。下の図で表したように、あるポイントから値が小さい箇所に少し進み、そこより小さい値がないところまで進むことによって、最小値を求めていく方法です。実はこのとき、どこからスタートするかによって最小値となる箇所が変わるのもこの方法の特徴の一つです。

 

 

式で表すと下のようになります。(この式の値が収束するまで繰り返します)

$$θ_j := θ_j – α\frac { δ }{ δθ_j } J(θ_0, θ_1) (for j = 0 and j = 1)$$

ここでのまず注意点ですが「:=」はイコールという意味ではありません。ここでのこの表記は代入を表します。
そしてこの数式を実行する際に注意することがあります。それはθ0とθ1を同時に実行することです。順々に実行してしまうと結果がが変わってしまいます。下の式のような順序で代入していく必要があります。

$$1. temp0 := θ_0 – α\frac { δ }{ δθ_0 } J(θ_0, θ_1)$$

$$2. temp1 := θ_1 – α\frac { δ }{ δθ_1 } J(θ_0, θ_1)$$

$$3. θ_0 := temp0$$

$$4. θ_1 := temp1$$

これを1→3→2→4の順で実装してしまうのは間違った実装方法になります。

上記式の説明をします。
導関数は微分ですので、最小値を求めたい関数の接戦を表します。θを横軸で考え、縦軸を最小値にしようと考えるとき、導関数の値が負であれば、θの値をプラスして最小値に近づけ、導関数の値が正であれば、θの値をマイナスして最小値に近づけます。
「α」は学習率(learning rate)です。この「α」は上の図の幅(導関数の値θの幅)を表します。幅が広ければ、早く最小値を見つけることができますが、収束できずに発散してしまう可能性があります(最小値を通り過ぎてしまいます)。そして幅が狭ければ、時間がものすごくかかってしまいます。
この最小値に近づく幅は最初は勾配が急なので、大きな幅になりますが、最小値に近づくにつれ値が小さくなるので、局所的に最小値に収束していくことができます。値が小さくなるのは、最小値は微分が0に近づくことから想像することができるでしょうか。また「局所的」という言葉を用いたのは、スタート地点から下がっていた場合、そこから上って他の最小値を探すことはできません。そのスタート地点の最小値を探すことができる方法になります。しかし線形回帰の場合は、必ず凸関数となるので、最適な局所的最小値を取得することができます。(局所最小=グローバル最小)これについてはここでは割愛します。

 

これが「最急降下法」になります。これと前回の「最小二乗法」を用いることで「線形回帰」を作成することができます。これを実装することで教師あり学習である線形回帰アルゴリズムの機械学習を使うことができるようになりました。

次回は今までの応用として複数特徴のある「多変量線形回帰」について説明します。