パーセプトロンのアルゴリズム(線形分離)



スポンサードリンク

パーセプトロンのアルゴリズム

データを分類する際の境界を決める手法です。

xy平面で言えば、あるデータ群があった場合、それをうまく二つに分類できるような、xy平面上の直線の方程式を探索することになります。

探索フロー(境界直線の決定)

ここでは簡便なため、データが(x,y)で与えられているとし、それらのデータを二つに分類するものとして話を進めていきます。

  1. 直線の方程式をf(x,y)=w0+w1x+w2y=0 と仮定
  2. f(x,y)>0の時t=1、 f(x,y)<0の時t=-1として二つに分類。与えられたデータ(xn,yn)を上の方程式に代入します。なお一番最初は(w0,w1,w2)はこちらで初期値として指定します。

なお分類が正しければ、f(xn,yn)×tn>0

間違っていれば、f(xn,yn)×tn<0 となります。

そして全ての(xn,yn)において、上が成り立つ直線(w0,w1,w2)を決定していきます(パーセプトロン)。

3.f(xn,yn)×tn<0の点(誤分類のデータ)がある場合、それを「誤差」としてカウントします

あるデータ(xn,yn)における誤差の大きさは次式で定義されます。これは幾何学的(点と直線の距離)にイメージできると思います(下の図を参照してください)。

\begin{eqnarray}
E_{n}=|f(x_{n},y_{n})|
\end{eqnarray}
全ての誤分類データにおける誤差の総量は
\begin{eqnarray}
\sum_{n}E_{n}&=&\sum_{n}|f(x_{n},y_{n})|\\
&=&-\sum_{n}f(x_{n},y_{n})\times t_{n}\\
&=&-\sum_{n}(w_{0}+w_{1}x_n+w_{2}y_{n})\times t_{n}\\
&=&-\sum_{n}t_{n}w^{T}\phi_{n}
\end{eqnarray}
ここで\(w^{T},\phi_{n}\)は次式で定義されるベクトルである。
\begin{eqnarray}
w = \left(
\begin{array}{c}
w_0 \\
w_1 \\
w_2 \\
\end{array}
\right)\\
\phi_{n} = \left(
\begin{array}{c}
1 \\
x_n \\
y_n \\
\end{array}
\right)\\
\end{eqnarray}

4. 総誤差ΣEを0(最小)にするように(w0,w1,w2)を探索していく

最も一般的なものが「確率的勾配降下法」です。


スポンサードリンク

確率的勾配降下法

これは「勾配ベクトル」の意味と「確率的」の意味を考える必要があります。

例えばh(x,y)=\(\frac{3}{4}(x^2+y^2)\)のグラフを考えます。

この場合勾配ベクトルは∇h(x,y)=(\(\frac{3}{2}x,\frac{3}{2}y\))となりますが、勾配ベクトルはその値(図で言うところのピンク)を最も増加させる方向を表しています。-∇hの方向に移動すれば、原点0に近づくことになります。

このことから、現在の居場所をxoldとして次の居場所xnewを求めるアルゴリズムが以下の式で表せられることになります。
\begin{eqnarray}
x_{new}=x_{old}-\nabla h
\end{eqnarray}
たとえ勾配ベクトルが大きく、xを更新した時に原点を通り過ぎても、問題ないことは以下の図でわかると思います。原点を行ったり来たりを繰り返し、最終的に原点にたどり着くと、勾配ベクトルは0になるので、そこで停止することになります。

話を戻します。今、勾配ベクトルは以下の式で計算できます。
\begin{eqnarray}
\nabla E(w) &=& \left(
\begin{array}{c}
\frac{\partial E}{\partial w_{0}} \\
\frac{\partial E}{\partial w_{1}} \\
\frac{\partial E}{\partial w_{2}} \\
\end{array}
\right)\\
&=&-\sum_{n}t_{n}\phi_{n}
\end{eqnarray}
そして誤差を0(最小)に近づけるには、上の例で見たように現在のw=(w0,w1,w2)から勾配ベクトルを引けば良いので、

\begin{eqnarray}
w_{new}=w_{old}+t{_n}\phi_{n}   (1)
\end{eqnarray}
となります。「勾配降下法」の「勾配降下」は勾配ベクトルの反対方向にパラメーターを修正して、誤差関数のグラフを下っていくところからきているのでしょう。

では「確率的」とは何を意味しているのでしょうか?

勾配ベクトルの計算方法について、もう少し深掘りしていきます。

\begin{eqnarray}
\nabla E(w) = -\sum_{n}t_{n}\phi_{n}
\end{eqnarray}
上の式から誤差関数の勾配ベクトルの計算は全ての誤分類されたデータの\(t_{n}\phi_{n}\)を合計することを意味しています。

データが大量にある場合、毎回正しい(w0,w1,w2)を更新していくために\(t_{n}\phi_{n}\)を計算するのは時間がかかるので、誤分類のデータを一つ選んで、とりあえずそのぶんだけパラメータを修正します。

そして修正された新しいwを用いて、また誤分類されたデータのうち一つを選んで同様に式(1)を用いて修正していきます。

このように誤分類データをランダムに選んでパラメータを修正するため「確率的」とついています。



スポンサードリンク


これからは、実際にコードを書いてどのように計算が行われているのか、上の説明を元に論じていきます。

>>>続きはこちら。

記事が役に立ったらシェア!

投稿者:

中村 俊

中村 俊

1993/09/04生まれ。機械系大学院を休学し、ベンチャーでインターンしている最中。直近では、デカルトの「方法序説」に感銘を受けた。 趣味:読書、web開発の勉強、異分野の論文読んだり、記事書いたり。 最終的には経営者か研究者になりたい。

「パーセプトロンのアルゴリズム(線形分離)」への1件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA