サポートベクトルマシン (機械学習プロフェッショナルシリーズ) を読んでいます. SVMについて,わかっている気になっていましたが,わかっていませんでした. 意外と奥が深いですね.というわけでその整理の意味も込めてのポスト.

この記事ではハードマージンSVMを考えます. ハードマージンSVMでは,与えられたデータは線形分離可能であると仮定します. つまり,超平面で,与えられた訓練データがミスなく分離できることを仮定します. このような超平面は複数存在すると考えられますが, SVMでは,「マージンを最大化する超平面を求める」,というのはよくある説明ですね.

ではまず,マージンの定義から入りましょう. 今,訓練データが与えられているとします. マージンを, 超平面からもっとも近いサンプルまでの距離と定義します. つまり,

と定義すると,マージンは

と表すことができます. 全ての訓練データを正しく分類しつつ,このマージンを最大化したいので,以下の最適化問題を解きます.

分子が邪魔なので,これを以下のように書き換えます.

二つの制約条件を一つにまとめると,以下のようになります.

個人的にはここの変形が一番きつかったですね…. なので軽く補足しときます. 以下の制約を書き換えていきます.

の定義から,(2)は以下のように書き換えられます.

ここで,(1)と(2’)を合体させたいのですが, を示すことができれば良さそうです. ここで,

ですが,(1)より, は成り立たず,この文脈では必ず となります.

なので,を示すことにします. すごく簡単すぎて示す必要もないかもしれませんが….

の時,(1)より,の時,(1)とより,も同様.

よって,

そういうわけで,(2’)は,

これで,(1)と(2’‘)を合体できますね. 最後に最大化と最小化を書き換えて,ノルムを2乗すれば,よく見るハードマージンSVMの最適化問題の完成です:

ここで,与えられたデータに対して,制約を満たすが存在しないかもしれません. というより,現実問題ではそのような場合がほとんどだと考えられます. そこで,ソフトマージンの考え方が出てきます. これについてはまた後日書けたらと思います.