A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
1 初めに
パーセプトロン型の線型識別器である. 1960年にVapnikらが考案.1990年にKernel法と合流.
- その後の研究に大きな潮流をうんだ
- 凸最適化と機械学習が合流したこと
- SVMの汎化誤差の研究が大きく発展し,PAC学習に引き継がれている.
- カーネル法の発展と合流.
つまり,SVMは死んだが,その要素技術が現代の機械学習に通底しているということだろう.
Support vector algorithms are commonly considered the first practicable spin-off of statistical learning theory. (Schölkopf and Smola, 2002, p. 187)
2 SVMによる識別の定式化1
内積空間を
決定関数
2.1 分離超平面
定義 1 (線型分離可能) データ
定義 2 (Canonical Hyperplane) データ
このとき,線型分離可能ならば,標準超平面
2.2 マージン
定義 3 (Geometrical Margin) 超平面
- 点
との幾何的マージンとは, という. - データ
との幾何的マージンとは, をいう.
すなわち,超平面
2.3 最小マージン超平面
ここで,幾何的マージン
こうして,判別のためのSVMの主最適化問題は次のようになる:
定義 4 (Primal Optimization Problem)
これを特には双対理論を用いる.
定理 1 (Kuhn-Tucker Saddle Point Condition2)
定理 2 (KKT for Differentiable Convex Problems3)
最初の条件から
3 二次計画問題(凸最適化)
4 ソフトマージン法
訓練誤差が,最適超平面の誤差よりも定数倍だけ悪いような超平面を決定する問題はNP困難である(Ben-David and Simon, 2001).これに立ち向かうには,超平面のマージンのある定数倍の範疇にあるデータ点だけ無視すれば,多項式クラスにまで問題の難易度が落ちる.
一方で,(Cortes and Vapnik, 1995) はスラック変数による全く別の解決をした.
References
Footnotes
(Schölkopf and Smola, 2002) 第7章などを参考.↩︎
(Schölkopf and Smola, 2002) 定理6.21 p.166.↩︎