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
内積空間を \(H\)，入力を \(x\in\mathcal{X}\subset H\)，出力を \(y\in\{\pm1\}\) とし，訓練データ集合を \(\mathcal{D}:=\{(x_i,y_i)\}_{i=1}^n\) とする．
決定関数 \[f(x)=(w|x)+b\quad(w\in H,b\in\mathbb{R})\] と識別関数 \(d=\operatorname{sgn}\circ f\) とする．分離超平面は \[ \begin{align*} \mathcal{S}&=\{x\in H\mid f(x)=0\}\\ &=\{x\in H\mid(w|x)+b=0\} \end{align*} \] である．この \(\mathcal{S}\) は \(w\) を法線ベクトルの1つに持つ超平面である．\(y\in H\setminus\mathcal{S}\) に対して， \[ \|w\|d(y,\mathcal{S})=(w|y)+b \] が成り立つ．
2.1 分離超平面
定義 1 (線型分離可能) データ \(\mathcal{D}:=\{(x_i,y_i)\}_{i=1}^n\) が線型分離可能とは，ある \(w,b\in\mathbb{R}^p\) が存在して， \[ \frac{y_i((w|x_i)+b)}{\|w\|}\ge0\quad i\in[n] \] が成り立つことをいう．
定義 2 (Canonical Hyperplane) データ \(\mathcal{D}:=\{(x_i,y_i)\}_{i=1}^n\) が定める標準超平面とは，次を満たす組 \((w,b)\in H\times\mathbb{R}\) をいう： \[ \min_{1\le i\le n}\lvert(w|x_i)+b\rvert=1. \] すなわち， \(\{x_i\}_{i=1}^n\) との距離の最小値が \(\frac{1}{\|w\|}\) となる超平面をいう．
このとき，線型分離可能ならば，標準超平面 \((w,b)\in H\times\mathbb{R}\) は \[ y_i\biggr((x_i|w)+b\biggl)\ge1 \] を満たす．
2.2 マージン
定義 3 (Geometrical Margin) 超平面 \((w,b)\in H\times\mathbb{R}\) について，
- 点 \((x,y)\in H\times\{\pm1\}\) との幾何的マージンとは，\[\rho_{(w,b)}(x,y):=\frac{y((w|x)+b)}{\|w\|}\]という．
- データ \(\mathcal{D}:=\{(x_i,y_i)\}_{i=1}^n\) との幾何的マージンとは，\[\rho_{(w,b)}:=\min_{1\le i\le n}\rho_{(w,b)}(x_i,y_i)\]をいう．
すなわち，超平面 \(\mathcal{S}\) に対して \(d(\mathcal{S},\mathcal{D})\) の値に他ならない．
2.3 最小マージン超平面
ここで，幾何的マージン \[ \rho_{(w,b)}=\min_{1\le i\le n}\frac{y_i((w|x_i)+b)}{\|w\|} \] の最大化は，線型分離可能である場合は分母が一定であるから \(\|w\|\) の最小化に等価である．したがって，標準超平面に対象を絞り，その中で \(\|w\|\) を最小にするような \(w\) を発見し，それに合わせて \(b\) を定めれば良い．
こうして，判別のためのSVMの主最適化問題は次のようになる：
定義 4 (Primal Optimization Problem) \[ \begin{align*} \operatorname{minimize}_{w\in H,b\in\mathbb{R}}&\quad\tau(w):=\frac{\|w\|^2}{2}\\ \operatorname{subject to}&\quad c(w):=y_i\biggr((x_i|w)+b\biggl)\ge1\quad i\in[n] \end{align*} \] 次の関数を未定乗数 \(\{\alpha_i\}_{i=1}^n\subset\mathbb{R}_+\) を持ったLagrangianという \[ L(w,b,\alpha):=\frac{\|w\|^2}{2}-\sum_{i=1}^n\alpha_i\biggr(y_i((x_i|w)+b)-1\biggl) \]
これを特には双対理論を用いる．
定理 1 (Kuhn-Tucker Saddle Point Condition2) \(H=\mathbb{R}^p\) とする．\((\overline{x},\overline{\alpha})\in H\times\mathbb{R}_+^n\) が次を満たすならば，\(\overline{x}\in H\) は上の最適化問題の解である： \[ L(\overline{x},\alpha)\le L(\overline{x},\overline{\alpha})\le L(x,\overline{\alpha})\quad(x\in H,\alpha\in\mathbb{R}_+^n) \]
定理 2 (KKT for Differentiable Convex Problems3) \(\tau,c\) が \(x:=(w,b)\) について可微分であるとする．このとき，ある \(\overline{\alpha}\in\mathbb{R}_+^n\) が存在して次が成り立つならば，\(\overline{x}\in\mathbb{R}^p\) は解である： \[ \partial_wL(\overline{x},\overline{\alpha})=\partial_xf(\overline{x})+\sum_{i=1}^n\overline{\alpha}_i\partial_xc_i(\overline{x})=0 \] \[ \partial_{\alpha_i}L(\overline{x},\overline{\alpha})=c_i(\overline{x})\le0 \] \[ \sum_{i=1}^n\overline{\alpha}_ic_i(\overline{x})=0 \]
最初の条件から \[ w=\sum_{i=1}^n\alpha_iy_ix_i \] が要請される．加えて，\(\overline{\alpha}_i\ne0\) が成り立つ \(i\in[n]\) においてのみ，制約条件の等号が成立する： \[ \alpha_i\biggr(y_i((x_i|w)+b)-1\biggl)=0\quad i\in[n]. \] このときの \(\alpha_i>0\) を満たすデータ点 \(x_i\in H\)，すなわち最小のマージンを達成するベクトルをサポートベクトルという．他のベクトルは \(\alpha_i=0\) が成り立つために，本質的には関与してこないとみなされる．
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．↩︎