サポートベクターマシンによるパターン認識高知大学理学部数理情報科学科４回生本田研究室９８ー数理０１９緒方浩二背景    サポートベクターマシン（SVM)とはVapnik 等によって提案された識別学習今、注目を集めている新しいパターン認識手法であるパターン認識とは、システムに学習機能を組み込んだり、最適なパラメータを求めたりする際に必要な技術である発表の流れ１．パターン認識２．サポートベクトルマシン（SVM）３．線形SVM ４．非線形SVM ５．数値解法６．まとめパターン認識 n ある次元特徴空間のベクトルと、分類されるべきクラスとの対応付けをすること xi  R  yi n x i ：特徴ベクトル yi ：クラス SVMの対象は２クラスの識別問題パターン認識の具体例 x x2 x1 図－1 ２種類のキノコの特徴ベクトル（青丸および赤丸）の分布と毒キノコ（赤丸）を見分けるための識別境界（黒実線） 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の定式化その１線形識別関数 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/ w マージンを最大化する識別面を求めることは   以下の式を満たす w , b を求めることに相当 1 2 Minim ize G ( w)  w 2 s.t. i, yi  ( wt xi  b)  1  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 を満たす、２点のラグランジュ係数のみ可変として、W を最大化する、 1 , 2 は、解析的に解ける。最も、効果的に Wを最大化できる２点を選択 1 , 2 を更新繰り返し全データを使用せずに効率よく最適化を行える →データマイニングなど大規模データにも適用可能非線形SVMの識別境界の例前田英作 IPSJ Magazine Vol.42 No.7 July 2001 まとめ（今後の研究課題）まとめ ①SVMはマージン最大化基準を採用した識別手法であり、２次最適化問題を解くことにより、最適な識別関数が得られる ②カーネルトリックの利用によって複雑な識別面が扱える ③大規模データに対する適用可能な効率的なアルゴリズム（SMO)が存在する  問題 ①文字認識など多クラスの識別にそのままの形では適用できない ②二次計画法を解くための計算量の問題 ③カーネルの選択 