サポートベクターマシン によるパターン認識 高知大学 理学部 数理情報科学科 ４回生 本田研究室 ９８ー数理０１９ 緒方浩二
背景 サポートベクターマシン（SVM)とはVapnik等によって提案された識別学習 今、注目を集めている新しいパターン認識手法である パターン認識とは、システムに学習機能を組み込んだり、最適なパラメータを求めたりする際に必要な技術である
発表の流れ １．パターン認識 ２．サポートベクトルマシン（SVM） ３．線形SVM ４．非線形SVM ５．数値解法 ６．まとめ
パターン認識 ある 次元特徴空間のベクトルと、分類さ れるべきクラスとの対応付けをすること ：特徴ベクトル ：クラス ある 次元特徴空間のベクトルと、分類さ れるべきクラスとの対応付けをすること ：特徴ベクトル ：クラス SVMの対象は２クラスの識別問題
パターン認識の具体例 図－1 ２種類のキノコの特徴ベクトル（青丸および赤丸）の分布 と毒キノコ（赤丸）を見分けるための識別境界（黒実線） 従来、パターン認識の問題では、観測されたデータの中の代表的なデータに注目し分類するニューラルネットワークなどの方法が採られてきた。 図－1 ２種類のキノコの特徴ベクトル（青丸および赤丸）の分布 と毒キノコ（赤丸）を見分けるための識別境界（黒実線） ：毒のないクラスの集合 ：毒キノコの集合
SVMによるパターン認識 ：識別関数 ：識別境界 SVMによるパターン認識では、クラス が、 既知の観測データ集合 から、識別規則 ：識別関数 ：識別境界 SVMによるパターン認識では、クラス が、 既知の観測データ集合 から、識別規則 を満たす識別面 を求める。
SVMの種類 線形SVM 非線形SVM －カーネル法ー
線形SVM SVMではマージンを最大化する識別面を最良と見なす SVMではマージンを最適化する識別面を最良と見なす マージン 前田英作 IPSJ Magazine Vol.42 No.7 July 2001
線形SVMの定式化その１ 線形識別関数 とおく。 ここで、 個の学習パターン の 満たすべき条件を、 とする。
線形SVM定式化その２ マージン→ マージンを最大化する識別面を求めることは 以下の式を満たす を求めることに相当
マージン最大化に双対な問題 × × 最大化 するλを求める 制約条件： ラグランジュ乗数 ラグランジュの未定乗数法を用いる ● ● ● ● サポートベクトル λ＞０ ラグランジュの未定乗数法を用いる 最大化 するλを求める 制約条件： ラグランジュ乗数 ● ● ● ● × ● ● ● × ● ● ● ●
線形SVM適用例 サポートベクトル サポートベクトル 前田英作 IPSJ Magazine Vol.42 No.7 July 2001
非線形SVM-カーネルトリックー に変換して、変換後の空間においてSVMを適用 ガウシアン型カーネル ◎カーネル関数 ガウシアン型カーネル
マージン最大化双対問題 ーカーネル法の場合ー 最大化 制約条件：
数値解法 Gradient Ascent （勾配上昇法） SMO（Sequential Minimal Optimization）
SMO(Sequential Minimal Optimization) を満たす、 ２点のラグランジュ係 数のみ可変として、 を最大化する、 は、解析的に解ける。 最も、効果的に を最大化できる２点を選択 を更新 繰り返し 全データを使用せずに効率よく最適化を行える →データマイニングなど大規模データにも適用可能
非線形SVMの識別境界の例 前田英作 IPSJ Magazine Vol.42 No.7 July 2001
まとめ（今後の研究課題） まとめ ①SVMはマージン最大化基準を採用した識別手法であり、２次最適化問題を解くことにより、最適な識別関数が得られる ②カーネルトリックの利用によって複雑な識別面が扱える ③大規模データに対する適用可能な効率的なアルゴリズム（SMO)が存在する 問題 ①文字認識など多クラスの識別にそのま まの形では適用できない ②二次計画法を解くための計算量の問題 ③カーネルの選択