SVM
Last update : 2018/08/22
SVMの概要
サポート・ベクター・マシン(Suport vector machines, SVM)は、判別分析(Discriminant analysis)の一つの手法です。図１に示すように、女性と男性の体重と身長のデータがあるとします。この図をみると、大柄な男性（赤丸）はグラフの右上に、小柄な女性（青丸）はグラフの左下に分布しています。判別分析では、このグラフに境界線（図2の緑の実線）を引き、データが男性（赤）と女性（青）のどちらのクラスに属するかの判定を行います。実際の応用では、例えば、正常／異常がわかっている製品のデータを学習して、あらかじめ判別器を作っておき、正常／異常がわからない製品をテストする、というような場合に使います。
SVMでは、次式の判別関数(Decision function)で、データ x がどちらのクラスに属するかの判定を行います。図１の例では、 x = [体重、身長]T となります。{w,w0} はSVMの係数で、学習データを用いて決定（最適化）します。φ()は、任意の関数で、データをより識別しやすい空間に写像します。この空間は、特徴空間(Feature space)と呼ばれます。φ()が線形関数 φ(x) = x の場合は、クラスの境界線は、図2に示すような直線（２次元データの場合）になります。判別では、２つのクラスを C1 と C2 とすると、f(x)≧0 であれば C1 に、f(x)<0 であれば C2 に分類します。
SVMの学習
SVM係数を決定するための学習では、式(2)および(3)の最小化問題を解きます。
図2における境界線と境界線に一番近いデータを通る直線（点線）との距離はマージンと呼ばれ、1/||w|| で表されます。式(2)の最小化により、このマージンが最大化されることになります。結果的に、データをきれいにわける境界線がひけることになります。"subject to"のあとの式は、最小化の条件を表しています。このような問題を拘束付き最小化問題(Constrained minimization)と言います。n は学習データの番号、N はその数を表しています。tn は、クラスラベルと呼ばれ、データ xn が C1 と C2 のどちらに属するかで、±1のどちらかの値をとります。すなわち、クラス分けの正解です。このように、正解を与えて学習するやり方を、教師あり学習(Supervized learning)と呼びます。式(3)の意味は、すべての学習データ {xn|n=1,...,N} が正しく分類され、かつ、マージン（点線と点線の間）に入らない、ということを意味しています。
ソフトマージン
図2のように、データをきれいに２つのクラスに分けれれば問題ありませんが、きれいに分けれらない場合もあります。この場合、ある程度の誤りを許してでも、境界線を引くことが考えられます。この誤分類の評価指標として、マージン境界（図の点線）を超えた場合に次式の値を持つ、スラック変数(slack variable)を定義します。マージン境界内での値は0です。このスラック変数を用いて、式(2),(3)の拘束付き最小化問題を、次式のように変更します。
これにより、マージン最大化に加え、誤分類を最小にするよう学習が行われます。定数 C は、マージン最大化と誤分類最小化のバランスをとるためのものです。このような手法を重み付き最適化問題と呼びます。また、マージン境界の間にデータがあることを許すことから、式(5)による境界は、ソフトマージン(Soft margin)と呼ばれます。重み定数Cを大きくすると、誤分類は減りますが、その分マージンも減ります。
カーネル
データの境界にうまく直線を引けない場合は、φ()に非線形関数を用いるのが有効です。SVMでは、非線形関数の効果を、カーネルで実現しています。カーネル関数の定義は、次式で与えられます。式(6)は、式(2)及び(3)を実際に解く時に用いるラグランジュの未定乗数法の計算過程で現れます。詳しくは、参考文献[1]を参照してください。SVMでは、式(6)ではなく、カーネル関数を直接構成して用いる場合があります。図3で用いているRBF(Radial basis function)カーネルは、次式で定義されます。
図１：データの分布
図２：SVMによる識別結果(線形カーネル)
図3：SVMによる識別結果(RBFカーネル)
サンプルプログラム
SVM.py
このサンプルでは、人工的に作成した男性と女性の{体重、身長}データに対して、SVMを用いて識別を行います。
# Library
import numpy as np
from sklearn import svm
import matplotlib.pyplot as plt
from sklearn.model_selection import LeaveOneOut
# パラメータ設定
Kernel = 'linear' # 'linear' or 'rbf'
Gamma = 0.1 # RBFカーネルの非線形パラメタ
# 身長・体重データの読み込み
fileName = '../../Data/etc/weightHeightData.csv'
print( 'Input File: ', fileName )
data = np.loadtxt(fileName,delimiter=',')
print( data )
X = data[:,(0,1)]
y = data[:,2]
# 散布図
fig = plt.figure(figsize=(6,6))
plt.plot(X[y==1,0],X[y==1,1],'bo')
plt.plot(X[y==-1,0],X[y==-1,1],'rd')
(gxmin,gxmax) = (min(X[:,0])-5.0,max(X[:,0]+5.0))
(gymin,gymax) = (min(X[:,1])-5.0,max(X[:,1]+5.0))
plt.xlim(gxmin, gxmax)
plt.ylim(gymin, gymax)
plt.xlabel('Weight [kg]')
plt.ylabel('Height [cm]')
plt.title('True label')
# SVMの学習
clf = svm.SVC(kernel=Kernel,gamma=Gamma)
clf.fit(X,y)
# 学習データの識別
yHat = clf.predict(X)
print( 'Predicted label:',yHat )
score = clf.score(X,y)
print( 'Score:',score )
# 散布図
fig = plt.figure(figsize=(6,6))
plt.plot(X[yHat==1,0],X[yHat==1,1],'bo')
plt.plot(X[yHat==-1,0],X[yHat==-1,1],'rd')
(gxmin,gxmax) = (min(X[:,0])-5.0,max(X[:,0]+5.0))
(gymin,gymax) = (min(X[:,1])-5.0,max(X[:,1]+5.0))
plt.xlim(gxmin, gxmax)
plt.ylim(gymin, gymax)
plt.xlabel('Weight [kg]')
plt.ylabel('Height [cm]')
plt.title('kernel=%s, Score=%.3f'%(Kernel,score))
# 判別関数
XX, YY = np.mgrid[gxmin:gxmax:100j, gymin:gymax:100j]
Z = clf.decision_function(np.c_[XX.ravel(), YY.ravel()])
Z = Z.reshape(XX.shape)
if Kernel == 'linear':
plt.pcolormesh(XX, YY, Z, cmap=plt.cm.RdBu)
elif Kernel == 'rbf':
plt.contourf(XX, YY, Z, cmap=plt.cm.RdBu)
# 超平面
if Kernel == 'linear':
w = clf.coef_[0]
a = -w[0] / w[1]
xx = np.array([gxmin,gxmax])
b = - clf.intercept_[0] / w[1] # H0
yy = a*xx + b
plt.plot(xx, yy, 'g-')
b = - (clf.intercept_[0]+1) / w[1] # H1
yy = a*xx + b
plt.plot(xx, yy, 'c--')
b = - (clf.intercept_[0]-1) / w[1] # H2
yy = a*xx + b
plt.plot(xx, yy, 'c--')
else: # f(x)=0
plt.contour(XX, YY, Z, colors=['g'], linestyles=['-'], levels=[0])
# 交差検証(Leave-One-Out)
loo = LeaveOneOut()
CVscore = 0.0
for train, test in loo.split(y):
clf.fit(X[train,:],y[train])
CVscore += clf.score(X[test,:],y[test])
print( "CV Score:",CVscore/len(y) )
参考文献
C. M. Bishop, "Pattern recognition and machine learning," Springer, 2006