確率的勾配降下法のアルゴリズムをExcelに実装して具体例を解いてみた。
前回は最小二乗法を解くために、最急降下法のアルゴリズムをExcelで試してみました。
>> 【例題をExcelでわかりやすく】最急降下法で単回帰の最小二乗法を解いてみる
今回は、同じ例題を確率的勾配降下法のアルゴリズムで解いてみます。
最急降下法のアルゴリズム
まずは最急降下法のおさらいです。
最小二乗法における残差平方和である
を最小にするaとbを求めるために、適当な初期値a0とb0を決めて、
an+1=an-η∂Q(a,b)/∂a
bn+1=bn-η∂Q(a,b)/∂b
に従ってaとbを更新していけば、Q(a,b)を最小化させるaとbに収束していきました。
この時、∂Q(a,b)/∂aと∂Q(a,b)/∂bは次式で計算できます。
最急降下法の欠点
以上が最急降下法でした。
この方法の欠点は、aとbが更新される度にΣを計算しないといけないことです。
∂Q/∂aや∂Q/∂bの式の中には残差平方和が含まれていますが、これはaとbが変わると変わります。
aとbを何千回、何万回と少しずつ変化させながら収束解を見つけていくので、その度に何万とあるデータの残差を計算するというのはあまり実用的ではありません。
確率的勾配降下法のアルゴリズム
この問題を解決するのが確率的勾配降下法です。
SGD（Stochastic Gradient Descent）とも呼ばれます。
aとbを少しずつ変化させるというのは同じですが、∂Q/∂aや∂Q/∂bの計算を簡単にしています。
データの数だけ残差平方和を計算しないで、たった1つのデータから∂Q/∂aや∂Q/∂bを計算するようにしているのです。
具体的には次のように計算します。
∂Qi/∂a＝-2xi(yi -(axi+b))
∂Qi/∂b＝-2(yi -(axi+b))
最急降下法ではデータn個分の合計を計算しないといけなかったところ、i番目のデータだけで計算するため、手間は1/nになります。
i番目のデータは、n個あるデータの中からランダムに選びます。
また最小化する関数Q(a,b)もΣがなくなり、次のように簡単になります。
Qi(a,b)={yi -(axi+b)}2
確率的勾配降下法と最急降下法の比較
本当にこんな簡単で良いのかと不安になりますが、最急降下法ではすべてのサンプルデータを一遍に計算していたのに対し、確率的勾配降下法では一つずつ、しかし短時間でできるので数をこなせるため計算する量は結局同じと考えるとわかりやすいと思います。
イメージ図で比較すると次のようになります。
最急降下法
確率的勾配降下法
しかし、計算する量が結局同じならば、わざわざ確率的勾配降下法を使う理由がありませんよね。
実はもう一つメリットがあり、局所的最適解に捕まらず、大局的最適解に辿り着ける可能性が高くなることです。
局所的最適解とは下図における右側の谷、大局的最適解とは左側の谷です。
最急降下法では初期値がこのように右側にある場合、局所的最適解で収束してしまうため、右側の谷へ行くために山を乗り越えられる望みはありません。
ところが確率的勾配降下法では、ランダムに選ぶデータによっては乗り越えられる可能性が出てきます。
これが確率的勾配降下法の大きなメリットです。
確率的勾配降下法をExcelに実装する
それではExcelで実際に試してみましょう。
今回も説明を簡単にするため単回帰で、xとyのサンプルデータが次のように100組あるとします。
この表からランダムに1組ずつの(xi, yi)を選んできて、初期値のaとbを更新していきます。
具体的には、RANDBETWEEN関数で1から100までの乱数を生成して、それに対応する(xi, yi)をINDEX関数とMATCH関数で取り出すことにします。
次のようなシートを作れば実行できます。
収束判定はa、b共に、前回からの更新幅が0.000001以下になった時点としています。
初期値a=b=-40から出発していますが、4,182回目で収束しました。
収束する様子をグラフにすると次のようになります。
このグラフではスケールが大きいので見にくいのですが、a、b共に収束していく過程で行ったり来たりしています。
もっとスケールを小さくしてみましょう。
aの収束過程は次のようになっています。
データを一つずつ選んでaとbを逐次更新していくため局所的には行ったり来たりしますが、データをランダムに選んでいるため、最終的には最急降下法でやった場合と同じ値に収束していくことになります。
また、このやり方も初期値を入れれば一瞬でaとbの収束値が求まることは最急降下法と同じです。
>> 【例題をExcelでわかりやすく】最急降下法で単回帰の最小二乗法を解いてみる
しかし、最急降下法ではサンプルデータの数だけ列数が増えますので、データ数が多くなると入力が面倒です。
これに対して確率的勾配降下法ではそのようなことがないため、Excelでも実用性のある実装ができると言えます。
でも収束していく過程の振幅が少し気になりますね。
余りにモタモタ振動していると、収束が遅くなってしまいます。
そのための改良版のアルゴリズムがこちらです。
>> 【Excelでアルゴリズムを実装】モーメンタム法を使って最小二乗法を解いてみる
>> 【Excelでアルゴリズムを実装】RMSProp法を使って最小二乗法を解いてみる
>> 【Excelでアルゴリズムを実装】最終兵器Adamを使って最小二乗法を解いてみる