SVM

1500 days ago by takepwave

Hiroshi TAKEMOTO (take@pwv.co.jp)

はじめに

SVMは、オーバーフィッティングを避けて効率よく識別関数を求めることができる 手法です。

「集合知」の9章で紹介されているSVMをSageを使ってまとめてみます。

簡単な例題

いきなりSVMに進む前にクラス分けを簡単な例を使って解いてみます。

下図は、赤(-1)のグループと青(1)のグループの分布です。

# 線形クラス分類の例 # データの用意 c1 = [[1,2],[1,4],[2,4]] c2 = [[2,1],[5,1],[4,2]] # プロットして分布を確認 pl1 = list_plot(c1, rgbcolor='red') pl2 = list_plot(c2, rgbcolor ='blue') (pl1+pl2).show(xmin=0, xmax=5, ymin=0, figsize=5) 
       

線形分類

青点の値に1、赤点の値に-1をセットし、$w_1 x_1 + w_2 x_2 + b$の線形モデルを find_fit関数を使って解いて、$w_1, w2, b$の値を求めます。

find_fitのデータは、$x_1, x_2, 値$の順にセットします。

# 各クラスに判別値をセット v1 = [-1, -1, -1] v2 = [1, 1, 1] # (x, y, 判別値)のリストを作成 data = [flatten((pt, v)) for (pt, v) in zip(c1 + c2, v1 + v2)] data 
       
[[1, 2, -1], [1, 4, -1], [2, 4, -1], [2, 1, 1], [5, 1, 1], [4, 2, 1]]
[[1, 2, -1], [1, 4, -1], [2, 4, -1], [2, 1, 1], [5, 1, 1], [4, 2, 1]]
# 最もフィットするw1, w2, bを求める var('x1 x2 w1 w2 b') model(x1, x2) = w1*x1 + w2*x2 + b fit = find_fit(data, model, solution_dict=True); print fit # 求まった解(判別式)を返す関数を定義します f(x1, x2) = model.subs(fit); 
       
{b: 0.1962962962945436, w2: -0.4333333333364595, w1:
0.32592592592445524}
{b: 0.1962962962945436, w2: -0.4333333333364595, w1: 0.32592592592445524}

結果の表示

implicit_plot関数を使ってデータ(赤、青)と判別式が0となる線を表示します。 上手く赤と青の点を分離しているのが分かります。

# 判別式が0の線を表示 pl6 = implicit_plot(f(x1, x2) == 0, (x1, 0, 5), (x2, 0, 5)) (pl1 + pl2 +pl6).show(xmin=0, xmax=5, ymin=0, figsize=5) 
       

求まった判別式がどのような形なのかplot3dを使って表示してみます。 データ(赤、青)の判別式の値も合わせて表示してみます。

一つの平面上として表されています。

pl3 = plot3d(f(x1, x2), (x1, 0, 5), (x2, 0, 5)) pl4 = list_plot([(x, y, f(x, y)) for (x, y) in c1], rgbcolor='red') pl5 = list_plot([(x, y, f(x, y)) for (x, y) in c2], rgbcolor='blue') (pl3+pl4+pl5).show(xmin=0, xmax=5) 
       

SVMを使った分類

SVM(サポートベクターマシン)は、クラスの境界線と分離平面(超平面) の距離(マージン)を最大になるようにクラスを分類します。

先ほどの例では、下図のように境界線(半線)の中間に$y = x$の分離平面が、 あります。(線形分類の境界線とずれていることに注意して下さい)

境界線を求めるとき使った学習データのことを「サポートベクター」と呼びます。

# SVMでは、クラスの境界線と分離平面(超平面)の距離を最大になるように求めます sv = plot(lambda x : x, (x, 0, 5)) cl1 = plot(lambda x : x + 1, (x, 0, 5), linestyle='dashed') cl2 = plot(lambda x : x - 1, (x, 0, 5), linestyle='dashed') (sv+cl1+cl2+pl1+pl2).show(xmin=0, xmax=5, figsize=5) # 青の実線が分離平面で、半線がクラスの境界線です 
       

LIBSVMのインストール

sageを使ってSVMを計算したいところですが、sageにはSVMを計算する関数がありません。 そこで、LIBSVMをインストールします。

LIBSVMの ホームページ のDownload LIBSVMから最新のtar.gzファイルをダウンロードします。

ダウンロードしたファイル(libsvm-2.9.tar.gz)を適当な場所(~/local)で解凍します。

$ tar xzvf libsvm-2.9.tar.gz
$ cd libsvm-2.9/python	
		

MacOSXの場合、Makefileの一部を変更します。

#LDFLAGS = -shared
# Mac OS
LDFLAGS = -framework Python -bundle			
		

また、そのままではsageで動かなかったので、svm.pyの以下の2点にfloatのキャストを 追加するように修正してください。

126c126
< 		svmc.svm_node_array_set(data,j,k,x[k])
---
> 		svmc.svm_node_array_set(data,j,k,float(x[k]))
138c138
< 			svmc.double_setitem(y_array,i,y[i])			
---
> 			svmc.double_setitem(y_array,i,float(y[i]))
		

sage内部のpythonにLIBSVMをインストールするには、sageのpythonで seup.pyを実行します。私は、sageを~/localにインストールしているので

$ ~/local/sage/local/bin/python setup.py install			
		
と実行しました。

正しく動くか、集合知の9.9.2の例題で確認します。 無事、同じ結果がでたので、次に進みます。

# svm.pyを2カ所修正した # 動作を確認するために、集合知の9.9.2の例題を実行する from svm import * prob = svm_problem([1,-1],[[1,0,1],[-1,0,-1]]) param = svm_parameter(kernel_type = LINEAR, C=float(10)) m = svm_model(prob, param) 
       
*
optimization finished, #iter = 1
nu = 0.025000
obj = -0.250000, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 2
*
optimization finished, #iter = 1
nu = 0.025000
obj = -0.250000, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 2
m.predict([1,1,1]) 
       
1.0
1.0

LIBSVMで簡単な例題を解く

LIBSVMへの入力は、各データどのクラスに属するかを示すclsと データのベクトル値datを引数に取ります。

# LIBSVM用にデータを加工する cls = v1 + v2; print cls dat = c1 + c2; print dat 
       
[-1, -1, -1, 1, 1, 1]
[[1, 2], [1, 4], [2, 4], [2, 1], [5, 1], [4, 2]]
[-1, -1, -1, 1, 1, 1]
[[1, 2], [1, 4], [2, 4], [2, 1], [5, 1], [4, 2]]
# 例題にSVMを適応 prob = svm_problem(cls, dat) m = svm_model(prob, param) 
       
*
optimization finished, #iter = 4
nu = 0.033333
obj = -1.000000, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 2
*
optimization finished, #iter = 4
nu = 0.033333
obj = -1.000000, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 2

データが正しく分類されているか赤(1,4)の座標を入力すると、-1.0が返され、 正しい結果が返ってきます。

m.predict([1, 4]) 
       
-1.0
-1.0

結果の表示

contour_plotを使って、SVMの予想をコンタマップで表示すると、$y = x$ の線でうまく、分類されているのが、分かります。

contour_plot(lambda x, y : m.predict([x, y]), (x, 0, 5), (y, 0, 5), figsize=5) 
       

さらに、各点(赤、青)の予想値と境界線の形状をlist_plot3で表示します。

# plot3dがうまく表示できないので、list_plot3dで代替 pl7 = list_plot3d([(x, y, m.predict([x, y])) for x in srange(0, 5, 0.1) for y in srange(0, 5, 0.1)]) pl8 = list_plot([(x, y, m.predict([x, y])) for (x, y) in c1], rgbcolor='red') pl9 = list_plot([(x, y, m.predict([x, y])) for (x, y) in c2], rgbcolor='blue') (pl8 + pl9 +pl7).show(xmin=0, xmax=5, ymin=0) 
       

SVMのカーネルメソッドのすごさを確かめるために点の値がチェスボードのように 格子状に部分布する点を分析することにします。

まずは、チェスボードのマスの値を返すchessBox関数を作成します。 ただしく、値がセットされるか、conour_plotでみてみましょう。

# チェスボックスの例 def chessBox(x, y): if ((int(x)+int(y))%2) == 0: return 1 else: return -1 #[chessBox(x, y) for x in range(0,5) for y in range(0,5)] contour_plot(chessBox, (x, 0, 5), (y, 0, 5), figsize=5) 
       

テストデータの作成

0から5の範囲にランダムに点を生成し、chessBox関数で赤(red)と青(blue) に振り分けます。

# ランダムな点を生成 rndPts = [[5*random(), 5*random()] for i in range(0,1000)]; 
       

Kernel関数LINEARの場合

kernel_type=LINEAR(線形を意味する)を使って分類すると、 うまく格子状のデータを分類することができません。

red = [pt for pt in rndPts if chessBox(pt[0], pt[1]) == -1]; blue = [pt for pt in rndPts if chessBox(pt[0], pt[1]) == 1]; redCls = [-1 for pt in red] blueCls = [1 for pt in blue] chessRedPlt = list_plot([(x, y) for (x, y) in red], rgbcolor='red') chessBluePlt = list_plot([(x, y) for (x, y) in blue], rgbcolor='blue') (chessRedPlt+chessBluePlt).show(xmin=0, xmax=5, figsize=5) 
       
# カーネルメソッドをLINEARだとうまく分けられない prob = svm_problem(redCls + blueCls, red + blue) param = svm_parameter(kernel_type = LINEAR, C=float(1000)) m = svm_model(prob, param) contour_plot(lambda x, y : m.predict([x, y]), (x, 0, 5), (y, 0, 5), figsize=5) 
       
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
.................................*......................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
...........................................*............................\
........................................................................\
........................................................................\
........................................................................\
............................................................*...........\
........................................................................\
....................*...................................................\
.................*......................................................\
........................................................................\
.......................*................................................\
...................................................................*....\
......................................................*.................\
........................................................................\
........................................................................\
........................................................................\
...............................*........................................\
........................................................................\
........................................................................\
............................................*...........................\
........................................................................\
........................................................................\
........................................................................\
........................................................................\
..................................................*
optimization finished, #iter = 3348299
nu = 0.974402
obj = -974232.337534, rho = -0.857296
nSV = 976, nBSV = 973
Total nSV = 976
.........................................................................................................................................................................................................................................................................................................................................................................................................*.........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................*................................................................................................................................................................................................................................................................................................................*.......................................................................................................*....................................................................*.....................................................................................................................................................*...................................................................................................................*..........................................................*........................................................................................................................................................................................................................................................................*....................................................................................................................................................................................................................................*.............................................................................................................................................................................................................................................................................................................................................................................*
optimization finished, #iter = 3348299
nu = 0.974402
obj = -974232.337534, rho = -0.857296
nSV = 976, nBSV = 973
Total nSV = 976

Kernel関数RBFの場合

次に、kernel_type=RBF(ガウシアンカーネル関数)を使って分類すると、 なんとなく格子状に分類しているように見えます。

ガウシアンカーネル関数は、 $$ K(x, x') = e ^{\left( - \frac{| x - x' |^2}{\sigma^2} \right)} $$

# カーネルメソッドをRBFにするとある程度格子の形が見て取れる prob = svm_problem(redCls + blueCls, red + blue) param = svm_parameter(kernel_type = RBF, C=float(1000)) m = svm_model(prob, param) contour_plot(lambda x, y : m.predict([x, y]), (x, 0, 5), (y, 0, 5), figsize=5) 
       
...............................................*.......................*\
....................*
optimization finished, #iter = 90313
nu = 0.213203
obj = -161853.152563, rho = 9.646479
nSV = 238, nBSV = 187
Total nSV = 238
...............................................*.......................*....................*
optimization finished, #iter = 90313
nu = 0.213203
obj = -161853.152563, rho = 9.646479
nSV = 238, nBSV = 187
Total nSV = 238

簡単な画像認識

最後に簡単な画像認識をLIBSVMを使って確かめてみます。

5x5のマス目に数字の0から4までを書いた画像5個(本当に少ないです!) をテストデータとして使用します。

# 文字認識 m0 = [[0,1,1,1,0], [1,0,0,0,1], [1,0,0,0,1], [1,0,0,0,1], [0,1,1,1,0]] m1 = [[0,0,1,0,0], [0,0,1,0,0], [0,0,1,0,0], [0,0,1,0,0], [0,0,1,0,0]] m2 = [[0,1,1,1,1], [1,0,0,1,0], [0,0,1,0,0], [0,1,0,0,0], [1,1,1,1,1]] m3 = [[0,1,1,1,0], [1,0,0,0,1], [0,0,1,1,0], [1,0,0,0,1], [0,1,1,1,0]] m4 = [[0,0,1,0,0], [0,1,0,0,0], [1,0,0,1,0], [1,1,1,1,1], [0,0,0,1,0]] p0 = flatten(m0); p1 = flatten(m1); p2 = flatten(m2); p3 = flatten(m3) p4 = flatten(m4) v = [0,1,2,3,4] 
       

作成したデータをcontour_plotを使って表示して、確認します。 なんとなくそれらしく見えるでしょう。(笑)

# 画像作成用の関数 def mesh(x, y, tbl): idX = int(x) idY = int(4.9-y) return tbl[idY][idX] # 学習用画像を表示 trn0 = contour_plot(lambda x, y : mesh(x, y, m0), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) trn1 = contour_plot(lambda x, y : mesh(x, y, m1), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) trn2 = contour_plot(lambda x, y : mesh(x, y, m2), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) trn3 = contour_plot(lambda x, y : mesh(x, y, m3), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) trn4 = contour_plot(lambda x, y : mesh(x, y, m4), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) html.table([[trn0, trn1, trn2], [trn3, trn4]]) 
       

画像認識

いよいよ画像認識の準備が整いました。 えいや〜で、モデルを作成します。

# 画像認識 param = svm_parameter(kernel_type = RBF, C=float(10)) prob = svm_problem(v,[p0,p1,p2,p3,p4]) m = svm_model(prob, param) 
       
*
optimization finished, #iter = 1
nu = 0.246622
obj = -2.466216, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.676333
obj = -6.763327, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.330771
obj = -3.307713, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.202682
obj = -2.026823, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 5
*
optimization finished, #iter = 1
nu = 0.246622
obj = -2.466216, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.676333
obj = -6.763327, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.280928
obj = -2.809276, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.330771
obj = -3.307713, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.202682
obj = -2.026823, rho = 0.000000
nSV = 2, nBSV = 0
*
optimization finished, #iter = 1
nu = 0.262318
obj = -2.623181, rho = 0.000000
nSV = 2, nBSV = 0
Total nSV = 5

テスト用の画像

テストに使う画像は、以下の3個です。 判別結果は、ただしく0, 1, 1となっています。(めでたし、めでたし)

# テスト用の画像を作成する m0_1 = [[0,1,1,1,0], [0,1,0,0,1], [0,1,0,0,1], [0,1,0,0,1], [0,1,1,1,0]] m1_1 = [[0,0,1,0,0], [0,1,1,0,0], [0,0,1,0,0], [0,0,1,0,0], [0,1,1,1,0]] m1_2 = [[0,0,0,1,0], [0,0,0,1,0], [0,0,1,0,0], [0,0,1,0,0], [0,0,1,0,0]] t0_1 = flatten(m0_1) t1_1 = flatten(m1_1) t1_2 = flatten(m1_2) 
       
# テスト用画像の表示 cnt1 = contour_plot(lambda x, y : mesh(x, y, m0_1), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) cnt2 = contour_plot(lambda x, y : mesh(x, y, m1_1), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) cnt3 = contour_plot(lambda x, y : mesh(x, y, m1_2), (x, 0, 4.9), (y, 0, 4.9), aspect_ratio=1, figsize=(2, 1.23)) html.table([[cnt1, cnt2, cnt3]]) 
       
# テスト用画像の認識 print m.predict(t0_1) print m.predict(t1_1) print m.predict(t1_1) 
       
0.0
1.0
1.0
0.0
1.0
1.0

念のため、学習に使ったデータが正しく識別されるかもみてみました。

こんなに少ないデータでよく認識できるものだと感心しました。これがSVMのすごさなのでしょうか?

# 学習用画像の認識 print m.predict(p0) print m.predict(p1) print m.predict(p2) print m.predict(p3) print m.predict(p4) 
       
0.0
1.0
2.0
3.0
4.0
0.0
1.0
2.0
3.0
4.0