![45
ペアワイズカップリング法（２）
1. 識別関数?????? ?? から分類確率??????? ?? のモデル化
??????? ?? =
1
1 + exp(????????? ?? + ??)
→最尤推定法によりA,Bを推定
2. モデル化した??????? ?? と実際の?????? ?? が近くなるよ
うに????
?? の推定
min
????
??∈[??]
? ???? + ???? ???? ??????? ∥ ??????
??≠??
→ ?????? = ????/(???? + ????)より ????
??∈[??]
に関して最小化](https://image.slidesharecdn.com/2017b4m1svm-170523142253/85/SVM-46-320.jpg)
![50
SVMの定式化の拡張（多クラス）
? SVMの識別関数を以下のように拡張
（????
, ??0
??
は各クラス??(∈ [??])に対応するパラメータ）
?? ?? = argmax
??
???? ??
?? ?? + ??0
??
? あるデータ(????, ????)を分類するために必要な条件
?????? ??
?? ?? + ??0
????
≥ ???? ??
?? ?? + ??0
??
+ 1 (?? ≠ ????)
クラス????の時の
識別関数の値
クラス????以外の時の
識別関数の値
+1（ハードマージン）
→ +1 ? ????
??
（ソフトマージン）](https://image.slidesharecdn.com/2017b4m1svm-170523142253/85/SVM-51-320.jpg)
![51
多クラスSVMの最適化問題
２クラス分類SVMの時と同様に最適化問題に帰着
→SVMの時と同様に双対問題を考えられる
min
????,??0
??,????
??
??∈[??]
1
2
? ???? 2
??
+ ?? ? ? ????
??
??≠??????
??. ??. ??? ?????? ?? ?? ?? + ??0
????
≥ ???? ??
?? ?? + ??0
??
+ 1 ? ????
??
(?? ≠ ????)
??? ????
??
≥ 0 (?? ≠ ????)](https://image.slidesharecdn.com/2017b4m1svm-170523142253/85/SVM-52-320.jpg)
コンピュータ先端ガイド２巻３章勉强会(厂痴惭)
- 2. 1 自己紹介 ? 名前：金子 真也（かねこ まさや） ? Twitter：@syinari0123 ? 出身：巣鴨高校 ? 趣味：お散歩, 美味しいもの?美術館巡りなど ? やる気だけはなくさないように生きてます
- 3. 2 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 4. 3 発表を始める前に ? 今回の発表は基本的にデータ解析アルゴリズム の話なので数式がかなり多いです… ? できる限り抑えるようにしましたが, せっかくの 勉強会なので「ある程度の数式は仕方ない ですかね…」としてスライドを作っています ? すみません…
- 5. 4 目次 ? パターン識別 ← ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 6. 5 パターン識別とは 与えられた入力データがどのクラスに属するか を教師あり学習で識別する問題 →正解クラスを適切に出力できる?? ???? を求める 特徴ベクトル ???? 識別関数 ??(????) 正解クラス ???? ネコである (クラス１ ??1) ネコじゃない (クラス２ ??2) ??(????) ≥ ?? ?? ???? ≤ ?? 入力画像 ???? = ????1 ? ???? ??
- 7. 6 線形パターン識別 識別関数?? ???? として以下のように定める ?? ???? = ???? ???? + ??0 ? ≥ 0 (???? ∈ ??1) ≤ 0 (???? ∈ ??2) →適切に????を識別できるような??, ??0を求める (空間を適切に分断する超平面を求める) http://www.neuro.sfc.keio.ac.jp/~masato/study/SVM/SVM_1.htm
- 8. 7 目次 ? パターン識別 ? 線形から非線形への拡張 ← ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 10. 9 線形から非線形への拡張（２） 非線形関数Φによりデータの非線形変換 ??: ?? = ??1, . . , ???? ?? → ??1 ?? , … , ???? ?? →線形分離可能な分布をするような空間に変換 ?? ???? = ???? ??(????) + ??0 ? ≥ 0 (???? ∈ ??1) ≤ 0 (???? ∈ ??2) https://www1.doshisha.ac.jp/~mjin/R/31/31.html
- 12. 11 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ← ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 13. 12 カーネル関数（１） ある関数?? ?? (???? → ????)があり, ???, ?? ∈ ????に対して, ?? ??, ?? = ?? ?? ?? ??(??) が成立する関数Φが存在する時, 関数kを カーネル関数という. ※カーネル関数が存在するための必要十分条件と してはMercer’s theoremが存在（省略）
- 14. 13 カーネル関数（２） カーネル関数の例 ? 線形カーネル ?? ??, ?? = ???? ?? ? 多項式カーネル ?? ??, ?? = ???? ?? + ?? ?? ? ガウスカーネル ?? ??, ?? = exp(? ?? ? ?? 2??2 ) ? RBFカーネル ?? ??, ?? = exp(??? ?? ? ?? 2)
- 15. 14 カーネル関数（３） カーネル関数を使うとメリットがある 1. D次元ベクトルの内積がd次元ベクトルの関数 で表される(?? ? ??の時,計算量の削減に) →カーネルトリック 2. 具体的な?? ?? の形を与える必要がない カーネル法はSVMと相性がかなり良い
- 16. 15 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) ← – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 17. 16 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM ← – 非線形SVM ? SVMの多クラス分類 ? SVMの応用
- 18. 17 線形SVM ? 基本的な考えとしてはパターン識別と同じ ? クラスを分類する超平面の候補のうち, 以下の 図で点線間の距離を最大にする境界を求める （マージン最大化） 最先端ガイド２ ３章 図３.８右
- 19. 18 マージン最大化（１） 分類境界から最も近くにある????との距離の最大化 max ??,??0 min ?? ???? ???? + ??0 ?? 制約条件として ?? ???? = ???? ???? + ??0 ≥ 1 ? (?) を入れることで上の式は以下に帰着できる max ?? 1 ?? = min ?? ??
- 20. 19 マージン最大化（２） マージン最大化の直感的解釈 min ??,??0 ?? = max ??,??0 2 ?? ??. ??. ?? ???? ≥ 1 2 ?? ??(????) ?? = ???? ?? + ??0 ?? ?? ?? = ???? ?? + ??0 ?? ?? = 1 ?? ?? = ?1 ?? ?? = 0 ????|?? ?? | ≥ 1
- 21. 20 ハードマージン 制約式 ? は次のように書き換えられる ?? ???? = ???? ???? + ??0 ? ≥ 1 (???? ∈ ??1) ≤ ?1 (???? ∈ ??2) 制約式 ? 条件下で以下を求める問題に帰着できる min ??,??0 ?? →線形分離不可能な場合に解が存在しない ?? ?? ≥ 1 ?? ?? ≤ ?1 ?? ?? = 0
- 22. 21 ソフトマージン 分離の誤りを少し許すために制約式 ? に 誤差項????(≥ 0)を導入 ?? ???? = ???? ???? + ??0 ? ≥ 1 ? ???? (???? ∈ ??1) ≤ ?1 + ????(???? ∈ ??2) ? (??) ???? ?????1 ????+1 ?? ?? = 1 ?? ?? = ?1
- 23. 22 最適化問題への帰着（１） ????の属するクラスの変数(正解クラス)を 以下のように定める ???? = ? 1 (???? ∈ ??1) ?1 (???? ∈ ??2) ????のクラス属性も組み込んだ制約式 ?? は次になる ???? ???? ???? + ??0 ≥ 1 ? ???? ???? ≥ 0 ???? = 1 ???? = ?1 ?? ?? ≥ 1 ? ???? ?? ?? ≤ ?1 + ????
- 24. 23 最適化問題への帰着（２） 最終的に線形SVM（ソフトマージン）の最適化は 以下のような最小化問題に帰着できる ? 第一項：マージン(2/ ?? )の最大化 ? 第二項：誤差項(????)の最小化（??は正則化係数） min ??,??0,???? 1 2 ?? 2 + ?? ? ???? ?? ??=0 ??. ??. ??? ???? ???? ???? + ??0 ≥ 1 ? ???? ??? ???? ≥ 0
- 25. 24 ソフトマージンの実例 パラメータＣの調節により誤りの許容度を 変化させることができる ?? = 100 の時 ?? = 0.1 の時 MLP サポートベクターマシン 第一章 図1.5
- 26. 25 線形SVMの双対問題 ラグランジュ関数を用いることで最適化問題から 以下の双対問題を導ける (??は双対変数) ? SVMの場合には強双対性が成立するために上式のように 書き換えられる（省略） ? カールシュ?クーン?タッカー条件（KKT条件） max ?? (? 1 2 ? ???? ???? ???? ???? ???? ?? ???? ??,?? + ? ???? ?? ) ??. ??. ? ???? ???? = 0 ?? ??? 0 ≤ ???? ≤ ??
- 27. 26 双対問題の利点 ? 非線形SVMへ拡張する際にはカーネルトリック をそのまま適用できる ? 内積がわかっていればデータ????そのものの保持 の必要がない（メモリの節約） – データ行列 ??1, … , ???? ?? の要素???? – 内積計算に必要なデータ量?? ?? ? 1 /2 ? 双対変数??の一部が0要素を多く持つ場合があり, 計算時間の短縮化に （マージン外領域にデータが多い場合）
- 28. 27 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ← ? SVMの多クラス分類 ? SVMの応用
- 29. 28 非線形SVM ? 線形な分離には限界がある ? 非線形関数Φを使ってデータを線形分離可能な 分布をするような空間に変換 ? 双対問題に対して非線形変換を行うことで カーネルトリックを利用できる https://www1.doshisha.ac.jp/~mjin/R/31/31.html
- 30. 29 非線形SVMの最適問題（１） 入力データを特徴空間へ写像する関数Φを用いて ?? ?? = ???? ??(??) + ??0 を識別関数とすればよい. 双対問題に代入すると, max ?? (? 1 2 ? ???? ???? ???? ???? ?? ???? ?? ??(????) ??,?? + ? ???? ?? ) ??. ??. ? ???? ???? = 0 ?? ??? 0 ≤ ???? ≤ ??
- 31. 30 非線形SVMの最適問題（２） 前式をカーネル関数で書き直すと (KKT条件より) ?? ?? = ? ???? ???? ??(????, ??) ?? + ??0 双対問題は以下のようになる. max ?? (? 1 2 ? ???? ???? ???? ???? ??(????, ????) ??,?? + ? ???? ?? ) ??. ??. ? ???? ???? = 0 ?? ??? 0 ≤ ???? ≤ ??
- 33. 32 非線形SVMの実例（２） ガウスカーネルを利用した場合 σが小さい時 σが大きい時 http://aidiary.hatenablog.com/entry/20100503/1272889097
- 34. 33 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ← ? SVMの応用
- 36. 35 SVMの多クラス分類（２） 工夫の方向性として次のようなものが考えられる ? 複数の２クラス分類器の組み合わせ – １対他方式 – １対１方式 – 誤り訂正出力符号 ? SVMの定式化の拡張
- 37. 36 SVMの多クラス分類の目次 ? 複数の２クラス分類器の組み合わせ ← – １対他方式 – １対１方式 – 誤り訂正出力符号 ? SVMの定式化の拡張
- 38. 37 SVMの多クラス分類の目次 ? 複数の２クラス分類器の組み合わせ – １対他方式 ← – １対１方式 – 誤り訂正出力符号 ? SVMの定式化の拡張
- 39. 38 １対他方式（１） ? 最も単純な方式 ? 1クラスと残りのクラスに分類 ? k番目のクラスの識別関数?? ?? ?? の最大値を選ぶ ことで属するクラスの決定 argmax ?? ?? ??(??) クラス 1 クラス 2 クラス 3 http://qiita.com/pika_shi/items/5e59bcf69e85fdd9edb2
- 40. 39 １対他方式（２） 特徴として以下のようなことが挙げられる ? 実装が容易 ? 識別関数?? ?? ?? の値を比較することが適切か不明 ↑異なるSVMを利用しているから
- 41. 40 SVMの多クラス分類の目次 ? 複数の２クラス分類器の組み合わせ – １対他方式 – １対１方式 ← – 誤り訂正出力符号 ? SVMの定式化の拡張
- 42. 41 １対１方式（１） ? 全体から２つのクラスのペアを作り分類 – nクラスに対して ?? ??2個のSVM ? 全ての組み合わせに対して多数決を行う ?????? ?? ? > 0 ??に投票 < 0 ??に投票 3クラス分類問題において, あるデータ??が… ??12 ?? > 0 クラス１に投票 ??23 ?? < 0 クラス３に投票 ??13 ?? > 0 クラス１に投票 → データ??はクラス１に分類（２票獲得）
- 43. 42 １対１方式（２） 特徴として以下のようなことが挙げられる ? 訓練時には毎回対象の２クラス分のデータしか 用いないのでSVMの学習コストが小さい ? 使うSVMの個数が多い(??(??2)) ? 単純な多数決以外にも… – 非循環有効グラフによる方法 – ペアワイズカップリング法
- 44. 43 非循環有効グラフによる方法 逐次的に２クラス分類を行っていくことで 分類回数を減らす http://www.kri.sfc.keio.ac.jp/report/mori/2004/c-118/
- 45. 44 ペアワイズカップリング法（１） 確率的な解釈で1対１分類結果?????? ?? から 多クラス分類確率???? ?? の推定 １対１での分類確率 ?????? ?? 全体からの分類確率 ???? ?? 識別関数 ?????? ?? ↓ ?? ?? = ?? ?? ∈ ??, ?? , ?? = ?? ↓ ??(?? = ??|?? = ??) SVMでの識別境界 (1)モデル化 (2)推定
- 46. 45 ペアワイズカップリング法（２） 1. 識別関数?????? ?? から分類確率??????? ?? のモデル化 ??????? ?? = 1 1 + exp(????????? ?? + ??) →最尤推定法によりA,Bを推定 2. モデル化した??????? ?? と実際の?????? ?? が近くなるよ うに???? ?? の推定 min ???? ??∈[??] ? ???? + ???? ???? ??????? ∥ ?????? ??≠?? → ?????? = ????/(???? + ????)より ???? ??∈[??] に関して最小化
- 47. 46 SVMの多クラス分類の目次 ? 複数の２クラス分類器の組み合わせ – １対他方式 – １対１方式 – 誤り訂正出力符号 ← ? SVMの定式化の拡張
- 49. 48 誤り訂正出力符号（２） ? m個の符号の列それぞれで識別関数???? ?? を学習 ? それぞれの符号とのハミング距離を計算し, 最も 距離が近いクラスへと分類 識別関数 ???? ???? (?? = 1 … ??) -1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 正解符号語 ?? = 2 距離0 特徴ベクトル ???? 入力画像 ???? = ????1 ? ???? ?? 符号語
- 50. 49 SVMの多クラス分類の目次 ? 複数の２クラス分類器の組み合わせ – １対他方式 – １対１方式 – 誤り訂正出力符号 ? SVMの定式化の拡張 ←
- 51. 50 SVMの定式化の拡張（多クラス） ? SVMの識別関数を以下のように拡張 （???? , ??0 ?? は各クラス??(∈ [??])に対応するパラメータ） ?? ?? = argmax ?? ???? ?? ?? ?? + ??0 ?? ? あるデータ(????, ????)を分類するために必要な条件 ?????? ?? ?? ?? + ??0 ???? ≥ ???? ?? ?? ?? + ??0 ?? + 1 (?? ≠ ????) クラス????の時の 識別関数の値 クラス????以外の時の 識別関数の値 +1（ハードマージン） → +1 ? ???? ?? （ソフトマージン）
- 52. 51 多クラスSVMの最適化問題 ２クラス分類SVMの時と同様に最適化問題に帰着 →SVMの時と同様に双対問題を考えられる min ????,??0 ??,???? ?? ??∈[??] 1 2 ? ???? 2 ?? + ?? ? ? ???? ?? ??≠?????? ??. ??. ??? ?????? ?? ?? ?? + ??0 ???? ≥ ???? ?? ?? ?? + ??0 ?? + 1 ? ???? ?? (?? ≠ ????) ??? ???? ?? ≥ 0 (?? ≠ ????)
- 53. 52 多クラスSVMの双対問題 同様にラグランジュ関数によって最適化問題から 以下の双対問題を導ける (???? ??, ????? ??は双対変数) 識別関数も以下のようになる（KKT条件の利用） ???? ?? ?? ?? + ??0 ?? ＝ ? ??????? ?? ????, ???? ?? + ??0 ?? max ?? ? 1 2 ? ? ??????? ??????? ?? ????, ???? ????,?? + ? ? ?????? ??≠?????? ??. ??. ??? ? ??????? ?? = 0 (?? ≠ ????) ??? 0 ≤ ?????? ≤ ?? (?? ≠ ????)
- 54. 53 目次 ? パターン識別 ? 線形から非線形への拡張 ? カーネル関数 ? SVM(Support Vector Machine) – 線形SVM – 非線形SVM ? SVMの多クラス分類 ? SVMの応用 ←
- 55. 54 SVMの応用 今回は分類問題に絞って解説を試みたが他にも – 回帰分析 – 教師なし学習（異常検知） – 構造化問題（自然言語処理など） – 半教師あり学習 にも利用可能！（すごそう）
- 56. 55 参考文献 ? 八木康史?斎藤英雄 編 「コンピュータビジョン最先端ガイド２」 ? 竹内一郎?鳥山昌幸 「MLPシリーズ サポートベクターマシン」