SVM - (2) ソフトマージン SVM

概要

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

pynote.hatenablog.com

ソフトマージン

ハードマージン SVM の記事では、訓練集合が線形分離可能という仮定を置いた。
しかし、訓練集合が線形分離可能でない場合も考えられる。
この場合、ハードマージンの最適化問題

$\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}$

を満たす解は存在しない。
この問題を解決するためにスラック変数 $\xi_i \ge 0, (i = 1, 2, \cdots, N)$ を導入して、最適化問題を次のように書き換える。

$\displaystyle \begin{align} & \min_{\boldsymbol{w}, b, \boldsymbol{\xi}} \|w\|_2^2 + C \sum_{i = 1}^N \xi_i \\ & \textrm{s.t.} \begin{matrix} \forall i, \ y_{i}(\boldsymbol{w}^T \boldsymbol{x}_{i} + b) \ge 1 - \xi_i \\ \forall i, \xi_i \ge 0 \end{matrix} \end{align}$

ただし、 $\boldsymbol{\xi} = (\xi_1, \xi_2, \cdots, x_N)^T, C > 0$ とする。

制約条件に注目すると、 $\forall i, \ y_{i}(\boldsymbol{w}^T \boldsymbol{x}_{i} + b) \ge 1$ から $\forall i, \ y_{i}(\boldsymbol{w}^T \boldsymbol{x}_{i} + b) \ge 1 - \xi_i$ に変更したことで、点が超平面 $\boldsymbol{w}^T \boldsymbol{x}_{i} + b = \pm 1$ を超えることが許可される。

点 $x_i$ が超平面 $\boldsymbol{w}^T \boldsymbol{x}_{i} + b = \pm 1$ を超えた場合に、超えた分の距離は $\frac{\xi_i}{\|\boldsymbol{w}\|_2}$ で表される。
できるだけ超えないようにしたいので、すべての点の超えた距離の合計 $\sum_{i = 1}^N \frac{\xi_i}{\|\boldsymbol{w}\|_2}$ をできるだけ小さくしたい。
よって、目的関数に $\min_{\boldsymbol{w}, b, \boldsymbol{\xi}} \|w\|_2^2 + C \sum_{i = 1}^N \xi_i$ という形で組み込む。

$C > 0$ は正則化定数とよばれるハイパーパラメータで超平面 $\boldsymbol{w}^T \boldsymbol{x}_{i} + b = \pm 1$ を超えた場合の罰則の強さを設定する。

$C$ が小さい値の場合、超えた場合の罰則が小さくなるので、誤分類が許容される。
逆に $C$ を大きい値にすると、誤分類に対する罰則が大きくなり、ハードマージン SVM に近くなる。

コード

sklearn.svm.LinearSVC で線形 SVM による学習が行える。

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=100, centers=2, random_state=0)

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

# 学習する。
clf = svm.LinearSVC(C=1)
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()

グリッドサーチ

正則化定数 $C$ はハイパーパラメータであり、最適な値は学習するデータによって異なる。
そのため、グリッドサーチでいくつかの値での学習を試して、最適な値を採用するとよい。
scikit-learn の sklearn.model_selection.GridSearchCV を使用すると、この探索を簡単に行える。

使い方は以下の記事を参照されたい。

pynote.hatenablog.com

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.datasets import make_blobs
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.preprocessing import minmax_scale
from sklearn.svm import LinearSVC

# データセットを作成する。
X, y = make_blobs(n_samples=100, centers=2, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 試行するパラメータとその値
params = {"C": [0.01, 0.1, 1, 10, 100, 1000]}

# グリッドサーチする。
clf = GridSearchCV(LinearSVC(), params, cv=5, return_train_score=False, iid=False)
clf.fit(X_train, y_train)

# 最も精度がいいモデルを取得する。
best_clf = clf.best_estimator_
best_score = best_clf.score(X_test, y_test)
print(f"score: {best_score:.2%}")  # score: 95.00%

cv_result = pd.DataFrame(clf.cv_results_)
for row in cv_result.itertuples():
    print(f"C = {row.params['C']}: {row.mean_test_score:.2%}")
# C = 0.01: 87.54%
# C = 0.1: 92.48%
# C = 1: 91.23%
# C = 10: 91.30%
# C = 100: 92.40%
# C = 1000: 91.54%

参考文献

Lecture 9: SVM

Pynote

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

SVM - (2) ソフトマージン SVM

概要

関連記事

ソフトマージン

コード

グリッドサーチ

参考文献