サポートベクトルマシンとは、複数のサンプルデータを2つのクラスに分類する手法です。
空間内の点の分類
$D$ 次元空間の $N$ 個の点(${\bf x}_n$)を2つのクラスに分類する問題を考えます。$D$ 次元空間を仕切るためには、次の超平面を求める必要があります。
$$a_1x_1+a_2x_2+\cdots+a_Dx_D+b=0$$
ここで、次の関数を定義し、
$$y({\bf x})=a_1x_1+a_2x_2+\cdots+a_Dx_D+b={\bf a}\cdot{\bf x}+b$$
全ての点が、超平面のどちらかの側に分類された場合、目的変数 $t_n$ を次のように定義すると、
- クラス1:$y({\bf x}_n)\gt0$ ならば $t_n=1$
- クラス2:$y({\bf x}_n)\lt0$ ならば $t_n=-1$
常に、$t_ny({\bf x}_n)\gt0$ であることが分かります。このことを利用すると、点 ${\bf x}_n$ と超平面との距離は以下で求められるため、
$$\frac{|{\bf a}\cdot{\bf x}_n+b|}{|{\bf a}|}=\frac{t_n({\bf a}\cdot{\bf x}_n+b)}{|{\bf a}|} -①$$
超平面に最近接の点(${\bf x}_n$)に対し、その距離(マージン)が最大になるような超平面(${\bf a},b$)を求める問題に帰着します。これを式で表すと以下になります。
$$\max_{{\bf a},b}\Big(\frac{1}{|{\bf a}|}\min_n[t_n({\bf a}\cdot{\bf x}_n+b)]\Big) -②$$
問題の簡略化
②の解くことは複雑であるため、ラグランジュ未定乗数法を利用して、問題の簡略化を図ります。距離①は、超平面の係数(${\bf a},b$)を定数倍しても変わらないため、
$$t_n({\bf a}\cdot{\bf x}_n+b)=1 -③$$
とういう条件を置けば、この条件のもとで、以下の関数を最大にすればよいことになります。
$$\max_{{\bf a},b}\frac{1}{|{\bf a}|}$$
さらに、これを最大ということは、$|{\bf a}|^2$ を最小化することなので、③の条件の下で、以下の関数を最小化する問題と等価になります。
$$\min_{{\bf a},b}\frac{1}{2}|{\bf a}|^2$$
ここで、ラグランジュ未定乗数法を利用すると、次のラグランジュ関数($\lambda_n\ge0$)が、
$$L({\bf a},b,\lambda_n)=\frac{1}{2}|{\bf a}|^2-\sum_{n=1}^N\lambda_n[t_n({\bf a}\cdot{\bf x}_n+b)-1] -④$$
停留値を取る(${\bf a},b$)を求めればよいことになります。この停留値を取る条件は以下で表されます。
$$\frac{\partial L}{\partial{\bf a}}={\bf a}-\sum_{n=1}^N\lambda_nt_n{\bf x}_n=0 -⑤$$
$$\frac{\partial L}{\partial b}=-\sum_{n=1}^N\lambda_nt_n=0$$
双対表現
双対表現とは、⑤を④に代入して得られる次のラグランジュ関数のことです。
$$\tilde{L}(\lambda_n)=\sum_{n=1}^N\lambda_n-\frac{1}{2}\sum_{n,m=1}^N\lambda_n\lambda_mt_nt_mk({\bf x}_n,{\bf x}_m)$$
ここで、$k$ はカーネル関数と呼ばれており、以下で一般に定義されます。
$$k({\bf x}_n,{\bf x}_m)\equiv\phi({\bf x})^t\phi({\bf x})={\bf x}_n\cdot{\bf x}_m$$
尚、制約条件は以下になります。
$$\frac{\partial L}{\partial b}=-\sum_{n=1}^N\lambda_nt_n=0$$
$$\lambda_n\ge0$$

