ハードマージンSVM
SVMの仕組み
SVM(サポートベクタマシン)はパターン認識を行うための、教師あり学習法です。
例として、下の図のような赤丸と青丸の分類を考えてみましょう。
あまり複雑なことはしたくないので、この二つを直線を引いて分けることにします。 点と直線の距離を求めるで少し触れたように直線のどちら側にあるかは かけ算と足し算で簡単に求まります。
しかし直線で分けると言っても、赤丸と青丸を分ける直線は無数に存在します。 SVMではその無数の直線の中から、もっとも適したものを選ぶために「マージン最大化」を考えます。
マージンとは、分離を行う直線と、その直線にもっとも近い丸との距離のことです。 データにはばらつきがあるので、間違った判断をしないためにはこのマージンが大きい方が良さそうです。 図の例では、青い直線より赤い線の方がマージンが大きいので、赤い直線の優れた分離だと考えられます。 SVMはマージンがもっとも大きい直線を見つけることで、未知のデータも正しく分類しようとします。
この例では、二次元を直線でしたが、もっと大きな次元では超平面で分類します。 その場合でも、超平面とのマージンを最大化することによりもっとも適した分離超平面を見つけ出します。
数学的に考えてみる
すこし長くなりそうなので、別ページへ。 「数学的に考えてみる(ハードマージンSVM)」を参照してください。
サポートベクタ
分離超平面に最も近い点はサポートベクタと呼ばれます。 サポートベクタが、分離平面をサポート(支持)しているように見えるからです。 分離超平面はサポートベクタだけできまり、それ以外の点は関与しません。
実際にやってみよう
2変数の場合についてやってみました。 例によって、SVGにJavascriptを埋め込んだものです。 赤の点と、青の点を、黒い線で分けます。各点はドラッグ＆ドロップで動かせるのでいじってみてください。 サポートベクタ(中が塗りつぶされた点)を動かすと分離線が変化しますが、それ以外の点を動かしても変化しないことが確認できるはずです。
少し手を抜いたSMOで実装してある(部分最適化をランダムな点で行っています)ので、少し収束が遅いです。 徐々に収束していく様子をお楽しみください。
