パターン認識論 #9

パターン認識論 第9回 伊藤 彰則

サポートベクターマシン ◦Support Vector Machine (SVM) ◦ 線形識別の仲間（非線形もできる） ◦ 未知データに強い識別境界を探す （マージン最大化） ◦ 高次元非線形特徴空間への暗黙の写像 （カーネルトリック）

線形識別 ◦超平面でクラスを分ける

線形識別 ◦様々な識別境界：どれが良い？ できるだけ「ぎりぎりでない方」が良さそう

マージン最大化 ◦識別境界に一番近い学習サンプル （サポートベクター）と識別境界との 距離（マージン）を最大化する

数学的準備 ◦データとラベル ◦ 𝒙1 , … 𝒙𝑁 ; 𝒙𝑖 ∈ 𝑅𝐷 ◦ 𝑦1 , … , 𝑦𝑁 ; 𝑦𝑖 ∈ {1, −1} ◦識別関数 ◦ 𝑓 𝒙𝑖 ; 𝜃 これは 𝑦𝑖 に近い値を返す ◦ 線形識別関数 𝑓 𝒙; 𝒘, 𝑏 =𝒘⋅𝒙+𝑏

係数の大きさとマージン ◦線形識別関数 𝑓 𝒙; 𝒘, 𝑏 =𝒘⋅𝒙+𝑏 ◦ サポートベクター𝑥𝑖 に対し 𝒘 ⋅ 𝒙𝑖 + 𝑏 = 1 となるように 𝒘, 𝑏 を正規化しておく 𝑤 𝒘⋅𝒙+𝑏 =0

係数の大きさとマージン サポートベクター 𝒙2 𝒘 𝒘 ⋅ 𝒙 + 𝑏 = −1 𝒙1 𝒘⋅𝒙+𝑏 =1 𝒘⋅𝒙+𝑏 =0 𝒘 ⋅ 𝒙1 + 𝑏 = 1 𝒘 ⋅ 𝒙2 + 𝑏 = −1 𝒘 ⋅ 𝒙1 − 𝒙2 = 2 𝒘 2 𝒙1 − 𝒙2 = 𝒘 𝒘 これは𝒙𝟏 − 𝒙2 の𝒘方向への射影 ＝マージンの2倍 𝒘 が小さいほどマージンが大きい

マージン最大化 目的関数 ◦𝑅 𝜃 1 𝑁 = σ𝑖=1 𝑙 𝒘 ⋅ 𝒙𝑖 + 𝑏, 𝑦𝑖 𝑁 + 𝒘 2 ◦ ただし min 𝒘 ⋅ 𝒙𝑖 + 𝑏 = 1 𝑖 ◦ 𝑙(𝑦 ′ , 𝑦):損失関数 ′ 0 𝑦 =𝑦 ′ ◦ バイナリ損失の場合 𝑙 𝑦 , 𝑦 = ቊ 1 𝑦′ ≠ 𝑦 ◦ ただしバイナリ損失は最適化が難しい →ヒンジ損失

マージン最大化 ◦ヒンジ損失 ◦ 満たすべき条件 ◦ 𝒘 ⋅ 𝒙𝑖 + 𝑏 ≥ 1 𝑖𝑓 𝑦𝑖 = 1 𝒘 ⋅ 𝒙𝑖 + 𝑏 ≤ −1 𝑖𝑓 𝑦𝑖 = −1 ◦ まとめると 𝑦𝑖 𝒘 ⋅ 𝒙𝑖 + 𝑏 ≥ 1 ◦ ヒンジ損失関数 ◦ 𝑙 𝑦 ′ , 𝑦 = 𝐻1 𝑦 ′ 𝑦 = max(0,1 − 𝑦 ′ 𝑦) 𝐻1 (𝑥)

マージン最大化 ◦目的関数 2 ◦ 𝑅 𝜃 = 𝐶 σ𝑁 𝐻 (𝒘 ⋅ 𝒙 + 𝑏)𝑦 + 𝒘 𝑖 𝑖 𝑖=1 1 誤り最小化 定数 マージン最大化

高次空間への非線形写像 ◦ある次元では線形識別できない問題でも 高次空間なら解けることがある 𝑥2 Φ 𝑥 = (𝑥, 𝑥 2 ) 𝑥 𝑥1

高次空間での識別 ◦識別関数 ◦𝑓 𝒙 = 𝒘 ⋅ Φ 𝒙 + 𝑏 ◦重みwは非常に大きい次元のベクトル ◦ 直接最適化することは難しい ◦学習データによって学習可能な重みは何 か？

学習データから学習できる 重み ◦学習データ𝒙1 , … 𝒙𝑁 →サンプルΦ 𝒙1 , … Φ 𝒙𝑁 ◦重みベクトルwを、サンプルの重み付き和 で表せる部分と表せない部分に分けてみる ◦ 𝒘 = 𝒘0 + σ𝑗 𝛼𝑗 Φ(𝒙𝑗 ) ◦ 𝒘0 ⋅ Φ 𝒙𝑗 = 0 for all j

学習データから学習できる 重み ◦目的関数 = 𝐶 σ𝑁 𝑖=1 𝐻1 (𝒘 ⋅ Φ(𝒙𝑖 ) + 𝑏)𝑦𝑖 ◦𝑅 𝜃 ◦ ここで ◦ 𝒘 ⋅ Φ 𝒙𝑖 + 𝑏 = 𝒘0 + σ𝑗 𝛼𝑗 Φ 𝒙𝑗 1 + 2 ⋅ Φ 𝒙𝑖 + 𝑏 = 𝒘0 ⋅ Φ 𝒙𝑖 + ෍ 𝛼𝑗 Φ 𝒙𝑗 ⋅ Φ 𝒙𝑖 + 𝑏 𝑗 = ෍ 𝛼𝑗 Φ 𝒙𝑗 ⋅ Φ(𝒙𝑖 ) + 𝑏 𝑗 𝒘 2

学習データから学習できる 重み ◦前の式から ◦ 𝒘0 = 0と置いても識別誤りには影響がない ◦ 𝒘0 = 0と置いた方が 𝑤 2 は小さくなる ◦以上のことから ◦ 𝒘 = σ𝑖 𝛼𝑖 Φ(𝒙𝑖 )と置いてよい ◦ 学習データだけによって張られる次元内の1点 ◦識別関数は ◦ 𝑓 𝒙 = σ𝑖 𝛼𝑖 Φ(𝒙𝑖 ) Φ 𝒙 + 𝑏 = σ𝑖 𝛼𝑖 Φ 𝒙𝑖 ⋅ Φ 𝒙 + 𝑏

カーネル関数 ◦識別関数 ◦ 𝐾 𝒙, 𝒙′ = Φ 𝒙 ⋅ Φ(𝒙′ )とおく ◦ 𝑓 𝒙 = σ𝑖 𝛼𝑖 Φ 𝒙𝑖 ⋅ Φ 𝒙 + 𝑏 = σ𝑖 𝛼𝑖 𝐾 𝒙𝑖 , 𝒙 + 𝑏 ◦ 関数𝐾(𝒙, 𝒙′ )：カーネル関数 ◦カーネル関数に工夫 ◦ 「高次空間に写像して内積」 →「内積の非線形関数」

カーネルトリック ◦非線形なカーネル関数を使うと？ ◦ 例えば 𝐾 𝒙, 𝒚 = 𝒙 ⋅ 𝒚 2 ◦ xが2次元の場合 ◦ 𝒙⋅𝒚 2 = 2 𝑥1 , 𝑥2 ⋅ 𝑦1 , 𝑦2 = 𝑥1 𝑦1 + 𝑥2 𝑦2 2 = 𝑥12 𝑦12 + 2𝑥1 𝑥2 𝑦1 𝑦2 + 𝑥22 𝑦22 = 𝑥12 , 2𝑥1 𝑥2 , 𝑥22 ⋅ (𝑦12 , 2𝑦1 𝑦2 , 𝑦22 ) ◦ Φ 𝒙 = Φ 𝑥1 , 𝑥2 = (𝑥12 , 2𝑥1 𝑥2 , 𝑥22 )

カーネルトリック 𝐾 𝒙, 𝒚 = 𝒙 ⋅ 𝒚 + 1 2 ◦２次の多項式カーネル ◦2次元の場合 ◦ Φ(𝒙) = (𝑥12 , 2𝑥1 𝑥2 , 𝑥22 , 2𝑥1 , 2𝑥2 , 1) ◦3次元の場合 ◦ Φ(𝒙) = (𝑥12 , 𝑥22 , 𝑥32 , 2𝑥1 𝑥2 , 2𝑥1 𝑥3 , 2𝑥2 𝑥3 , 2𝑥1 , 2𝑥2 , 2𝑥3 , 1)

カーネルトリック 𝐾 𝒙, 𝒚 = 𝒙 ⋅ 𝒚 + 1 3 ◦３次の多項式カーネル ◦2次元の場合 ◦ Φ 𝒙 = (𝑥13 , 3𝑥12 𝑥2 , 3𝑥1 𝑥22 , 3𝑥23 , 3𝑥12 , 6𝑥1 𝑥2 , 3𝑥22 , 3𝑥1 , 3𝑥2 , 1)

カーネルトリック 𝐾 𝒙, 𝒚 = exp 𝛾 𝒙 − 𝒚 2 ◦ Radial Basis Function (RBF)カーネル ◦ Expをテイラー展開すると無限級数 ⇒無限に高い次元への写像 ◦ 𝒙−𝒚 2 = 𝒙−𝒚 𝑡 𝒙−𝒚 = 𝒙𝑡 𝒙 − 2𝒙𝑡 𝒚 + 𝒚𝑡 𝒚 = 𝒙 2 + 𝒚 2 − 2𝒙 ⋅ 𝒚

SVMの学習 ◦解くべき問題 ෠ ◦ 𝒘 = σ𝑗 𝛼𝑗 Φ(𝒙𝑗 ) = 𝑋𝜶 ◦ 𝜶 = 𝛼1 … 𝛼𝑁 𝑡 , 𝑋෠ = Φ 𝒙1 , … Φ 𝒙𝑁 1 ◦ 目的関数 2 2 1 𝑡 𝑡 ෠ → min = 𝜶 𝑋෠ 𝑋𝜶 2 𝒘 ◦ 条件 𝒘 ⋅ Φ 𝒙𝑖 + 𝑏 𝑦𝑖 ≥ 1,∀i → σ𝑗 𝛼𝑗 Φ 𝒙𝑗 Φ 𝒙𝑖 + 𝑏 𝑦𝑖 − 1 ≥ 0 𝑌 𝐾𝜶 + 𝑏𝟏 − 𝟏 ≥ 0 𝑌 = 𝑑𝑖𝑎𝑔 𝑦𝑖 , 𝟏 = 1, … , 1 𝑡

SVMの学習 ◦最小化すべきもの 1 ◦ 2 𝒘 グラム行列 2 = 1 𝜶𝑡 𝑋 ෠ 𝑡 𝑋𝜶 ෠ = 1 𝜶𝑡 𝐾𝜶 2 2 ◦ 𝐾 = Φ 𝒙𝑖 Φ 𝐱j = {𝐾 𝒙𝑖 , 𝒙𝑗 } ◦制約条件 ◦ 𝟏 − 𝑌 𝐾𝜶 + 𝑏𝟏 ≤ 0 ◦目的関数（最小化） 1 𝑡 ◦ 𝐿 = 𝜶 𝐾𝜶 + 𝝀𝑡 𝟏 − 𝑌 𝐾𝜶 + 𝑏𝟏 2 𝝀𝑡 = 𝜆1 , … , 𝜆𝑁 , 𝜆𝑖 ≥ 0

SVMの学習 1 𝑡 ◦𝐿 = 𝜶 𝐾𝜶 + 𝝀𝑡 𝟏 − 𝑌 𝐾𝜶 + 𝑏𝟏 2 𝜕𝐿 ◦ = 𝐾𝜶 − 𝐾𝑌𝝀 = 𝟎 𝜕𝜶 𝜕𝐿 ◦ = −𝝀𝑡 𝑌𝟏 = 𝟎 𝜕𝑏 ◦ここで𝜶, 𝑏を消去 1 𝑡 ◦ 𝐿 = 𝝀 𝑌𝐾𝑌𝝀 − 𝝀𝑡 𝑌𝐾𝑌𝝀 + 𝝀𝒕 𝟏 2 1 𝑡 𝑡 = − 𝝀 𝑌𝐾𝑌𝝀 + 𝝀 𝟏 2 ◦ 制約 𝜆𝑖 ≥ 0, σ𝑖 𝜆𝑖 𝑦𝑖 = 0 ２次計画問題

SVMの学習 ◦通常の２次計画法で問題は解ける ◦ 𝝀が求まる ◦ 𝜶 = 𝑌𝝀 つまり 𝛼𝑗 = 𝑦𝑗 𝜆𝑗 1 ◦ 𝑏 = σ𝑖 𝑦𝑖 − σ𝑗 𝛼𝑗 𝐾(𝒙𝑗 , 𝒙𝑖 ) 𝑁 ◦識別境界に寄与するのはその周辺の データだけ →これまでの学習をサポートベクター だけ使って行う ◦ 高速化、高精度化

例 ◦1次多項式カーネル

例 ◦2次多項式カーネル

例 ◦3次多項式カーネル

例 ◦10次多項式カーネル

例 ◦RBFカーネル γ=1

例 ◦RBFカーネル γ=0.1

演習 Wine dataset*を使って、SVMと決定木ベー スの手法の性能を比較してみよう。 ◦ http://archive.ics.uci.edu/ml/datasets/Wine ◦ ワインの化学分析結果と等級(class)のデータ ◦ 分析結果から等級を予測する SVMと決定木ベース手法は何を使ってもよい ◦ 決定木ベース手法やSVMにはハイパーパラメータが あることに注意 ◦ ハイパーパラメータチューニングに別なデータセッ トを使う必要はないが、ハイパーパラメータの違い による影響は見ること

• http://archive.ics.uci.edu/ml/datasets/Wine

何を使うか ◦ Python ◦ Scikit-learnに含まれているパッケージ ◦ sklearn の svm, tree（決定木） ◦ sklearn.ensamble の RandomForestFlassifier, AdaBoostClassifier ◦R ◦ SVM ◦ e1071パッケージのsvm ◦ kernlabパッケージのksvm ◦ 決定木 ◦ rpartパッケージのrpart ◦ Random Forest ◦ randomForestパッケージのrandomForest ◦ AdaBoost ◦ rboosterパッケージのbooster ◦ mlpackパッケージのadaboost

何を使うか ◦ WEKA ◦ 標準で入っていないパッケージはToolsのパッケージマネー ジャからダウンロード・追加することができる

何を使うか ◦ SVM ◦ libSVM, libLINEAR ◦ 決定木 ◦ J48 ◦ RandomForest ◦ AdaBoost ◦ AdaBoostM1

WEKAを使う例 ◦ Weka ExplorerのPreprocessタブの [Open File…] からwine_train.arffを開く

WEKAを使う例 ◦ Classifyタブに移り、[Choose]から適当な識別器を 選ぶ ◦ Test optionsでは[Supplied test set]を選び、ダイ アログからwine_test.arffを選んで、目的変数class を選ぶ

WEKAを使う例 ◦ 目的変数として(Nom)classを選び、[start]で学習・識別開始