ハードマージンSVM

ハードマージン法を利用して、超平面までのマージンを求める方法。

SVMの予測イメージ

SVM の学習データとして、d 次元のベクトルを xi を用意する。学習データが正例か負例かを示すラベル yi も用意する。

\[ \left\{ (\mathbf{x}_{i}, y_{i}) | \mathbf{x}_{i} \in \mathbb{R}^{d}, y_{i} \in \{-1, 1\}, i = 1, 2, \cdots, n \right\} \]

ハードマージン SVM では、これらのデータに対して、次に示す条件を満たす、w·w が最小となる w を求める。

\[ \begin{eqnarray} \left\{ \begin{array}{ll} \mathbf{w}\cdot\mathbf{x}_{i} + b \ge 1 & y_{i} = 1\\ \mathbf{w}\cdot\mathbf{x}_{i} + b \le -1 & y_{i} = -1 \end{array} \right. \end{eqnarray} \]

なお、上の連立方程式は、次のように一つの式で書き表される場合もある。

\[ y_{i}(\mathbf{w}\cdot\mathbf{x}_{i} + b) \ge 1 \]

この問題は、凸 2 次計画問題であり、多項式時間で最適解を計算することが可能。