Pythonと機械学習

Pythonも機械学習も初心者ですが、頑張ってこのブログで勉強してこうと思います。

トップ > 機械学習 > 確率的勾配降下法

確率的勾配降下法

機械学習

ADALINEでは、全てのトレーニングサンプルからコスト関数の勾配を求め、コスト関数が小さくなる方向に向かって重みを更新していました。その為エポック毎に重みが更新されることになります。

これに対し、1トレーニングサンプル毎にコスト関数の勾配を求め、重みを更新してやる方法を確率的勾配降下法と言います。

この方法を用いると1つのトレーニングサンプルが得られた時に、リアルタイムで重みを更新することができます。

最新の結果をリアルタイムで反映することができるので、オンライン勾配降下法とも言います。

また、全トレーニングサンプルからコスト関数の重みを更新する従来の方法はバッチ勾配降下法と呼ばれています。

※以下の式は全て行列で表記しています。大文字で太字は行列、小文字で太字は縦ベクトルを表します。

バッチ勾配降下法 (全トレーニングサンプルを使って重みを更新)

{\displaystyle \Delta \mathbf{w} = - \eta ( - \alpha\mathbf{X}^{T} \mathbf{y} + \alpha^{2} \mathbf{X} ^{T} \mathbf{X} \mathbf{w} ) \tag{1} }

確率的勾配降下法 (1トレーニングサンプルを使って重みを更新)

{\displaystyle \Delta \mathbf{w} = - \eta ( - \alpha\mathbf{x}_i^{T} y_i + \alpha^{2} \mathbf{x}_i^{T} \mathbf{x}_i \mathbf{w} ) \tag{2} }

{\mathbf{x}_i}は{i}番目のトレーニングサンプルを表しており、

 {
\displaystyle
\begin{eqnarray}
\mathbf{x}_i = \left[
\begin{array}{ccccc}
1 & x_{i1} & x_{i2} & \cdots & x_{in}
\end{array}
\right]
\end{eqnarray}    \tag{3}
}

です。

最小二乗法

ADALINEのコスト関数は、{\mathbf{w}}に対して単純な2次関数になっており、コスト関数の最小値を与える{\mathbf{w}}が1組だけ存在します。

最小値におけるコスト関数の勾配が0になることから、勾配降下法のような逐次計算を行わなくても、実は一発でコスト関数の最小値を与える{\mathbf{w}}を求める事が出来ます。

この方法を最小二乗法と言います。

 {
\displaystyle
\begin{align}
\frac{\partial J(\mathbf{w})}{\partial \mathbf{w}} &=- \alpha\mathbf{X}^T\mathbf{y} + \alpha^2 \mathbf{X} ^T \mathbf{X} \mathbf{w} \\

&= 0
\end{align}    \tag{4}
}

 {
\displaystyle
\therefore ~~~
\mathbf{w} = \frac{1}{\alpha} (\mathbf{X} ^T \mathbf{X})^{-1} \mathbf{X}^T\mathbf{y}     \tag{5}
}

最小二乗法では一発でコスト関数の最小値を与える{\mathbf{w}}が求まるので一番いい方法なのですが、もっと複雑な関数の場合は使えません。限られた場合にしか使えないことに注意してください。

前回のADALINEのコードを少し変更して、確率的勾配降下法がどのような振る舞いをするのか見ていきたいと思います。

確率的勾配降下法では1トレーニングサンプル毎に重みが更新されるので、トレーニングサンプルの順番をランダムにシャッフルしてやった方が学習効率は上がります。この機能もつけようと思います。

また、最小二乗法で一発で求めた解とも比較してみます。

Adalineクラスにトレーニングサンプルをシャッフルするプライベートメソッド__shuffleを追加してあります。

また、確率的勾配降下法による学習実施メソッドfitSGDと、最小二乗法による学習メソッドfitLSを追加しました。

このスクリプトを実行すると以下4つの学習結果をグラフで出力します。

バッチ勾配効果法の結果(学習率:0.01 最大エポック数:20 特徴量を標準化:オン トレーニングサンプルシャッフル:オフ)

バッチ勾配降下法の結果です。比較用に出力しています。

f:id:darden:20160821163652p:plain

確率的勾配効果法の結果(学習率:0.01 最大エポック数:20 特徴量を標準化:オン トレーニングサンプルシャッフル:オフ)

バッチ勾配効果法に比べ、1エポック目からコスト関数がずいぶん小さくなっているのがわかります。1エポック目の正答率も96%と高くなっています。

f:id:darden:20160821163724p:plain

確率的勾配効果法の結果(学習率:0.01 最大エポック数:20 特徴量を標準化:オン トレーニングサンプルシャッフル:オン)

トレーニングサンプルをシャッフルする事でもっと学習効率が上がるかと思いましたが、そんなに大したことなかったですね。でも1エポック目の正答率が97%とシャッフルしなかった時より高くなっているので少しは効果があります。

f:id:darden:20160821163755p:plain

最小二乗法の結果(学習率:0.01 最大エポック数:20 特徴量を標準化:オン トレーニングサンプルシャッフル:オン)

さすが最小二乗法ですね。一発で最小となるコスト関数が求まっています。最小二乗法では、学習率、エポック数、特微量の標準化、トレーニングサンプルのシャッフルに関係なく、一発でコスト関数の最小値が求まります。

ちなみにコスト関数の最小値は2.435です。

f:id:darden:20160821163831p:plain

コスト関数が重み{\mathbf{w}}で微分可能で、極小値がただ一つだけ存在する場合は最小二乗法を用いるのがいいです。

しかしながら、特微量行列の転置と特微量行列の積の逆行列{(\mathbf{X} ^T \mathbf{X})^{-1}}を求める必要があるのでトレーニングサンプルが非常に多い場合は、計算コストが増大しメモリ不足で逆行列が計算できなくなってしまう恐れがあります。

実際はトレーニングサンプルが非常に多くなる場合がほとんどで、勾配降下法で逐次的にコスト関数の最小値を求める方がはるかに計算コストが少なくなる為、一般的にはあまり使われていないみたいです。