白猫のメモ帳

C#とかJavaとかJavaScriptとかHTMLとか機械学習とか。

勾配降下法ってなんだろう

こんばんは。

一年中穏やかな気候な土地に移り住みたいです。


さて、機械学習においては学習器がなるべく正しい答えを出力できるように
いくつかのパラメタを訓練していきます。これを最適化といいます。

最適化にはいくつも方法がありますが、
いちばん基本的で多くのアルゴリズムに利用できるものに勾配降下法があります。

今回はこいつが何をしているのか見ていきたいと思います。

アルゴリズムの評価


機械学習アルゴリズムが何を目標に学習するか、
どれだけ学習できているかということを判断するためには、その指標が必要になります。
これを「誤差関数」といいます。(目的関数とかコスト関数とか呼ばれたりもします)

たとえば下図のような青い点を直線で近似したいとします。
すると、大体赤い直線になることは分かります。

f:id:Shiro-Neko:20160930163120p:plain

横軸をx、縦軸をyとして考えましょう。
x=25とすると、実際のyの値と近似した直線のyの値の差は10くらいになります。
x=30とすると、実際のyの値と近似した直線のyの値の差は5くらいになります。

これを式として表現するならば、こうなりますね。

 {
J = y - f(x)
}


おっと、誤差には正負があるのでした。
なので、誤差を2乗して正の値にしてしまいましょう。

 {
J = (y - f(x)) ^ 2
}


ある点の誤差だけとっても困りますね。
全部足してしまいましょう。

 { \displaystyle
J = \sum_{i=0}^n (y_n - f(x_n)) ^ 2
}


さて、このままでも別に良いのですが、
とある理由で普通はこの値を1/2した値を二乗誤差といいます。
なんで1/2するのかはもう少し後で。

 { \displaystyle
J = \frac{1}{2} \sum_{i=0}^n (y_n - f(x_n)) ^ 2
}


このように誤差を単一の値で表現することができました。
二乗誤差以外にも誤差の種類はいくつかありますので、気になったら調べてみてください。

誤差を最小化しよう


誤差の求め方がわかりました。
誤差というのは誤りの大きさですから、やはり誤差が少ないほうが良いアルゴリズムですよね。

今回近似したい直線は原点を通るようになっています。
なので、バイアスはなく、求めたいパラメタはひとつです。

 {
f(x) = wx
}

試しにこのパラメタwを1から5までにしてみて、その二乗誤差を確認してみましょう。
一目瞭然。このパラメタは3くらいにチューニングするとよい精度が出そうですね。

f:id:Shiro-Neko:20160930171105p:plain

誤差関数という坂道、つまり「勾配」を下へ下へと「降下」していけばよいわけです。
これが勾配降下法です。

たとえば、
wの値が4だとします。すると右上がりなので、wは小さくしたほうが誤差が小さくなりそうですね。
一方でaの値が1だとします。すると右下がりなので、wは大きくしたほうが誤差が小さくなりそうですね。

傾き。そうです。微分です。
微分をするのです。

ここでポイントは何で微分するかということです。
今回はwの値の大小によってJの最小値を求めたいわけですよね。
この場合、Jをwで微分するんです。

勾配が(微分値が)プラスの時にはwを小さくしいので、こうしましょう。

 {
w = w - \frac{\partial J}{\partial w}
}

傾きの絶対値が大きいときは大きく変化し、小さいときは小さく変化します。
ただ、これだと更新の値が大きすぎるので、普通は学習率ρを掛けます。
これは単純パーセプトロンの時にも出てきましたが、1より小さな値を設定します。

 {
w = w - ρ\frac{\partial J}{\partial w}
}

また、パラメタが複数ある場合には誤差関数をそれぞれのパラメタで微分して、
同様に勾配降下していくと、すべてのパラメタが最小値に近づきます。

確率的勾配降下法


勾配降下法の中にもいくつかの方法が存在します。
メジャーな方法としては、

があります。(共役勾配法は勾配降下法ではない…?)

最急降下法はすべての誤差の合計を取ってからパラメタを更新するのに対して、
確率的勾配降下法は学習データの中からランダムに1つを取り出して誤差を計算、パラメタを更新をします。

ミニバッチ確率的勾配降下法は上二つの間を取ったような形で、
学習データの中からランダムにいくつかのデータを取り出して誤差を計算、パラメタを更新をします。
このときの一回に取り出すデータの数をバッチサイズと呼びます。


さて、では確率的勾配降下法のメリットとデメリットについて簡単に見ていきましょう。

メリット① 計算が早い

最急降下法はすべての誤差の合計を取ってから更新するため、
学習データが多いと計算コストがとても大きくなってしまいます。

確率的勾配降下法は1つの学習データだけで更新するため、計算が早いというメリットがあります。

メリット② 最適解にたどり着きやすい

誤差関数がいつも二次関数のような素直なカーブを描けばよいのですが、
いったん下がってまた上がるみたいなうねうねした形をとる場合、
小さな谷(これを局所解といいます)に捕まってしまうことがあります。

確率的勾配降下法はこのうねうねのいろいろなところから勾配を下ろうとするため、
最急降下法よりも局所解に陥る可能性が小さくなります。

メリット③ オンライン学習ができる

学習させる際にすべてのデータが出そろっていれば幸せなのですが、
世の中はそんなに甘くなく、学習のためのデータはだんだんと集まるのが普通です。

そしてせっかく学習ができるのですから、
学習済みモデルを利用するだけでなく、リアルタイムに学習をさせたいと思うのが人の常です。

最急降下法では1つデータが増えるたびにすべてのデータを計算しなおさなければなりませんが、
確率的勾配降下法では新しいデータだけを学習させて、学習結果を更新することができます。
このような学習方法をオンライン学習といいます。


では逆にデメリットを見ていきましょう。

デメリット① 最短で最適解にたどりつかない

ランダムにデータを取り出しているので、必ずしもパラメタが良い方向に更新されるとは限りません。
それでも、回数を重ねるとちょっと遠回りしつつもだいたいいい感じにはなります。
(1回の計算量が少ないので、実行時間としてはむしろ早いことが多い)

デメリット② 例外(異常)データに引っ張られやすい

たとえば分類問題を解いている場合、本来の分類からは外れてしまうような例外データというのは存在します。
こういったデータはいろいろな方法である程度許容しないといつまでたっても分類できないのですが、
全体の平均をとって更新をする場合、こういった例外データの誤差は全体からみると小さいのであまり気になりません。

いっぽうでランダムに1つだけ取ったデータが例外データの場合、
このデータだけをもってパラメタの更新をしようとするため、影響が大きくなってしまう場合があります。


と、ちょっとデメリットも交えつつ考察してみたのですが、
基本的には確率的勾配降下法を使うことが多いと思います。

まとめ


機械学習ではフィットするパラメタを見つけることが目的になることが多いです。
この際に一番メジャーな方法というのが勾配降下法です。

誤差を定義する⇒対象のパラメタで(偏)微分する。
だいたいこれで何とかなる。たぶん。