サポートベクターマシン

1.2K Views

February 13, 23

スライド概要

サポートベクタマシンの資料です.サポートベクターマシンは線形分類器であることを忘れないように.カーネル法は別の機会に.

profile-image

コンピュータを使って色々計算しています.個人的な技術に関するメモと講義資料が置いてあります.気が向いた時に資料を修正しています. 公立小松大学臨床工学科准教授 https://researchmap.jp/read0128699

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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

2.

導⼊

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

サポートベクターマシン

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

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

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

82 9 3 𝝓 𝒙2 ;$
𝒘

=

<
𝒘

• つまり, argmax𝒘,$ min
7

82 𝒘3 𝝓 𝒙2 ;$
𝒘

= argmax𝒘,$

<
𝒘

である.

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

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

<
.

𝒘

.

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

19.

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

20.

双対表現 $ • 𝒘 = ∑$ 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

21.

双対表現 < @ @ • 𝐿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 • を最⼤化する 𝒂を探すことである.

22.

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

23.

サポートベクタ • 𝑎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

24.

バイアスパラメタ𝑏 • 𝒂が求まれば,バイアスパラメタ𝑏が求まる. • サポートベクタ𝒙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 はサポートベクタの数とする.

25.

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

26.

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

27.

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

28.

おまけ:ラグランジュ関数の最⼤化と最⼩化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 𝒂 𝒘,$ 𝒂 𝒂

29.

ソフトマージン

30.

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

31.

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

32.

スラック変数 • マージン内であるが,データが正しく分類されている場合 • 𝑡" = 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

33.

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

34.

⽬的関数とラグランジュ関数 • ソフトマージン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のときのみ(誤分類なくマー ジンの外側にデータ点があるとき)最⼩となるため.

35.

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

36.

ラグランジュ関数の変形 " • 𝐿 𝒘, 𝑏, 𝒂, 𝝁 = > 𝒘 > $ % + 𝐶 ∑$ 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 • これをラグランジュ関数に代⼊する.

37.

ラグランジュ関数の変形 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 • となる. !() !()

38.

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

39.

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

40.

サポートベクタ • 𝑎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のサ ポートベクタは誤分類されている.

41.

パラメタ𝒃 • 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

42.

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

43.

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

44.

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

45.

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

46.

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

47.

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

48.

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

49.

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