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$$
例
線形識別できない例を考える。
label | x | y |
---|---|---|
+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という解を出力した。