徒然なる日々を送るソフトウェアデベロッパーの記録(2)

技術上思ったことや感じたことを気ままに記録していくブログです。さくらから移設しました。

今更 Support Vector Machine を実装してみる(2)

だいぶ間が空いてしまいましたが、機械学習入門の続き。

フリーソフトではじめる機械学習入門

フリーソフトではじめる機械学習入門

前回の minosys.hateblo.jp では連立一次方程式
 { \displaystyle
\alpha_i \beta = -\frac{1}{2} \sum_{j=0}^N \alpha_j y_i y_j \vec{x}_i \cdot \vec{x}_j + 1 \\
\sum_{i=0}^N \alpha_i y_i = 0
}
を解けばいいことが分かりましたが、元の数はサンプル数だけあり、
Gauss-Jordan 法のような陽解法では解けません。また行列に表現し直すと
最後の式は対角成分が0になるため、Jaccobi 法も使えません。

このような時は共役勾配法 - Wikipediaを使うことになります。
初期ベクトルは \vec x=\vec 0とします。共役勾配法の詳細は Wikipedia
参照してください。プログラムは素直に実装可能です。

{\displaystyle
\vec{w} = \sum_{i=0}^N \alpha_i  y_i \vec{x}_i
}
\vec{w} を算出することができ、正例、負例に属する support vector
それぞれ \vec{x}_+, \vec{x}_-とすると
{\displaystyle
w_0=-\frac{1}{2} ( \vec{w} \cdot \vec{x}_+ + \vec{w} \cdot \vec{x}_- )
}
で、それぞれ \vec{w}, w_0を計算できます。

テストデータに対する判定は
{\displaystyle
\vec{w} \cdot \vec{x} + w_0 > 0
}
なら正例、そうでないなら負例に属するとします。