1

Support Vector Machines (Masinile cu suport vectorial )

Masinile cu suport vectorial reprezint o metod de clasificare introdus n anul 1992 de

ctre Boser, Guyon si Vapnik . Clasificatorul care foloseste aceast tehnic este folosit

att n bioinformatic ct si n alte discipline, datorit acuratetei ridicate si a abilittii de a

se descurca bine atunci cnd ntlneste date cu multe dimensiuni, cum ar fi expresii ale

genelor, dar si pentru flexibilitatea n modelarea diferitelor surse de date.

Masinile cu suport vectorial apartin unei categorii generale de metode cu

nucleu. O astfel de metod este un algoritm care depinde de date doar prin produse

scalare. Cnd este necesar, produsul scalar poate fi nlocuit de o functie nucleu, care

calculeaz acest produs scalar ntr-un posibil spatiu de caracteristici multidimensional.

Aceast abordare are dou avantaje. Primul dintre ele este capacitatea de a genera decizii

neliniare asupra limitelor folosind metode construite pentru clasificatorii liniari. Al doilea

avantaj l constituie faptul c folosirea functiilor nucleu permit utilizatorului s aplice un

clasificator datelor care nu au o reprezentare a spatiului vectorial de dimensiune fix.

Printre primele exemple de astfel de date n bioinformatic se numr ADN-ul si

structura proteinelor.

Folosirea masinilor cu suport vectorial necesit o ntelegere n profunzime a

modului n care acestea functioneaz. Cnd se antreneaz un algoritm de masini cu suport

vectorial, practicantul trebuie s ia un anumit numr de decizii importante: cum vor fi

datele preprocesate, ce fel de nucleu se va folosi si, n final, setarea parametrilor att

pentru nucleu ct si pentru masinile cu suport vectorial. Alegerile uniforme pot conduce

la o performant sczut.

2.2 Definitia formal a problemei

Masinile cu suport vectorial construiesc un hiperplan sau o multime de hiperplane

ntr-un spatiu cu mai multe dimensiuni sau cu un numr infinit de dimensiuni, care pot fi

utilizate pentru clasificare, regresie sau alte sarcini. Intuitiv, o bun separare este obtinut

de hiperplanul care are cea mai mare distant pn la cea mai apropiat dat de

antrenament reprezentat indiferent de clasa din care aceasta face parte (numit si marj

2

functional), avnd n vedere c n general cu ct este mai mare marja, cu att este mai

redus eroarea de generalizare a clasificatorului.

Chiar dac problema initial este specificat ntr-un spatiu finit dimensional, se

ntmpl de multe ori ca multimile care trebuie distinse s nu fie separabile liniar n acel

spatiu. Din acest motiv a fost propus ca spatiul finit original s fie potrivit ntr-unul mai

mare ca dimensiune, separarea fiind probabil mai usor de fcut n acest nou spatiu. Pentru

a pstra un efort computational rezonabil, potrivirile folosite de schemele masinilor cu

suport vectorial sunt construite n asa fel nct s poat asigura c produsele scalare vor

putea fi calculate cu usurint n ceea ce priveste variabilele din spatiul original, prin

definirea unei functii nucleu selectate s satisfac cerintele problemei.

Hiperplanele din spatiul cu mai multe dimensiuni sunt definite prin multimi de puncte al

cror produs scalar cu un vector din acel spatiu este constant. Vectorii care definesc

hiperplanurile pot fi alesi ca fiind combinatii liniare cu parametrii ai imaginilor

vectorilor de caracteristici care exist n baza de date. Folosind aceast alegere a

hiperplanului, punctele din spatiul caracteristicilor care sunt potrivite n hiperplan sunt

definite prin relatia . n cazul n care devine mai mic

pe msur ce creste si mai mult fat de , fiecare element din sum msoar gradul

de apropiere al punctului de test fat de punctul corespunztor din baza de date . n

aceste conditii, suma nucleelor poate fi utilizat n vederea msurrii apropierii relative al

fiecrui punct de test n comparatie cu punctul original apartinnd uneia dintre multimile

ce trebuie distinse.

SVM sunt modele de invatare supervizata cu algoritmi de invatare asociati care

analizeaza date si recunosc tipare (patterns), folositi in clasificare si regresie. Fiind dat un

set de date de antrenare, fiecare observatie apartinand unei clase din doua clase posibile,

un algoritm SVM construieste un model care asigneaza noi exemple unei clase sau alteia.

Modelarea matematica a SVM

Consideram o populatie ale carei obiecte sunt studiate din punctul de vedere a n

caracteristici (atribute). Un obiect este reprezentat de un punct nn Rxx ),...,( 1 ,

nxx ,...,1 fiind valorile celor n caracteristici pentru obiectul studiat.

3

Populatia este impartita in doua clase 21, EE (disjuncte).

Punerea problemei

Se fac r observatii (masuratori) asupra unui esantion din populatie. Dupa cum am

vazut, observatiile sunt reprezentate de puncte din nR .

Datele de intrare obtinute (numite si date de antrenare, de instruire) se impart in doua

clase 11 ED , 22 ED .

( 21 DDD =datele de intrare)

Se pune problema clasificarii unor date noi: pe baza unui algoritm, pornind de la datele

de antrenare, sa se spuna daca o observatie noua este in 1E sau in 2E .

D=spatiul intrarilor

Spatiul intrarilor este linear separabil daca exista un hiperplan H al lui nR ce separa 1D si

2D .

Dificulti n rezolvarea problemelor de clasificare 1. Pentru clasificare se pot utiliza mai muli separatori ai claselor.

2. Spatiul intrarilor nu este liniar separabil.

4

Support vector machines (SVM) sunt modele de invatare supervizata ce raspund

problemei de clasificare de mai sus.

Metoda SVM liniara

SVM =linear separabil daca spatiul intrarilor este linear separabil. Presupunem ca datele de intrare sunt linear separabile.

Observatie: Pot exista mai multe hiperplane ce separa 1D de 2D .

- 1H nu separa planele

- 2H le separa la o distanta mica intre clase

- 3H le separa la o distanta maxima

Alegerea hiperplanului separator H se face pe baza urmatorului criteriu:

Cu cat hiperplanul H este la o distanta mai mare de multimile de date initiale 1D si

2D , cu atat clasificarea noilor observatii (realizata de hiperplanul H) va fi mai buna

(mai vizibila).

5

Observatie Fiecare hiperplan ce separa 1D de 2D conduce la o clasificare distincta a

noilor observatii.

Vom formaliza ideile expuse mai sus.

Multimea datelor de intrare este pusa sub forma )},(),...,,{( 11 rr yxyx .

ix este un vector input din nR

}1,1{iy este o eticheta a clasei lui ix (class label)

1iy : clasa pozitiva ( 1D )

1iy : clasa negativa ( 2D )

Interpretare: daca H: 0 bxw este un hiperplan ce separa 1D si 2D , atunci

01

01

bxwdaca

bxwdacayi

Consideram un hiperplan separator H: 0 bxw si alte doua hiperplane separatoare:

bxwH :

bxwH :

Observatie: H, HH , sunt hiperplane paralele.

Calculam distantele intre aceste hiperplane:

ww

bbHHdd

),(

bxwH

bxwH

:

:

ww

bbHHdd

),(

bxwH

bxwH

:

:

ww

bbHHdd

2)(),(

6

HH , sunt echidistante fata de H

ddd = margin

Observatie: Putem considera (prin impartire la ) ca HH , sunt de forma:

1:

1:

bxwH

bxwH.

In acest caz: w

d1

, w

d1

, w

d2

.

Atunci criteriul enuntat mai sus ne spune ca trebuie sa il alegem pe H (adica pe w si

pe b) astfel incat w

d2

sa fie maximizata.

Se ajunge la urmatoarea problema de optimizare patratica.

Sa se determine nRw si Rb astfel incat

(1)

)(1,1

)(1,1

2max

2

1

Ddinxydacabxw

Ddinxydacabxw

w

iii

iii

Problema (1) este echivalenta cu:

(2)

ripentrubxwy

w

ii ,...,1,1)(

2min

2

Reamintim: Conditiile Kuhn-Tucker pentru problema de optimizare:

( RRff ni :, functii convexe si diferentiabile)

nkx

rixf

xf

k

i

,...1,0

,...,1,0)(

)(min

sunt:

rixf

ri

rixf

nkx

L

ii

i

i

k

,...,1,0)(

,...,1,0

,...1,0)(

,...,1,0

unde ),...,( 1 nxxx si

r

i

iirn xfxfxxL1

11 )()(),...,;,...,(

7

Scriem problema (2) sub forma:

(3)

ribxwy

w

ii

n

k

k

,...,1,0)(1

2

1min

1

2

Scriem lagrangeanul:

),...,;,,...,(),,( 11 rn bwwLbwL

n

k

r

i

iiik bxwyw1 1

2 )](1[2

1

n

k

r

i

n

k

ikkiik bxwyw1 1 1

2 )](1[2

1

),...,( 1 inii xxx

Scriem conditiile Kuhn-Tucker pentru problema de optim (3)

r

i

ikiik

k

xyww

L

1

0 , k=1,,n [

r

i

iii xyw1

0 ] scriere vectoriala

r

i

ii yb

L

1

0

rii ,...,1,0

ribxwy ii ,...,1,0)(1

ribxwy iii ,...,1,0)](1[

Rescriem aceste conditii:

(4)

ribxwy

ribxwy

y

xyw

iii

ii

i

r

i

ii

r

i

iii

,...,1,0]1)([

,...,1,01)(

0

0

0

1

1

conditii necesare si suficiente conform

observatiei ulterioare

Observatie In general, conditiile Kuhn-Tucker (4) sunt necesare. In cazul unei probleme

de optim, in care functia obiectiv este convexa si restrictiile sunt liniare, conditiile Kuhn-

Tucker sunt si suficiente. In cazul problemei (3), aceste conditii sunt indeplinite.

Deci (4) ne da conditii necesare si suficiente pentru optimul problemei (3).

Observatie Daca 0i atunci 1)( bxwy ii (din ultima egalitate (4)). Aceasta

inseamna ca Hxi sau Hxi .

Asemenea puncte ix se numesc vectori suport.

Se considera acum problema duala: este o problema de maxim in care functia obiectiv

este chiar lagrangeanul.

8

Mai intai trebuie sa exprimam lagrangeanul numai in functie de r ,...,1 .

Scriem lagrangeanul sub forma:

r

i

iii bxwywbwL1

2)](1[

2

1),,(

r

i

r

i

r

i

iiiiii ybxwyww1 1 1

)(2

1

r

i

r

i

iiii xwyww1 1

)(2

1

(

r

i

ii y1

0 )

Cum

r

i

iii xyw1

si produsul scalar este linear in fiecare argument

r

i

r

j ri

jijijijjjiii xxyyxyxyww1 1 1

)()()(

r

j

r

j

jijjijjji xxyxxyxw1 1

)()(

r

i

r

i

r

j

r

ji

jijijijijjiiiii xxyyxxyyxwy1 1 1 1,

)())(()(

Inlocuind mai sus

(5)

r

i

r

ji

jijijiirD xxyybwLL1 1,

1 )(2

1),,(),...,(

Problema duala va fi:

(6)

ri

y

L

i

r

i

ii

rD

,...,1,0

0

),...,(max

1

1

Dupa ce rezolvam problema de optim (2), daca r ,...,1 este solutia optima, calculam pe

r

i

iii xyw1

.

Calculul lui b

Fie SV=multimea vectorilor suport (: corespunzatori 0i )

Atunci

r

i

iii xyw1

= SVx

iii

i

xy [ 0 ii SVx ]

Fie kx un vector suport. Conform ultmei relatii din (4):

0]1)([ bxwy kkk

Cum 0k , rezulta

9

01)( bxwy kk

1)( bxwy kk | ky

kkk ybxwy )(2

kkk ybxwy 12

Deci kk xwyb

Clasificarea noilor observatii

Fie RbRw n , determinati prin rezolvarea problemei de optim. Consideram functia

RRf n :

SVx

iii

i

bxxybxwxf )()(

Daca nRz este o noua observatie, calculam sign f(z)

sign f(z)=1 1Dz partea pozitiva

sign f(z)=-1 2Dz partea negativa

f se numeste functie clasificator.

Cazul neliniar

Consideram cazul cand datele de intrare )},(),...,,{( 11 rr yxyx nu pot fi separate printr-un

hiperplan. In acest caz se procedeaza in doi pasi:

se transforma spatiul initial al datelor (input space) intr-un alt spatiu (feature space), in care datele vor fi separabile printr-un hiperplan.

se aplica formularile si tehnicile din cazul liniar X=input space, F=feature space

mn RFRX , , cu mn

FX : aplicatie neliniara

Prin transformarea , datele initiale )},(),...,,{( 11 rr yxyx se transforma in

)}),((),...,),({( 11 rr yxyx .

Obs. In cazul de mai sus, feature space X are aceeasi dimensiune 2 cu input space F. In

general, F are dimensiune mai mare ca X.

Pentru datele transformate )}),((),...,),({( 11 rr yxyx problema de minim

(corespunzatoare lui (3)) se scrie

(7)

0))((1

2min

bxwy

w

ii

10

Recapitulam, pentru problema (7), etapele algoritmului prezentat in cazul liniar.

Etapa 1

Se considera lagrangeanul problemei duale (cf. (8))

(8)

r

i

r

ji

jijijiirD xxyyL1 1,

1 ))()((2

1),...,(

si problema duala:

(9)

0

0

),...,(max

1

1

i

n

i

ii

nD

y

L

Se calculeaza solutia optima n ,..,1 a problemei (9)

Etapa 2

Se calculeaza vectorul

(10)

ir

i

iii xyw1

)(

Etapa 3

Se calculeaza numarul real (pentru un 0k )

r

i

kiiikkk xxyyxwyb1

)())(()(

(11)

r

i

kiiik xxyyb1

)()(

Se formeaza functia de separare

bxwxf )()(

Cf. (10) si (11) functia de separare se mai scrie

r

i

kiii

r

i

kiii xxyyxxyxf11

))()(()())(()(

r

i

kkiii

r

i

iii yxxyxxy11

))()(())()((

De unde

(12)

r

i

kkiiii yxxxxyxf1

)]()()()([)(

Observatie importanta Inspectand formulele (8), (11) si (12), se vede ca nu este

nevoie sa cunoastem valorile rixi ,...,1),( , ci numai produsele scalare

)()( ji xx si )()( xxi .

Functia de transformare poate sa conduca la date de dimensiuni mari, deci la calcule costisitoare.

Pe baza observatiei precedente putem introduce notiunea de nucleu.

O functie RRRK nn : este nucleu al functiei mn RR : daca pentru orice doi

vectori nRzx , , )()(),( zxzxK .

Daca K este nucleu al lui atunci formulele (8), (11) si (12) se scriu

11

(8)

r

i

r

ji

jijijiirD xxKyyL1 1,

1 ),(2

1),...,(

(11)

r

i

kiiik xxKyyb1

),(

(12)

r

i

kkiiii yxxKxxKyxf1

)],(),([)( ( 0k )

Conform (8), (12), daca K este un nucleu al functiei atunci procedam astfel

(I) Se determina solutiile optime r ,...,1 ale problemei de maxim

(13)

ri

y

L

i

r

i

ii

rD

,...,1,0

0

),...,(max

1

1

unde ),...,( 1 rDL are forma (8).

(II) Cu r ,...,1 determinate la I, se formeaza functia clasificator f data de (12).

Daca nRx este o noua observatie atunci

sign f(x)=1 x se afla in partea pozitiva 1D

sign f(x)=-1 x se afla in partea negativa 2D

Exemplu Se considera transformarea 32: RR , )2,,(),( 212

2

2

121 xxxxxx .

Luam functia RRRK 22: , 2)(),( zxzxK produs scalar

Fie ),( 21 xxx , ),( 21 xzz . Atunci 2

2211

2 )()(),( zxzxzxzxK 2

2

2

22211

2

1

2

1 2 zxzxzxzx

)2,,()2,,( 212

2

2

121

2

2

2

1 zzzzxxxx

)()( zx

Rezulta ca functia K este nucleu al lui .

Apendix1 . Elemente de geometrie a lui nR

Fie nRyx , ,

n

i

ii yxyx1

produsul scalar al vectorilor ),...,(),,...,( 11 nn yyyxxx

n

i

ixxxx1

2, norma lui x

n

i

ii yxyxyxd1

2)(),( distanta dintre x si y

Hiperplan in nR : o multime de forma }|{ bxaRxH n unde nn Raaa ),...,( 1 ,

Rb

12

bxa

n

i

ii bxa1

ecuatia hiperplanului H

Cazuri particulare

a)n=2 bxaxa 2211 (in plan, hiperplanele sunt dreptele)

b) n=3 bxaxaxa 332211 (in plan, hiperplanele sunt planele)

Fie hiperplanul H: bxa si punctul nn Rppp ),...,( 1

Distanta de la p la hiperplanul H: ),(min),( xpdHpdHx

Proppozitia 1 a

bpa

a

bpaHpd

n

i

ii

1

),(

Definitie Doua hiperplane bxaH :1 , cxaH :2 se numesc hiperplane paralele.

Propozitia 2 Fie bxaH :1 , cxaH :2 doua hiperplane paralele.

a

cbHqdHpdHqp

),(),(, 212

Demonstratie

a

bc

a

bpaHpd

),( 1

a

bc

a

bqaHqd

),( 1

qacpaHqp 2, (vezi Figura A)

Conform Propozitiei 2, toate punctele de pe 2H sunt echidistante fata de hiperplanul 1H :

anume la distanta a

cb .

Prin definitie, distanta dintre hiperplanele 1H si 2H este a

cbHHd

),( 21 .

Fie nRDD 21, , 21 DD . Spunem ca hiperplanul H: bxa separa multimile

21, DD daca

}|{1 bxaRxDn

}|{2 bxaRxDn Figura B

13

Figura A

Figura B

1x

2x 1H

2H

),( 1Hqd

),( 1Hpd p

q

1x

2x

H

1D

2D

14

APENDIX2

Clasificare nonlineara

Algoritmul initial propus de Vapnik in 1963 era un clasificator liniar. In 1992, Bernhard

E. Boser, Isabelle M. Guyon si Vladimir N. Vapnik au propus o metoda de a crea

clasificatori neliniari aplicand abordarea kernel pentru a determina distanta maxima

dintre hiperplane. Algoritmul rezultat este similar, numai ca produsul scalar este inlocuit

prin o functie kernel neliniara. Hiperplanul se transforma intr-un spatiu multidimensional

al atributelor, numit feature space. Functia kernel poate fi:

Polinomiala (omogena): djiji xxxxk )(),(

Polinomiala (neomogena): djiji xxxxk )1(),(

Gaussiana (Gaussian Radial Basis): )exp(),(2

jiji xxxxk , pentru >0.

Uneori se considera 22

1

.

Tangenta hiperbolica: )tanh(),( cxlxxxk jiji , pentru anumiti l>0 si c

15

Pentru a construi un hiperplan optim, SVM foloseste un algoritm de antrenare iterativ,

care minimizeaza o functie eroare. Dupa forma functiei eroare, modelele SVM se impart

in 4 grupe distincte:

Classification SVM Type 1 (= C-SVM classification)

Classification SVM Type 2 (= nu-SVM classification)

Regression SVM Type 1 (= epsilon-SVM regression)

Regression SVM Type 2 (= nu-SVM regression)

In continuare rezumam fiecare model.

Classification SVM Type 1

Antrenarea presupune minimizarea functiei eroare:

N

i

i

T Cww12

1

Cu restrictia

ii

T

i bxwy 1))(( , Nii ,1,0

C=constanta

w =vectorul coeficientilor

b=constanta

=parametri pentru date inseparabile

N=nr. de observatii ale setului de antrenare

iy =1 =etichetele claselor

ix =variabilele independente

Functia kernel transforma datele din inputuri (independente) in spatiul atributelor (feature

space).

CLASSIFICATION SVM TYPE 2

Se minimizeaza functia eroare:

N

i

i

T

Nww

1

1

2

1

Cu restrictia

ii

T

i bxwy ))(( , Nii ,1,0 , 0

Intr-o regresie SVM, trebuie sa estimam dependenta functionala intre variabila dependenta

y si o multime de variabile independente x. Presupune, ca alte probleme de regresie, ca

16

relatia dintre variabilele independente si dependente este data de o functie determinista f la

care se adauga un zgomot.

Regresie SVM

y=f(x)+zgomot

Scopul este de a gasi o forma functionala pentru f care poate face predictii corecte asupra

unor noi observatii. In functie de forma functiei eraore, exista doua tipuri de modele de

regresie SVM.

REGRESSION SVM TYPE 1

Functia eroare este:

N

i

N

i

ii

T CCww1 1

*

2

1

pe care o minimizam sub restrictiile: *)( iii

T ybxw

iii

T

i bxwy )(

Niii ,1,0,*

REGRESSION SVM TYPE 2

Functia eroare este:

N

i

ii

T

NCww

1

* ))(1

(2

1

pe care o minimizam sub restrictiile: *)( iii

T ybxw

iii

T

i bxwy )(

Niii ,1,0,* , 0

Clasificare nonlineara