PRMLの線形識別モデルの章の内容。PRMLの中に書いてある線形識別モデルをざっと実装しようと思っていたけれど、 最小二乗法に依る識別とフィッシャーの線形識別は割りとけちょんけちょんにけなされているイメージだったので、とりあえずおいておくことにします。
というわけでパーセプトロンを作ってみたよ。 今回もソースはここ
パーセプトロンは誤分類を行ったデータに対してのみパーセプトロン基準にもとづいて重みベクトルを変化させていくアルゴリズム。このアルゴリズムは基本的には 2クラスの分類にだけしか使えないが、線形分類可能なデータ集合に対しては有限ステップで必ず分類できるモデルを構築できるという特徴と持つ。すごい！
パーセプトロン規準
val phi = DenseVector(1.0, point(0), point(1))
phi * point(2) * _eta
データ点にバイアスを加えたベクトルphiとデータ点の目的値(-1, 1)の積がパーセプトロン規準になる。この値は正しく分類されているデータに対しては常に正の値になる。つまりこの値が負の場合だけ重みベクトルを更新するように書くことができる。
こんな感じに書いた。
plist.foreach {
point => {
val phi = DenseVector(1.0, point(0), point(1))
if ((_w.t * phi).apply(0) * point(2) < 0) {
_w += phi * point(2) * _eta
}
}
}
すべての点に対してパーセプトロン規準に従い更新処理をかける。PRMLでは確率的最急降下アルゴリズムで更新をかける式が書いてあったので後でそちらも試してみる。 ここで注意しておきたいのは、パーセプトロンでは学習中に重みベクトルが変化すると正しく分類されていたパターンも誤分類されてしまうことがある。そのため、すべてのパターンが正しく分類されているかを再度検証する必要がある。
plist.foreach {
point => {
val phi = DenseVector(1.0, point(0), point(1))
if ((_w.t * phi).apply(0) * point(2) >= 0) {
correct += 1
}
}
}
このcorrectがデータ点と等しくなったら学習を終える。
パーセプトロンははじめに線形分離可能なモデルならば必ず分離できるモデルを構築できるが、そうでない場合はいつまでも収束しない。そのため、もしそのようなデータ集合を与えた場合は上記のcorrectはずっとデータ点数を同じにならない。
今回は2次元上に2クラスの学習用データ集合を生成。それぞれのクラスの平均、共分散行列は固定で書いてあとは良きにはからってpylabに生成してもらった。
さて、実際にどのような感じか見てみる。
初期の重みベクトルはすべて要素が1の単純なベクトルで行った。それでもこの処理にかかったステップ数は３とかなり少ない。 PRMLではパーセプトロン学習アルゴリズムが収束するのに必要なステップ数はかなり多いと書いてあったけれど思っていたよりは少ない。もちろん2次元空間上で、尚且つたかだかデータ点数が100なので総結論づけれれないけれど、あくまでも思っていたよりかはということ。
結構分類が難しそうなものもやってみた。
きちんと分類できている。これも重みベクトルの初期値は同じ。ステップ数も変わらない。つまりあくまでも初期値と線形分離可能性に大きく依存するので、あんまりクラス集合が近いとか遠いとか関係ないみたい。そこら辺は最小二乗法と大きく違うところ。
線形分離不可能なものもやってみた。
はい、やっぱりダメ。実際には収束しないので途中でプログラムを切って得た画像。
10minくらい走らせたけどダメだった。終わらない。
確率的最急降下法
さっきまでは全点を選んでの最急降下法で重みベクトルを更新していったけれど、PRMLに書いてあるように確立的最急降下法で計算してみるとどうだろう。計算コスト的にはかなり小さくなるはずだけれど、ステップ数も増えなければ最急降下法での計算の方が良さそう。どうなるか試してみたい。
実装としては以下のようにした。
val index = Math.floor(Math.random()*plist.length).toInt
val point = plist(index)
val phi = DenseVector(1.0, point(0), point(1))
if ((_w.t * phi).apply(0) * point(2) < 0) {
_w += phi * point(2) * _eta
}
データ点の中からランダムに1点を選び、その点に対してパーセプトロン規準に従い重みベクトルを更新する。
さて、やってみた。
分類結果は当然変わらない。線形分類可能なら必ず収束する。左が先ほどまでの全点選択での最急降下法。右が確率的最急降下法。
ただしステップ数が大きく異なる。全点選択はステップ数3に対して確率的最急降下法はステップ数が1069！
確率的に降下方向を選ぶのは全点選ぶのと対して変わらないとどっかに(PRMLではない)書いてあったのに、結構違う。 もちろん全点選択の場合は1ステップで今回200点のループを回しているので実質600ほどのパーセプトロン規準での計算を行っている。それでも確率的最急降下法の方が多い。
個人的には確率的最急降下法は計算コストもかからないし、精度も対して落ちないかなり良さげなアルゴリズムだと思っていたのでちょっと意外だった。まあもちろんデータ点の数や状態、あとは重みベクトルの初期値なんかでもいろいろ変わってくると思うので一概には言えないですよね。
パーセプトロン奥が深いです