サポートベクターマシン

サポートベクターマシン 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver. 20230329 BishopのPRMLを参考にしています．

導⼊

分類 訓練データ • 分類とは入力を離散クラスに選り分けるこ とである． 覚えた B A • 予めクラスに分けられたデータ（答えが分 かっているデータ）を用い機械はデータを 分類するルールを学習する ． A A A • 機械は分類ルールをデータを分ける線 （面）として獲得する．データを分ける線 を決定境界という． B B B データを分ける線（決定境界） Bだと思う • 分類ルールを獲得した機械は未知のデータ に対しても，正しく分類できるかもしれな い． 未知のデータ

パーセプトロン • パーセプトロンは与えられたデータを２つのクラスに選り分ける（識 別する）⼿法の⼀つである． • データ点𝒙 = 𝑥! , 𝑥" , … , 𝑥# , … , 𝑥$ % が与えられたとき， • 𝑦 𝒙 = 𝒘% 𝒙 常に𝑥" = 1で𝑤" 𝑥" はバ イアスとなる． • が正ならばクラス１，負ならばクラス２に分ける． • 与えられたデータセットを正確に分けることを⽬的とする． 1 0.5 𝒘 • データを分ける線（⾯）を決定境界と⾔う． • 単純なパーセプトロンでは直線の決定境界しか引けない． 0 −0.5 −1 −1 −0.5 0 0.5 1

決定境界とデータ点の距離 • 決定境界に対して垂直なベクトル（重みベクトル）を𝑤，⼊⼒ベクト ルを𝒙，バイアスを𝑏とすると，決定境界は • 𝒘&𝒙 + 𝑏=0 • と書ける． 𝑥" 決定境界 𝒙 • 決定境界とデータ点との距離を求めてみる． 𝒘 𝑥! 𝒘! 𝒙 + 𝑏 = 0

決定境界とデータ点の距離 • 決定境界と原点との距離は • '( である（計算の詳細は次ページ）． ‖𝒘‖ 𝒙! 𝒘 𝒙の𝒘への射影ベクトルの⼤きさは 𝒘 である． • つまり，決定境界と𝒙との距離は • 𝒙! 𝒘 − 𝒘 − , 𝒘 = 𝒘! 𝒙 + 𝑏 = 0 𝒙! 𝒘-( 𝒘 𝑏 • ここで •𝑦 𝒙 = 𝑥" 𝒙&𝒘 + • とする． 𝑏 𝒙 𝒘 𝑥! 𝒙𝐓𝒘 𝒘 − 𝑏 ‖𝑤‖

𝑦 𝒙 と識別 • % 𝒙 𝒙 と決定境界との距離が ‖𝑾‖ • • 𝒙( 𝒘 >− 𝒘 𝒙( 𝒘 𝒘 • − • 𝒘 𝑥" > 0のとき と変形できる． は 𝒙を 𝒘に射影したベクトルの⼤きさである． 𝒙! 𝒘 $ 𝒘 𝒙( 𝒘 𝒘 $ = 𝒙' 𝒘*+ 𝒘 は原点と決定境界の距離である． • = 𝒙 𝒙! 𝒘 + 𝑏 𝒘 𝒘 >− $ 𝒘 は， 𝒙が決定境界より原点から遠いこ とを意味する． • つまり， 𝒙が決定境界で分けられる領域（決定領 域）のうち原点を含まない領域にあることを意味 する． % 𝒙 ‖𝑾‖ 𝒘 𝒙' 𝒘*+ 𝒘 < 0 の場合は， 𝒙が原点を含む決定 領域にあることを意味する． −𝑏 ‖𝑤‖ 𝑥!

𝑦 𝒙 と識別 • 𝑦 𝒙 = 𝒘&𝒙 + 𝑏 の符号が，⼊⼒ベクトルが識別境界の分ける領域のど ちらにあるかを⽰す． • 領域を分ける直線（⾯）が𝑦 𝒙 = 𝒘&𝒙 + 𝑏 = 0 となっている． 𝑥" 𝑦 𝒙 が正の領域 𝒙 𝑦 𝒙 が負の領域 𝑥! 𝑦(𝒙) = 0

おまけ：原点から直線への距離 𝒘と同じ⽅向で 𝒘( 𝒙 + 𝑏 = 0 の直線上の点は 次のように表せる． 𝒙 = 𝑎𝒘 これを直線の式に代⼊すると 𝑎𝒘( 𝒘 + 𝑏 = 0 𝑎𝒘( 𝒘 = −𝑏 𝑏 𝑎=− 𝒘 ) よって𝒙は 𝑏 𝒙=− 𝐰 𝒘 ) 𝑏 𝐰 𝒙=− ‖𝒘‖ ‖𝒘‖ 𝐰 は単位ベクトルなので，𝒙の⼤きさ，す ‖𝒘‖ なわち原点から直線への距離𝑑は 𝑏 𝑑=− ‖𝒘‖ 𝑥" 𝒙 𝒘 −𝑏 ‖𝑤‖ 𝑥! 𝒘! 𝒙 + 𝑏 = 0

おまけ：ベクトルの計算 内積と余弦 ピタゴラスの定理より 𝒂 − 𝒃 . = ‖𝒂‖ − 𝒃 𝒂−𝒃 / 𝒂−𝒃 = 𝒂 .−2 𝒂 𝒃 𝒂/ 𝒂 − 2𝒂/ 𝒃 + 𝒃/ 𝒃 = 𝒂 . − 2 𝒂 𝒂 . − 2𝒂/ 𝒃 + 𝒃 . = 𝒂 −2𝒂/ 𝒃 = −2 𝒂/ 𝒃 = 𝒂 cos 𝜃 . + 𝒂 . sin. 𝜃 cos 𝜃 + 𝒃 . cos . 𝜃 + 𝒃 . sin. 𝜃 𝒃 cos 𝜃 + 𝒃 . sin. 𝜃 + cos . 𝜃 . − 2 𝒂 𝒃 cos 𝜃 + 𝒃 . 𝒂 𝒃 cos 𝜃 𝒃 cos 𝜃 𝑏 𝑎−𝑏 𝑏 sin 𝜃 ベクトル𝑏のベクトル𝑎への射影𝑏∥1 𝒂 𝒂/ 𝒃 𝒂 𝒂3 𝒃 𝒂 𝒃∥𝒂 = 𝒃 cos 𝜃 = 𝒃 = ‖𝒂‖ 𝒂 ‖𝒃‖ ‖𝒂‖ 𝒂 ‖𝒂‖ よって𝒃∥𝒂の⼤きさは 𝒂(𝒃 𝒂 = 𝒂 𝒃3 𝒂 𝜃 𝒃∥𝒂 𝑏 cos 𝜃 𝑎

サポートベクターマシン

サポートベクターマシン • サポートベクターマシン(SVM; support vector machine)はデータを分 類する⼿法の⼀つである． • サポートベクターマシンはデータを直線で分ける． • 直線で分けられるデータのことを線形分離可能という． • つまり，サポートベクターマシンは線形分離可能な問題に適⽤できる． • サポートベクターマシンは決定境界とマージ ンを最⼤化することを⽬的とする． • マージンとは，決定境界とデータ点との距離 の最⼩値である． 決 定 境 界 y=1 y=0 y= margin 1

決定境界 • 決定境界に対して垂直なベクトル（重みベクトル）を𝒘，⼊⼒ベクト ルを𝒙，バイアスを𝑏とする． • ⼊⼒ベクトル 𝒙 を特徴空間変換関数𝝓で変換する． • このとき決定境界は • 𝑦 𝒙 = 𝒘% 𝝓 𝒙 + 𝑏 = 0 • と書ける．

訓練データ • 訓練データは𝒙" , … , 𝒙$ の𝑁個の⼊⼒ベクトルとそれぞれに対応したラ ベル𝑡" , … , 𝑡$ 𝑡6 ∈ {−1, 1} からなり，⼊⼒ベクトル𝒙は𝑦 𝒙 の符号に応 じて分類されるとする． • 訓練データは線形分離可能であると仮定する． • ⼊⼒ベクトル𝒙6 の⽬標変数が𝑡6 = 1であるとき𝑦 𝒙6 > 0， ⼊⼒ベク トル𝒙6 の⽬標変数が𝑡6 = −1であるのとき𝑦 𝒙6 < 0がそれぞれ成⽴す ると仮定する．

マージン • ⼊⼒ベクトルを𝒙6 とすると決定境界と𝝓 𝒙6 の距離は • 75 8 𝒙5 9 = 75 𝒘6 𝝓 𝒙5 -( 𝒘 • である． • マージンは決定境界と𝝓 𝒙6 の距離の最⼩値なので • 75 𝒘6 𝝓 𝒙5 -( min 𝒘 6 y = 1 決定境界 y=0 y= 1 • である． 決定境界に⼀番近い𝝓 𝒙1 margin

マージンの最⼤化 • サポートベクターマシンの⽬的はマージンを最⼤化するパラメタ 𝒘, 𝑏 を求めることにある． • つまり，サポートベクターマシンでは • argmax𝒘,( 75 𝒘6 𝝓 𝒙5 -( min 𝒘 6 • で与えられる最適化問題を解くことになる．

最適化問題の変形 • argmax𝒘,+ min 形する． / • argmax𝒘,+ min らない． / 0, 𝒘- 𝝓 𝒙, *+ 𝒘 0, 𝒘- 𝝓 𝒙, *+ 𝒘 を直接解くのは難しいので，より簡単な形へ変 は𝒘と𝑏を 𝜅𝒘と𝜅𝑏 のように定数倍しても変わ • よって決定境界に最も近い 𝝓 𝒙/ について，次の式を成り⽴たせるように パラメタを指定できる． • min 𝑡/ 𝒘1 𝝓 𝒙/ + 𝑏 = 1 / • このようにパラメタを決めれば，すべての 𝒙/ について次の式が成り⽴つ． • 𝑡/ 𝒘1 𝝓 𝒙/ + 𝑏 ≥ 1

最適化問題の変形
• min 𝑡7 𝒘/ 𝝓 𝒙7 + 𝑏 = 1
7

• これの式の両辺を 𝒘 で割ると
• min
7

82 9 3 𝝓 𝒙2 ;$
𝒘

=

<
𝒘

• つまり， argmax𝒘,$ min
7

82 𝒘3 𝝓 𝒙2 ;$
𝒘

= argmax𝒘,$

<
𝒘

である．

"" 𝒘 𝝓 𝒙" &'
.
• よって， min
を最⼤にするということは，
𝒘
を最⼩化することと等価で
𝒘
!
ある．
#

• 結局，マージンを最⼤化する解は，
• argmin𝒘,$

<
.

𝒘

.

• を𝑡7 𝑤 / 𝝓 𝒙7 + 𝑏 ≥ 1の制約下で解くことで得られる．

ラグランジュ関数 • argmin𝒘,+ 2 3 𝒘 3 を解くのだが，制約条件𝑡/ 𝒘1 𝝓 𝒙/ + 𝑏 ≥ 1がある． • これを解くにはラグランジュの未定乗数法を⽤いる．ラグランジュ関数は， • 𝐿 𝒘, 𝑏, 𝒂 = 2 3 𝒘 3 1 − ∑5 /42 𝑎/ 𝑡/ 𝒘 𝝓 𝒙/ + 𝑏 − 1 • である．𝒂 = 𝑎2 , … , 𝑎5 , 𝑎/ 1 ≥ 0はラグランジュ乗数である． • 最⼩化問題なのでラグランジュ乗数の前の符号は負となる． • 𝐿 𝒘, 𝑏, 𝒂 を𝒘と𝑏 で微分し，それらを0と等しいとおくと • 𝒘 = ∑5 /42 𝑎/ 𝑡/ 𝝓 𝒙/ • 0 = ∑5 /42 𝑎/ 𝑡/ • が得られる．

双対表現 $ • 𝒘 = ∑$ 6<" 𝑎6 𝑡6 𝝓 𝒙6 , ∑6<" 𝑎6 𝑡6 = 0を𝐿に代⼊する． 6 1 𝐿6 𝑎 = : 𝑎1 𝑡1 𝝓 𝒙1 2 6 145 6 6 7 6 6 : 𝑎8 𝑡8 𝝓 𝒙8 − : 𝑎1 𝑡1 : 𝑎8 𝑡8 𝝓 𝒙8 7 𝝓 𝒙1 + 𝑏 − 1 845 145 6 6 845 6 6 145 145 1 𝐿6 𝑎 = : : 𝑎1 𝑡1 𝑎8 𝑡8 𝝓 𝒙1 7 𝝓 𝒙8 − : 𝑎1 𝑡1 : 𝑎8 𝑡8 𝝓 𝒙8 7 𝝓 𝒙1 − : 𝑎1 𝑡1 𝑏 + : 𝑎1 2 145 845 6 6 145 845 6 1 𝐿6 𝑎 = − : : 𝑎1 𝑡1 𝑎8 𝑡8 𝝓 𝒙1 7 𝝓 𝒙8 + : 𝑎1 2 145 845 145 • 𝝓 𝒙6 % 𝝓 𝒙= = 𝑘(𝒙6 , 𝒙= )とおくと 6 6 6 1 𝐿6 𝑎 = − : : 𝑎1 𝑡1 𝑎8 𝑡8 𝑘(𝒙1 , 𝒙8 ) + : 𝑎1 2 145 845 145

双対表現 < @ @ • 𝐿4 𝒂 = − ∑@ 7?< ∑A?< 𝑎7 𝑡7 𝑎A 𝑡A 𝑘(𝒙7 , 𝒙A ) + ∑7?< 𝑎7 . • 𝒘 . を最⼩化する問題が𝐿4 𝒂 を𝒂に対して最⼤化させる問題に変わった（おまけス ライド参照）． • ただし，𝑎7 ≥ 0, ∑@ 7?< 𝑎7 𝑡7 = 0の制約条件を満たす必要がある． < • argmin𝒂 𝐿4 𝒂 は argmin9,$ . 𝒘 . の双対表現である． • 𝑘(𝒙7 , 𝒙A )をカーネル関数という． • ハードマージンSVMを解くとは < @ @ • 𝐿4 𝒂 = − . ∑@ 7?< ∑A?< 𝑎7 𝑡7 𝑎A 𝑡A 𝑘(𝒙7 , 𝒙A ) + ∑7?< 𝑎7 • を最⼤化する 𝒂を探すことである．

出⼒をカーネル関数で表す y=1 y=0 y= • カーネル関数を使い𝑦(𝒙)を書き直すと • 𝑦 𝒙 = 𝒘% 𝝓(𝒙) + 𝑏 = ∑$ 6<" 𝑎6 𝑡6 𝑘 𝒙, 𝒙6 + 𝑏 margin • となる． • Karush-Kuhn-Tucker条件(KKT条件)を適⽤すると，次の３つの条件が 成り⽴つことがわかる． • 𝑎6 ≥ 0 • 𝑡6 𝑦 𝑥6 − 1 ≥ 0 • 𝑎6 𝑡6 𝑦 𝑥6 − 1 = 0 1

サポートベクタ • 𝑎6 𝑡6 𝑦 𝒙6 − 1 = 0 から，すべてのデータ点に対し𝑎6 = 0あるいは 𝑡6 𝑦 𝒙6 = 1が成り⽴つ． • 𝑡" 𝑦 𝒙" − 1 ≠ 0ならば𝑎" = 0でなければ 𝑎" 𝑡" 𝑦 𝒙" − 1 = 0が成り⽴たな い． • 𝑡" 𝑦 𝒙" − 1 = 0すなわち𝝓(𝒙)がマージン境界にある場合，𝑎" ≠ 0である． • 𝑎6 = 0となるデータ点𝒙6 は 𝑦 𝒙 = ∑$ 6<" 𝑎6 𝑡6 𝑘 𝒙, 𝒙6 + 𝑏の値に影響を 与えない． つまり，𝑎6 = 0となるデータ点は分類には必要ない． • 逆に， 𝑎6 ≠ 0となるデータ点は分類のために必要である． • この点をサポートベクタと呼ぶ． y= 1 y=0 y=1

バイアスパラメタ𝑏 • 𝒂が求まれば，バイアスパラメタ𝑏が求まる． • サポートベクタ𝒙7 は • 𝑡7 𝑦 𝒙7 = 𝑡7 ∑@ A?< 𝑎A 𝑡A 𝑘 𝒙7 , 𝒙A + 𝑏 = 1 • を満たすので， • 𝑏= < 82 𝑡1 = 1 𝑜𝑟 − 1だから𝑡1: = 1 @ − ∑@ 7?< 𝑎A 𝑡A 𝑘 𝒙7 , 𝒙A = 𝑡7 − ∑7?< 𝑎A 𝑡A 𝑘 𝒙7 , 𝒙A • これで𝑏は求まるが，数値計算の誤差の影響を減らすため，すべてのサポートベク タから求めた𝑏の平均を取ることにする． • サポートベクタの添字からなる集合を𝑆とすると， • 𝑏= < @9 @ ∑@ 7∈C 𝑡7 − ∑7∈C 𝑎A 𝑡A 𝑘 𝒙7 , 𝒙A • ただし𝑁C はサポートベクタの数とする．

特徴空間変換関数とサポートベクターマシン • サポートベクターマシーンは線形分離可能な問題しか解けない． • そこで，⼊⼒ベクトル 𝒙 を特徴空間変換関数𝝓で⾼次元なベクトルに 変換する（⾼次元特徴空間に射影する）． • ⾼次元特徴空間に射影し，⾼次元特徴空間でデータを線形識別する． • その結果，元の空間で⾮線形な決定境界を作ることができる． • だからといって，線形分離不可能な問題が必ず解けるわけではない． y=1 y=0 y= 1 2 0 −2 margin −2 データ ⾼次元特徴空間 特徴空間上で線形な識別 0 2 元の空間では⾮線形

カーネルサポートベクターマシン • ⾼次元への写像は計算が⼤変なので楽がしたい． • カーネル法を⽤いれば，少ない計算量で⾼次元特徴空間での分類が可 能となる． • カーネル法を⽤いたサポートベクターマシンをカーネルサポートベク ターマシンという． • しかし，サポートベクターマシンを使う場合ほぼカーネル法も使って いるので，サポートベクターマシンと⾔えばほぼカーネルサポートベ クターマシンのことを指す．

おまけ：ラグランジュ関数の最⼤化と最⼩化1 < < • SVMはmin𝒘,$ . 𝒘 . を⽬的としている．ここで，min𝒘,$ . 𝒘 . = 𝑝∗ とする． • また，ラグランジュ関数の最⼩化 • min𝒘,$ 𝐿 𝒘, 𝑏, 𝒂 = min𝒘,$ < . 𝒘 . / − ∑@ 7?< 𝑎7 𝑡7 𝒘 𝝓 𝒙7 + 𝑏 − 1 • を考える．𝑡7 𝒘/ 𝝓 𝒙7 + 𝑏 − 1 ≥ 0, 𝑎7 ≥ 0なので • min𝒘,$ 𝐿 𝒘, 𝑏, 𝒂 ≤ 𝑝∗ となる， • min𝒘,$ 𝐿 𝒘, 𝑏, 𝒂 = 𝑝∗ となるのは ， min𝒘,$ 𝐿 𝒘, 𝑏, 𝒂 が最⼤値を取るときである． • よって • min𝒘,$ < . 𝒘 . = max min𝒘,$ 𝐿 𝒘, 𝑏, 𝒂 𝒂

おまけ：ラグランジュ関数の最⼤化と最⼩化2 • 𝜃 𝑤, 𝑏 = max 𝐿 𝑤, 𝑏, 𝑎 = max 1 1 < 𝒘 . . / − ∑@ 7?< 𝑎7 𝑡7 𝒘 𝝓 𝒙7 + 𝑏 − 1 • を考える． • 𝑎7 ≥ 0， 𝑡7 𝒘/ 𝝓 𝒙7 + 𝑏 − 1 ≥ 0の条件があるので， / • ∑@ 7?< 𝑎7 𝑡7 𝒘 𝝓 𝒙7 + 𝑏 − 1 = 0のとき 𝐿 𝑤, 𝑏, 𝑎 が最⼤となる．よって • 𝜃 𝒘, 𝑏 = max 𝐿 𝒘, 𝑏, 𝒂 = 1 < . 𝒘 . < • ⽬的は . 𝒘 . の最⼩化なので < • min𝒘,$ . 𝒘 . = min 𝜃 𝒘, 𝑏 = min max 𝐿 𝒘, 𝑏, 𝒂 9,$ 𝒘,$ 𝒂 • 𝐿 𝒘, 𝑏, 𝒂 = 𝐿4 𝒂 だから • min𝒘,$ < . 𝒘 . ＝ min max 𝐿4 𝑎 = max 𝐿4 𝒂 𝒘,$ 𝒂 𝒂

ソフトマージン

ソフトマージンSVM • 先のサポートベクターマシンは，データを完全に分離できると仮定し ている． • 現実のデータは完全に分離できることは少なく，多くの場合，決定境 界でそれぞれのクラスに属するデータが⼊り乱れている． • 誤分類を許すように変更する必要がある．

誤分類の度合いを数値化する • 誤分類といっても，⼤きく間違えた場合や，ほとんど間違えていない場合など様々であ る． • そこで，誤分類の度合いを定量化する必要がある． • この度合いをスラック変数𝜉7 ≥ 0を⽤い表す． • データ点が正しく分類され，かつマージン境界上もしくはマージンの外側にある場合 • 𝜉7 = 0 • とし，それ以外の場合は • 𝜉7 = 𝑡7 − 𝑦 𝒙7 y= 1 y=0 y=1 ⇠>1 • とする． • ただし，⼊⼒ベクトルが決定境界上の場合（ 𝑦 𝑥7 = 0）, • 𝜉7 = 1とする． ⇠<1 ⇠=0 ⇠=0

スラック変数 • マージン内であるが，データが正しく分類されている場合 • 𝑡" = 1のとき， 0 < 𝑦 𝑥" < 1だから， 0 < 𝑡" − 𝑦 𝑥" <1 • 𝑡" = −1のとき， −1 < 𝑦 𝑥" < 0だから， 0 < 𝑡" − 𝑦 𝑥" <1 • よって，0 < 𝜉6 < 1 • 誤って分類されている場合 • 𝑡" = 1のとき𝑦 𝑥" < 0なので 𝜉" = 𝑡" − 𝑦 𝑥" • 𝑡" = −1のとき𝑦 𝑥" > 0なので 𝜉" = 𝑡" − 𝑦 𝑥" • よって， 𝜉6 > 1． y= y=0 >1 >1 1 y=1 ⇠>1 ⇠<1 ⇠=0 ⇠=0

識別関数 • 識別関数はハードマージンの場合 • 𝑡6 𝑦 𝑥6 ≥ 1 • であった． • これをソフトマージンでは • 𝑡6 𝑦 𝑥6 ≥ 1 − 𝜉6 • とする． y= 1 y=0 y=1 ⇠>1 ⇠<1 ⇠=0 ⇠=0

⽬的関数とラグランジュ関数 • ソフトマージンSVMの⽬的は誤分類に対しペナルティを与えつつ，マージ ンを最⼤化することである． • つまり，ソフトマージンSVMでは • 2 3 𝒘 3 + 𝐶 ∑5 /42 𝜉/ • を⽬的関数とし，これを𝑡/ 𝑤 1 𝝓 𝒙/ ≥ 1 − 𝜉/ ，𝜉/ ≥ 0の条件のもと最⼩化 する． • よって，この最⼩化問題のラグランジュ関数は • 𝐿 𝒘, 𝑏, 𝒂, 𝝁 = ∑5 /42 𝜇/ 𝜉/ 2 3 𝒘 3 5 1 + 𝐶 ∑5 /42 𝜉/ − ∑/42 𝑎/ 𝑡/ 𝒘 𝝓 𝒙/ + 𝜉/ − 1 + • となる．{𝑎/ ≥ 0}と{𝜇/ ≥ 0}はラグランジュ定数である． 𝐶 → ∞のとき，ソフトマージンSVMはハードマージンSVMと等価となる．なぜならば， 𝜉! = 0のときのみ（誤分類なくマー ジンの外側にデータ点があるとき）最⼩となるため．

KKT条件 • 𝐿 𝒘, 𝑏, 𝒂 のKKT条件は， • 𝑎6 ≥ 0 • 𝑡6 𝑦 𝑥6 − 1 + 𝜉 ≥ 0 • 𝑎6 𝑡6 𝑦 𝑥6 − 1 + 𝜉 = 0 • 𝜇6 ≥ 0 • 𝜉6 ≥ 0 • 𝜇6 𝜉6 = 0 • である．

ラグランジュ関数の変形 " • 𝐿 𝒘, 𝑏, 𝒂, 𝝁 = > 𝒘 > $ % + 𝐶 ∑$ 6<" 𝜉6 − ∑6<" 𝑎6 𝑡6 𝒘 𝝓 𝒙6 + 𝜉6 − 1 + ∑$ 6<" 𝜇6 𝜉6 の偏微分から • ?@ ?9 = 0 ⟹ 𝒘 = ∑$ 6<" 𝑎6 𝑡6 𝝓 𝒙6 • ?@ ?( = 0 ⟹ ∑$ 6<" 𝑎6 𝑡6 = 0 • ?@ ?A5 = 0 ⟹ 𝐶 − 𝑎6 − 𝜇6 = 0 ⟹ 𝜇6 = 𝐶 − 𝑎6 • これをラグランジュ関数に代⼊する．

ラグランジュ関数の変形 5 • 𝒘 = ∑5 /42 𝑎/ 𝑡/ 𝝓 𝒙/ , ∑/42 𝑎/ 𝑡/ = 0, 𝜇/ = 𝐶 − 𝑎/ * 1 𝐿K 𝑎 = O 𝑎! 𝑡! 𝝓 𝒙! 2 * 𝐿K 𝑎 = !() * * + * * * * O 𝑎, 𝑡, 𝝓 𝒙, + 𝐶 O 𝜉! − O 𝑎! 𝑡! O 𝑎, 𝑡, 𝝓 𝒙, + 𝝓 𝒙! + 𝜉! − 1 ,() !() * * !() * ,() * * !() !() − O 𝐶 − 𝑎! 𝜉! !() * * 1 O O 𝑎! 𝑡! 𝑎, 𝑡, 𝝓 𝒙! + 𝝓 𝒙, + 𝐶 O 𝜉! − O 𝑎! 𝑡! O 𝑎, 𝑡, 𝝓 𝒙, + 𝝓 𝒙! − O 𝑎! 𝜉! + O 𝑎! − O 𝐶𝜉! + O 𝑎! 𝜉! 2 !() ,() !() * !() * ,() * 1 𝐿K 𝑎 = − O O 𝑎! 𝑡! 𝑎, 𝑡, 𝝓 𝒙! + 𝝓 𝒙, + O 𝑎! 2 !() ,() !() • 𝝓 𝒙/ 1 𝝓 𝒙D = 𝑘(𝒙/ , 𝒙D )とおくと 2 5 5 • 𝐿F 𝒂 = − ∑5 /42 ∑D42 𝑎/ 𝑡/ 𝑎D 𝑡D 𝑘(𝒙/ , 𝒙D ) + ∑/42 𝑎/ 3 • となる． !() !()

双対表現 • ソフトマージンSVMは " $ $ • 𝐿N 𝑎 = − ∑$ 6<" ∑=<" 𝑎6 𝑡6 𝑎= 𝑡= 𝑘(𝒙6 , 𝒙= ) + ∑6<" 𝑎6 > • を0 ≤ 𝑎6 ≤ 𝐶，∑$ 6<" 𝑎6 𝑡6 = 0の条件のもとで最⼤化する問題となる． • KKT条件から，𝑎" ≥ 0， 𝜇" = 𝐶 − 𝑎" ≥ 0より 0 ≤ 𝑎" ≤ 𝐶 • 制約条件を除いてハードマージンと同じ式が得られる．

サポートベクタ • ハードマージンSVM同様に，𝑎6 = 0となるデータ点は分類には必要な い． • 𝑎6 ≠ 0となるデータ点がサポートベクタとなる． • よって𝑎6 ≥ 0だから，サポートベクタについては𝑎6 > 0が成り⽴つ． • サポートベクタについては𝑎6 ≠ 0なので，𝑎6 𝑡6 𝑦 𝑥6 − 1 + 𝜉 = 0の両 辺を𝑎6 で割ることができ， • 𝑡6 𝑦 𝑥6 − 1 + 𝜉 = 0が成り⽴つ．

サポートベクタ • 𝑎6 < 𝐶のとき，ラグランジュ関数の微分より求まった𝜇6 = 𝐶 − 𝑎6 から 𝜇6 > 0である． • このとき，KTT条件𝜇6 𝜉6 = 0から 𝜉6 = 0となる． • つまり， 𝑎6 < 𝐶のときのサポートベクタはマージン境界上にある． y= 1 y=0 y=1 ⇠>1 • また， 𝑎6 = 𝐶のとき， 𝜇6 = 𝐶 − 𝑎6 から𝜇6 = 0である． • このとき， KTT条件𝜇6 𝜉6 = 0から𝜉6 ≠ 0となる． ⇠<1 ⇠=0 ⇠=0 • つまり，𝑎6 < 𝐶のときのサポートベクタはマージン内にある． • 特に， 𝜉6 ≤ 1のサポートベクタは正しく分類されており，𝜉6 > 1のサ ポートベクタは誤分類されている．

パラメタ𝒃 • 0 < 𝑎/ < 𝐶となるサポートベクタは𝜉/ = 0なので， • 𝑡/ 𝑦 𝑥/ − 1 = 0 • が成り⽴つ．これを利⽤すると， • 𝑡/ ∑D∈F 𝑎D 𝑡D 𝑘 𝒙/ , 𝒙D + 𝑏 − 1 = 0 • 両辺𝑡/ を掛けると， • 𝑏 = 𝑡/ − ∑D∈F 𝑎D 𝑡D 𝑘 𝒙/ , 𝒙D 𝑡1 = 1 𝑜𝑟 − 1だから𝑡1: = 1 • ここでも，ハードマージンSVMと同様に，0 < 𝑎/ < 𝐶となるサポートベク タから計算した𝑏の平均を取ることにする． • 0 < 𝑎/ < 𝐶となるサポートベクタの添字の集合を𝑀とすると， •𝑏= 2 ∑ 5. /∈G 𝑡/ − ∑D∈F 𝑎D 𝑡D 𝑘 𝒙/ , 𝒙D

𝒂を求めるには • 散々数式の説明してきたが，これまでの説明ではサポートベクターマ シンを使えない． • なぜならば，ラグランジュ乗数𝒂を求める⽅法を説明していないから である． • ソフトマージンSVMの⽬的は， " $ $ • 𝐿N 𝑎 = − > ∑$ 6<" ∑=<" 𝑎6 𝑡6 𝑎= 𝑡= 𝑘(𝒙6 , 𝒙= ) + ∑6<" 𝑎6 • を0 ≤ 𝑎6 ≤ 𝐶，∑$ 6<" 𝑎6 𝑡6 = 0の条件の下で最⼤化することであった． • これは２次計画問題である． • 𝒂を求めるには２次計画問題を解くアルゴリズムを使う必要がある．

おまけ ラグランジュの未定乗数法

おまけ：ラグランジュの未定乗数法1 • 関数𝑓(𝒙)を𝑔 𝒙 = 0の条件のもとで最⼤化するにはどうすればよいか． • 曲⾯𝑔 𝒙 = 0上の点𝒙と𝒙 + 𝝐を考える． 𝝐は微⼩であるとする． rf (x) • 𝑔 𝒙 + 𝝐 を𝒙の周りでテーラー展開すると， • 𝑔 𝒙+𝝐 =𝑔 𝒙 + 𝒙+𝝐−𝒙 H ∇𝑔 𝒙 +⋯ • 𝑔 𝒙 + 𝝐 ≃ 𝑔 𝒙 + 𝝐1 ∇𝑔 𝒙 • 𝒙と𝒙 + 𝝐は共に曲⾯上にあるので，𝑔 𝒙 = 𝑔 𝒙 + 𝝐 = 0 xA rg(x) g(x) = 0 • よって 𝝐1 ∇𝑔 𝒙 = 𝟎 • 𝒙と𝒙 + 𝝐は共に曲⾯上にあり，それぞれ近傍であるから𝝐は接線ベクトルで ある． • よって ∇𝑔 𝒙 は曲⾯𝑔 𝒙 = 0に対し垂直である．

おまけ：ラグランジュの未定乗数法2 • 制約⾯上の点で𝑓(𝒙)を最⼤化する𝑥 ∗を考える． • ∇𝑓 𝒙 が点𝒙 での制約⾯の接線ベクトルに対し垂直ではない場合， 𝑓 𝒙 の値を増やすように制約⾯そって𝒙を更に動かす事ができる． • ∇𝑓 𝒙 が点𝒙 での制約⾯の接線ベクトルに対し垂直ならば， 𝒙を制約⾯ そって更に動かすと𝑓 𝒙 は減るだけである． • つまり， ∇𝑔 𝒙 と∇𝑓 𝒙 は平⾏なベクトルである必要がある． • よって，次の式を満たすパラメタ𝜆 ≠ 0が存在する． • ∇𝑓 𝒙 + 𝜆∇𝑔 𝒙 = 0 • 𝜆をラグランジュ乗数という． rf (x) xA rg(x) ∇𝑓(𝑥) g(x) = 0

おまけ：ラグランジュの未定乗数法3 • ラグランジュ関数 • 𝐿 𝒙, 𝜆 = 𝑓 𝒙 + 𝜆𝑔 𝒙 • を導⼊する．先程のスライドから，ラグランジュ関数の𝑥についての偏 微分は∇𝒙𝐿 = ∇𝒙𝑓 𝒙 + 𝜆∇𝒙𝑔 𝒙 = 0となることが分かる． • ラグランジュ関数を𝜆について偏微分すると • ?@ ?C = 𝑔 𝑥 = 0となり制約式が導かれる． • つまり， 𝑔 𝑥 = 0の制約下で𝑓 𝑥 を最⼤化するためには， ラグランジ ュ関数𝐿 𝒙, 𝜆 の𝑥と𝜆の停留点を求めれば良い．

おまけ：ラグランジュの未定乗数法4 • 制約式が不等式である場合𝑔 𝒙 ≥ 0はどうであろうか． • 𝑔 𝒙 > 0の場合， 𝑔 𝒙 はない場合と同じなので，停留条件は単に∇𝑓 𝒙 = 0となる． • 𝑔 𝒙 = 0の場合，先程議論した場合と同じくラグランジュ関数の停留点を 求めれば良い． • しかし， 𝑔 𝒙 = 0の⾯上点における ∇𝑓 𝒙 は領域の外向きでなければなら ない．なぜならば，内向きならば領域内部に解があるかもしれなからであ rf (x) る． • よって，𝑔 𝒙 = 0の場合𝜆 > 0が存在し xA rg(x) • ∇𝑓 𝒙 = −𝜆∇𝑔 𝒙 • が成り⽴つ必要がある． xB g(x) > 0 g(x) = 0

おまけ：ラグランジュの未定乗数法5 • 𝑔 𝒙 > 0の場合， ∇𝑓 𝒙 = 0で良いのだから𝜆 = 0となる． • 𝑔 𝒙 = 0の場合， 𝜆 > 0である． • いずれにしても，𝜆𝑔 𝒙 = 0は成り⽴つ． • よって， 𝑔 𝒙 ≥ 0のとき𝑓 𝒙 を最⼤化するには，次の条件下で𝑥と𝜆に ついてラグランジュ関数の停留点を求めれば良い． • 𝑔 𝒙 ≥ 0：制約条件 •𝜆≥0 • 𝜆𝑔 𝒙 = 0 • これらの条件はKarush-Kuhn-Tucker条件（KKT条件）という．

おまけ：ラグランジュの未定乗数法6 • 逆に 𝑓 𝒙 を最⼩化するにはどうすればよいか． • 𝑔 𝒙 = 0の⾯上点における ∇𝑓 𝒙 は，領域の内向きでなければならな い．なぜならば，外向きならば領域内部に解があるかもしれなからで ある． • よって，𝑔 𝒙 = 0の場合𝜆 > 0が存在し • ∇𝑓 𝒙 = 𝜆∇𝑔 𝒙 • が成り⽴つ必要がある． • つまり，KKT条件の下で • 𝐿 𝒙, 𝜆 = 𝑓 𝒙 − 𝜆𝑔 𝒙 （符号が変わっていることに注意） • の停留点を⾒つければ良い．