SVM - (1) ハードマージン SVM
データセット
2クラスの訓練集合を とする。
ただし、 は 次元の点、 はその点に対応するラベルを または で表す。
2次元の訓練集合の例
訓練集合は、線形分離可能 (linearly separable) であると仮定する。
マージン最大化
このとき、線形分離可能な超平面はいくつも存在するが、どのような超平面がよいだろうか。
超平面と訓練集合の最も近い点との距離をマージン (margin) という。
SVM では、マージンが最大となるように超平面を決める。
このことをマージン最大化という。
マージンが最大の超平面はクラス に属する最も近い点とクラス に属する最も近い点とのちょうど真ん中を通る。
なぜなら、もしそうでないとすると、その点から遠い方向に超平面を平行移動させることで、よりマージンを大きくできるので、マージン最大化と矛盾する。
マージン最大化の数式表現
超平面 からある点 までの距離は
で計算できる。*1
超平面から最も近い点との距離 (マージン) を
とおく。このマージンを最大化するので
となるパラメータ を求めればよい。
超平面はスケール倍しても不変なので、
を満たすように を選ぶことにすると、最適化問題は次のように変形できる。
は で単調増加であり、 なので、
また、超平面はすべての点を正しく分類できるように選ぶので、クラスが の点は 、 の点は である必要がある。
つまり、 を満たす必要がある。
よって、最適化問題は
制約条件を1つにまとめると、
これは2次制約つき2次計画問題 (Quadratically Constrained Quadratic Program / QCQP) である。
サポートベクトル
を満たす点 は超平面から最も近い点であり、サポートベクトル (support vecotor) という。
サンプルコード
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=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()