いい加減時代の潮流に乗ろうということで機械学習を学びたいと思う。またRはともかくとしてPythonは未経験であるため、丁度良い書籍として
を用いることにする。
8. サポートベクトルマシン
- サポートベクトルマシンは
のサンプル
が与えられたときに
と境界の距離(
])の最小値を最大にする分類の方法である。
となるサンプルがある平面で分類されていない場合にも一般化される。境界が平面でない場合にも一般化される。
- 一般の
クラスの場合にも、回帰の場合にも適用される。
8.1 最適な境界
クラス数がで
と仮定する。
平面と点の距離
で与えられる。
と書ける。垂線の足は
上の点であり、
は
上の点であるから、
が成立し、ここからを消去することで
を得る。したがって
を得、これを用いることで求める距離は
である。 )
これは一般の次元に拡張することができ、
と平面
の距離は、
として、
である。となるように
を同じ定数で割ることにより正規化することで
と書ける。
次の議論のために、
が成立するようなが存在するとき、その標本は平面によって分離可能であるとする。
サンプルが分離可能のとき、のサンプルを分離する平面は無数にある。まず分離可能なサンプルに対して、両者の間にどのサンプルも含まないような2つの平面のうち、その距離が最大になるものを求める。そして新しいデータに対しての境界は平行な両者のちょうど中間にある平面だとする。そのためにはサンプル
に対して、各点
と平面
の距離の最小値
を最大にすればよい。
一般性を失うことなく、平面の係数がだと仮定すれば、
となるから、最終的に
を最大にするようなを求める問題になる。その場合には
の等号が成立するような
の部分集合が境界
およびマージン
を決定づける。
サンプルが分離可能であったとしても、同じ分布にしたがう組の別のサンプルに対しても分離可能であるとは限らない。むしろ一般的な分離可能でないサンプルに対しての最適化問題の定式化が必要になる。これまでの定式化を一般化して
として
および
を満足する範囲でおよび
を動かして、
の最大値を求める。
分離可能なサンプルに対しては、、すなわち
についての問題を解けばよい。
となるような
以外にも
であるような
も、マージン
のサポートベクトルになる。このとき最適な境界の
の決定がより多くのサンプルでなされるようになる。ただし推定が鈍感になるため、
はクロスバリデーションなどで適正に設定する必要がある。
分離可能でない場合、の値を小さくしすぎると解が存在しなくなる。実際
であれば
で
を満たさないものが1個はあるため、解が無くなる。また境界の反対側にあるの個数が
を超えれば
の解が存在しなくなる。
サポートベクトルマシンの問題は、
を最小にするようなを見出す問題として定式化される。
を最小にすることは
を
に正規化する前の
を最大化することに相当する。ここで
はコストを意味し、これを
の代わりに用いる。最後の2項が制約、
が
係数である。
8.2 最適化の理論
のもとで
を最小にするような
を求める問題で、そのような解が存在することを仮定し、そのような
だとする。
まずに対して
を定義すると、任意のについて
が成立する。
また
が成り立つ。
のもとで
を最小にする問題を主問題、
のもとで
を最大にする問題をその双対問題という。