サポートベクターマシン(厂痴惭)の数学をみんなに説明したいだけの会
?
17 likes?81,347 views
SVMの基本的な数学を説明しています． ブログにもまとめてますので，どうぞ https://kenyu-life.com/2019/02/11/support_vector_machine/ 動画解説してます 「https://www.youtube.com/watch?v=TNOC0vyIL-g」
サポートベクターマシン(厂痴惭)の数学をみんなに説明したいだけの会
- 1. サポートベクターマシン(SVM)の 数学をみんなに説明したいだけの会 上原賢祐 @kenyu0501_ 山口大学大学院 博士課程/ 学術研究員/ 最近のトピック? 人工知能の検定(g検定)に合格 したので，AIに関するマウント がとれるようになりました． ゼミ第2回 20190516 撮影，ソーシャル，自己使用，全部OK
- 2. 今回のゼミの目的とコンテンツ ?機械学習の大枠をざっくりと理解すること ???10% ?SVMの数学的背景を理解すること ???80% ?SVMを実際に使用できるようになること ???10% ?機械学習とは！？ ?機械学習の位置付け ?機械学習のアルゴリズム(教師あり VS なし) ?SVMは教師あり学習 ?デモンストレーション：身近なSVM ?ベクトルの復習 ?線形学習マシンの数学：ハードマージン→ソフトマージンへ? ?主問題 VS 双対問題：線形から非線形SVMへの拡張 ?特徴空間への写像，カーネルの導入 目的 めっちゃ数学！ 内容
- 4. 人工知能からみた機械学習の位置付け 振る舞いが決められているもの人工知能の4つのレベル分け Level 1 Level 2 Level 3 Level 4 シンプルな制御プログラム 古典的な人工知能 機械学習 ディープラーニング On-O? 制御 PID制御 (Proportional-Integral-Di?erential) ある特定の環境に限定した場合のみ， 複雑な動きができる 入出力の関係を学習したもの． 入力に特徴量という人間が 設定する概念がある． 特徴量自体を自動で学習できる あらゆる条件に対応した動作や制御系の 組み合わせ サポートベクターマシン 決定木 などなど ニューラルネットワーク RNN, CNNなど
- 5. 機械学習のアルゴリズム：教師あり，教師なし，半教師，強化学習 機械学習 教師あり学習 教師なし学習 半教師あり学習 強化学習 ラベル付きデータを用いて入出力間の 関数を作る ラベルなしのデータから隠れた構造を 記述する関数を作る ラベル付きと無しの両方のデータを用 いて入出力間の関数を作る ある環境内で行動の価値を最大化する ような動作を決める関数を作る ?回帰 (線形回帰，ベイズ回帰) ?分類 (SVM，決定木) ?クラスタリング (K-means法，混合正規分布モデル) ?情報圧縮 (PCA，特異値分解) ?分類 (半教師ありk近傍法グラフ， 半教師あり混合ガウスモデル) ?ゲーム，制御，推定 (Q-learning，Sarsa)
- 6. 機械学習のアルゴリズム：教師あり サポートベクターマシンSVM 古典的な制御 入力 プログラム コンピュータ 出力 入力 出力 コンピュータ プログラム 教師あり学習 機械学習 サポートベクターマシン 入出力データのパターンを コンピュータに探してもらう
- 7. SVMがはじめに使われた課題：手書き文字認識 アメリカ郵政サービス：手書き郵便番号を認識して，自動仕分けする課題 V. Vapnik, Statistical Learning Theory, Springer-Verlag (1995). 実装demoあり 手書き文字入力 数字出力機械学習の実行 SVM (NN etc.) 1. コールセンタ 2. 郵便物仕分け 3. 電話交換手 現在，機械に代替される と予想されている仕事 Best 3 「RaspberryPiではじめる機械学習」 を参考にしました 分類器 →内側の処理をざっと説明． →SVMにより分類器を作成して，実際に手書き 文字認識を行うことができるかどうかのテスト． デモンストレーションの内容
- 8. 4 3 2 7 6 015 8 9 0 0 5 13 9 1 0 0 0 0 13151015 5 0 0 3 15 2 0 11 8 0 0 4 12 0 0 8 8 0 0 5 8 0 0 9 8 0 0 4 11 0 1 12 7 0 0 2 14 5 1012 0 0 0 0 6 1310 0 0 0 SVMがはじめに使われた課題：手書き文字認識 拡大 7がちょっと異質だと思いますが， 世界的にはこの形態が主流 特徴量 (8 × 8ピクセル) 0:白 → 15:黒 特徴量を持ったベクトルをターゲット毎に 着色して分布を確認してみる 主成分分析pcaという次元を落とす手法（64→3次元へ） を使いますが，ここでは説明を省きます！ Principle Components Analysis 手書き数字(オープンアクセス) 43名分の手書き数字1797個 機械学習ライブラリScikit-learnより入手 各数字における 特徴量の分布のばらつき
- 11. ベクトルの復習：幾何学的表現から代数的表現へ r θ x y (r, θ)x1x x1x (x, y) 有向線分から座標系の成分へ 代数的概念だと ベクトルを使った 和差内積の演算が容易 地理座標系-wikipedia (https://ja.wikipedia.org/wiki/地理座標系) 各国も緯線と経線の 情報を持つベクトル 社会人のためのデータ分析入門 第5回 (https://amusement-japan.co.jp/article/detail/10000149/) マックとパチンコの 情報を持つベクトル (10万人あたり) こういったものも ベクトル
- 12. 特徴量 1 特徴量2 線形分離可能 K2 K1 特徴量 1特徴量2 K2 K1 線形分離不可能 ハードマージン ソフトマージン ハードマージンよりも賢明なSVMSVMの取っ掛かりに良い 線形学習マシンの数学：ハードマージン
- 13. 特徴量 1 特徴量2 サポートベクトル サポートベクトルマージン最大化 (矢印部の長さ) wT x + b = 0 K2 K1 直線より下にあるデータは クラス2に属する 直線より上にあるデータは クラス1に属する wT xi + b > 0wT xi wT xi + b < 0 xi ∈ K1 wT xi xi ∈ K2 となるデータxの集合 線形分離可能なデータ 分類境界である直線(超平面)の方程式をこのように定義する ラベル変数 ti を導入して，0より大きい形に! ti(wT xi + b) > 0wT xi i = 1,2,?, n w 幾何マージン というよ！ ?分類境界を決定する関数により分類器を定義する． ?データを完璧に分離する関数が存在するという仮定がある． ?サポートベクトルでない点は，分離直線(超平面)に全く影響を与えない． つまり，最適解に影響はない． ww b重み(n次元実数ベクトル) バイアス(スカラー) 線形学習マシンの数学：ハードマージン
- 14. 点と直線の距離 (2次元Ver) (x1, x2) d d = |w1x1 + w2x2 + b| w2 1 + w2 2 wT xi + b = 0wT xi 点と超平面の距離 (n次元Ver) (x1, x2, ?, xn) d = |w1x1 + w2x2 + ? + wnxn + b| w2 1 + w2 2 + ? + w2 n n次元かけないけど，? 3次元的に，，，wT xi + b = 0wT xi d = |wT x + b| ||w||w wT x 一般化する は，重みベクトルのノルム(長さ)を表す||w||w n次元データ 2次元平面の 点と直線の距離 高校数学だね 線形学習マシンの数学：ハードマージン
- 15. 特徴量 1 特徴量2 サポートベクトル サポートベクトル マージン最大化 (矢印部の長さ) wT x + b = 0 K2 K1 ２つのクラスを分ける超平面に最も近いデータ(サポートベクトル)への距離を考える wT x M = wT x+ + b ||w|| = ?(wT x? + b) ||w||w wT x x+ x? x x w wT x サポートベクトル サポートベクトル ti(wT xi + b) ||w|| ≥ MmaxM, w, bw (i = 1,2,?, n) wT xi w この最適化問題を解く ①サポートベクトル( or ) に対してマージン最大化する ②全てのベクトル が そのマージンよりも距離が長い この2つの条件を満たす xixix+x+ x?x? 線形学習マシンの数学：ハードマージン
- 16. ti(wT xi + b) ||w|| ≥ MmaxM, w, bw (i = 1,2,?, n) wT xi w この最適化問題を解く 関数出力として測定される関数マージンMが変化するので， 幾何マージンを最適化するためにも，関数マージンを1にする． その後，重みベクトルのノルムを最大化(最小化)する M = wT x+ + b ||w|| = ?(wT x? + b) ||w||w wT x w wT x サポートベクトル サポートベクトル wT x + b = 1w ここで，両辺をMで割る ti(wT xi + b) M||w|| ≥ 1 ti( ?wT xi + ?b) ≥ 1 ?w = w M||w|| ?b = b M||w|| 全てのデータに対して，この不等式がなりたつ wT xi w wT xi w w 簡単のためチルダで表しておく ?M = ti( ?wT xi + ?b) || ?w|| = 1 || ?w|| サポートベクトル( x+ や x- )においては， 以下の等号が成立する wT xi w w (目的関数) (制約条件) ti( ?wT xi + ?b) = 1wT xi 特にサポートベクトルでは等号が成立 線形学習マシンの数学：ハードマージン
- 17. max 1 || ?w|| , ?w, bw (i = 1,2,?, n)ti( ?wT xi + ?b) ≥ 1wT xi w min 1 2 ||w||2 , ti(wT xi + b) ≥ 1wT xi (i = 1,2,?, n) w, bw 最大化は，逆数をとって最小化するのと等価である 最大化 → 最小化問題 w (ノルムの二乗や1/2は計算を行いやすくするため！) (目的関数) (制約条件) 最適化問題の最適解を求めると， wT x + b = 1w ti( ?wT xi + ?b) = 1wT xi は通常いくつか現れる． これは，分類境界に最も近いベクトルであり，左図の破線上 の点に相当する 線形学習マシンの数学：ハードマージン
- 18. 特徴量 1 特徴量2 wT x + b = 0 線形分離可能 K2 K1 特徴量 1特徴量2 K2 K1 線形分離不可能 wT x + b = 0 ハードマージン ソフトマージン ハードマージンよりも賢明なSVM ハードマージンの持つ制約条件の緩和 SVMの取っ掛かりに良い 線形学習マシンの数学：ソフトマージン
- 19. K2 K1 線形分離不可能 wT x + b = 0 wT x + b = ? 1 wT x + b = 1 ti(wT xi + b) ≥ 1 ? ξiwT xi K1において分離する直線の 一番近いデータ(サポートベクトル) K2において一番近いデータ (サポートベクトル) w, bw 線形分離可能な場合(ハードマージン)は，これの最小化問題を解くことが必要だった min 1 2 ||w||2 , ti(wT xi + b) ≥ 1wT xi (i = 1,2,?, n)w 等号が成立する場合 マージン マージン内部に異なるデータが 入り込んでしまう スラッグ変数 ξ を導入して制約を弱める ξi = max { 0, M ? ti(wT xi + b) ||w|| } (スラッグ変数 ξ はmax関数) wT x w w x w x w x グ ザ イ 線形学習マシンの数学：ソフトマージン
- 20. ξi = max { 0, (1 ? 0.4 = 0.6) } ξi = max { 0, M ? ti(wT xi + b) ||w|| } wT x w K2 K1 具体例を考える wT x + b = 0 wT x + b = 1 マージン M 例えば，この入り込んだ データ(点)を考える ti(wT xi + b) ||w|| = 0.4直線と点の距離 マージン M = 1 ξi = 0.6 ti(wT xi + b) ≥ 1 ? ξi = 0.4wT xi この入り込んだデータ(点)に対しては，制約が小さくなる w x w x 上の具体例のように，マージンを超えてしまった点の存在を許可するためのもの これによって，分離不可能な場合も境界の推定を可能にしている 線形学習マシンの数学：ソフトマージン
- 21. ti(wT xi + b) ≥ 1wT xi (i = 1,2,?, n) ハードマージン min 1 2 ||w||2 w, bw w 目的関数 制約条件 ソフトマージン min { 1 2 ||w||2 + C n ∑ i=1 ξi}w, b, ξw w 目的関数 制約条件 ti(wT xi + b) ≥ 1 ? ξi,wT xi (i = 1,2,?, n) ξi ≥ 0 C > 0：正則化係数(ペナルティの度合い) 目的関数を最小化するためには，２項のバランスを上手く取らないといけない マージンを広げようとすると，C n ∑ i=1 ξi の部分( ξ の総和)が大きくなるため 1よりも小さくなるので， マージンを超えて異なるクラスに入るのを許す マージンを広げると，第一項は小さくなるが，第二項は大きくなっていく 線形学習マシンの数学：ソフトマージン
- 22. 正則化係数(ハイパーパラメータ)の探求 ソフトマージン 正則化係数の値によって，マージンにどのような影響があるのか確認する min { 1 2 ||w||2 + C n ∑ i=1 ξi}w, b, ξw w目的関数 C > 0：正則化係数(ペナルティの度合い) C = 100 C = 0.1 図の引用，サポートベクトルマシン， 竹内一郎，鳥山昌幸，講談社 (2015) ? Question どっちがC=100？C=0.1？ ?目的関数最小化をする際，Cが大きいと，ξを抑制する力が強くなる． (誤ったデータがマージンを超えて侵入することがなくなる) ?Cが小さいと，データがマージンを超えてしまうことを許すので，マージンを広く取れる． SVMはマージン最大化をしたいのだけど，，，， 2項のバランスを考える必要がある C → ∞では「ハードマージン」になる．
- 23. 主問題 VS 双対問題：線形から非線形SVMへの拡張 ソフトマージン min { 1 2 ||w||2 + C n ∑ i=1 ξi}w, b, ξw w 目的関数 制約条件 ti(wT xi + b) ≥ 1 ? ξi,wT xi (i = 1,2,?, n) ξi ≥ 0 主問題：これまで定式化してきた最適化問題のこと SVMを計算する場合は，主問題は解かず，双対問題を解く 双対問題：主問題を別の解き易い形に変形させた問題 分類境界の非線形化を考える上で，双対問題の形式が有用である ? ? ? ? ? ? ? ? ? １．変数を減らすことができる ２．カーネル関数が導入できる 制約条件のない最適化問題への変形をすること
- 25. 目的関数 f(x) を最小にする点を，n 個の不等式制約 gi(x) ≦ 0 のもとで求める ラグランジュの未定乗数法 ラグランジュ関数 主変数 双対変数 (ラグランジュ乗数) x x (i = 1,2,?, n) xL(x, α) = f(x) + n ∑ i=1 αigi(x) ?L(x, α) ?x = ?f(x) ?x + n ∑ i=1 αi ?gi(x) ?x ?L(x, α) ?αi = gi(x) ≤ 0 αi ≥ 0 αigi(x) = 0 1. 2. 3. 4. x x x x xx x x x 主変数に関する変微分 双対変数に関する変微分 ラグランジュ乗数は常に正 制約条件とラグランジュ乗数の積は0 以下の4つを解くことによって求まる 非線形SVMへの拡張：ラグランジュの未定乗数法
- 26. (1, 1, 1) 0 x y z【例題】中心(1, 1, 1 ), 半径1の球表面に おいて，原点(0, 0, 0)から距離が 最小となる座標を求めよ この問題をラグランジュの 未定乗数を使って解くよ 最小f(x, y, z) = x2 + y2 + z2 目的関数 制約条件 g(x, y, z) = (x ? 1)2 + (y ? 1)2 + (z ? 1)2 ? 1 = 0 ラグランジュ関数 L(x, y, z, α) = x2 + y2 + z2 ? α{(x ? 1)2 + (y ? 1)2 + (z ? 1)2 ? 1} ? 問題引用，工学のための最適化手法入門， 天谷賢治，数理工学社 (2008). 非線形SVMへの拡張：ラグランジュの未定乗数法
- 27. ?L(x, y, z, α) ?x = 2x ? 2α(x ? 1) ?L(x, y, z, α) ?y = 2y ? 2α(y ? 1) ?L(x, y, z, α) ?z = 2z ? 2α(z ? 1) ?L(x, y, z, α) ?α = ? {(x ? 1)2 + (y ? 1)2 + (z ? 1)2 ? 1} (x, y, z, α) = ( 1 ± 1 3 , 1 ± 1 3 , 1 ± 1 3 , 1 ± 3 ) 上の4本の連立方程式を解くと， が得られる．f は符号が + のときに，最大値を，- のときに最小値をとる．? よって，原点からの距離が最小となる座標は， ( 1 ? 1 3 , 1 ? 1 3 , 1 ? 1 3 ) 非線形SVMへの拡張：ラグランジュの未定乗数法
- 28. min { 1 2 ||w||2 + C n ∑ i=1 ξi}w, b, ξw w 目的関数 制約条件 ti(wT xi + b) ≥ 1 ? ξi,wT xi (i = 1,2,?, n)ξi ≥ 0 ラグランジュの未定乗数法を使ってSVMの主問題を双対問題へと変形する L(w, b, ξ, α, β) = 1 2 ||w||2 + C n ∑ i=1 ξi ? n ∑ i=1 αi{ti(wT xi + b) ? 1 + ξi} ? n ∑ i=1 βiξiwT xiww βα ラグランジュ乗数 ラグランジュ関数 1. 2. 3. 主変数 w に関する変微分 ?L(w, b, ξ, α, β) ?w = w ? n ∑ i=1 αitixi = 0 ?L(w, b, ξ, α, β) ?b = ? n ∑ i=1 αiti = 0 ?L(w, b, ξ, α, β) ?ξ = C ? αi ? βi = 0 主変数 b に関する変微分 主変数 ξ に関する変微分 w w w w w xi 主変数( w, b, ξ )に関する偏微分を解く w = n ∑ i=1 αitixiw xi n ∑ i=1 αiti = 0 C = αi + βi ラグランジュ関数へ代入 これらの制約がどの程度重要であるかを 定量化した乗数になる 非線形SVMへの拡張：ラグランジュの未定乗数法
- 29. L(w, b, ξ, α, β) = 1 2 ||w||2 + C n ∑ i=1 ξi ? n ∑ i=1 αi{ti(wT xi + b) ? 1 + ξi} ? n ∑ i=1 βiξiwT xiww max { ?L(α) = n ∑ i=1 αi ? 1 2 n ∑ i=1 n ∑ i=j αiαjtitjxT i xj} xT i xj 3つの条件式をラグランジュ関数へ代入し，整理することによって， α のみの式に変形できる サポートベクターマシンの双対問題は，上の関数によって表現される ラグランジュ関数 ここで，bの値は双対問題に現れないので，b は主問題の制約を利用して導出する必要がある b = ? maxti=?1 (wxi) + minti=1 (wxi) 2 wxi wxi 非線形SVMへの拡張：ラグランジュの未定乗数法
- 32. 入力空間 特徴空間 x1 x2 x1 x2 x1x2 x = (x1, x2)x ?(x) = (x1, x2, x1x2)x 写像 ?(x) = (x1, x2, x2 1, x2 2, x1x2)x 他にもいろんな方法があるよ 次元拡張 特徴空間への写像，カーネルの導入
- 33. L(w, b, ξ, α, β) = 1 2 ||w||2 + C n ∑ i=1 ξi ? n ∑ i=1 αi{ti(wT xi + b) ? 1 + ξi} ? n ∑ i=1 βiξiwT xiww max { ?L(α) = n ∑ i=1 αi ? 1 2 n ∑ i=1 n ∑ i=j αiαjtitjxT i xj} xT i xj ラグランジュ関数 max { ?L(α) = n ∑ i=1 αi ? 1 2 n ∑ i=1 n ∑ i=j αiαjtitj?(x)T i ?(x)j} ?(x)T i ?(x)j 特徴空間上への拡張 ?(x) = (?1(x), ?2(x), ?, ?r(x))x x x x 内積のみのお話 問題：次元拡張により，内積の計算量が膨大 ?(x)T i ?(x)j?(x)T i ?(x)j 特徴空間の次元数 r は，もともとの入力空間の n よりもはるかに大きい そのため，内積 の計算がとても大変 ?(x)T i ?(x)jK(xi, xj) = ?(x)T i ?(x)jxi, xj カーネル関数 特徴ベクトルの内積をカーネル関数で置き換える (言い換えると，内積の計算さえできればおk) 特徴空間への写像，カーネルの導入
- 34. ?(x) = ?(x1, x2) = (x2 1, 2x1x2, x2 2)x x, yx y二つのベクトル を考える ?(x) = ?(x1, x2) = (x2 1, 2x1x2, x2 2)x ?(y) = ?(y1, y2) = (y2 1, 2y1y2, y2 2)y これら二つの内積を考える ?(x)T ?(y)x y = (x2 1, 2x1x2, x2 2)T (y2 1, 2y1y2, y2 2) = x2 1 y2 1 + 2x1x2y1y2 + x2 2 y2 2 = (x1y1 ? x2y2)2 = ((x1, x2)T (y1, y2))2 = (xT y)2x y 変換後のベクトルの内積は， 元のベクトルの内積の2乗に等しい c = 0, d = 2とした時の多項式カーネル 特徴空間への写像，カーネルの導入 特徴空間での内積がどのような形に落ち着くか，簡単な例で考えてみる こういった形が，カーネル関数として成り立ちそうだぞ．．．
- 35. max { ?L(α) = n ∑ i=1 αi ? 1 2 n ∑ i=1 n ∑ i=j αiαjtitj?(x)T i ?(x)j} ?(x)T i ?(x)j 目的関数 ?(x)T i ?(x)jK(xi, xj) = ?(x)T i ?(x)jxi, xj カーネル関数 ある特定の性質を満たすと これが適応できる！ カーネル関数を用いる事で，最適化をする際に，明示的に φ を計算しなくても良い 特徴空間への写像，カーネルの導入 「マーサーの定理」を満足できる関数が，カーネル関数として適用する事ができる カーネル関数の例 ?多項式カーネル K(xi, xj) = (xT i xj + c)dxi, xj xT i xj ?ガウスカーネル K(xi, xj) = exp { ? ||xi ? xj ||2 2σ2 } ?シグモイドカーネル K(xi, xj) = tanh(bxT i xj + c)xi, xj xi, xj xi xj xT i xj
- 36. カーネル関数の例 ?多項式カーネル K(xi, xj) = (xT i xj + c)dxi, xj xT i xj ?ガウスカーネル K(xi, xj) = exp { ? ||xi ? xj ||2 2σ2 } ?シグモイドカーネル K(xi, xj) = tanh(bxT i xj + c)xi, xj xi, xj xi xj xT i xj 各カーネルの内側のハイパーパラメータ c や d，σ などは別途決定しなければならない． これらの設定は，ヒューリスティックであるし，いくつかの求め方もある． (必ずしも正しい答えを導けるわけではないが、ある程度のレベルで正解に近い解を得ることができる) σ ：別々のクラスに分類された2点間の距離の最も小さいものを選択する． 信ぴょう性のある基準がない場合，交差検証や検証集合などを用いて設定する たとえば 結果として満足のいく性能を達成するまで，様々なパラメータをいじくりまわす？ しかし，多くの場合，SVMを使用する場合，素朴な設定，実装で，満足できる結果を返す．? 逆に，これらの経験は，SVMがうまく適応できる領域が完全に開拓されていないことを暗に示す． “サポートベクターマシン入門”，Nello C., John S. T., 大北剛，共立出版 (2005), p.196. 特徴空間への写像，カーネルの導入