ディープラーニング(深層学習)を理解してみる(勾配降下法：最急降下法と確率的勾配降下法)

はじめに

勾配降下法をどうして使うのかは理解できたのですが、その計算方法がまだ理解が足りてなくて、微分の本とかを読んでいました。
数学は苦手なんですが、理解はしたい。おまじないとかそういうルールだからとかで済ましたくないんですよね。

勾配降下法の他にも最急降下法とか確率的勾配降下法の用語がありますので、この違いも理解したい。
今回は下記の本(Kindle)を参考にしている。

勾配降下法

f:id:Yaju3D:20170917211137p:plain
勾配には、傾斜の程度・斜面という意味があります。
上図では1変数による関数 $y=f(x)$ でグラフは放物線となります。

リンゴとミカンの値段を求める場合は2変数による関数 $z=f(x,y)$ となり下図のようにワイングラスの底のような形になります。ちなみに3変数以上は図で表わすのは困難です。
f:id:Yaju3D:20170924173848p:plain
下図は関数のグラフの一部を拡大し、斜面に見立てた図となります。その斜面上のある点Pにピンポン玉を置き、そっと手を放すと玉は最も急な斜面を選んで転がり始めます。
f:id:Yaju3D:20170924181321p:plain

この操作を何回も繰り返せば、ピンポン玉は最短な経路をたどってグラフの底、すなわち関数の最小値にたどり着くはずです。この玉の動き(誤差関数という坂道、つまり「勾配」を下へ下へと「降下」していく)を真似たのが勾配降下法です。
f:id:Yaju3D:20170924183956p:plain

正確には最小値を探す場合を勾配降下法(gradient descent mothod)と言い、最大値を探す場合を勾配上昇法(gradient ascent mothod)と言います。descentは、SQLで降順にソートさせる時に略称(desc)で、order by column descと使いますね。

最短で下るには、少しずつ下りながら、場所ごとに最も急な勾配を探すことになります。
$P_0$ から最も勾配の急な点 $P_1$ の位置を求める。その位置 $P_1$ から更に最も勾配の急な点 $P_2$ の位置を求める。このように繰り返すことで最も早く最小点にたどり着くようになります。
f:id:Yaju3D:20170924211620p:plain

数値解析の分野では勾配降下法を最急降下法と呼びますが、勾配降下法の中にもいくつかの方法が存在します。

最急降下法(Gradient Descent) ※デフォルト
確率的勾配降下法（Stochastic Gradient Descent - SDG）
ミニバッチ確率的勾配降下法（Minibatch SGD - MSGD）

最急降下法とは

最急降下法は学習データのすべての誤差の合計を取ってからパラメーターを更新します。学習データが多いと計算コストがとても大きくなってしまいます。また、学習データが増えるたびに全ての学習データで再学習が必要となってしまいます。

確率的勾配降下法とは

確率的勾配降下法は学習データをシャッフルした上で学習データの中からランダムに1つを取り出して誤差を計算し、パラメーターを更新をします。勾配降下法ほどの精度は無いが増えた分だけの学習データのみで再学習する(重みベクトルの初期値は前回の学習結果を流用)ため再学習の計算量が圧倒的に低くなります。
運が良ければ最急降下法よりも早く最適解にたどり着けますが、運が悪ければいつまで経っても適した答えを導けません。

ミニバッチ確率的勾配降下法とは

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

最急降下法と確率的勾配降下法の違い

パラメーター更新の式

最急降下法のパラメーター更新の式
$\displaystyle \theta_j := \theta_j - \eta\sum_{i=1}^n(f_{\theta}({x}^{(i)}) - y^{(i)}){x_j}^{(i)}$

確率的勾配降下法のパラメーター更新の式
$\displaystyle \theta_j := \theta_j - \eta(f_{\theta} ({x}^{(k)}) - y^{(k)}){x_j}^{(k)}$
(式中のkは、パラメーター更新毎にランダムに選ばれたインデックス)

大きな違いとして、確率的勾配降下法ではシグマ $\sum$ (1～nまで合計)が取れています。
その分、計算コストは少なくなっていることが分かりますよね。

最小値へのたどり着き方

最急降下法がほぼ直線的に最小値にたどり着くのに対し、確率的勾配降下法はランダムなのでくねくねしながら最小値にたどり着きます。
f:id:Yaju3D:20170925010546p:plain

局所解に陥る可能性

誤差関数が素直なカーブのみならいいですが、下図のようにいったん下がってまた上がるみたいなうねうねした場合があります。本当は④が最小値なのに別の小さな谷(これを局所解といいます)に捕まってしまうことがあります。
f:id:Yaju3D:20170917223314p:plain

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

定数η(イータ)は学習係数と呼ばれます。このηは人が移動する際の「歩幅」と見立てられます。このηで決められた値に従って次に移動する点が決められるからです。その歩幅が大きいと最小値に達しても、それを飛び越えてしまう危険があります(下図左)。歩幅が小さいと、極小値で停留してしまう危険があります(下図右)。
f:id:Yaju3D:20170925010945p:plain