Support Vector Machines

Agenda

Alcuni richiami matematici– vettori, norme e prodotti interni – punti linearmente separabili e iperpiani di separazione

Generalità sulle SV– Il problema e alcune definizioni: margini di un iperpiano,

iperpiano canonico– due ragioni di carattere teorico per supportare la validità

delle SVM– La formulazione del programma (matematico) per la

soluzione al problema

Premessa

Considereremo punti o vettori su

Per facilità di rappresentazione faremo quasi sempre riferimento a R2

In R2 (geometricamente, nel piano) i punti sono rappresentati da coppie ordinate (x1, x2) di numeri reali (coordinate)

Tali punti sono facilmente rappresentabili attraverso segmenti orientati, caratterizzati da:

– direzione, verso, lunghezza

w

P

RxRx…xR = Rn

n volte

Vettori in R2

Sull’insieme di questi punti possiamo eseguire due operazioni fondamentali

– Addizione

– Moltiplicazione per un numero reale (riscaliamo il punto! )

Alcuni concetti utili per iniziare

P: (x1,x2)Q: (x3,x4)

P+Q: (x1+x3,x2+x4)

2P: (2x1,2x2)

P: (x1,x2)

- P: (-x1,-x2)

Il prodotto interno in Rn

Il prodotto interno tra due vettori in Rn è il numero reale

– Alcune proprietà

Alcuni concetti utili per iniziare

∑=

=⋅≡n

iii yx

1

', yxyx

0, .4

,yx, e ,yx, .3

,,zyx, e ,,zy,x .2

,, .1

≥

==

+=++=+

=

xx

yxyx

zxyxzyzx

xyyx

λλλλ

La norma in Rn

La norma di un vettore in Rn (o anche modulo, lunghezza) è il numero reale non negativo

– Alcune proprietà

Vettore unitario

∑=

=⋅≡n

iiixxxx

12

'x

Alcuni concetti utili per iniziare

||x|| 0xx

xx

yxyx

≠>=

+≤+

se 0|||| 3. |||||||| .2

|||||||||||| .1λλ

||||w

w 0w ≠se

Norma e prodotto interno

Geometricamente l’angolo sotteso da due vettori in R2 è dato da:

22 ||||||||

,cos

yx

yx=ϑ

ϑ

xxxxxxn

iii ,'

12

==⋅≡ ∑=

x

Proiezione di un vettore

ϑ

v

Proiezione di v su u

u

)cos||(|| ϑvu =v

uv

Nota

ϑ

v

u

v

u

ϑv

u

0, 90 == uvϑ

0, 90 >< uvϑ 0, 90 <> uvϑ

ϑ

Rette e iperpiani

Una retta r che passa per l’origine in R2 può essere definita assegnando un vettore w = (w1, w2)’ ad essa ortogonale

Tutti i punti (vettori)

x = (x1,x2)

sulla retta sono ortogonali a w Quindi

ww

wwx

0', 2211 =+=>=< xwxwxwxw

Alcuni concetti utili per iniziare

Iperpiano in R2

Alcuni concetti utili per iniziare

w

Un iperpiano h in R2

con il vettore w ad essoortogonale

Nota: tutti i punti su h sono tali che <x, w> = 0

h

x0

x

Iperpiano in R2

w

h

x0

x

Nota: l’iperpiano determina 2 semispazi !

Punti linearmente separabili

Alcuni concetti utili per iniziare

classificatore

Classe +1

Classe -1

Iperpiani in Rn

Generalizziamo in più dimensioni (nello spazio euclideo !):

– ogni iperpiano h (di dimensione (n-1)) che passa per l’origine di Rn è caratterizzato dall’equazione

– Se l’iperpiano non passa per l’origine

– Un iperpiano è quindi un insieme di punti espresso in questo modo

0, >=< xw

}0,|{ =+>< bxwx

0, =+>< bxw

Alcuni concetti utili per iniziare

Nota...

I vettori sull’iperpiano si proiettano tutti nello stesso punto I punti da un lato dell’iperpiano sono tali che

I punti dall’altro lato sono tali che

w

x

h

0, >+>< bxw

0, <+>< bxw

Generalità sulle SVM

Classe di metodi che– sulla base di argomentazioni teoriche derivanti

dalla “teoria statistica dell’apprendimento”– per mezzo di un problema di programmazione

matematica– trovano l’iperpiano separatore (il migliore) per

classificare un insieme di punti (linearmente separabili)

Assunto che i punti siano linearmente separabili

Intuitivamente

Classe +1

Classe -1

Ci sono diversi iperpiani separatori !

Var1

Var2

Ognuno di questi va bene !Ma qual è il migliore ?

Intuitivamente

Classe +1

Classe -1

Idea …. prendiamo un iperpiano e ne allarghiamo il margine … fino a toccare un punto !

Consideriamo l’ampiezza della “zona verde”

Var2

Var1

Nota: all’interno della “zona verde” non ci sono punti !Nota: La “zona verde” è anch’essa racchiusa tra 2 iperpiani

Intuitivamente

Classe +1

Consideriamo il margine di un altro iperpiano

Var2

Var1 Questa volta la “zona verde” è decisamentepiù ampia

Intuitivamente

Una domanda cui rispondere...ad intuito

– Se riuscissimo a separare i dati con un largo margine (quell’ampia “zona verde”) avremmo ragione di credere che (assunto che i punti siano generati sempre dalla stessa “regola” !) il classificatore (l’iperpiano) sia (in un certo senso) “più robusto” tanto da avere una migliore generalizzazione ?

Un prova per il nostro intuito !

Var2

Var1

Il classificatore f divide correttamente (fino ad ora) i punti sul quale è stato addestrato ...

f

Una prova per il nostro intuito !

Var2

Var1 AIl nuovo punto estrattodi cui conosco la posizione (ma non la classe) sarà classificato correttamente da f ?

f

In questa posizione comparirà un nuovo punto di cui non conosciamo la classe

Una prova per il nostro intuito !

Var2

Var1

Questa volta con successiveestrazioni B e C cadonosempre piùvicino (ad f) ...

CB

Una prova per il nostro intuito !

Var2

Var1

E se ci chiedessero di scommettere ?

CB

A

ATTENZIONE: il nostro intuito non sbaglia !

Con la teoria statistica dell’apprendimento si dimostra che più allarghiamo il margine più l’iperpiano generalizza ( VC dimension)

Non ci resta che scrivere un algoritmo per trovare l’iperpiano di separazione di massimo margine

– Lo faremo per mezzo della programmazione matematica

Le SVM

Supponiamo, quindi, di avere un insieme di punti di training

Ad ogni xi è associata la rispettiva classe di appartenenza yi

I punti sono linearmente separabili

– Ma questo lo possiamo anche scrivere in un solo vincolo

n)1,..,(i 0),( =>+bxwy ii

{ }),),....(,(),,( 2211 nn yxyxyxS ≡

}1,1{ +−∈iy

1 t.c.gli per tutti 0, +=>+ ii ybxw1 t.c.gli per tutti 0, −=<+ ii ybxw

IL MIGLIORE !Quello che separa meglio i punti negativi da

quelli positivi

Obiettivo !

Noi cerchiamo tra gli iperpiani separatori

– O equivalentemente cerchiamo tra le funzioni (di decisione) lineari associate

Dove g è

),()(, bgh b += xwxw

(w,b)

⎩⎨⎧

−>+

=altrimenti 1

0 se 1)(

zzg

Troviamo prima una formula per l’ampiezza della “zona verde”

Sia d+ (d-) la distanza tra l’iperpiano separatore e il punto positivo (negativo) più vicino

Var2

Var1

dd

Def: i margini di un iperpiano- Margine funzionale

- Margine geometrico

Definizione: margine funzionale

Il margine funzionale di un punto (xi,yi) rispetto all’iperpiano (w, b) è definito come segue:

Il valore minimo

– viene definito come il margine funzionale dell’iperpiano rispetto al training set S

),(ˆ by iii += xwγ

iniγρ ˆminˆ

,...,1==

Note sul margine funzionale

Se il punto x+ è tale che y = +1 perchè il margine funzionale sia grande è necessario che abbia un grande valore positivo la quantità

Se il punto x- è tale che y = -1 perchè il margine funzionale sia grande è necessario che abbia un grande valore negativo la quantità

b++xw,

),(ˆ by iii += xwγ

Note sul margine funzionale

Se la classificazione è OK ! (Verificare per credere) !

Quindi un ampio margine funzionale ci da una certa “speranza” sulla nostra previsione !

Ma utilizzare semplicemente causa dei problemi infatti ....

),(ˆ by iii += xwγ

0ˆ >iγ

γ̂

Note sul margine funzionale

Il margine funzionale è invariante rispetto ad un iperpiano riscalato

– Ovvero: per come abbiamo impostato Il classificatore f e g in {-1 1}

– se scaliamo l’iperpiano (w, b) (cw, cb) Otteniamo lo stesso iperpiano ! Stesso luogo dei punti ! Otteniamo la stessa g ! (dipende solo dal segno di <w, b>+b )

– e ovviamente la stessa h dipende dal segno di g !

vedremo che questo fatto ci aiuterà però a trovare l’algoritmo (impostare in maniera efficace il problema di programmazione)!

),(ˆ by iii += xwγ

Definizione: il margine geometrico

Qual è la distanza di un punto x dall’iperpiano ?

Dalla geometria con qualche calcolo ...

Var2

Var

1

dxi

||||||||1

w

xw

w

bbxw

d i

n

iii +⋅

=+

=∑= w

f

Definizione: il margine geometrico

Il margine geometrico di un punto (xi, yi) rispetto all’iperpiano (w, b) è definito come segue:

Il valore minimo

Viene definito come il margine geometrico dell’iperpiano rispetto al training set S

wxw /),( by iii +=γ

iniγρ

..1min=

=

Note sul margine geometrico

Se la classificazione è OK (come per quello funzionale) – (Verificare per credere) !

Se il punto non è correttamente classificato otteniamo un margine che eguaglia la distanza negativa dall’iperpiano

Dato un punto positivo (negativo) il margine geometrico rappresenta la sua distanza (geometrica) dall’iperpiano

Il margine geometrico, quindi, da meglio l’idea della distanza di un punto in Rn

0>iγ

wxw /),( by iii +=γ

Note sul margine geometrico

Anche il margine geometrico è invariante

– Grazie a tale invarianza possiamo riscalare l’iperpiano senza cambiare nulla (non varia il margine) !

– Se imponiamo ||w|| = 1 stiamo di fatto riscalando l’iperpiano (w,b) (w/||w||,b/||w||). Stiamo considerando un iperpiano (w/||w||,b/||w||) con vettore pesi w/||w|| di norma unitaria

wxw /),( by iii +=γ

Definizione iperpiano canonico

Un iperpiano è detto canonico qualora

In altri termini per un iperpiano canonico– Il margine funzionale è 1– il margine geometrico è

1, min..1

=+=

binixw

w/1

Note sui margini

se ||w|| = 1 il margine funzionale è uguale al margine geometrico !

In generale possiamo metterli in relazione

wxw /),( by iii +=γ

||||

ˆ

w

γγ =

),(ˆ by iii += xwγ

Verso il programma (matematico)

Per quanto detto sembra naturale cercare di estendere quanto possibile il margine geometrico !

– Dobbiamo ottimizzarlo !– Lo faremo attraverso un

programma matematico del tipo

0)( ,0g(x) s.t.

)(min

=≤ xhxf

OBIETTIVO: Arrivare ad una impostazione (del programma) per una efficace implementazione

OBIETTIVO: Arrivare ad una impostazione (del programma) per una efficace implementazione

4 note su

funzione obiettivo Vincoli Si deve trovare x che renda minimo f(x)

rispettando i vincoli Non sempre esiste una soluzione e, se

esiste, difficilmente si può trovarla per via analitica a volte si può approssimare con metodi iterativi.

0)( ,0g(x) s.t.

)(min

=≤ xhxf

0)( ,0g(x) =≤ xh

f

Verso il programma (matematico)

γ

γ

w

Vorremmo assicurarci chetutti i punti (sia quelli positivisia quelli negativi) cadano al di fuori del margine

Dato un vorremmo cheper ogni punto (i)

γ

γ≥+ wxw /),( by ii

γ γ

Il problema !

Se vogliamo che per ogni i, sia grande

– In modo tale da

allora scriviamo

1||||

),( s.t.

max

=

≥+

w

xw γγ

by ii

γ≥+ wxw /),( by ii

margine geom. = margine funz.

γ

Ma possiamo arrivare ad una forma “migliore” da implementare

1||||

),( s.t.

max

=

≥+

w

xw γγ

by ii

γ

γ

ˆ),( s.t.

||||

ˆmax

≥+by

w

ii xw

||||

ˆ

w

γγ =Ripensiamo la formulazione: Il margine geo può essere scritto

Problema !(vincolo non

convesso)

Problema !(vincolo non

convesso)

Problema !(obbiettivo non

conv)

Problema !(obbiettivo non

conv)

Possiamo arrivare ad una forma migliore da implementare

Ricordiamoci che possiamo scalare l’iperpiano senza cambiare nulla (invarianza)! Quindi possiamo riscalare (w,b) in modo tale che il margine funzionale sia ad esempio 1 (iperpiano canonico)

1),( s.t.

||||

1min

≥+by ii xw

w

Il programma

Rendere massimo Equivale a rendere

minimo

||||

1

w

2||||2

1w

Questa è la forma sulla qualelavorare

NB si dimostra che esiste una sola soluzione al problemaOvvero esiste un unico iperpiano di massimo margine !

1...ni per tutti 1)(y ..

||||2

1)( min

i

2

=≥+><

=

bxwts ii

wwτ

Riassumendo: 2 ragioni che supportano il metodo delle SVM

– 1° : la capacita’ dell’iperpiano di separazione di massimo margine ( generalizzazione)

– 2° : esiste un’unica soluzione del problema precedente !

Ora 2 punti importanti– La formulazione della soluzione del programma precedente– La formulazione della funzione di decisione associata alla

soluzione

1° - La formulazione della soluzione (attraverso) i vettori di supporto

La soluzione al problema

può essere scritta

– Ovvero è scritta in termini di un sottoinsieme di esempi del training set (noto come vettori di supporto) che giacciono sul margine dell’iperpiano

1...n)(i 1)(y ..

||||2

1)( min

i

2

=≥+><

=

bxwts ii

wwτ

∑∈

=Qi

iixw α

1* La formulazione della soluzione (attraverso): i vettori di supporto

Var1

Var2

Margin Width

Support Vectors

2° la formulazione della funzione di decisione associata alla soluzione

Quindi nella funzione di decisione possiamo scrivere

La funzione di decisione associata alla soluzione può essere scritta in termini del prodotto interno tra xi e x

∑∑∈∈

+=+=+Qi

iiiQi

iii bybyb xxxxxw ,,, αα

E se i punti non sono linearmente separabili ?

Si puo’ risolvere (rivedere la formulazione delle SVM) con i metodi kernel ....

Kernels

Give a way to apply SVMs efficiently in very high (or infinite) dimensional feature spaces

K(x, z) = (x)T (z), where : Rn Rm

K(x, z) may be very inexpensive to calculate, even though (x) itself may be very expensive (perhaps because it is an extremely high dimensional vector). In such settings, by using in our algorithm an efficient way to calculate K(x, z), we can get SVMs to learn in the high dimensional feature space space given by , but without ever having to explicitly find or represent vectors (x)

Example

Suppose x, z Rn, and consider K(x, z) = (xT z)2:

SMO algorithm

Gives an efficient implementation of SVMs