サポートベクターマシン
によるパターン認識
高知大学 理学部 数理情報科学科
4回生 本田研究室
98ー数理019 緒方浩二
背景



サポートベクターマシン(SVM)とはVapnik
等によって提案された識別学習
今、注目を集めている新しいパターン認識
手法である
パターン認識とは、システムに学習機能を
組み込んだり、最適なパラメータを求めた
りする際に必要な技術である
発表の流れ
1.パターン認識
2.サポートベクトルマシン(SVM)
3.線形SVM
4.非線形SVM
5.数値解法
6.まとめ
パターン認識
n
ある 次元特徴空間のベクトルと、分類さ
れるべきクラスとの対応付けをすること
xi  R  yi
n
x i :特徴ベクトル
yi
:クラス
SVMの対象は2クラスの識別問題
パターン認識の具体例
x
x2
x1
図-1
2種類のキノコの特徴ベクトル(青丸および赤丸)の分布
と毒キノコ(赤丸)を見分けるための識別境界(黒実線)
x1:毒のないクラスの集合 x2 :毒キノコの集合
SVMによるパターン認識
1
f w ( x)  sign( g w ( x))  
 1
x  x1
x  x2
:識別関数
g w ( x)  0 :識別境界
SVMによるパターン認識では、クラス y が、
既知の観測データ集合 から、識別規則 f w (x)
を満たす識別面 g w (x)を求める。
x
SVMの種類


線形SVM
非線形SVM
-カーネル法ー
SVMではマージ
ンを最大化する
識別面を最良と
見なす
線形SVM
マージン
前田英作 IPSJ Magazine Vol.42 No.7 July 2001
線形SVMの定式化その1
線形識別関数
t
とおく。
f ( x)  sign( g ( x))  sign(w x  b)
n
ここで、 個の学習パターン
満たすべき条件を、
xi (i  1,...,n) の
 1 xi  x1
i, g ( x)  w xi  b


1
x

x
i
2

とする。
t
線形SVM定式化その2
マージン→
2/ w
マージンを最大化する識別面を求めることは


以下の式を満たす w , b を求めることに相当
1
2
Minim ize G ( w)  w
2
s.t. i, yi  ( wt xi  b)  1  0
マージン最大化に双対な問題
サポートベクトル
λ>0
ラグランジュの未定乗数法を用いる
l
l
1
t
W ( )   i   i  j yi y j x x
2 i , j 1
i 1
最大化
するλを求める
●
●
0  i  C (i  1,...,l ),
制約条件:
l
 y
i 1
i i
0
 : ラグランジュ乗数   0
●
●
×
●
●
×
●
●
●
●
●
0
線形SVM適用例
サポートベクトル
 o
前田英作 IPSJ Magazine Vol.42
No.7 July 2001
非線形SVM-カーネルトリックー
x   (x) に変換して、
i ( x)(i  1,...,d )
変換後の空間において
SVMを適用
 ( x)  (1 ( x),2 ( x),...,d  ( x))
t
n

*t
*
*
t
*
f ( x)  sign w  ( x)  b  sign  yi i ( xi )  ( x)  b 
 i 1



◎カーネル関数
K ( x, y )   ( x) t  ( y ) 

x y

K ( x, y )  exp 
2

2


d

i 1
2
i
( x)i ( y )

  ガウシアン型カーネル


マージン最大化双対問題
ーカーネル法の場合ー
l
l
1
t
W ( )   i   i  j yi y j x x
2 i , j 1
i 1
K ( xi , x j )
制約条件:
0  i  C (i  1,...,l ),
l
 y
i 1
i i
0
最大化
数値解法


Gradient Ascent (勾配上昇法)
SMO(Sequential Minimal
Optimization)
勾配上昇法
l
1 l
W ( )   i   i  j yi y j K ( xi , x j )
2 i , j 1
i 1
SMO(Sequential
Minimal Optimization)
0  i  C (o  1,...,l ),
l
 y
i 1
i
i
0
1x1  2 x2  0
を満たす、 2点のラグランジュ係
数のみ可変として、W を最大化する、
1 , 2 は、解析的に解ける。
最も、効果的に Wを最大化できる2点を選択
1 , 2 を更新
繰り返し
全データを使用せずに効率よく最適化を行える
→データマイニングなど大規模データにも適用可能
非線形SVMの識別境界の例
前田英作 IPSJ Magazine Vol.42 No.7 July 2001
まとめ(今後の研究課題)
まとめ
①SVMはマージン最大化基準を採用した識別手法であり、2次最適化
問題を解くことにより、最適な識別関数が得られる
②カーネルトリックの利用によって複雑な識別面が扱える
③大規模データに対する適用可能な効率的なアルゴリズム(SMO)が存
在する

問題
①文字認識など多クラスの識別にそのま まの形では適用できない
②二次計画法を解くための計算量の問題
③カーネルの選択

ダウンロード

サポートベクトルマシンによる パターン認識手法の研究