サポートベクターマシン（ハードマージン）（１） - 機械学習に詳しくなりたいブログ

サポートベクターマシンにはハードマージン/ソフトマージンという分類があります。訓練データが線形分離可能であるという前提をおいたものをハードマージン、そうでないものをソフトマージンと呼びます。まずはハードマージンを見ていきます。下図はサポートベクターマシンで分類問題を解いた結果例です。緑色で強調した点がサポートベクトルと呼ばれる点です。分類境界を作っているのはこのサポートベクトルのみであり、その他の点は境界に一切影響しないのが特徴です。

f:id:opabinia2:20200122224207p:plain

分類境界が $y(\mathbf{x})=\mathbf{w}^{T}\phi(\mathbf{x})+b$ で与えられるとすれば、訓練データ点 $\mathbf{x}_n$ と境界までの距離 $d_n$ は、直線と点の距離より、

$\displaystyle | d_n | = \frac{|y(\mathbf{x}_n)|}{\|\mathbf{w}\|} = \frac{|\mathbf{w}^{T}\phi(\mathbf{x}_n)+b|}{\|\mathbf{w}\|}\tag{1}$

です。

問題の前提をハードマージン、つまり訓練データが線形分離可能としていますから、データのラベルを $t_n \in \{-1,1\}$ とすれば常に $t_n y(\mathbf{x}_n) \gt 0$ となります。また、 $t_n$ をかけても大きさは変わりませんから、

$\displaystyle d_n = \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{2}$

のように絶対値を外すことができます。

最大マージン分類器で書いた通り、サポートベクターマシンは、分類境界と最も近い点との距離（マージン）を最大にするような分類境界を求めることが目標です。マージンが最大となる $\mathbf{w},b$ は、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits} \newcommand{\min}{\mathop{\rm min}\limits} \displaystyle \argmax_{\mathbf{w},b} \left( \min_{n} \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \right) \tag{3}$

です。ややこしいですが、内側の $\min$ は、分類境界と最も近い $n$ 番目のベクトルを指し、このようなベクトルが境界から最も遠くなる $\mathbf{w},b$ を選ぶというのが式(3)の意味です。まあ要するにマージンを最大化するということです。

ここで、 $\mathbf{w} \rightarrow \kappa\mathbf{w}$ 、 $b \rightarrow \kappa b$ とすると、式(2)の右辺は

$\begin{eqnarray*} \displaystyle \frac{t_n(\kappa \mathbf{w}^{T}\phi(\mathbf{x}_n)+\kappa b)}{\kappa \|\mathbf{w}\|} &=&\frac{t_n\kappa (\mathbf{w}^{T}\phi(\mathbf{x}_n)+ b)}{\kappa \|\mathbf{w}\|} \tag{4}\\ &=& \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{5}\\ &=&d_n \tag{6} \end{eqnarray*}$

となり、結局距離 $d_n$ は変わりません。 $\kappa$ によって任意に $\mathbf{w},b$ をスケーリングできるわけですから、境界に最も近い点に対して、

$t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) = 1 \tag{7}$

となるように $\mathbf{w},b$ を選ぶことができます。これを式(3)に代入すれば、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits} \displaystyle \argmax_{\mathbf{w},b} \frac{1}{\|\mathbf{w}\|} \tag{8}$

となります。式(8)を最大にする $\mathbf{w},b$ は、 $\|\mathbf{w}\|^{2}$ を最小にする $\mathbf{w},b$ と同じです。したがって求める $\mathbf{w},b$ は

$\newcommand{\argmin}{\mathop{\rm arg~min}\limits} \displaystyle \argmin_{\mathbf{w},b} \frac{1}{2}\|\mathbf{w}\|^{2} \tag{9}$

と書けます。 $\frac{1}{2}$ をかけているのは、微分したときにきれいな形にするためのもので、あってもなくても求められる解は同じです。また、わざわざ2乗しているのは、後で書くように2次計画問題にもっていきたいからです*1。なお $b$ は式(7)の制約がありますから、消えているわけではありません。