サポートベクターマシン

線形判別ではデータの平均ベクトルや分散共分散行列を用いて判別法を構成した。サポートベクターマシンはこれらの判別法とは全く異なる考え方に基づく。

サポートベクターマシン（SVM）
- 最適化問題の立式
サポートベクターマシン（SVM）のカーネル法
- 高次元化
- カーネル法

サポートベクターマシン（SVM）

マシンとは判別器の意味。判別が自明な2群のデータを用いて、2群を最もよく分離するような関数を構成する。判別が自明である、とは図1の左のように、直線（超平面）によってデータが青（1群）、赤（2群）に完全に分離されている。この状態を線形分離可能という。図1の右側はどのような直線によっても2群を分離できない状況を表している。

線形分離可能なデータの場合、直線の傾きによって、最も近いデータやその距離は異なる。直線とそれに最も近いデータの距離（マージン）を最大にするような直線を選ぶ。

最適化問題の立式

n個の2次元のデータを $\boldsymbol{x_i}=(x_{i1},x_{i2})^\top$ （ただし $i=1,2,\cdots,n$ ）とする。2群を分離する直線と直交する方向を $\boldsymbol{w} = (w_1,w_2)\top$ とする。直線の方程式は任意の定数を $b$ として、データの線形結合によって表される。

${ \begin{align} \boldsymbol{w}^\top \boldsymbol{x_i} + b = 0 \tag{1} \end{align} }$

各データと直線の距離（点と直線の距離）は

${ \begin{align} \frac{|\boldsymbol{w}^\top \boldsymbol{x_i} +b|}{||\boldsymbol{w}||} &= \frac{|w_{1}x_{i1}+w_{2}x_{i2} + b|}{\sqrt{w_1^2 + w_2^2}} \tag{2} \end{align} }$

線形分離が可能なデータは、直線（分離超平面）によって $\boldsymbol{w}^\top \boldsymbol{x_i} + b >0$ または $\boldsymbol{w}^\top \boldsymbol{x_i} + b <0$ のどちらか一方に分類される。図3の青のデータは $\boldsymbol{w}^\top \boldsymbol{x_i} + b <0$ 、赤のデータは $\boldsymbol{w}^\top \boldsymbol{x_i} + b >0$ 、を満たすとする。青（1群）、赤（2群）は直線（超平面）によって分離されるデータによって次のように構成される。

${ \begin{align} \text{青のデータ}：\boldsymbol{w}^\top \boldsymbol{x_i} + b <0 \text{となるデータの集合} \\ \text{赤のデータ}：\boldsymbol{w}^\top \boldsymbol{x_i} + b >0 \text{となるデータの集合} \tag{3} \end{align} }$

群の所属を表すためのラベル変数 $y_i(i=1,2,\cdots,n)$ を導入する。 $(\boldsymbol{x_1},y_1),(\boldsymbol{x_2},y_2),\cdots,(\boldsymbol{x_n},y_n)$ に対して

${ \begin{eqnarray} y_{i} &=& \left\{\begin{array}{l} {-1} \qquad &データ\boldsymbol{x_i} が青　\\ {1} \qquad &データ\boldsymbol{x_i} が赤　\\ \end{array} \right. \end{eqnarray} \tag{4} }$

青に属するデータには-1を掛けるため不等式の向きは反対になり、全てのデータが $y_{i}(\boldsymbol{w}^\top \boldsymbol{x_i} + b) > 0$ を満たす。するとデータと直線の距離(2)は次のように書き直せる。

${ \begin{align} \frac{y_i(\boldsymbol{w}^\top \boldsymbol{x_i} +b)}{||\boldsymbol{w}||} \tag{5} \end{align} }$

線形分離可能な場合、2群を分離する超平面 $H$ とそれを中間に挟む形で2つの超平面 $H_{+},H_{-}$ が存在する。両端の超平面には少なくとも1つのデータが存在し、その間にはデータは存在しない。

青と赤それぞれの群のうち超平面 $H$ と最も近いデータとの距離をマージンと呼ぶ。線形分離可能なデータにおいては、2群を分離する直線は無数に引くことができる。サポートベクターマシンでは、2群の間の幅が最も大きいすなわちマージンを最大にする直線の $\boldsymbol{w},b$ を求める。最適化問題は以下のように定義される。

${ \begin{align} \max_{\boldsymbol{w},b} \ &\text{マージン}　\\ \text{subject to} \ &\frac{y_i(\boldsymbol{w}^\top \boldsymbol{x_i} +b)}{||\boldsymbol{w}||} \leq \text{マージン} \\ &i = 1,2,\cdots n \tag{6} \end{align} }$

つまりすべてのデータが直線とその値以上に離れているというマージンの定義を満たすような直線のうち、最大の距離を実現するものを見つける問題。超平面 $H_{+},H_{-}$ 上にあるデータには(6)の制約条件の等号が成立して、

${ \begin{align} y_i (\hat{\boldsymbol{w}}^\top \boldsymbol{x_i} +\hat{b}) = 1 \tag{7} \end{align} }$

超平面のスケールを変換することで(6)の最適化問題は次のように書き換えられる。

${ \begin{align} \min_{\boldsymbol{w},b} \ & \frac{1}{2} ||\boldsymbol{w}||^2 　\\ \text{subject to} \ &y_i(\boldsymbol{w}^\top \boldsymbol{x_i} +b) \leq 1 \\ &i = 1,2,\cdots n \tag{8} \end{align} }$

(8)をラグランジュ未定乗数法を用いて解く。 $α_i \geq 0,i=1,2,\cdots n$ をラグランジュ乗数とする。ラグランジュ関数は、

${ \begin{align} L(\boldsymbol{w},b,α_1,\cdots,α_n) = \frac{1}{2} ||\boldsymbol{w}||^2 -\sum_{i=1}^n α_i \{y_i(\boldsymbol{w}^\top \boldsymbol{x_i} +b)-1\} \tag{9} \end{align} }$

双対理論を用いることにより(9)はさらに次のように書き換えられる。

${ \begin{align} \max_{α_1,\cdots,α_n} \ &\sum_{i=1}^{n}α_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n α_i α_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{x_j} \\ \text{subject to} \ & α_i \geq 0 \quad i = 1,2,\cdots, n \\ & \sum_{i=1}^{n}α_i y_i = 0 \tag{10} \end{align} }$

(9)の最適解は $\hat{α_1},\cdots,\hat{α_n}$ であり、これを満たす $\hat{\boldsymbol{w}}$ は、

${ \begin{align} \hat{\boldsymbol{w}} = \sum_{i=1}^n \hat{α_i} y_i \boldsymbol{x_i} \tag{11} \end{align} }$

$\hat{α_1},\cdots,\hat{α_n}$ のうちゼロでないのは青と赤のそれぞれのデータのうち超平面（直線）に近いものだけ（図4で超平面に垂線を下ろすデータ、マージンを与えるものだけ）であり、これらをサポートベクターと呼ぶ。サポートベクターによって構成される判別器のことをサポートベクターマシンと呼ぶ。サポートベクターであるデータの添え字を $SV$ と書く。すると最適な $\hat{\boldsymbol{w}}$ は次のように書ける。

${ \begin{align} \hat{\boldsymbol{w}} = \sum_{i=1}^n \hat{α_i} y_i \boldsymbol{x_i} = \sum_{i \in SV} \hat{α} y_i \boldsymbol{x_i} \tag{12} \end{align} }$

図4の超平面（直線）の式は

${ \begin{align} \boldsymbol{w}^\top \boldsymbol{x} + \hat{b} = 0 \\ \sum_{i \in SV} \hat{α} y_i \boldsymbol{x_i}^\top \boldsymbol{x_i} + \hat{b} = 0 \tag{13} \end{align} }$

と書き表される。新たに得られたデータ $x_0 = (x_{01},x_{02})^\top$ の判別は $\boldsymbol{w}^\top \boldsymbol{x_0} + \hat{b}$ の正負で行う。

${ \begin{align} \text{sign} [\boldsymbol{w}^\top \boldsymbol{x_0} + \hat{b}] \\ \text{sign} \left[ \sum_{i \in SV} \hat{α} y_i \boldsymbol{x_i}^\top \boldsymbol{x_i} + \hat{b}\right] \tag{14} \end{align} }$

サポートベクターマシン（SVM）のカーネル法

SVMは線形分離可能な学習データに基づき、マージンを最大にする分離超平面を求める。この考え方を線形な判別から非線形な判別へと拡張するにはどうすればよいか。一般的にデータの次元が上がると、高次元空間での2群の学習データはより線形分離の状態に近づいていく。特にデータの次元がサンプル数を超えると線形分離可能となることが知られている。この性質を利用し、データを非線形関数によって高次元空間へ写像して分離超平面を求めるという考え方。この特徴空間で求めた分離超平面は、元の空間では非線形判別関数を構成する。

高次元化

データがある平面 $z=z(x_1,x_2)$ にのっていると仮定し、直線 $z(x_1,x_2) = 0$ とサポートベクターが最も離れるような平面を選択した、と考える。

2次元のデータがどちらの群に含まれるかを曲線で判別する場合、データが3次元の曲面にのっていると考える。図5,6ではサポートベクターと曲線 $z(x_1,x_2) = 0$ が一番離れるような曲面を選ぶことで、 $z(x_1,x_2)$ の正負で判別できる。

これは入力空間上で2次元のデータを3次元データへと変換している。2次元データを $\boldsymbol{x} = (x_1,x_2)^\top$ を、例えば $\boldsymbol{z}= (x_1,x_2,x_{1}x_{2})^\top$ へと変換する。入力空間でのn次元のデータ $\boldsymbol{x} = (x_1,x_2,\cdots,x_n)^\top$ を高次元に変換する関数を $Φ(\boldsymbol{x} )$ とする。最適化問題は線形の場合(10)と同じになる。

${ \begin{align} \max_{α_1,\cdots,α_n} \ &\sum_{i=1}^{n}α_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n α_i α_j y_i y_j Φ(\boldsymbol{x_i})^\top Φ(\boldsymbol{x_j}) \\ \text{subject to} \ & α_i \geq 0 \quad i = 1,2,\cdots, n \\ & \sum_{i=1}^{n}α_i y_i = 0 \tag{15} \end{align} }$

最適な曲面の式（判別関数） $z(x_1,x_2)$ も線形のときと同じように

${ \begin{align} z(x_1,x_2) = \sum_{i \in SV} \hat{α_i} y_i Φ(\boldsymbol{x_i})^\top Φ(\boldsymbol{x}) + \hat{b} \tag{16} \end{align} }$

と表される。新たなデータ $\boldsymbol{x_0}$ が得られたときの判別は、

${ \begin{align} \text{sign} = \left[ \sum_{i \in SV} \hat{α_i} y_i Φ((\boldsymbol{x_i})^\top Φ((\boldsymbol{x}) + \hat{b} \right] \tag{17} \end{align} }$

の正負で判別する。

カーネル法

入力空間上のデータの次元が大きくなると、サポートベクターマシンを適用する特徴空間の次元も極めて大きくなる。このような場合最適化問題や判別関数に現れる内積 $Φ(\boldsymbol{x_i})^\top Φ(\boldsymbol{x})$ を計算が事実上不可能となる。この問題に対処するのがカーネル法であり、内積の計算をカーネル関数に置き換える方法である。

${ \begin{align} K(\boldsymbol{x_i},\boldsymbol{x_j}) &= Φ(\boldsymbol{x_i})^\top Φ(\boldsymbol{x_j}) \\ &= \sum_{k=1}φ_k(\boldsymbol{x_i})φ_k(\boldsymbol{x_j})) \tag{18} \end{align} }$

最適化問題と、最適な曲面の式（判別関数）はそれぞれ次のように表される。

${ \begin{align} \max_{α_1,\cdots,α_n} \ &\sum_{i=1}^{n}α_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n α_i α_j y_i y_j K(\boldsymbol{x_i} ,\boldsymbol{x}) \\ \text{subject to} \ & α_i \geq 0 \quad i = 1,2,\cdots, n \\ & \sum_{i=1}^{n}α_i y_i = 0 \tag{19} \end{align} }$