SVMの理論2
KKT条件について
ここを見ればよいと思われ
http://www.indsys.chuo-u.ac.jp/~konnolab/lect/Optimization3.pdf
SVMは非線形計画問題である。
制約条件が線形で、目的関数が上に凸の2次式のとき、2次計画と呼ぶ。
SVMの制約条件はマージン領域にデータが入り込まないことで、と表されるので線形である。
目的関数はマージンの最大化であり、重みベクトルの逆数のノルムの最大化である。
マージンは幾何的な距離なので発散することはなく、すなわちこれは上に凸である。
定式化においてのノルム2乗の最小化とすることで、上に凸な2次式となり、2次計画となる。
このとき、ラグランジュの未定乗数法を用いると、KKT条件が成り立つ。
このときのラグランジュ乗数はとなり、の値によって、データが分類される。
のときは、KKT条件のよりとなり、制約不等式の境界、すなわちサポートベクターとなる。
のときは、KKT条件のとより、制約不等式の中、すなわちサポートベクターではなく、超平面の構成と関係のない点となる。
今日までで、一応SVMの定式化の部分は理解できた(と思う)
ので、実装の際の、SVMの2次計画問題をどのように解くか、というところを見ていく。
これはSMOアルゴリズムが有名で、論文も公開されていて読めるし、持っている本にも書かれている。
ぼちぼち見ていく。
あと、非線形SVMのときにKKT条件が成り立つところも見ていく。
ようやくSVMの見通しがよくなるところまできた。
とはいいつつVC理論などはしばらく放置する予定なんですがね…