SVMの理論2

KKT条件について


ここを見ればよいと思われ
http://www.indsys.chuo-u.ac.jp/~konnolab/lect/Optimization3.pdf

SVM非線形計画問題である。
制約条件が線形で、目的関数が上に凸の2次式のとき、2次計画と呼ぶ。

SVMの制約条件はマージン領域にデータが入り込まないことで、1-y_i((w^T x_i) + b) <= 0と表されるので線形である。
目的関数はマージンの最大化であり、重みベクトルの逆数1/wのノルムの最大化である。
マージンは幾何的な距離なので発散することはなく、すなわちこれは上に凸である。
定式化においてwのノルム2乗の最小化とすることで、上に凸な2次式となり、2次計画となる。


このとき、ラグランジュの未定乗数法を用いると、KKT条件が成り立つ。
このときのラグランジュ乗数は\alpha >= 0となり、\alphaの値によって、データが分類される。
\alpha>0のときは、KKT条件の\alpha g(x) = 0よりg(x) = 0となり、制約不等式の境界、すなわちサポートベクターとなる。
\alpha=0のときは、KKT条件の\alpha g(x) = 0g(x) <= 0より、制約不等式の中、すなわちサポートベクターではなく、超平面の構成と関係のない点となる。


今日までで、一応SVMの定式化の部分は理解できた(と思う)
ので、実装の際の、SVMの2次計画問題をどのように解くか、というところを見ていく。
これはSMOアルゴリズムが有名で、論文も公開されていて読めるし、持っている本にも書かれている。
ぼちぼち見ていく。


あと、非線形SVMのときにKKT条件が成り立つところも見ていく。
ようやくSVMの見通しがよくなるところまできた。


とはいいつつVC理論などはしばらく放置する予定なんですがね…