フリーソフトではじめる機械学習入門 (第2版) 第7章

7. サポートベクトルマシン 線形分離不可能なデータ 線形分離可能性の⾼い⾼次元へ写像 7.1 サポートベクトルマシンとは 7.2 ソフトマージンによる誤識別データの吸収 7.3 カーネル関数を用いたSVM 7.4 文書分類問題へのSVMの適用 7.5 ハイパーパラメータの調整 荒木雅弘: 『フリーソフトではじめる機械 学習入門（第2版）』 （森北出版，2018年） スライドとJupyter notebook サポートページ

• https://masahiroaraki.github.io/ja/
• https://www.morikita.co.jp/books/mid/085212
• https://masahiroaraki.github.io/MachineLearning/
• https://github.com/MasahiroAraki/MachineLearning/

第7章～第10章 教師あり学習の発展的手法 識別と回帰のいずれにも適用可能 線形モデルでは高い性能が得られないデータに適する 機械学習 教師あり学習 教師なし学習 中間的学習 識別 回帰 サポートベクトルマシン ニューラルネットワーク（深層学習） アンサンブル学習

7. サポートベクトルマシン 本章の説明手順 1. 線形分離可能なデータに対して、なるべく学習データに特化しすぎない識別面を求める 2. 線形分離不可能なデータに対して、誤識別に対するペナルティを設定することで、1. の手法 を改良する 3. さらに複雑なデータに対して、学習データを高次元の空間に写して、2. の手法を適用する 4. 3.の手法に対して、最適なハイパーパラメータを求める

7.1 サポートベクトルマシンとは (1/6) 汎化性能を高めるために、マージンを最大化する識別面を求める マージン : 識別面と最も近いデータとの距離 学習データは線形分離可能とする サポート ベクトル (a) マージンの⼩さい識別⾯ マージン (b) マージンの⼤きい識別⾯

7.1 サポートベクトルマシンとは (2/6) マージン最大化のための定式化 学習データ: x ∈ Rd , y ∈ {−1, 1} {(xi , yi )}, i = 1, … , N ​ ​ 識別面の式（超平面） w T x + w0 = 0 ​ 識別面の式に制約を導入（係数を定数倍しても超平面は不変） min ∣wT xi + w0 ∣ = 1 ​ i ​ ​

7.1 サポートベクトルマシンとは (3/6) 学習対象の設定 学習データと識別面との最小距離（マージン） cf) 点と直線の距離の公式 ∣wT xi + w0 ∣ 1 = min Dist(xi ) = min i i ∥w∥ ∥w∥ ​ ​ ​ ​ ​ ​ 目的関数：マージン最大化を、逆数の2乗の最小化と置き換える 1 min ∥w∥2 2 ​ 制約条件 : w で定まる超平面で正しく識別が行えること yi (wT xi + w0 ) ≥ 1 ​ ​ ​ i = 1, … , N ​

7.1 サポートベクトルマシンとは (4/6) 最適化問題の解法 : ラグランジュの未定乗数法 例題（2変数、等式制約） min f (x, y) s.t. g(x, y) = 0 ラグランジュ関数の導入 : L(x, y, α) = f (x, y) + αg(x, y) α≥0 L を x, y, α で偏微分して 0 になる値が f の極値 ラグランジュ係数の制約 : 変数3つに対して制約式が3つなので、変数について解ける ∂L ∂L ∂L = = =0 ∂x ∂y ∂α ​ ​ ​

7.1 サポートベクトルマシンとは (5/6) より解きやすい問題への変換 N 1 L(w, w0 , α) = ∥w∥2 − ∑ αi (yi (wT xi + w0 ) − 1) 2 i=1 ​ ​ ​ N ​ ​ ​ ​ ​ N ∂L = 0 ⇒ ∑ αi yi = 0, ∂w0 i=1 ​ ​ ∂L = 0 ⇒ w = ∑ α i y i xi ∂w i=1 ​ ​ ​ ​ N ​ ​ N 1 L(α) = ∑ αi αj yi yj xTi xj − ∑ αi 2 i,j=1 i=1 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ αi ≥ 0 での2次計画問題なので、容易に極値となる α を求めるこ とができ、そこから w が求まる 最後の式の最小化は ​

7.1 サポートベクトルマシンとは (6/6) 定数項の計算 各クラスのサポートベクトルを引数とした識別関数の値の絶対値が1であることから求める 1 wT x+ + w0 = −(wT x− + w0 ) ⇔ w0 = − (wT x+ + wT x− ) 2 ​ ​ ​ ​ ​ ​ ​ ​ マージンが最大の識別関数 N g(x) = wT x + w0 = ∑ αi yi xT xi + w0 ​ ​ ​ ​ i=1 サポートベクトル xi に対応する αi のみが0以上、残りは0 ​ ​ マージン最大の識別面の決定にはサポートベクトルしか関与しない ​ ​

7.2 ソフトマージンによる誤識別データの吸収 (1/3) 少量のデータが線形分離性を妨げている場合 誤差を考える

7.2 ソフトマージンによる誤識別データの吸収 (2/3) スラック変数 ξi の導入 ​ y i ( w T x i + w 0 ) ≥ 1 − ξi ​ ​ ​ ​ i = 1, … , N ξi = 0 : マージンの外側、0 < ξi ≤ 1 : マージンと識別面の間、1 < ξi : 誤り ​ ​ ​ 最小化問題の修正: スラック変数も小さい方がよい N 1 min( ∥w∥2 + C ∑ ξi ) 2 i=1 ​ 計算結果 αi の2次計画問題に 0 ≤ αi ≤ C が加わるだけ ​ ​ ​ ​

7.2 ソフトマージンによる誤識別データの吸収 (3/3) C : エラー事例に対するペナルティの大きさ 大きな値 ： 誤識別データの影響が大きい マージンが狭くても誤識別をなるべく減らすようにする 小さな値 ： 誤識別データの影響が小さい 多少の誤識別があっても、なるべくマージンを広くする

7.3 カーネル関数を用いたSVM (1/7) クラスが複雑に入り交じった学習データ 特徴ベクトルを高次元空間に写像して線形分離可能性を高める ただし、もとの空間でのデータ間の近接関係は保持するように写像する 線形分離不可能なデータ 線形分離可能性の⾼い⾼次元へ写像

7.3 カーネル関数を用いたSVM (2/7) 高次元への非線形変換関数 ϕ(x) を設定する カーネル関数 : 2つの点の近さを表す k(x, x′ ) = ϕ(x)T ϕ(x′ ) もとの空間での2つの点の近さを、変換後の空間での2つのベクトルの内積に対応させる x と x′ が近ければ k(x, x′ ) は大きい値 カーネル関数が正定値性を満たすとき、このような非線形変換が存在することが保証され ている

7.3 カーネル関数を用いたSVM (3/7) 正定値カーネル関数の例（scikit-learn SVCの定義） 線形(linear) : k(x, x′ ) = xT x′ 高次元に写像せず、もとの特徴空間でマージン最大の超平面を求めるときのカーネル関数 多項式(poly) : k(x, x′ ) = (xT x′ + r)d d 項の相関を加えるので d が大きいほど複雑な識別面。r はたいてい1 ガウシアン(rbf) : k(x, x′ ) = exp(−γ∥x − x′ ∥2 ) γ が大きいほど近くのデータしか影響しないので複雑な識別面 シグモイド(sigmoid) : k(x, x′ ) = tanh(xT x′ + r) ベクトルの近さに対して閾値関数的な振る舞い

7.3 カーネル関数を用いたSVM (4/7) 線形カーネルの解釈 θ が 0 に近い（＝ベクトルとして似ている）ほど大きな値 K(x, x′ ) = xT x′ = ∥x∥ ⋅ ∥x′ ∥ ⋅ cos θ → 6次元空間に写像されている） 2次多項式カーネルの展開例（x が2次元の場合 K(x, x′ ) = (xT x′ + 1)2 = (x1 x′1 + x2 x′2 + 1)2 ​ ​ ​ ​ = (x1 x′1 )2 + (x2 x′2 )2 + 2x1 x′1 x2 x′2 + 2x1 x′1 + 2x2 x′2 + 1 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ = ((x1 )2 , (x2 )2 , 2x1 x2 , 2x1 , 2x2 , 1) ⋅ ((x′1 )2 , (x′2 )2 , 2x′1 x′2 , 2x′1 , 2x′2 , 1) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

7.3 カーネル関数を用いたSVM (5/7) RBFカーネルの解釈 K(x, x′ ) = exp(−γ∥x − x′ ∥2 ) = exp(−γ(∥x∥2 − 2xT x′ + ∥x′ ∥2 )) = exp(−γ∥x∥2 ) exp(−γ∥x′ ∥2 ) exp(2γxT x′ ) RBFカーネルの展開 exp(x) のマクローリン展開 ex = 1 + x + 1 2 1 1 x + x3 + x4 + ⋯ 2! 3! 4! ​ ​ ​ RBFカーネルを展開した第3項は無限次元ベクトルの内積と解釈できる ​

7.3 カーネル関数を用いたSVM (6/7) = wT ϕ(x) + w0 N SVMで求めた w の値を代入: w = ∑i=1 αi yi ϕ(xi ) 変換後の線形識別関数：g(x) ​ ​ ​ N ​ ​ N g(x) = ∑ αi yi ϕ(x)T ϕ(xi ) + w0 = ∑ αi yi K (x, xi ) + w0 ​ i=1 ​ ​ ​ ​ ​ ​ ​ ​ ​ i=1 カーネルトリック : 非線形変換の式は不要で、カーネル関数を用いて元の空間の情報のみで 識別関数が書ける 変換後の空間での線形識別面は、もとの空間での複雑な非線形識別面に対応

7.3 カーネル関数を用いたSVM (7/7) sklearn で識別を行う SVM の定義 SVC(C=1.0, kernel='rbf', degree=3, gamma='scale', coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape='ovr', break_ties=False, random_state=None) ハイパーパラメータ C : スラック変数の重み kernel : カーネルの種類 'poly' : 多項式カーネル 'rbf' : RBFカーネル その他 : 'linear', 'sigmoid', 'precomputed' degree : polyカーネルを指定したときの次数 gamma : （主として）RBFカーネルを指定したときの係数

7.4 文書分類問題へのSVMの適用 文章のベクトル化 入力例）「顔認証はヤバいぐらい便利」 形態素解析 : 「顔認証 は ヤバい ぐらい 便利」 単語ベクトル化 : (0, 0, … , 0, 1, 0, … , 0, 1, 0, … ) 各次元が単語辞書の見出し順に対応し、入力に出現した単語の次元の値が1、それ以外は0 高次元特徴に強い SVM を用いて識別器を学習 多項式カーネルを用いると単語間の共起が相関として取れるので性能が上がることもある ただし、元が高次元なのでむやみに次数を上げるのも危険

One-class SVM One-class SVMによる新規検知 RBFカーネルによる写像後の学習データを正例、原点を負例とみなして境界を得る 新規データに対して、境界の外の場合は異常とみなす

サポートベクトル回帰 回帰における基底関数としてカーネル関数を用いる RBFカーネルを用いた場合 N N c^(x) = ∑ αj K (x, xj ) = ∑ αj exp(−γ∥x − xj ∥2 ) ​ ​ j=1 1次元特徴の場合 ​ ​ ​ ​ j=1 2次元特徴の場合

7.5 ハイパーパラメータの調整 (1/2) パラメータ : 学習データを用いて調整 線形識別関数の重み SVMの w α ニューラルネットワークの結合の重み ハイパーパラメータ : 学習前に決めておくもの 高次識別関数の次数 b、正則化項の重み SVM におけるスラック変数の重み α C , 多項式カーネルの次数 d ニューラルネットワークの中間ユニット数、層数

7.5 ハイパーパラメータの調整 (2/2) ハイパーパラメータが複数ある場合 グリッドサーチ：各格子点で性能を予測する 格子点の最小値・最大値・間隔等の知見が必要 ハイパーパラメータが連続値の場合は等比数列で設定する ランダムサーチ：各ハイパーパラメータの適切な範囲内で乱数によって複数点を設定 性能に大きく寄与するハイパーパラメータが存在する場合に有効 ベイズ最適化 ハイパーパラメータの値を入力、性能を出力とした回帰問題を設定し、ガウス過程回帰を用いて性 能が高くなりそうなハイパーパラメータを探索

7.6 まとめ SVMは線形分離可能なデータに対して，マージン最大の識別面を求める手法 誤識別に対するペナルティをスラック変数として設定することで、線形分離不可能な データへも適用可能 学習データを高次元の空間に写像するカーネル法では、カーネルトリックによって元 の空間での情報のみで識別関数を表現できる SVMのような多数のハイパーパラメータを持つモデルではハイパーパラメータチュー ニングを行う

ベイズ最適化 (1/4) ガウス過程とは ランダムな関数を生成する確率分布 平均が異なる正規分布の重み付き和で回帰関数を表現 H (x − μh )2 y = ∑ wh exp(− ) 2 σ h=0 ​ ​ ​ x がハイパーパラメータ、y が性能 この関数に対応する基底関数 ϕ(x) = (ϕ0 (x), ϕ1 (x), … , ϕH (x))T ​ ​ ​

ベイズ最適化 (2/4) 線形回帰モデル y = Φw Φ : 基底関数適用後のパターン行列 重み w が平均 0、分散 λ2 I の正規分布から生成されたと仮定すると、その線形変換であ る y も正規分布 平均 : E[y] = E[Φw] = ΦE[w] = 0 分散 : Σ = E[yy T ] − E[y]E[y]T = E[(Φw)(Φw)T ] = ΦE[w]E[w T ]ΦT = λ2 ΦΦT y の分布 y ∼ N (0, λ2 ΦΦT )

ベイズ最適化 (3/4) カーネルを用いたガウス過程の表現 K = λ2 ΦΦT K はN行N列で、n行n’列の要素は Knn′ = ϕ(xn )T ϕ(xn′ ) ​ ​ ​ 回帰関数がカーネル関数を用いた多次元正規分布で表現できた

ベイズ最適化 (4/4) ベイズ最適化の手順 ハイパーパラメータを特徴ベクトル、評価値をターゲットと見なしてガウス過程回帰を行う 最適値になりそうな近辺を中心にハイパーパラメータを探索