Diapositiva 1 - Bioinformatica e Calcolo Naturale

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
RxRx…xR = Rn

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
n volte
P
w
Alcuni concetti
utili per iniziare
Vettori in R2

Sull’insieme di questi punti possiamo
eseguire due operazioni fondamentali
–
P+Q: (x1+x3,x2+x4)
Addizione
Q: (x3,x4)
–
P: (x1,x2)
Moltiplicazione per un numero reale

(riscaliamo il punto! )
2P: (2x1,2x2)
P: (x1,x2)
- P: (-x1,-x2)
Alcuni concetti
utili per iniziare
Il prodotto interno in Rn

Il prodotto interno tra
due vettori in Rn è il
numero reale
–
n
x, y  x'y   xi yi
i 1
Alcune proprietà
1.
x, y  y , x
2.
x  y, z  x, z  y, z
3.
x, y   x, y
4.
x, x  0
e
x, y  z  x, y  x, z
e x, y   x, y
Alcuni concetti
utili per iniziare
La norma in Rn

La norma di un vettore
in Rn (o anche modulo,
lunghezza) è il numero
reale non negativo
–
x 2  x'x 
Alcune proprietà
Vettore unitario
x x
i 1
i i
1. || x  y |||| x ||  || y ||
2. || x ||  || x ||
3. || x || 0 se x  0
||x||

n
w
|| w ||
se
w0
Norma e prodotto interno
x 2  x'x 

Geometricamente
l’angolo  sotteso da
due vettori in R2 è dato
da:
n
x x
i 1
i i
cos  

x, x
x, y
|| x ||2 || y ||2

Proiezione di un vettore
vu  (|| v || cos  )
v

vu
u
Proiezione di v su u
Nota
v
v


u
  90
u
  90
v, u  0
v

u
  90
v, u  0
v, u  0
Alcuni concetti
utili per iniziare
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
 w, x  w' x  w1 x1  w2 x2  0
w
x
w
Alcuni concetti
utili per iniziare
Iperpiano in R2
h
Un iperpiano h in R2
con il vettore w ad esso
ortogonale
x
w
x0
Nota: tutti i punti su h sono
tali che <x, w> = 0
Iperpiano in R2
h
Nota: l’iperpiano determina 2 semispazi !
x
w
x0
Alcuni concetti
utili per iniziare
Punti linearmente separabili
classificatore
Alcuni concetti
utili per iniziare
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
 w, x  0
 w , x  b  0
{x | w, x  b  0}
Nota...
I vettori sull’iperpiano si
proiettano tutti nello
stesso punto
 I punti da un lato
dell’iperpiano sono tali
che

h
x
 w , x  b  0
I
punti dall’altro lato sono
tali che
w
 w , x  b  0
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)
Intuitivamente
Assunto che i punti siano
linearmente separabili
Intuitivamente
Ci sono diversi iperpiani separatori !
Var1
Ognuno di questi va bene !
Ma qual è il migliore ?
Var2
Intuitivamente
Idea …. prendiamo un iperpiano e ne allarghiamo il
margine … fino a toccare un punto !
Var1
Consideriamo l’ampiezza
della “zona verde”
Var2
Nota: all’interno della “zona verde” non ci sono punti !
Nota: La “zona verde” è anch’essa racchiusa tra 2 iperpiani
Intuitivamente
Consideriamo il margine di
un altro iperpiano
Var1
Questa volta
la “zona verde”
è decisamente
più ampia
Var2
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 !
Var1
f
Var2
Il classificatore f divide correttamente (fino ad ora) i punti
sul quale è stato addestrato ...
Una prova per il nostro intuito !
In questa posizione comparirà
un nuovo punto di cui non
conosciamo la classe
Var1
A
f
Il nuovo punto estratto
di cui conosco la
posizione (ma non la
classe) sarà classificato
correttamente da f ?
Var2
Una prova per il nostro intuito !
Var1
C
B
Questa volta con successive
estrazioni B e C cadono
sempre più
vicino (ad f) ...
Var2
Una prova per il nostro intuito !
Var1
C
A
B
Var2
E se ci chiedessero di scommettere ?
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
S  ( x1 , y1 ), ( x2 , y2 ),....( xn , yn )
yi {1,1}
w, xi  b  0
w, xi  b  0
per tutti gli t.c. yi  1
per tutti gli t.c. yi  1
yi ( w, xi  b)  0
(i  1,.., n)
Obiettivo !

Noi cerchiamo tra gli iperpiani
separatori
–
(w,b)
O equivalentemente cerchiamo tra
le funzioni (di decisione) lineari
associate
hw,b (x)  g ( w, x  b)

Dove g è
  1 se z  0
g ( z)  
  1 altrimenti
IL MIGLIORE !
Quello che separa meglio i punti negativi da
quelli positivi
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
Var1
d
Def: i margini di un iperpiano
- Margine funzionale
- Margine geometrico
d
Var2
Definizione: margine funzionale

Il margine funzionale di un punto (xi,yi) rispetto
all’iperpiano (w, b) è definito come segue:
ˆi  yi ( w, xi  b)

Il valore minimo
ˆ  min ˆi
i 1,..., n
–
viene definito come il margine funzionale dell’iperpiano
rispetto al training set S
ˆi  yi ( w, xi  b)
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à
w, x   b
ˆi  yi ( w, xi  b)
Note sul margine funzionale



Se ˆi  0 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 ....
ˆi  yi ( w, xi  b)
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)!
Definizione: il margine geometrico

Qual è la distanza di un
punto x dall’iperpiano ?
Var
1

Dalla geometria con
qualche calcolo ...
f
xi
d
n
d
w x b
i 1
i i
|| w ||

w  xi  b
|| w ||
w
Var2
Definizione: il margine geometrico

Il margine geometrico di un punto (xi, yi) rispetto all’iperpiano
(w, b) è definito come segue:
 i  yi ( w, xi  b) / w

Il valore minimo
  min  i
i 1.. n
Viene definito come il margine geometrico dell’iperpiano
rispetto al training set S
 i  yi ( w, xi  b) / w
Note sul margine geometrico

Se
–
 i  0 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
 i  yi ( w, xi  b) / w
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
Definizione iperpiano canonico

Un iperpiano è detto canonico qualora
min w, xi  b  1
i 1.. n

In altri termini per un iperpiano canonico
–
–
Il margine funzionale è 1
il margine geometrico è
1/ w
Note sui margini


se ||w|| = 1 il margine
funzionale è uguale al
margine geometrico !
In generale possiamo
metterli in relazione
 i  yi ( w, xi  b) / w
ˆi  yi ( w, xi  b)

ˆ
|| w ||
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
min f ( x)
s.t. g(x)  0,
h( x )  0
OBIETTIVO:
Arrivare ad una
impostazione (del
programma) per una
efficace implementazione
4 note su




min f ( x)
s.t. g(x)  0,
h( x )  0
f
funzione obiettivo
Vincoli g(x)  0, h( x)  0
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.
Verso il programma (matematico)



Vorremmo assicurarci che
tutti i punti (sia quelli positivi
sia quelli negativi) cadano
al di fuori del margine
Dato un  vorremmo che
per ogni punto (i)
yi ( w, xi  b) / w  
w
Il problema !


Se vogliamo che per
ogni i, sia grande 
yi ( w, xi  b) / w  
– In modo tale da
allora scriviamo
max 
s.t. yi ( w, x i  b)  
|| w || 1
margine geom. = margine funz.
Ma possiamo arrivare ad una forma
“migliore” da implementare
max 
s.t. yi ( w, x i  b)  
|| w || 1
Problema !
(vincolo non
convesso)
Ripensiamo la formulazione: Il margine geo può essere scritto  
max
ˆ
|| w ||
s.t. yi ( w, x i  b)  ˆ
Problema !
(obbiettivo non
conv)
ˆ
|| w ||
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
min
|| w ||
s.t. yi ( w, x i  b)  1
Il programma


Rendere massimo
Equivale a rendere
minimo
1
|| w ||2
2
s.t. yi ( wi xi  b)  1
min  (w ) 
per tutti i  1...n
1
|| w ||
1
|| w ||2
2
Questa è la forma sulla quale
lavorare
NB si dimostra che esiste una sola soluzione al problema
Ovvero esiste un unico iperpiano di massimo margine !
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
1
|| w ||2
2
s.t. y i ( wi xi  b)  1
min  (w ) 

(i  1...n)
può essere scritta
w    i xi
iQ
–
Ovvero è scritta in termini di un sottoinsieme di esempi del
training set (noto come vettori di supporto) che giacciono
sul margine dell’iperpiano
1* La formulazione della soluzione
(attraverso): i vettori di supporto
Var1
Support Vectors
Margin
Width
Var2
2° la formulazione della funzione di
decisione associata alla soluzione

Quindi nella funzione di decisione possiamo
scrivere
w, x  b 
 y x , x
iQ

i
i
i
 b   i yi xi , x  b
iQ
La funzione di decisione associata alla
soluzione può essere scritta in termini del
prodotto interno tra xi e x
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