danglingfarpointer's memoization

仕事周りでの気付き、メモ、愚痴などを書いていきます。

Widrow-Hoffの学習規則

はじめに

前回、識別境界を求めるためのアルゴリズムとしてパーセプトロンを組んだが、その流れで"Widrow-Hoffの学習規則"を組んでみる。ほぼ勉強の備忘録。。

Widrow-Hoffの学習規則

パーセプトロンと同様、2値のラベルが与えられた多次元データを分類するための境界を 求めるアルゴリズム

パーセプトロンは、与えた学習データが線形識別可能である場合、学習データを正しく分離する境界を必ず返す。一方で、与えたデータが線形識別可能でない場合、アルゴリズムが停止しない。

Widrow-Hoffの学習規則は、与えたデータが線形識別可能でない場合も、誤差をなるべく小さく抑える識別境界を求められる。その代わり、線形識別可能な場合でも、学習データを正しく識別しないことがある。

理論

\({\bf x}_1,\dots,{\bf x}_n\)を学習データ、\(b_1,\dots,b_n\)を各学習データに与えられたラベル(教師信号)とする(\(b_i \in \{-1,+1\}\)). \({\bf w}\)を 線形識別関数の重みベクトル(識別ベクトル)とする。

各学習データ\({\bf x}_i\)について、識別関数による識別結果\({\bf w}^t{\bf x}_i\)と教師信号\(b_i\)の誤差は、以下のようになる。$$\epsilon_i ={\bf w}^t {\bf x}_i - b_i$$

ここで、二乗誤差\(J_i\)を考える。$$J_i = \frac{1}{2}\epsilon_i^2 = \frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2$$

各学習データの二乗誤差\(J_i\)の和\(J\)は以下のようになる。$$J = \sum_i J_i = \sum_i\frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2 $$

\(J\)を最小化する\({\bf w}\)を求めることが目的となる。ランダムな\({\bf w}\)を初期値とし、最急降下法で反復的に\({\bf w}\)を更新していく。\({\bf w'}\)は1つ前(更新前)の識別関数である: $${\bf w} = {\bf w'} - \rho\frac{\partial J}{\partial {\bf w}}$$

ここで、$$ \frac{\partial J}{{\partial {\bf w}}} = \sum_i \frac{\partial J_i}{{\partial {\bf w}}} = \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$ となるので、\({\bf w}\)の更新式は以下のとおり。 $${\bf w} = {\bf w'} - \rho \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$

線形識別できない例を考える。

labelxy
+1 -2 1
+1 -1 4
+1 1 3
+1 3 3
+1 -1 3
-1 -3 1
-1 0 -1
-1 2 1
-1 3 2
-1 0 3

この例に対してパーセプトロンを適用しても停止しないが、Widrow-Hoffの学習規則であれば停止する。

サンプルのソースコード https://gist.github.com/danglingfarpointer/2d425339ea54d4140668 だと、0.402 * x + 1.713という解を出力した。

f:id:danglingfarpointer:20140915192038p:plain