機械学習 - SVM

1. サポートベクターマシン
2. 非線形SVM

Transcript

1. 分類問題2: サポートベクターマシン 第7回 機械学習発展 （導入編） ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 yusuke_yamamoto@acm.org
2. 講義のトピック 機械学習 教師あり学習 教師なし学習 強化学習 ・クラスタリング ・データ圧縮 ・分類 ・回帰 … … 3 行動情報学科に 特有の応用手法 ・K近傍法 ・サポートベクタマシン ・ニューラルネットワーク
3. K-近傍法（k-NN: k nearest neighbor）のアイデア 4 対象データまでの距離が最も近いK個のデータの ラベルのうち、最も多いラベルに分類する ？ K=5:⻘ K=3:緑 K=1:⻘ 多 数 決
4. K-近傍法のメリット・デメリット 5 メリット • 単純なのに強⼒ • データの背後にある分布を仮定しなくてよい （ノンパラメトリックな⼿法） デメリット • 推論フェーズの計算量が⼤きい（毎回の距離計算） • 次元の呪いの影響を受けやすい
5. 教師あり学習のための機械学習アルゴリズムの分類 6 ロジスティック回帰 ナイーブベイズ サポートベクターマシン K近傍法 ランダムフォレスト & 決定木 ニューラルネットワーク 訓練データをすべて記憶して おき，それら全部を使って 予測を⾏う（推論計算が遅い） 訓練データの背後にあるモデル を抽出し，それを予測時に使う （推論計算は速い） インスタンスベース モデルベース 本⽇学ぶのはコレ
6. 1 一世を風靡した学習アルゴリズム サポートベクターマシン 7
7. 教師あり学習の歴史（⼀部抜粋） ロジスティック回帰 サポートベクターマシン 決定木 パーセプトロン 単純ベイズ分類器 ランダムフォレスト k-近傍法 ベイジアンネットワーク 深層学習 1958年 1957年 1951年 1979年 1985年 1992年 1960年代 2001年 2010年代 8 ⼀世を⾵靡した強⼒なアルゴリズム． 深層学習が台頭した今でも，状況に よっては⽤いられることも．
8. サポートベクターマシン（SVM） 入力 ・ベクトルデータ ・正則化係数 ! ・カーネル関数 " 学習 by SVM 9 それほど多くないデータでも精度よく推論したい時に有効 ID 血圧 （上） 喫煙 頻度 年齢 心臓 疾患 1 110 5 74 なし 2 160 17 53 あり … … … … … ⼼臓疾患データ 学習済み モデル ML 血圧 … 疾患 124 ？ 未知データ 推論 ⼼臓疾患あり 出力 ラベル（基本的には2値）
9. 2次元平⾯上で考える分類問題 •と×のデータ集合が与えられたときに， 未知の2次元データが•か×をどう予測する？ Q. X 0 Y ? ▲ ? ▲ 10
10. 2次元平⾯上で考える分類問題 •と×のデータを2分するような直線を見つける A. X 0 Y ? ▲ ? ▲ 直線より下側なら「•」 直線より上側なら「×」 ax+by+c=0 11
11. 2次元平⾯上で考える分類問題 •と×のデータを2分するような直線を見つける A. X 0 Y 直線といっても複数考えられる…どれがベストか？ A B C 12
12. 機械学習の⾄上命題 13 機械学習 汎化性能の高い 予測モデルの構築 未知データに対する予測性能を⾼める必要あり （訓練データに最適化しすぎても意味がない（過学習））
13. 2次元平⾯上で考える分類問題 X 0 Y ▲ ▲ ▲ ▲ 学習に使用したデータは 真の分布を完全に表現しているとは限らない ▲ ▲ できる限り未知のデータにも対応できる直線にしたい… 14
14. 2次元平⾯上で考える分類問題 X 0 Y A B C 未知のデータがどこに出現するか分からない状況で 未知データが•か×かを予測するベスト直線は？ Q. 15
15. 2次元平⾯上で考える分類問題 X 0 Y A 未知のデータがどこに出現するか分からない状況で 未知データが•か×かを予測するベスト直線は？ Q. 16 B
16. 2次元平⾯上で考える分類問題 X 0 Y B 未知のデータがどこに出現するか分からない状況で 未知データが•か×かを予測するベスト直線は？ Q. 17
17. 2次元平⾯上で考える分類問題 X 0 Y C 未知のデータがどこに出現するか分からない状況で 未知データが•か×かを予測するベスト直線は？ Q. 18 B
18. 2次元平⾯上で考える分類問題 X 0 Y 直線に最も近い訓練データから直線までの距離 （マージン）が最大となるような直線がベスト！！ A. 19 B
19. 2次元平⾯上で考える分類問題 X 0 Y A 20 直線に最も近い訓練データから直線までの距離 （マージン）が最大となるような直線がベスト！！ A.
20. 2次元平⾯上で考える分類問題 X 0 Y C 21 直線に最も近い訓練データから直線までの距離 （マージン）が最大となるような直線がベスト！！ A.
21. サポートベクター （直線に最も近い点） サポートベクターマシンの直感的なアイデア X 0 Y マージンを最大化する超平面を見つける （分類境界とサポートベクターの距離） !(#) = 0 サポートベクター （直線に最も近い点） 22
22. 数学的準備：超平⾯の数式表現（1/2） 23 x y x y z 2次元空間での直線 !" + $% + & = 0 !" + $% + &) + * = 0 3次元空間での平⾯
23. 数学的準備：超平⾯の数式表現（2/2） 24 x1 2次元空間での直線 +# "# + +$ "$ + +% = 0 '! (! + '" (" + ⋯ + '# = 0 N次元空間での超平⾯ x2 ! = ($! , $" ) ？ x1 x2 xN ベクトルwとxの内積 w=(w1 , w2 ) ※ 実は wは法線ベクトル ⟹ -&. + +% = 0
24. 数学的準備：2次元空間での点と直線間の垂直距離 25 x1 直線: '! $! + '" $" + '# = 0 x2 ($! ′, $" ′) + = |'! (! $ + '" (" $ + '# | '! " + '" " ⾼校で習った公式 L
25. 数学的準備：N次元空間での点と超平⾯の間の距離 26 |(! )! " + ⋯ + (# )# ′ + ($ | (! % + ⋯ + (# % = |-%#$ + '# | - x1 x2 xN !$ = ($! $ , $" $ , … , $% ′) + = L 直線: ,&! + '# = 0 ベクトルで表現 (- ! = ,&! + '# ) = |!(#)| -
26. サポートベクターマシンの定式化: 設定 X1 0 Xn N次元空間上の点 ! : " & = (% ! & , … , %' (&)) 点 ! のラベル値 y(&) = * 1 −1 … 点 . が×の場合 … 点 . が•の場合 27
27. サポートベクターマシンの定式化: 設定 X1 0 Xn N次元空間上の点 ! : " & = (% ! & , … , %' (&)) 点 ! のラベル値 y(&) = * 1 −1 … 点 . が×の場合 … 点 . が•の場合 y = −1の点 y = 1の点 28
28. サポートベクターマシンの定式化 : ⽬標設定(1/2) X1 0 Xn 点 1 について y(&) = 1 の場合，2(4 & ) ≥ 1 y(&) = −1の場合，2 4 & ≤ −1 目標1: 以下を満たす 2(4) を見つけたい ! # = 0 (* + = -!+" + /# ) 29
29. サポートベクターマシンの定式化 : ⽬標設定(2/2) X1 0 Xn 目標2: 2(4) のマージンを最大化させたい ! # = 0 (* + = -!+" + /# ) ×で - ! に 最も近い点 / •で - ! に 最も近い点 . 0' 0( ⟹ argmax 8 49 + 4: 30 分離超平⾯に最も近いデータはサポートベクトルと呼ばれる
30. サポートベクターマシンの最適化問題を解く 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) y(") = −1の場合，% ' " ≤ −1 31
31. サポートベクターマシンの最適化問題を解く 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) ⟹ argmax &, (! |!(#(*))| - + |!(# , )| - 点と超平⾯間の距離公式 32
32. サポートベクターマシンの最適化問題を解く 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) 式(1)より ≥ argmax &, (! 1 - + 1 - = argmax &, (! 2 - (* + = -!+" + /# ) ⟹ argmax &, (! |!(#(*))| - + |!(# , )| - 33
33. サポートベクターマシンの最適化問題を解く 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) ≥ argmax & 1 - + 1 - = argmax & 2 - ⟹ argmin &, (! - 2 逆数の最⼩化と等価 34
34. サポートベクターマシンの最適化問題を解く 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) ≥ argmax & 1 - + 1 - = argmax & 2 - ⟹ argmin & - 2 2乗を最⼩化 しても同じ ⟹ argmin & - " 2 35
35. サポートベクターマシンの最適化問題：問題設定の変形 点 ! について y(") = 1 の場合，%(' " ) ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmax 8 49 + 4: … 式(1) … 式(2) ⟹ argmin ; - $ 2 … 式(3) 最⼩化問題!! SVMの最適化は不等式制約下の最小化問題に帰着される （不等式制約） 36
36. 数理最適化の定⽯ 37 （不）等式制約下での 関数最小化 ラグランジュの未定乗数法
37. サポートベクターマシンに関する最適化問題の最終形 38 <(=(!), … , =(#)) = @ &0! # =(&) − 1 2 @ &0! # @ 10! # =(&)=(1)B(&)B(1)4 & 24(1) ∑ 123 4 "(1)#(1) = 0 および "(3) …, "(5) ≥ 0 の条件下で を最⼤化する " 1 を⾒つける(ただし ; = ∑&0! # =(&)B(&)4(&)) ラグランジュの未定乗数法 (. = 1, … , 7) ベクトルの内積
38. サポートベクターマシンの最適化を例で考える（1/4） X1 0 X2 ! # = 0 (* + = /$ 3$ + /% 3% + /# ) + $ = (3, 4) + % = (1,2) + & = (2, 6) 学習データとして2次元のデータが3つ与えられたとし， SVMを適用して最適な分離境界線を見つけたい 39 (* ! = 1) (* " = 1) (* # = −1)
39. サポートベクターマシンの最適化を例で考える（2/4） 40 <(=(!), =(%), =(:)) = @ &0! : =(&) − 1 2 @ &0! : @ 10! : =(&)=(1)B(&)B(1)4 & 24(1) ただし , = 8(!)$(!) − 8 " $ " + 8(/)$(/) = 38 ! − 8 " + 28(/) 48 ! − 28 " + 68(/) + =(!) − = % + =(:) = 0 および =(!), =(%), =(:) ≥ 0 の条件下で 以下の関数F を最⼤化したい
40. サポートベクターマシンの最適化を例で考える（3/4） 41 =(!) − = % + =(:) = 0 および =(!), =(%), =(:) ≥ 0 の条件下で 以下の関数F を最⼤化したい + = − 25 2 = ! % − 5 2 =(%) % − 20 =(:) % +11=(!)=(%) + 14= % = : − 30= : = ! − = ! + = % − =(:) < = ! , = % , = :
41. 微分などを駆使し，各変数についてFを最⼤化すればよい サポートベクターマシンの最適化を例で考える（4/4） 42 =(!) − = % + =(:) = 0 および =(!), =(%), =(:) ≥ 0 の条件下で 以下の関数F を最⼤化したい = − 25 2 = ! % − 5 2 =(%) % − 20 =(:) % +11=(!)=(%) + 14= % = : − 30= : = ! − = ! + = % − =(:) < = ! , = % , = : 9(: ! ) = … : ! " + … :(!) + … 変数1つに着⽬すれば…単なる2次関数!! ゼロでない λ に紐付いたデータがサポートベクター いわゆる 2次計画問題！
42. 理想世界でのサポートベクターマシン X1 0 Xn 1 , サポートベクター サポートベクター マージンの外側でデータの分布がキレイに分かれる !(#) = 0 この領域には データはない 43
43. サポートベクターマシンを使う現実的な状況 X1 0 Xn ノイズ1 ノイズ2 ノイズ3 学習で使うデータにノイズが混入する 44
44. サポートベクターマシンを使う現実的な状況 X1 0 Xn ノイズ1 ノイズ2 ノイズ3 <! <- <" 学習で使うデータにノイズが混入する ノイズを考慮してサポートベクターマシンを修正したい… 45
45. サポートベクターマシン with ハードマージン の最適化問題 点 ! について y(") = 1 の場合，% ' " ≥ 1 y(") = −1の場合，% ' " ≤ −1 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmin ; - $ 2 46
46. サポートベクターマシン with ソフトマージン の最適化問題 点 ! について y(") = 1 の場合，% ' " ≥ 1 − ," y(") = −1の場合，% ' " ≤ −(1 − ,") 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmin ; - $ 2 + 8 9 9I# J :9 反対側に⾏っても 認めてあげる (; ≥ 0) 反対側に⾏った分は ペナルティを与える 47
47. サポートベクターマシン with ソフトマージン に関する最適化問題の最終形 48 <(=(!), … , =(#)) = @ &0! # =(&) − 1 2 @ &0! # @ 10! # =(&)=(1)B(&)B(1)4 & 24(1) ∑ 123 4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で を最⼤化する " 1 を⾒つける(ただし ; = ∑&0! # =(&)B(&)4(&) , ラグランジュの未定乗数法 (. = 1, … , 7) ∀., ? = 8 ' + @ ' , @ ' A ' = 0)
48. Hands-on タイム 以下のURLにアクセスして， サポートベクターマシンを体験してみましょう https://mlnote.hontolab.org/ 49
49. 2 「トリック」を使う 非線形SVM 50
50. 線形分離不可能な問題 51 X 0 Y どうやっても1つの直線で分離できないデータ分布がある 線 形 分 離 不 可 能
51. 線形分離不可能な問題の解決策 52 X 0 Y 0 X Y Z = X2+Y2 複数の直線（超平面）を 組み合わせる 高次元化された空間で 分離超平面を見つける
52. データの⾼次元化の例 53 ! = ($! , $" ) !# = (1, 2$! , 2$" , 2$! $" , $! ", $" ") : 2次の多項式に写像（変換） ;(.) 線形分離不能なデータも 高次元化すればSVMで分類しやすくなる
53. ⾼次元化対応のサポートベクターマシンの最適化問題（1/2） 点 ! について y(&) = 1 の場合，- .(" & ) ≥ 1 − 0& y(&) = −1の場合，- .(" & ) ≤ −(1 − 0&) 目標1: 以下を満たす !(#) を見つけたい 目標2: !(#) のマージンを最大化させたい ⟹ argmin ! ( " 2 + + , #$% & -# ⾼次元化関数 をかます X 0 Y 0 X Y Z マージン 最⼤化 ⾼次元空間 に B で写像 54
54. ⾼次元化対応のサポートベクターマシンの最適化問題（2/2） 55 <(=(!), … , =(#)) = @ &0! # =(&) − 1 2 @ &,10! # =(&)=(1)B(&)B(1)K(4 & )!K(4(1)) ∑ 123 4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で を最⼤化する " 1 を⾒つける(ただし ; = ∑&0! # =(&)B(&)4(&) , ∀., ? = 8 ' + @ ' , @ ' A ' = 0) ⾼次元化された ベクトルの内積
55. ⾼次元空間の内積計算は⼤変 56 . = ("# , "$ ) ? = (%# , %$ ) ;L . = 1, 2"# , 2"$ , 2"# "$ , "# $, "$ $ ;L (?) = (1, 2%# , 2%$ , 2%# %$ , %# $, %$ $) : 2次の多項式に写像（変換） ;L (.) 内積計算 ;L . &;L ? = 1 + 2(! =! + 2(" =" + 2(! (" =! =" + (! "=! " + (" "=" " 2次元ベクトルでも1ペアの内積計算でのかけ算回数が11回に… これではSVMの学習の 計算コストが膨大に…
56. カーネルトリック 57 . = "# , "$ , ? = (%# , %$ ) !! ", $ = 1 + "" ( $ # = 1 + )$ *$ + )# *# # = 1 + 2%! 4! + 2%% 4% + 2%! %% 4! 4% + %! %4! % + %% %4% % = +! " "+! $ かけ算回数 = 2 + 1 回 式展開 が与えられたとき カーネル関数を使えば，明示的に 高次元変換しなくても効率よく内積を計算できる 多項式変換したベクトルの内積と同じに!!
57. 最適化⽅法は線形SVMと全く同じ（記号が変わっただけ） カーネルトリックを使った⾮線形SVMの最適化問題 58 <(=(!), … , =(#)) = @ &0! # =(&) − 1 2 @ &,10! # =(&)=(1)B(&)B(1)K> (4 & )!K> (4(1)) ∑ 123 4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で を最⼤化する " 1 を⾒つける(ただし ; = ∑&0! # =(&)B(&)4(&) , ∀., ? = 8 ' + @ ' , @ ' A ' = 0) 多項式カーネルで計算簡略化 = @ &0! # =(&) − 1 2 @ &,10! # =(&)=(1)B(&)B(1)"> (4 & , 4(1))
58. 代表的なカーネル関数 for SVM 59 A(., ?) = & + .& B ? M A(., ?) = C N 4NO $ $P$ 多項式カーネル 動径基底カーネル ・⼊⼒ベクトルの成分の組合せを 成分とする⾼次元ベクトルを想定 ・⽂書分類タスクでよく⽤いられる （パラメータd=2） ・無限次元空間にベクトルを射影 ・最もよく⽤いられるカーネル． 分布の特徴が未知の時に使う ・ガウスカーネルと呼ばれることも Radial Basis Function 画像出典: https://scikit-learn.org/stable/auto_examples/svm/plot_iris_svc.html
59. サポートベクターマシンの⻑所・短所 60 • ⾼次元空間でも汎化性能が⾼い • 次元数に対して学習データ数が 少なくても性能を発揮 • 計算量が多い（DNNほどではない） • データ数に対して次元数がかなり ⼤きいと，過学習が起きる • パラメータが少ない（DNNよりは） ※ DNN = Deep Neural Network
60. Hands-on タイム 以下のURLにアクセスして， 非線形SVMを体験してみましょう https://mlnote.hontolab.org/ 61
61. 今後の予定 62 回 実施⽇ トピック 1 04/14 ガイダンス 2 04/21 pandas⼊⾨ 3 04/28 決定⽊からはじめる機械学習 4 05/12 クラスタリング1：k-means & 階層的クラスタリング 5 05/19 クラスタリング2：密度ベースクラスタリング 6 05/26 分類1：K近傍法 & 教師あり機械学習のお作法 7 06/02 分類2：サポートベクターマシン 8 06/09 分類3：ニューラルネットワーク⼊⾨