Pynote

Python、機械学習、画像処理について

SVM - (1) ハードマージン SVM

概要



サポートベクターマシン (support vector machine, SVM) の学習用メモ。
ハードマージン SVM の定式化を紹介する。

線形分類器

線形分類器 を次で定義する。


\displaystyle
\begin{eqnarray}
g(\boldsymbol{x})
=
    \begin{cases}
        1 & ( f(\boldsymbol{x}) \ge 0 ) \\
        -1 & ( f(\boldsymbol{x}) < 0 )
    \end{cases}
\end{eqnarray}

ただし、f(\boldsymbol{x}) = \boldsymbol{w}^T \boldsymbol{x} + b, \boldsymbol{w} \in \mathbb{R}^d, b \in \mathbb{R}

この線形分類器は 超平面 \mathcal{H} = \{\boldsymbol{x} \in \mathbb{R}^d|\boldsymbol{w}^T \boldsymbol{x} + b = 0\} で空間を2つに分離する。



データセット

2クラスの訓練集合を D = \{(\boldsymbol{x}_i, y_i)|\boldsymbol{x}_i \in \mathbb{R}^d, y_i \in \{-1, 1\}\}, (i = 1, 2, \cdots, N) とする。
ただし、\boldsymbol{x}_id 次元の点、y_i はその点に対応するラベルを 1 または -1 で表す。



2次元の訓練集合の例


訓練集合は、線形分離可能 (linearly separable) であると仮定する。


マージン最大化

このとき、線形分離可能な超平面はいくつも存在するが、どのような超平面がよいだろうか。



超平面と訓練集合の最も近い点との距離をマージン (margin) という。




SVM では、マージンが最大となるように超平面を決める。
このことをマージン最大化という。

マージンが最大の超平面はクラス 1 に属する最も近い点とクラス -1 に属する最も近い点とのちょうど真ん中を通る。
なぜなら、もしそうでないとすると、その点から遠い方向に超平面を平行移動させることで、よりマージンを大きくできるので、マージン最大化と矛盾する。


マージン最大化の数式表現

超平面 \mathcal{H} からある点 \boldsymbol{x} までの距離は


\displaystyle
\frac{|\boldsymbol{w}^T \boldsymbol{x} + b|}{\|w\|_2}

で計算できる。*1
超平面から最も近い点との距離 (マージン) を


\displaystyle
\gamma(\boldsymbol{w}, b)
= \min_i \frac{|\boldsymbol{w}^T \boldsymbol{x}_i + b|}{\|w\|_2}

とおく。このマージンを最大化するので


\displaystyle
\max_{\boldsymbol{w}, b} \gamma(\boldsymbol{w}, b)
= \max_{\boldsymbol{w}, b} \frac{1}{\|w\|_2} \min_i |\boldsymbol{w}^T \boldsymbol{x}_i + b|

となるパラメータ \boldsymbol{w}, b を求めればよい。
超平面はスケール倍しても不変なので、


\displaystyle
\min_i |\boldsymbol{w}^T \boldsymbol{x}_i + b| = 1

を満たすように \boldsymbol{w}, b を選ぶことにすると、最適化問題は次のように変形できる。


\displaystyle
\max_{\boldsymbol{w}, b} \frac{1}{\|w\|_2}
\Leftrightarrow
\min_{\boldsymbol{w}, b} \|w\|_2

z^2z \ge 0 で単調増加であり、\|w\|_2 \ge 0 なので、


\displaystyle
\min_{\boldsymbol{w}, b} \|w\|_2
\Leftrightarrow
\min_{\boldsymbol{w}, b} \|w\|_2^2

また、超平面はすべての点を正しく分類できるように選ぶので、クラスが y_i = 1 の点は \boldsymbol{w}^T \boldsymbol{x} + b \ge 0y_i = -1 の点は \boldsymbol{w}^T \boldsymbol{x} + b < 0 である必要がある。
つまり、y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 0 を満たす必要がある。

よって、最適化問題は


\displaystyle
\begin{align}
    & \min_{\boldsymbol{w}, b} \|w\|_2^2 \\
    & \textrm{s.t.} 
    \begin{matrix}
    \forall i, \ y_{i}(\boldsymbol{w}^T \boldsymbol{x}_{i} + b) & \ge 0 \\ 
    \min_i |\boldsymbol{w}^T \boldsymbol{x}_i + b| &= 1
    \end{matrix}
\end{align}

制約条件を1つにまとめると、


\displaystyle
\begin{align}
    & \min_{\boldsymbol{w}, b} \|w\|_2^2 \\
    & \textrm{s.t.} 
    \begin{matrix}
    \forall i, \ y_{i}(\boldsymbol{w}^T \boldsymbol{x}_{i} + b) \ge 1
    \end{matrix}
\end{align}

これは2次制約つき2次計画問題 (Quadratically Constrained Quadratic Program / QCQP) である。

サポートベクトル


\displaystyle
\min_i |\boldsymbol{w}^T \boldsymbol{x}_i + b| = 1

を満たす点 \boldsymbol{x}_i は超平面から最も近い点であり、サポートベクトル (support vecotor) という。


サンプルコード

sklearn.svm.LinearSVC で線形 SVM による学習が行える。
ソフトマージンのところで紹介するが、正則化定数 C を大きい値にすることで、ハードマージンに近い形にしている。

import matplotlib.pyplot as plt
import numpy as np
from sklearn import svm
from sklearn.datasets import make_blobs
from sklearn.preprocessing import minmax_scale

# データセットを作成する。
X, y = make_blobs(n_samples=40, centers=2, random_state=6)

# データセットを描画する。
fig, ax = plt.subplots(facecolor="w")
ax.scatter(X[:, 0], X[:, 1], c=y, s=20, cmap="Paired")

# 学習する。
clf = svm.LinearSVC(C=1000)
clf.fit(X, y)

# 分類平面及びマージンを描画する。
XX, YY = np.meshgrid(np.linspace(*ax.get_xlim(), 100), np.linspace(*ax.get_ylim(), 100))
xy = np.column_stack([XX.ravel(), YY.ravel()])
Z = clf.decision_function(xy).reshape(XX.shape)
ax.contour(
    XX, YY, Z, colors="k", levels=[-1, 0, 1], alpha=0.5, linestyles=["--", "-", "--"]
)

plt.show()


参考文献