SVM (közepesen mély bevezetés)

Bevezetés

Maximum margin classier

Szupport vektor gépek

Gyakorlatiasabb oldal

SVM

(közepesen mély bevezetés) Adatbányászat és Keresés Csoport, MTA SZTAKI dms.sztaki.hu

Szabó Adrienn

2013. április 4.

Bevezetés



Tartalom Bevezetés Alapötlet Jelölések Maximum margin classier Optimalizálási feladat Szupport vektor gépek Lagrange duális Lineáris SVM levezetés Soft maximum margin classier Nemlineáris SVM: a kernel trükk Gyakorlatiasabb oldal Kernelválasztás Paraméterválasztás Implementációk


Bevezetés




SVM

Az SVM (Suport Vector Machine) Vladimir N. Vapnik és Corinna Cortes többféle gépi tanulási feladatra alkalmazható modellje (1995).

Alapváltozata lineáris kétosztályos szeparálásra képes, de kiterjeszthet®

•

egy- vagy többosztályos szeparálásra

•

nemlineáris szeparálásra és

•

nemlineáris regressziós feladatokra is.[1]

Bevezetés




Motiváció

Mit tud az SVM (amit mások nem ennyire)?

•

jó általánosító képesség

•

gyorsaság

•

nagy dimenziós adatok kezelése

•

akkor is (egészen) használható ha több a dimenzió mint az adatpont

Bevezetés




SVM Alapötlet képekben

Lineárisan nem szeparálható feladat, de jól magasabb dimenzióba küldjük, és ott igen

Bevezetés



Szeparáló sík 3D-ben


Bevezetés




Jelölések (~x, y)

Egy tanítópont: Az

~x

ahol

~x ∈ Rn , y ∈ {+1, −1}

n

pontok dimenziója:

A tanítópontok darabszáma:

l

A tanítóhalmaz:

D = {(~xi , yi )|~xi ∈ Rn , yi ∈ {+1, −1}}

A szeparáló sík normálvektora:

ω ~

A szeparáló sík eltolása:

b

Az

f

Nem egységhosszú!

függvényt keressük amivel címkéket gyárthatunk az új

pontokhoz (amik nem voltak

D-ben):

f : Rn → {+1, −1}

~x

Bevezetés




Maximális szeparálás A szeparáló sík minél messzebb legyen mindkét osztály pontjaitól, és pontosan középen a két osztály ponjtjai között.

1. ábra. A szürkék is megoldják a szeparálást, de a fekete jobb

Bevezetés




Optimalizálási feladat általában Keressük a célfüggvényünk,

φ : Rn → R

széls®értékét:

min φ(~x) ~ x

miközben a megengedett megoldások:

gi (~x) ≥ 0 ahol

gi : Rn → R

lineáris függvények, 0-ra rendezve.

Az optimális megoldás az az

~x∗

lesz amire igaz bármely

~x

esetén hogy

∗

φ(~x ) ≤ φ(~x).

Ha φ is lineáris, akkor lineáris optimalizálási feladatunk van → LP feladat. Ha φ kvadratikus (négyzetes, plusz esetleg lineáris tag is) → QP feladat. Ha φ konvex akkor → konvex optimalizálási feladat.

Bevezetés




Az optimalizálási feladatunk A margót (margin) kell maximalizálni, ami a szupport-síkok távolsága.

Bevezetés




Optimalizáljuk a szeparáló síkot I •

A

φ(~ ω , b)

célfüggvényünket kellene úgy meghatározni, hogy a

maximális margót megkaphassuk az optimalizálással.

•

A korlátokat az fogja jelenteni, hogy a szupport-síkok nem mehetnek túl a tanítópontokon (ω ~

· ~x+ ≥ b + k

Tegyük fel hogy az optimális margó mérete

m∗ ,

ill.

ω ~ · ~x− ≤ b − k ).

és az optimális

szeparáló síkunk egyenlete:

ω ~ ∗ · ~x = b∗

(1)

Ekkor így írhatjuk fel a margót:

m∗ = φ(~ ω ∗ , b∗ ) = max φ(~ ω , b) De mi legyen a

φ

függvényünk?

(2)

Bevezetés



Optimalizáljuk a szeparáló síkot II


Bevezetés




Optimalizáljuk a szeparáló síkot III A szupport-síkokra ezeket írhatjuk fel:

Legyen

ω ~ ∗ · ~x = b∗ + k

(3)

ω ~ ∗ · ~x = b∗ − k

(4)

(x~p , +1) ∈ D és (x~q , −1) ∈ D egy-egy szupport vektor. Ekkor ω ~ ∗ irányába vetítve m∗ -ot kell kapnunk (ábra).

a különbségüket

ω ~ ∗ · (x~p − x~q ) ω ~ ∗ · x~p − ω ~ ∗ · x~q = k~ ω∗ k k~ ω∗ k ∗ ∗ (b + k) − (b − k) 2k = = k~ ω∗ k k~ ω∗ k

m∗ = kxp − xq k cos γ =

Bevezetés



Optimalizáljuk a szeparáló síkot IV


Bevezetés




Optimalizáljuk a szeparáló síkot V m∗ = max

2k k~ ωk

(5)

De inkább minimalizálnánk, ezért átírjuk:

2k k~ ωk k~ ω k2 1 = min = min = min ω ~ ·ω ~ k~ ωk 2k 2k 2k 1 = min ω ~ ·ω ~ 2

m∗ = max

Az utolsó lépésben

k=1

-et választhatunk, mert a skálázásra

invariáns az optimalizálásunk. Tehát a célfüggvényünk:

φ(~ ω ∗ , b∗ ) =

1 ω ~ ·ω ~ 2

(6)

Bevezetés




Optimalizáljuk a szeparáló síkot VI

A korlátok így alakulnak:

ω ~ · x~i ≥ 1 + b

minden

(x~i , yi ) ∈ D

-re, ahol

yi = +1

ω ~ · (−x~i ) ≥ 1 − b

minden

(x~i , yi ) ∈ D

-re, ahol

yi = −1

Ami rövidebben így is írható:

ω ~ · (yi x~i ) ≥ 1 − yi b

minden

(x~i , yi ) ∈ D

Így megvan a kvadratikus optimalizálási feladatunk.

-re

(7)

Bevezetés




Kvadratikus programozás (QP)

A kvadratikus optimalizálási feladatok (QP, Quadratic programming) megoldására vannak ismert módszerek. Erre most nincs id® részletesen, a lényeg hogy viszonylag egyszer¶en QP feladattá alakítható a fenti. Ennek a megoldásnak az a hátránya, hogy elég számításigényes ha sok tanítópontunk van (mindegyik megjelenik korlátként). Segít a helyzeten, ha a feladat duálisát nézzük. És ezt a duális felírást nevezzünk majd SVM-nek.

Bevezetés




Lagrange duális Optimalizálási feladatoknál viszonylag gyakori, hogy egy feladat átfogalmazásával, a duális néz®pontból szebben (vagy csak máshogy) megoldható feladatot kapunk. A Lagrange duális lényege egy mondatban: Ha

M

darab korlátunk van, és

f -nek

keressük széls®értékét (minden

folytonos és deriválható, és a célfüggvény konvex) akkor az eredeti helyett a következ®nek a megoldásával is megtaláljuk a megoldást:

∇f (~x) +

M X

λk ∇gk (~x) = 0

k=1 ahol

∇

a gradiens vektort jelöli, és a

amik pozitívak.[1]

λk

-k a Lagrange együtthatók,

Bevezetés




(*) Lagrange duális részletesebben I Ha keressük egy konvex függvény széls®értékét,

gi (~x) ≥ 0, (i = 1 . . . l)

min~x φ(~x)-et

korlátokkal (primál feladat), akkor ebb®l a

következ® Lagrange optimalizálási feladatot írhatjuk, amely egy képletbe fogja össze a korlátokat és a célfüggvényt:

max min L(~ α, ~x) = max min φ(~x) −

α ~ ,αi ≥0 Itt

~x

α ~ ,αi ≥0

~ x

a primál változó,

α ~

~ x

l X

! αi gi (~x)

(8)

i=1

pedig a duál változó.

A két, ellentétesirányú széls®érték miatt ez szemléletesen azt jelenti hogy

L(~x, α ~)

nyeregpontját keressük. Ha

egy ilyen nyeregpont van.

φ(~x)

konvex, akkor pontosan

Bevezetés




(*) Lagrange duális részletesebben II Bizonyítható, hogy az

(~x∗ , α ~ ∗)

megoldás akkor és csak akkor lesz az

eredeti feladatunknak is széls®értéke, ha teljesülnek a KKT (KarushKuhnTucker) feltételek:

∂L ∗ ∗ (~ α , ~x ) = ~0 ∂~x αi∗ gi (~x∗ ) = 0 ∗

(9) (10)

gi (~x ) ≥ 0

(11)

αi∗ ≥ 0

(12)

Bevezetés




SVM: a max margin klasszikátor duálisa SVM: A maximális margó keresése Lagrange duálissal. Ennek az lesz az el®nye hogy így szebben megoldható a feladat, illetve lehet®vé válik majd a kernel trükk. Tegyük fel hogy van egy lineárisan szeparálható tanítóhalmazunk:

D = {(x~1 , y1 ), (x~2 , y2 ), . . . (x~l , yl )} ⊆ Rn × {+1, −1} és a következ® az optimalizálandó célfüggvényünk:

1 ~ ·ω ~ min φ(~ ω , b) = min ω ω ~ ,b ω ~ ,b 2

(13)

a következ® korlátokkal:

gi (~ ω , b) = yi (~ ω · xi − b) − 1 ≥ 0

(i = 1 . . . l)

(Ez eddig ugyanaz ami már volt a maximum margin klasszikátornál.)

(14)

Bevezetés




(*) SVM levezetés I El®ször így fog kinézni a Lagrange duálisunk, keressük a nyeregpontot:

max min L(~ α, ω ~ , b)

α ~ ,αi ≥0 ω ~ ,b

(15)

ahol

L(~ α, ω ~ , b) = φ(~ ω , b) −

l X

αi gi (~ ω , b)

(16)

i=1

=

l X 1 ω ~ ·ω ~− αi (yi (~ ω · xi − b) − 1) 2 i=1

(17)

=

l l l X X X 1 ω ~ ·ω ~− αi yi ω ~ · ~xi + b αi yi + αi 2 i=1 i=1 i=1

(18)

Bevezetés




(*) SVM levezetés II Most tegyük fel, hogy

ω ~ ∗, α ~∗

és

b∗

az optimális megoldást adják.

Ekkor a KKT feltételek:

∂L ∗ ∗ ∗ (~ α ,ω ~ , b ) = ~0 ∂~ ω ∂L ∗ ∗ ∗ (~ α ,ω ~ ,b ) = 0 ∂b αi∗ (yi (~ ω ∗ · ~xi − b∗ ) − 1) = 0 ∗

∗

yi (~ ω · ~xi − b ) − 1 ≥ 0 αi∗

≥0

(19) (20) (21) (22) (23)

És ha minden igaz, akkor:

max min L(~ α, ω ~ , b) = L(~ α∗ , ω ~ ∗ , b∗ ) = φ(~ ω ∗ , b∗ ) α ~

ω ~ ,b

(24)

Bevezetés




(*) SVM levezetés III Most jön az a trükk, hogy

ω ~

és

b

kiesnek majd, és csak az

α ~

marad

majd, amire optimalizálni kell. Mivel a

ω ~ ∗ , b∗

és

ω ~ ∗ -nál

L nyeregpontjának kell L-t ω ~ szerint deriváljuk (18)-t

megoldás optimális, ezért

lennie. Az els® KKT-t (19) használva 0-vá tesszük:

l X ∂L αi yi ~xi = ~0 (~ α, ω ~ ∗ , b) = ω ~∗ − ∂~ ω i=1

(25)

Ebb®l következik:

ω ~∗ =

l X i=1

αi yi ~xi

(26)

Bevezetés




(*) SVM levezetés IV Most (18)-t

b∗ -nál

b

szerint deriváljuk, a második KKT-t (20)-t használva

ez is 0 kell legyen:

l

X ∂L (~ α, ω ~ , b∗ ) = αi yi = 0 ∂b i=1 Itt kiesett a

b,

de nem baj, ki tudjuk majd számolni ezt is az

(27)

αi -kb®l

(kicsit kés®bb). Végül (18)-be behelyettesítgetve ill. kiejtve ami nulla lett:

Ld (~ α) = L(~ α, ω ~ ∗ , b∗ ) =

l X i=1

l

αi −

l

1 XX αi αj yi yj ~xi · ~xj 2 i=1 j=1

Ebbe a képletbe már belefér majd a kernel trükk... :)

(28)

Bevezetés




A lineáris SVM formálisan A maximális margó megtalálásának duális alakja:

 max Ld (~ α) = max  α ~

α ~

l X

αi −

i=1

A következ® korlátokkal (i

l l 1 XX

2

 αi αj yi yj ~xi · ~xj 

(29)

i=1 j=1

= 1 . . . l): l X

αi yi = 0

(30)

αi ≥ 0

(31)

i=1

Bevezetés




A szupport vektorok Az egyik KKT feltétel (21) szerint:

αi∗ (yi (~ ω ∗ · ~xi − b∗ ) − 1) = 0 Ebb®l vagy az következik hogy

∗

∗

yi (~ ω · ~xi − b ) − 1 = 0.

αi∗ = 0,

tanítópontra. Ekkor a feltétel szerint

ω ~ ∗ · ~xj = b∗ + 1 ∗

vagy az hogy

αj∗ > 0 egy (~xj , yj ) ∈ D yi (~ ω ∗ · ~xi − b∗ ) = 1 :

Tegyük fel hogy

∗

ω ~ · ~xj − b − 1

ha

yj = +1

ha

yj = −1

Vagyis ezek a tanítópontok pont rajta vannak az egyik szupport-síkon.

(Ami meg nincs szupport síkon, annak az α értéke, vagyis Lagrange-együtthatója 0, mert ezek nem befolyásolják a margó méretét.)

Bevezetés




(*) Az eltolás

Még nem mondtuk meg hogy a

b∗ -ot

hogy számoljuk ki. Szerencsére

csak a szupport vektorok számítanak. Válasszunk egyet, például a

+1-es

osztályból

(~xsv+ , +1)-t.

Ekkor:

b∗ = ω ~ ∗ · ~xsv+ − 1 =

l X i=1

αi∗ yi x~i · ~xsv+ − 1

(32)

Bevezetés




A döntési függvényünk A primál feladat az optimális szupport-síkokat határozta meg, amiket a szupport vektorok korlátoznak. A duális megoldásban pedig a szupport vektorokat kaptuk meg, amik a síkokat korlátozzák. De arra szeretnénk majd használni a klasszikátorunkat hogy mondja meg egy pontról hogy a szeparáló sík melyik oldalára esik. Így a lineáris SVM döntési függvénye:

f (~x) = sgn (~ ω ∗ · ~x − b∗ ) = sgn

l X i=1

αi∗ yi ~xi · ~x −

(33)

l X i=1

! αi∗ yi ~xi · ~xsv+ + 1

(34)

Bevezetés




Soft maximum margin classier Eddig megköveteltük hogy a tanítópontok lineárisan szeparálhatóak legyenek. Ami sajnos nem mindig teljesíthet®, gyakaran zajos az adat...

Bevezetés




Soft maximum margin classier Kicsit lazítunk a feltételeken, bevezetjük a slack változókat, amikkel egy-egy tanítópont félreklasszikálhatóságát adjuk meg. Az össz-félreklasszikálhatóság-nak meg megadhatunk egy

C

súlyt

(büntetést). Így az új korlátaink:

yi (~ ω · x~i − b) ≥ 1 − ξi

ahol

i = 1...l

és ξi ≥ 0

(35)

A célfüggvény pedig igyekszik ezeket a slack változókat is minimalizálni a margó maximalizálása mellett:

( min

~ ω ~ ,ξ,b

l

X 1 k~ ω k2 + C ξi 2 i=1

) (36)

Bevezetés




Soft maximum margin classier duálisa Itt az a nagyszer¶ség áll fenn, hogy ha kiszámoljuk, a a célfüggvényünkb®l, és csak egy

C

ξi -k

jól kiesnek

fels® korlát marad bel®lük a

Lagrange együtthatókhoz:



 l X l X 1 max Ld (~ α) = max  αi − αi αj yi yj ~xi · ~xj  α ~ α ~ 2 i=1 i=1 j=1 A korlátok pedig (i

l X

(37)

= 1 . . . l): l X

αi yi = 0

(38)

0 ≤ αi ≤ C

(39)

i=1

Bevezetés




Nemlineáris SVM: a kernel trükk

Az eredeti pontokat magasabb dimenzióba transzformáljuk, remélve hogy ott már lineárisan szeparálhatóak az osztályok

Bevezetés




A kernel trükk I

Eddig (a primál megfogalmazásban) volt egy ilyen képletünk,

ω ~∗

és

~x

közötti skaláris szorzattal:

f (~x) = sgn (~ ω ∗ · ~x − b∗ )

(40)

És most szeretnénk a szeparálást egy magasabb dimenzióban eljátszani, vagyis az

~x-ek

helyett

ϕ(~x)-et

szeretnénk írni.

f (~x) = sgn (~ ω ∗ · ϕ(~x) − b∗ )

(41)

Bevezetés




A kernel trükk II

A kernel-trükk lényege az, hogy ha van egy megfelel® kernelünk:

K(~x, ~y ) = (ϕ(~x), ϕ(~y ))

ϕ-ket számolgatni, meg magasabb K(~x, ~y ) anélkül is számolható, és az SVM

akkor igaziból nem is kell majd a dimenzióba menni, mert a

(42)

duális alakjában ez pont elég is.

Bevezetés




A kernel trükk III A primál döntési függvényünkbe a (ω ~

∗

=

Pl

ω ~∗

duális reprezentációját

∗ xi )) helyettesítve: i=1 αi yi ϕ(~

f (~x) = sgn (~ ω ∗ · ϕ(~x) − b∗ ) = sgn

l X

(43)

! αi∗ yi ϕ(x~i ) · ϕ(~x) − b∗

(44)

i=1

= sgn

l X

! αi∗ yi K(x~i , ~x)

∗

−b

(45)

i=1 Ha okosan választunk

ϕ

függvényt, akkor a döntési függvényünk

ugyanolyan egyszer¶ lesz mint a lineáris esetben; csak annyi lesz a különbség, hogy a skaláris szorzat helyett a kernelt kell írni.

Bevezetés




Kernel függvények I De egy

K : Rn × Rn → R(~x, ~y )

függvény mikor olyan, hogy jó lesz

ϕ úgy hogy K(~x, ~y ) = (ϕ(~x), ϕ(~y ))

kernelnek, vagyis mikor létezik hozzá

?

Bizonyítható, hogy akkor, ha pozitív denit:

l X l X

θi θj K(~xi , ~xj ) ≥ 0

(46)

i=1 j=1

A kernel-függvény tulajdonképpen a két vektor hasonlóságát méri.[6]

Bevezetés




Kernel függvények II Kernel functions must be continuous, symmetric, and most preferably should have a positive (semi-) denite Gram matrix. Kernels which are said to satisfy the Mercer's theorem are positive semi-denite, meaning their kernel matrices have no non-negative Eigen values. The use of a positive denite kernel insures that the optimization problem will be convex and solution will be unique. However, many kernel functions which aren't strictly positive denite also have been shown to perform very well in practice (sigmoid kernel).[5]

Bevezetés




Néhány kernel függvény Hogy melyiket érdemes választani az mindig az adott feladattól/adathalmaztól függ.

Gauss-kernellel.)

(Ha nincs jobb ötletünk, kezdjük a

Polinomiális (homogén)

K(~xi , ~xj ) = (~xi · ~xj )d

Polinomiális (inhomogén)

K(~xi , ~xj ) = (~xi · ~xj + 1)d

Gauss (RBF)

K(~xi , ~xj ) = exp(−γk~xi − ~xj k2 ),

ahol

néha úgy paraméterezve hogy γ = 1/2σ2

Hiperbolikus tangens

γ>0

,

K(~xi , ~xj ) = tanh(κ~xi · ~xj + c)d ,

ahol κ > 0 és c < 0, plusz egyéb feltételek.

Bevezetés




Paraméterválasztás Az SVM teljesítménye függ a választott kernelt®l, a

C

puhasági

paramétert®l, és az adott kernel-függvény paraméterekt®l is. Például Gauss-kernel esetén a

γ

paraméter és a

C

legjobb

kombinációját egy grid-kereséssel szokás meghatározni, exponenciálisan növ® értékekkel, pl:

C ∈ {2−5 , 2−3 , . . . , 213 , 215 } γ ∈ {2−15 , 2−13 , . . . , 21 , 23 } Minden paraméter-párt CV-val kiértékelünk, és a legjobbat kiválasztjuk. Aztán a teljes tanítóhalmazt és a választott paramétereket használva építjük fel a klasszikáló modellünket.

Bevezetés




Implementációk LIBLINEAR

http://www.csie.ntu.edu.tw/~cjlin/liblinear/ LIBLINEAR is a linear classier for data with millions of instances and features

LIBSVM

http://www.csie.ntu.edu.tw/~cjlin/libsvm/ LIBSVM is an integrated software for support vector classication, regression and distribution estimation

SVMlight

http://svmlight.joachims.org/ SVMlight is an implementation of Vapnik's Support Vector Machine for the problem of pattern recognition, for regression, and for learning a ranking function.

WEKA

http://www.cs.waikato.ac.nz/ml/weka/ Ez azért kényelmes mert sok más klasszikátor is van benne; amúgy a LIBSVM-et wrappeli.

Bevezetés



Special Thanks

Különleges köszönet Fekete Zsoltnak és

Pálovics Robinak


Bevezetés




Hivatkozások I Wikipedia, Support vector machine,

http://en.wikipedia.org/wiki/Support_vector_machine,

2013. 03. 13. 22:35

Wikipedia, Optimization problem,

http://en.wikipedia.org/wiki/Optimization_problem,

2013. 03. 26. 21:51

Wikipedia, Mathematical optimization,

http://en.wikipedia.org/wiki/Mathematical_optimization,

2013. 04. 01. 22:03

Lutz Hamel, Knowledge discovery with support vector machines, John Wiley & Sons, Inc., Hoboken, New Jersey, 2009

César Roberto de Souza, Science, computing and machine learning. Blog, http: //crsouza.blogspot.hu/2010/03/kernel-functions-for-machine-learning.html,

2013. 04. 02. 14:47

Bevezetés




Hivatkozások II

Altrichter Márta, Horváth Gábor, Pataki Béla, Strausz György, Takács Gábor, Valyon József, Mesterséges Intelligencia Elektronikus Almanach, 6. fejezet - Kernel módszerek, http://project.mit.bme.hu/mi_almanach/books/neuralis/ch06

2013. 03. 27. 18:32

SVM (közepesen mély bevezetés)

Recommend Documents