フリーソフトでつくる音声認識システム(第2版) 第6章

6. 限界は破れるか（１） － サポートベクトルマシン － 𝛟 もとの次元で線形分離不可能なデータ 線形分離可能性の⾼い⾼次元へ 6.1 識別面は見つかったけれど 6.2 サポートベクトルマシンの学習アルゴリズム 6.3 線形分離可能にしてしまう 荒木雅弘: 『フリーソフトでつくる 音声認識システム（第2版）』（森北 出版，2017年） スライドとJupyter notebook サポートページ

• https://www.morikita.co.jp/books/mid/084712
• https://masahiroaraki.github.io/SpeechRecognition/
• https://github.com/MasahiroAraki/SpeechRecognition

6.1 識別面は見つかったけれど パーセプトロンの学習規則の2つの限界 1. 学習データが線形分離可能ならば識別面が見つかるが、信頼できる識別面とは限らない 2. 学習データが線形分離不可能である場合は、学習が停止しない 限界1について（学習データは線形分離可能と仮定） パーセプトロンの学習規則は全学習データが識別可能となった段階で停止するので、どの 識別面が見つかるかわからない 未知データに 強そう 未知データに 弱そう

6.2 サポートベクトルマシンの学習アルゴリズム 6.2.1 サポートベクトル 線形サポートベクトルマシン(SVM) : マージン最大となる線形識別面を求める マージン : 識別面と最も近いデータ（サポートベクトル）との距離 マージン サポート ベクトル (a) マージンの⼩さい識別⾯ (b) マージンの⼤きい識別⾯

6.2.2 マージンを最大にする (1/4) マージン最大化問題の定式化 {(xi , yi )} i = 1, … , N 線形識別面の式 : w T x + w0 = 0 学習データ : ​ yi = 1 or − 1 ​ ​ ​ 係数に関する制約の導入（係数を定数倍しても平面は不変） : mini ∣wT xi + w0 ∣ = 1 ​ ​ ​ 最大化の対象 : データと識別面との距離 (Dist) の最小値（＝マージン） ∣wT xi + w0 ∣ 1 = min Dist(xi ) = min i i ∥w∥ ∥w∥ ​ ​ ​ ​ ​ ​ 参考）2次元平面での点と直線の距離の公式 r= ∣ax + by + c∣ a 2 + b2 ​ ​ ​

6.2.2 マージンを最大にする (2/4) 目的関数の置き換え : min 12 ∥w∥2 ​ 最大化対象の分母の最小化 最小化問題として解きやすいように、2乗しておく 制約条件 : yi (w T xi ​ ​ + w0 ) ≥ 1 i = 1, … , n ​ 解法 : ラグランジュの未定乗数法 例題（2変数、等式制約）: min f (x, y) s.t. g(x, y) = 0 L(x, y, α) = f (x, y) − αg(x, y) ラグランジュ係数の制約 α ≥ 0 x, y, α で偏微分して0になる値が目的関数の極値 ラグランジュ関数 : ∂L ∂L ∂L = = =0 ∂x ∂y ∂α ​ ​ ​

6.2.2 マージンを最大にする (3/4) より解きやすい問題への変換 L(α) の最小化は αi ≥ 0 についての2次計画問題なので極値をとる α が容易に求まる ​ n 1 L(w, w0 , α) = ∥w∥2 − ∑ αi (yi (wT xi + w0 ) − 1) 2 i=1 ​ ∂L =0 ∂w0 ​ ​ ​ ∂L =0 ∂w ​ ​ ​ ​ ​ ​ ​ n ⇒ ∑ αi y i = 0 ​ ​ ​ i=1 n ​ ⇒ w = ∑ α i y i xi ​ ​ ​ i=1 n n 1 → L(α) = ∑ αi αj yi yj xTi xj − ∑ αi 2 i,j=1 i=1 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

6.2.2 マージンを最大にする (4/4) 定数項 w0 は各クラスのサポートベクトルから求める ​ wT x+ + w0 = 1, wT x− + w0 = −1 1 T → w0 = − (w x+ + wT x− ) 2 ​ ​ ​ ​ ​ ​ ​ ​ ​ マージンが最大の識別関数 サポートベクトルに対応する αi のみが正の値、残りは 0 ​ マージン最大の識別面の決定にはサポートベクトルしか関与しない g(x) = wT x + w0 ​ n ​ = ∑ αi yi xTi x + w0 ​ i=1 ​ ​ ​ ​ ​ ​

（補足） 演習問題6.1 少数のデータが線形分離可能性を満たさない場合 i 番目のデータが制約を破っている度合いを表す変数 ξi (≥ 0) を導入し，制約式を変更 ​ yi (wT xi + w0 ) ≥ 1 − ξi (i = 1, … , n) ​ ​ ​ 目的関数に ξi の総和に重みを表す ​ C を掛けて加える n 1 min ∥w∥2 + C ∑ ξi 2 ​ ​ i=1 解には 0 ≤ αi ≤ C という制約が加わるだけ ​ ​

6.3 線形分離可能にしてしまう 6.3.1 高次元空間への写像 限界2の問題（線形分離不可能なデータ）への対処 クラスが複雑に入り交じった学習データを、線形分離可能性が高まる高次元空間に写像 ただし、もとの空間でのデータ間の近接関係は保持する 𝛟 もとの次元で線形分離不可能なデータ 線形分離可能性の⾼い⾼次元へ

6.3.2 カーネル法 (1/2) 高次元空間への変換関数： 2つのベクトル ϕ(x) x, x′ の近さを表すカーネル関数 K(x, x′ ) を導入 元の空間での近さを変換後の空間の内積に対応させる K(x, x′ ) = ϕ(x)T ϕ(x′ ) カーネル関数の例 K(x, x′ ) = (xT x′ + r)d ガウシアンカーネル K(x, x′ ) = exp(−γ∥x − x′ ∥2 ) 多項式カーネル これらのような、正定値性とよばれる性質を満たすカーネルであれば、対応する変換関数が存在す ることが数学的に保証されている

6.3.2 カーネル法 (2/2) g(x) = wT ϕ(x) + w0 n サポートベクトルマシンを適用し、w = ∑i=1 αi yi ϕ(xi ) を代入 高次元空間での識別関数 ： ​ ​ ​ ​ n g(x) = ∑ αi yi ϕ(xi )T ϕ(x) + w0 ​ ​ ​ ​ ​ i=1 n ​ ​ = ∑ αi y i K ( x i , x ) + w 0 ​ ​ ​ ​ ​ i=1 変換関数が不要になった（＝カーネルトリック） 変換後の空間での線形識別面は、もとの空間での複雑な非線形識別面に対応

6.3.3 具体的なカーネル関数 d = 2, r = 1）の展開 多項式カーネル（特徴が2次元ベクトルで加算項が1, K(x, x′ ) = (xT x′ + 1)2 = (x1 x′1 + x2 x′2 + 1)2 ​ ​ ​ ​ ​ = x21 x′1 2 + x2 2 x′2 2 + 2x1 x2 x′1 x′2 + 2x1 x′1 + 2x2 x′2 + 1 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ′2 ′ ′ ′ ′ = (x21 , x22 , 2x1 x2 , 2x1 , 2x2 , 1) ⋅ (x′2 1 , x2 , 2x1 x2 , 2x1 , 2x2 , 1) ​ ​ ​ ​ 6次元空間に写像されている ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

（補足） 演習問題6.2 2クラス分類器を用いた多クラス分類 (1/2) one-versus-rest法 各クラスについて、そのクラスに属するか、他のクラスかを識別する SVM を作る 2つ以上のクラスに属すると判定された場合は、識別面からの距離が大きいものに分類

2クラス分類器を用いた多クラス分類 (2/2) ペアワイズ法 クラス対ごとに SVM を作る 判定は多数決を取る

まとめ サポートベクトルマシンの特徴 学習は2次計画問題なので、必ず最適解が見つかる 求めるパラメータ αi の大半が 0 となるので，この状況に特化した最適化アルゴリズム（た ​ とえば SMO）で高速化が可能 カーネル関数を用いて、特徴ベクトルを線形分離可能性が高い高次元空間に非線形写像す ることができる 2つのデータ間にカーネル関数さえ定義できれば，元のデータはグラフや木構造のような特徴ベク トルの形で表現されていないものでもよい 2クラスの分類器なので、多クラスの分類には工夫が必要 Jupyter notebook

• https://github.com/MasahiroAraki/SpeechRecognition/blob/master/Python/chap06.ipynb