Support Vector Machines

Marco Sciandrone

Dipartimento di Sistemi e InformaticaUniversita di Firenze- Italy

E-mail: sciandro@dsi.unifi.it

Appunti delle Lezioni tenute nell’a.a. 2005-06

Generalita

Le Support Vector Machines (SVM) costituiscono una classe di “macchine di apprendi-mento” recentemente introdotte in letteratura. Le SVM traggono origine da concettiriguardanti la teoria statistica dell’apprendimento e presentano proprieta teoriche di gen-eralizzazione. Approfondimenti teorici sull’argomento possono essere trovati in [1], [2],[3].

Scopo di queste note e quello di definire i concetti generali che sono alla base delleSVM e di mostrare come il problema dell’addestramento di una SVM e riconducibile adun problema di programmazione quadratica convessa con vincoli lineari (in particolare,l’insieme dei vincoli e costituito da un vincolo lineare e da vincoli di box). Verra infinedescritto e analizzato il metodo di decomposizione (Algoritmo SVMlight) usualmente adot-tato per la risoluzione del problema vincolato quadratico che, nelle applicazioni, risultaessere un problema a grandi dimensioni.

1 Cenni sui concetti riguardanti la teoria statistica

dell’apprendimento

Si supponga di disporre di l osservazioni, relative ad un problema di classificazione, incui ogni osservazione e costituita da una coppia: un vettore xi ∈ Rn e un’etichetta yi ∈{1,−1}, il cui valore definisce l’appartenenza del vettore ad una classe o all’altra (nelseguito, in relazione a problemi di regressione, considereremo anche il caso yi ∈ R).

Si assuma che esista una distribuzione di probabilita P (x, y) non nota, da cui sonostati estratti i dati disponibili. E supposta quindi l’esistenza di una distribuzione di y perun assegnato x (il caso piu semplice e quello per cui ad ogni assegnato x corrisponde undeterminato y).

Si consideri il problema della definizione di una macchina per l’apprendimento dellarelazione xi → yi. Una macchina e definita mediante un insieme di possibili funzioni

f(α) : Rn → {−1, 1},

in cui α rappresenta il vettore dei parametri modificabili. La macchina e deterministica,cioe, assegnati il vettore di ingresso x ed il vettore dei parametri α, la macchina forniscesempre la stessa uscita f(x, α). Addestrare la macchina significa determinare il vettoredei parametri α.

Una rete neurale multi-strato con architettura fissata rappresenta, ad esempio, unamacchina di apprendimento (nel senso specificato prima), in cui il vettore α corrispondeal vettore dei pesi e delle soglie della rete.

Riepilogando:

• l’insieme di funzioni {f(α)} rappresenta una macchina di apprendimento;

• scegliere un vettore α significa selezionare una determinata funzione, cioe deter-minare una macchina addestrata.

2

Il valore atteso dell’errore di test di una macchina addestrata e

R(α) =∫ 1

2|y − f(x, α)|dP (x, y)

(si osservi che P (x, y) e non nota). La quantita R(α) e denominata rischio effettivo (osemplicemente rischio). Si definisce rischio empirico la quantita

Remp(α) =1

2l

l∑

i=1

|yi − f(xi, α)|

(si noti che la distribuzione di probabilita non interviene nella definizione del rischioempirico, che, una volta fissati il vettore dei parametri α e il training set {xi, yi}i=1,...,l, eun determinato numero).

Sia η un numero fissato tale che 0 ≤ η ≤ 1. Con probabilita 1 − η vale la seguentedisuguaglianza [2]

R(α) ≤ Remp(α) +

√

√

√

√

(

h(log(2l/h) + 1) − log(η/4)

l

)

, (1)

in cui h e un intero non negativo denominato Vapnik Chervonenkis (VC) dimension,ed e una misura della capacita di classificazione espressa dalla macchina rappresentatadall’insieme di funzioni {f(α)}. In maniera formale, la VC dimension di una macchina{f(α)} verra definita di seguito. Il secondo termine del secondo membro della (1) vienedenominato VC confidence. Osserviamo che la VC confidence dipende dalla macchina diapprendimento scelta (cioe dalla classe di funzioni scelta), mentre sia il rischio empirico cheil rischio effettivo dipendono dalla particolare funzione determinata mediante la proceduradi addestramento della macchina.

Al fine di definire la VC dimension di un insieme di funzioni, premettiamo la seguentedefinizione.

Definizione 1 Un insieme di l punti in xi ∈ Rn, i = 1, . . . , l, e frammentabile da uninsieme di funzioni {f(α)} se, comunque si scelgano le etichette yi ∈ {1,−1}, i = 1, . . . , l,esiste un elemento dell’insieme {f(α)} che classifica correttamente i punti, cioe, esisteun vettore α tale che

f(xi, α) = yi, i = 1, . . . , l.

Definizione 2 La VC dimension h di un insieme di funzioni {f(α)} e il massimo numerodi punti che possono essere frammentati da {f(α)}.

Si osservi che se la VC dimension di un insieme {f(α)} e h, cio significa che esiste almenoun insieme di h punti che possono essere frammentati, ma in generale non e vero che unqualsiasi insieme di h punti puo essere frammentato da {f(α)}.

Come esempio, sia {f(α)} l’insieme degli iperpiani orientati in Rn, per cui, fissato uniperpiano, tutti i punti appartenenti ad un semispazio sono etichettati con 1, e tutti ipunti appartenenti all’altro semispazio sono etichettati con -1. Vale il seguente risultato.

3

Teorema 1 Un insieme di punti {x1, . . . , xm} ⊂ Rn e frammentabile dalla famiglia degliiperpiani orientati se e solo se i vettori x1, . . . , xm sono affinemente indipendenti.

Dim. Senza perdita di generalita possiamo assumere x1 = 0.

(a). Supponiamo che i vettori x1, . . . , xm siano affinemente indipendenti. Cio implica chei vettori x2 − x1, . . . , xm − x1 = x2, . . . , xm sono linearmente indipendenti.

Occorre dimostrare che, comunque si scelgano le etichette y1, . . . , ym, esistono un vet-tore dei pesi w ∈ Rn e una soglia b ∈ R tali che

yi(wTxi + b) > 0 i = 1, . . . ,m. (2)

Ponendo

b =

{

1/2 se y1 = +1−1/2 se y1 = −1

(3)

si ottiene ovviamente y1(wTx1+b) = y1b > 0 per qualunque vettore w ∈ Rn. L’indipendenzalineare dei vettori x2, . . . , xm implica che il sistema lineare nel vettore incognito w

(x2)T

(x3)T

...(xm)T

w =

y2

y3

...ym

ammette almeno una soluzione w. Per i = 2, . . . ,m risulta quindi

(w)Txi + b = yi + b = 1 + b > 0 per ogni i t.c. yi = +1

(w)Txi + b = yi + b = −1 + b < 0 per ogni i t.c. yi = −1.

Dalle precedenti relazioni e dalla (3) segue che la (2) e verificata, e quindi risulta di-mostrato che i vettori x1, . . . , xm sono frammentabili.

(b) Supponiamo che i vettori x1, . . . , xm siano frammentabili. Dimostreremo che essi sonoaffinemente indipendenti.

Supponiamo per assurdo che i vettori {x1, . . . , xm} siano affinemente dipendenti e taliche, comunque si scelgano le etichette y1, . . . , ym, e possibile determinare un vettore deipesi w ∈ Rn e una soglia b ∈ R per i quali si ha

yi(wTxi + b) > 0 i = 1, . . . ,m. (4)

I vettori x2, . . . , xm sono necessariamente linearmente dipendenti, per cui possiamo scri-vere

0 =∑

i∈I+

αixi −

∑

j∈J−

|βj|xj, (5)

dove αi > 0, βj < 0, I+ ∪ J− ⊆ {2, . . . ,m} e I+ ∩ J− = ∅. Si assuma yi = +1 per i ∈ I+

e yj = −1 per j ∈ J−. Di conseguenza si ha

wTxi > −b i ∈ I+

wTxj < −b j ∈ J−

4

da cui si ottiene∑

i∈I+

αiwTxi > −b

∑

i∈I+

αi

−∑

j∈J−

|βj|wTxj > b

∑

j∈J−

|βj|(6)

Dalla (5) e dalla (6) segue

0 =∑

i∈I+

αiwTxi −

∑

j∈J−

|βj|wTxj > b

∑

j∈J−

|βj| −∑

i∈I+

αi

, (7)

da cui otteniamo∑

j∈J−

|βj| −∑

i∈I+

αi 6= 0.

Supponiamo∑

j∈J−

|βj| −∑

i∈I+

αi > 0: la (7) implica

b < 0. (8)

D’altra parte, assumendo che l’etichetta y1 associata al vettore x1 = 0 sia pari a +1, dalla(4) abbiamo b > 0, che contraddice la (8).

Supponiamo allora che∑

j∈J−

|βj| −∑

i∈I+

αi < 0: la (7) implica

b > 0. (9)

Assumendo che l’etichetta y1 associata al vettore x1 = 0 sia pari a -1, dalla (4) abbiamob < 0, che contraddice la (9). 2

Il teorema precedente implica il seguente risultato.

Corollario 1 La VC dimension dell’insieme degli iperpiani orientati in Rn e n+ 1.

Avendo definito la VC dimension, si consideri nuovamente la (1). Osserviamo che la VCconfidence (il secondo termine del secondo membro) e una funzione monotona crescente dih. Quindi, dato un insieme di macchine di apprendimento (ognuna rappresentata da uninsieme di funzioni) che presentano rischio empirico zero, dalla (1) segue che la macchinacon VC dimension minima definisce il migliore upper bound del rischio effettivo. Ingenerale, per rischio empirico maggiore di zero, si desidera selezionare la macchina chepermette di minimizzare il secondo membro della (1).

Minimizzazione del rischio strutturale.Si vuole determinare quel sottoinsieme dell’insieme dato di funzioni per cui l’upper

bound del rischio effettivo e minimo.A questo fine, si puo pensare di introdurre una struttura nell’insieme di funzioni S

definito da {f(α)}, che viene decomposto in sottoinsiemi contenuti l’uno nell’altro:

S1 ⊂ S2 ⊂ . . . S, (10)

5

con h1 ≤ h2 . . . ≤ h (per ogni sottoinsieme Sk, deve essere quindi possibile o calcolare hk

oppure definire un upper bound di hk).In linea di principio, si puo pensare di addestrare una serie di macchine, una per ogni

sottoinsieme Sk, e l’obiettivo della procedura di addestramento e quello di minimizzare ilrischio empirico. Tra le varie macchine addestrate si seleziona quella per cui la sommadel rischio empirico e della VC confidence e minima.

1.1 Reti neurali e SVM

Per la minimizzazione del secondo membro della (1), due approcci possono essere indi-viduati.

Nel primo approccio viene determinato un insieme di funzioni con fissata VC dimensionh⋆. Il processo di addestramento e finalizzato in questo caso alla minimizzazione delnumero di errori nel training set (minimizzazione del rischio empirico). Se h⋆ e troppogrande rispetto al numero l di dati disponibili (stiamo quindi considerando una macchinadi “complessita” elevata), la VC confidence puo risultare elevata, per cui, anche riuscendoad ottenere rischio empirico nullo, l’errore sul test set (rischio effettivo) potrebbe esseregrande. Questo fenomeno e denominato overfitting.

Per evitare l’overfitting si potrebbe individuare un sottoinsieme di funzioni con VCdimension h⋆ sufficientemente piccola (stiamo quindi considerando una macchina di “com-plessita” bassa), D’altra parte, se h⋆ ha un valore troppo piccolo, potrebbe non esserepossibile (con la procedura di addestramento) ridurre sufficientemente il rischio empirico.Questo fenomeno e denominato underfitting.

Quindi, sarebbe auspicabile definire a priori (sulla base delle informazioni riguardantiil problema) una macchina con architettura (complessita) appropriata in modo da evitaresia l’overfitting che l’underfitting. Di conseguenza, l’addestramento della macchina efinalizzato alla minimizzazione degli errori sui dati di training.

In altre parole, la strategia del primo approccio e la seguente:

fissare la VC confidence (scegliendo opportunamente l’architettura della macchina)e minimizzare il rischio empirico.

Per quanto riguarda il secondo approccio si ha la seguente strategia:

fissare il valore del rischio empirico e minimizzare la VC confidence.

Macchine di apprendimento corrispondenti ai due approcci descritti sono:

(i) Reti neurali;

(ii) Support Vector Machines.

6

1.2 Iperpiano con gap di tolleranza

Definiamo iperpiano con gap di tolleranza ρ (con ρ > 0), un iperpiano H(w, b) tale cheper ogni x appartenente ad una sfera di diametro D si ha

y =

1 se wT x+b‖w‖

≥ ρ

−1 se wT x+b‖w‖

≤ −ρ

L’insieme degli iperpiani con gap di tolleranza ρ costituisce una famiglia di classificatoricontenuta nella famiglia di classificatori rappresentata dagli iperpiani orientati. In parti-colare, la funzione di decisione di un iperpiano con gap di tolleranza e la seguente: puntiappartenenti alla sfera di diametro D e a distanza maggiore di ρ sono etichettati con +1oppure -1, a seconda del semispazio di appartenenza. Tutti gli altri punti sono etichettaticonvenzionalmente con 0. Vale il seguente risultato [2].

Teorema 2 L’insieme degli iperpiani con gap di tolleranza ρ ha VC dimension h tale che

h ≤ min

{⌈

D2

ρ2

⌉

, n

}

+ 1 (11)

Dal teorema precedente segue che la VC dimension della classe di funzioni relativa agliiperpiani con gap di tolleranza puo essere controllata mediante il diametro D della sferaed il valore di gap ρ. Al variare di D e ρ si puo definire una struttura “annidata” disottoinsiemi di funzioni del tipo (10).

2 SVM lineari

Verra considerato il problema di classificare gli elementi di due insiemi di punti di Rn

mediante superfici di separazione definite da iperpiani.

2.1 Iperpiano ottimo

Si considerino due insiemi disgiunti di punti A e B in Rn. Si assuma che A e B sianolinearmente separabili, cioe, che esista un iperpiano H = {x ∈ Rn : wTx + b = 0} percui tutti i punti xi ∈ A appartengono ad un semispazio e quelli xj ∈ B appartengonoall’altro. Esistono quindi un vettore w ∈ Rn e uno scalare b ∈ R tali che

wTxi + b ≥ ε, ∀xi ∈ AwTxj + b ≤ −ε, ∀xj ∈ B

(12)

con ε > 0. Senza perdita di generalita, si puo pensare di riscalare la (12) dividendo perε, e si ottiene

wTxi + b ≥ 1, ∀xi ∈ AwTxj + b ≤ −1, ∀xj ∈ B

(13)

Dato un iperpiano di separazione H, cioe, una coppia (w, b) per cui la (13) e verificata,introduciamo il concetto di margine di separazione.

7

Definizione 3 Sia H un iperpiano di separazione. Si definisce margine di separazionedi H la minima distanza ρ tra i punti in A ∪B e l’iperpiano H, cioe

ρ(w, b) = minxi∈A∪B

{

|wTxi + b|

‖w‖

}

.

Definizione 4 Si definisce iperpiano ottimo l’iperpiano di separazione H(w⋆, b⋆) aventemargine di separazione massimo.

Determinare l’iperpiano ottimo equivale quindi a risolvere il seguente problema

maxw∈Rn,b∈R

minxi∈A∪B

{

|wTxi + b|

‖w‖

}

(14)

Dimostreremo che l’iperpiano ottimo esiste ed e unico. A questo fine proveremo l’equivalenzadel problema (14) con il seguente

minw∈Rn,b∈R

‖w‖2

t.c. wTxi + b ≥ 1, ∀xi ∈ AwTxj + b ≤ −1, ∀xj ∈ B

(15)

Lemma 1 Per ogni iperpiano di separazione, cioe per ogni coppia (w, b) tale che (13) everificata, segue

ρ(w, b) ≥1

‖w‖.

Dim. Poiche|wTxℓ + b| ≥ 1, ∀xℓ ∈ A ∪B,

si ha

ρ(w, b) = minxℓ∈A∪B

{

|wTxℓ + b|

‖w‖

}

≥1

‖w‖. 2

Lemma 2 Per ogni iperpiano di separazione (w, b), esiste un iperpiano di separazione(w, b) tale che

ρ(w, b) ≤ ρ(w, b) =1

‖w‖. (16)

Inoltre, esistono almeno due punti x+ ∈ A e x− ∈ B tali che

wTx+ + b = 1wTx− + b = −1

(17)

8

Dim. Siano xi ∈ A e xj ∈ B i punti piu vicini all’iperpiano (w, b), cioe i punti per i quali

di =|wT xi + b|

‖w‖≤

|wTxi + b|

‖w‖, ∀xi ∈ A

dj =|wT xj + b|

‖w‖≤

|wTxj + b|

‖w‖, ∀xj ∈ B

(18)

da cui segue

ρ(w, b) = min{di, dj} ≤1

2(di + dj) =

wT (xi − xj)

2‖w‖. (19)

Si considerino gli scalari α e β tali che

αwT xi + β = 1αwT xj + β = −1

(20)

cioe i valori

α =2

wT (xi − xj), β = −

wT (xi + xj)

wT (xi − xj).

Si puo facilmente verificare che 0 < α ≤ 1. Mostreremo che l’iperpiano (w, b) ≡ (αw, β)separa gli insiemi A e B, e soddisfa la (16). Infatti, dalla (18) si ha

wTxi ≥ wT xi, ∀xi ∈ AwTxj ≤ wT xj, ∀xj ∈ B.

Poiche α > 0, possiamo scrivere

αwTxi + β ≥ αwT xi + β = 1, ∀xi ∈ AαwTxj + β ≤ αwT xj + β = −1, ∀xj ∈ B

(21)

da cui segue che w e b soddisfano la (13), e quindi (w, b) e un iperpiano di separazioneper gli insiemi A e B.

Inoltre, tenendo conto della (21) e del valore di α, abbiamo

ρ(w, b) = minxℓ∈A∪B

{

|wTxℓ + b|

‖w‖

}

=1

‖w‖=

1

α‖w‖=wT (xi − xj)

2‖w‖.

La (16) segue dalla precedente relazione e dalla (19). Dalla (20) si ottiene la (17) conx+ = xi e x− = xj. 2

Proposizione 1 Il seguente problema

min ‖w‖2

t.c. wTxi + b ≥ 1, ∀xi ∈ AwTxj + b ≤ −1, ∀xj ∈ B

(22)

ammette una soluzione unica (w⋆, b⋆).

9

Dim. Sia F l’insieme ammissibile

F = {(w, b) ∈ Rn ×R : wTxi + b ≥ 1,∀xi ∈ A, wTxj + b ≤ −1,∀xj ∈ B},

e, per una assegnata coppia (wo, bo) ∈ F , si consideri l’insieme di livello

Lo = {(w, b) ∈ F : ‖w‖2 ≤ ‖wo‖2}.

L’insieme Lo e ovviamente chiuso, e dimostreremo che e anche limitato. Infatti, supponi-amo per assurdo che esista una sequenza illimitata {(wk, bk)} appartenente a Lo. Poiche‖wk‖ ≤ ‖wo‖,∀k, si ha necessariamente |bk| → ∞. Per ogni k possiamo scrivere

wTk x

i + bk ≥ 1, ∀xi ∈ AwT

k xj + bk ≤ −1, ∀xj ∈ B

e quindi, poiche |bk| → ∞, segue per k sufficientemente grande, ‖wk‖2 > ‖wo‖

2, e cioe in contraddizione con l’ipotesi che {(wk, bk)} appartenga all’insieme Lo, e quindi Lo

e compatto. Il teorema di Weirstrass implica che la funzione ‖w‖2 ammette un minimo(w⋆, b⋆) sull’insieme Lo e quindi su F , di conseguenza (w⋆, b⋆) e una soluzione del problema(22).

Per dimostrare che (w⋆, b⋆) e l’unico punto di minimo globale, assumiamo per con-traddizione che esista una coppia (w, b) ∈ F , (w, b) 6= (w⋆, b⋆), tale che ‖w‖2 = ‖w⋆‖2.Supponiamo che w 6= w⋆. L’insieme F e convesso, per cui

λ(w⋆, b⋆) + (1 − λ)(w, b) ∈ F , ∀λ ∈ [0, 1],

e poiche ‖w‖2 e una funzione strettamente convessa, per ogni λ ∈ (0, 1) segue

‖λw⋆ + (1 − λ)w‖2 < λ‖w⋆‖2 + (1 − λ)‖w‖2.

Ponendo, ad esempio, λ = 1/2, cioe considerando la coppia (w, b) ≡(

1

2w⋆ +

1

2w,

1

2b⋆ +

1

2b)

,

abbiamo (w, b) ∈ F e

‖w‖2 <1

2‖w⋆‖2 +

1

2‖w‖2 = ‖w⋆‖2,

che contraddice il fatto che (w⋆, b⋆) e un punto di minimo globale. Quindi abbiamonecessariamente w ≡ w⋆.

Supponiamo allora che b⋆ > b (il caso b⋆ < b e analogo), e consideriamo un puntoxi ∈ A tale che

w⋆T xi + b⋆ = 1

(L’esistenza di tale punto e assicurata dalla (17) del Lemma 2). Abbiamo

1 = w⋆T xi + b⋆ = wT xi + b⋆ > wT xi + b

che contraddice il fatto che wTxi + b ≥ 1, ∀xi ∈ A. Di conseguenza, b ≡ b⋆, e ladimostrazione e quindi completata. 2

10

Proposizione 2 Sia (w⋆, b⋆) la soluzione del problema (22). Allora, (w⋆, b⋆) e l’unicasoluzione del problema

max ρ(w, b)t.c. wTxi + b ≥ 1, ∀xi ∈ A

wTxj + b ≤ −1, ∀xj ∈ B(23)

.

Dim. Osserviamo che (w⋆, b⋆) e l’unica soluzione del problema

max 1‖w‖

t.c. wTxi + b ≥ 1, ∀xi ∈ AwTxj + b ≤ −1, ∀xj ∈ B.

Il Lemma 1 e il Lemma 2 implicano che per ogni iperpiano di separazione (w, b) segue

1

‖w‖≤ ρ(w, b) ≤

1

‖w⋆‖

e quindi, per la coppia (w⋆, b⋆), otteniamo ρ(w⋆, b⋆) =1

‖w⋆‖, cioe (w⋆, b⋆) e l’iperpiano

ottimo. 2

Osservazione. Ogni iperpiano di separazioneH(w, b) ha, per definizione, rischio empiriconullo, quindi si ha

R(w, b) ≤

√

√

√

√

(

h(log(2l/h) + 1) − log(η/4)

l

)

. (24)

Ogni iperpiano di separazione H(w, b) ha un margine ρ, di conseguenza appartiene adun sottoinsieme per cui, utilizzando il Teorema 2, e possibile definire un upper bounddella VC dimension. Poiche il margine ρ e minore del margine ρ⋆ dell’iperpiano ottimoH(w⋆, b⋆), segue che l’iperpiano ottimo appartiene ad un sottoinsieme per cui l’upperbound della VC dimension e minimo. Ricordando che il secondo membro della (24) euna funzione crescente di h, possiamo concludere che l’upper bound del rischio effettivorelativo all’iperpiano ottimo H(w⋆, b⋆) e minore dell’upper bound relativo ad un qualsiasiiperpiano di separazione, e cio giustifica l’interesse nella determinazione dell’iperpianoottimo. 2

3 Il duale di Wolfe

Il concetto di dualita e ampiamente utilizzato nella programmazione matematica. Inrelazione a determinati problemi, la teoria della dualita consente di definire formulazionialternative che, da un lato possono essere risolte piu efficientemente da un punto di vistacomputazionale, dall’altro possono fornire elementi teorici rilevanti.

11

L’idea alla base della teoria dela dualita e quella di costruire, in corrispondenza ad unproblema assegnato di minimo, detto problema primale:

minx∈S

f(x)

un problema di massimo, detto problema duale (definito, in genere, su uno spazio diverso)

maxu∈U

ψ(u)

in modo tale che valga almeno la condizione (detta proprieta di dualita debole)

infx∈S

f(x) ≥ supu∈U

ψ(u).

Ove si riesca a stabilire tale corrispondenza, e possibile fornire utili caratterizzazioni dellesoluzioni del primale attraverso lo studio del duale.

In particolare, dalla teoria della dualita e possibile ricavare

- stime del valore ottimo;

- condizioni di ottimalita;

- metodi di soluzione basati sulla considerazione del problema duale.

Per alcune classi di problemi si riesce anche a stabilire la consizione (detta proprieta didualita forte)

infx∈S

f(x) = supu∈U

ψ(u).

La possibilita di costruire un duale che soddisfi una proprieta di dualita forte sussiste peruna classe (ristretta ma importante) di problemi di ottimo che comprende, tipicamente,molti problemi di programmazione convessa.

Si consideri il problema

min f(x)

gi(x) ≤ 0, i = 1, . . . ,m

cTj x− dj = 0, j = 1, . . . , p

(25)

in cui f : Rn → R, gi : Rn → R, i = 1, . . . ,m sono funzioni convesse continuamentedifferenziabili. Sia

L(x, λ, µ) = f(x) +m∑

i=1

λigi(x) +p∑

j=1

µj(cTj x− dj)

12

Proposizione 3 Si assuma che il problema (25) ammetta almeno una soluzione ottimax⋆, e che esista almeno una coppia di moltiplicatori di lagrange (λ⋆, µ⋆). Allora la tripla(x⋆, λ⋆, µ⋆) e soluzione del seguente problema

max L(x, λ, µ)x, λ, µ

∇xL(x, λ, µ) = 0

λ ≥ 0.

(26)

Inoltre, il gap di dualita e nullo, ossia f(x⋆) = L(x⋆, λ⋆, µ⋆).

Dim. Le condizioni KKT implicano

∇xL(x⋆, λ⋆, µ⋆) = 0, (27)

(λ∗)Tg(x⋆) = 0,

λ⋆ ≥ 0.

Il punto (x⋆, λ⋆, µ⋆) e percio ammissibile per il problema (26), e risulta f(x⋆) = L(x⋆, λ⋆, µ⋆).Mostreremo che (x⋆, λ⋆, µ⋆) e soluzione del problema (26).

Sia (x, λ, µ) una soluzione ammissibile del problema (26), cioe tale che ∇xL(x, λ, µ) = 0e λ ≥ 0. Osserviamo che, per ogni λ ≥ 0 e per ogni µ, la funzione di x

L(x, λ, µ) = f(x) +m∑

i=1

λigi(x) +p∑

j=1

µj(cTj x− dj)

e una funzione convessa. Infatti, la funzione f(x) e convessa per ipotesi, il secondo terminee una combinazione lineare, con coefficienti non negativi, di funzioni convesse, e quindi,per un noto risultato e una funzione convessa; infine, il terzo termine e una funzione affinee quindi convessa. Di conseguenza, la funzione L(x, λ, µ) e espressa come somma di trefunzioni convesse, e quindi risulta essere una funzione convessa.

Tenendo conto della (27), del fatto che g(x⋆) ≤ 0 e λ ≥ 0, della convessita di L comefunzione di x (per cui risulta L(y) ≥ L(x) + (y− x)T∇xL(x)), e utilizzando la condizione∇xL = 0, per ogni λ ≥ 0 e per ogni µ, si puo scrivere

L(x⋆, λ⋆, µ⋆) = f(x⋆) ≥ f(x⋆) +∑m

i=1 λigi(x⋆) = L(x⋆, λ, µ)

≥ L(x, λ, µ) + (x⋆ − x)T∇xL(x, λ, µ) = L(x, λ, µ)

e quindi la tesi e dimostrata. 2

Il problema (26) e usualmente indicato come problema duale di Wolfe.

Osservazione. In generale, data una soluzione (x, λ, µ) del duale di Wolfe, non si possonotrarre conclusioni sui vettori x e (λ, µ). 2

13

Programmazione quadratica

Si consideri il seguente problema quadratico

min f(x) = 12xTQx+ cTx

Ax− b ≤ 0,(28)

dove Q ∈ Rn×n, A ∈ Rm×n, c ∈ Rn, b ∈ Rm. Posto L(x, λ) = f(x) + λT (Ax− b), il dualedi Wolfe e definito come segue

max L(x, λ)x, λ

∇xL(x, λ) = 0

λ ≥ 0.

(29)

Vale il seguente risultato.

Proposizione 4 Si assuma che la matrice Q sia semidefinita positiva. Sia (x, λ) unasoluzione del duale di Wolfe (29). Allora esiste un vettore x⋆ (non necessariamente ugualea x) tale che

(i) Q(x⋆ − x) = 0;

(ii) x⋆ e soluzione del problema (28);

(iii) (x⋆, λ) e una coppia (minimo globale- vettore di moltiplicatori di lagrange).

Dim. Si consideri il problema duale (29):

maxx,λ12xTQx+ cTx+ λT (Ax− b)

Qx+ ATλ+ c = 0

λ ≥ 0

Il vincolo Qx+ ATλ+ c = 0 implica

xTQx+ cTx+ λTAx = 0. (30)

Utilizzando la (30), il problema duale puo essere scritto nella forma

minx,λ12xTQx+ λT b

Qx+ ATλ+ c = 0

λ ≥ 0

(31)

14

Sia (x, λ) una soluzione del problema (31). Si consideri la funzione Lagrangiana associataal problema (31)

W (x, λ, v, z) =1

2xTQx+ λT b− vT (Qx+ ATλ+ c) − zTλ.

Poiche (x, λ) e soluzione del duale di Wolfe (29), dalle condizioni KKT si ha che esistonoun vettore v ∈ Rn e un vettore z ∈ Rr tali che

∇xW = Qx−Qv = 0

∇λW = b− Av − z = 0

Qx+ AT λ+ c = 0

zT λ = 0

z ≥ 0

λ ≥ 0

(32)

Dalla seconda e dalla quinta relazione si ricava z = b − Av ≥ 0, per cui le precedenticondizioni possono essere scritte nella forma

Qx−Qv = 0

−b+ Av ≤ 0

Qx+ AT λ+ c = 0

−λT b+ λTAv = 0

λ ≥ 0

(33)

Sottraendo la prima dalla terza relazione si ottiene

Qv + AT λ+ c = 0. (34)

Poiche la matrice Q e semidefinita positiva, la funzione f risulta essere una funzioneconvessa. Dalla Proposizione 16 segue quindi che le relazioni

Av − b ≤ 0

Qv + AT λ+ c = 0

λT (Av − b) = 0

λ ≥ 0

15

sono sufficienti ad assicurare che v e una soluzione del problema (28). Quindi perdefinizione (v, λ) e una coppia (minimo globale-vettore di lagrange). Posto x⋆ = v siha che x⋆ e soluzione del problema (28), inoltre, tenendo conto della prima relazione nella(33), risulta

Qx⋆ = Qv = Qx.

In tal modo, le asserzioni (i)-(iii) risultano dimostrate. 2

3.1 Programmazione quadratica per SVM lineari

Determinare una SVM lineare equivale a determinare l’iperpiano ottimo, cioe a risolvereil seguente problema

max ρ(w, b)

t.c. wTxi + b ≥ 1, ∀xi ∈ A

wTxj + b ≤ −1, ∀xj ∈ B,

(35)

dove A e B sono due insiemi di punti contenuti in Rn linearmente separabili. Abbi-amo visto che il problema (35) e equivalente al seguente problema di programmazionequadratica convessa

minF (w) =1

2‖w‖2

t.c. wTxi + b ≥ 1, ∀xi ∈ A

wTxj + b ≤ −1, ∀xj ∈ B

(36)

Associando l’etichetta yi = +1 ai vettori xi ∈ A, e l’etichetta yj = −1 ai vettori xj ∈ B,il problema (37) puo essere scritto nella seguente forma

minF (w) =1

2‖w‖2

t.c. yi[

wTxi + b]

− 1 ≥ 0, i = 1, . . . , l(37)

essendo l il numero dei punti dell’insieme A ∪B.

Considereremo ora la formulazione duale del problema (37). Le motivazioni sono leseguenti:

• i vincoli del problema (37) sono sostituiti da vincoli “piu semplici” sui moltiplicatoridi Lagrange;

• nella formulazione duale, i vettori di training compariranno attraverso prodottiscalari tra i vettori stessi, e cio consentira di generalizzare la procedura al casodi insiemi che non sono linearmente separabili.

16

La funzione Lagrangiana del problema (37) e la seguente funzione

L(w, b, λ) =1

2‖w‖2 −

l∑

i=1

λi[yi(wTxi + b) − 1] (38)

Il problema duale del problema (37) e il seguente

max L(w, b, λ) =1

2‖w‖2 −

l∑

i=1

λi[yi(wTxi + b) − 1]

t.c. ∇wL(w, b, λ) = 0

∂L(w, b, λ)

∂b= 0

λ ≥ 0,

ossia

max L(w, b, λ) =1

2‖w‖2 −

l∑

i=1

λi[yi(wTxi + b) − 1]

t.c. w =l∑

i=1

λiyixi

l∑

i=1

λiyi = 0

λi ≥ 0 i = 1, . . . , l

(39)

Il problema (39) puo essere riscritto nella seguente forma

max S(λ) = −1

2

l∑

i=1

l∑

j=1

yiyj(xi)Txjλiλj +l∑

i=1

λi

t.c.l∑

i=1

λiyi = 0

λi ≥ 0 i = 1, . . . , l

(40)

oppure, in maniera equivalente

17

min Γ(λ) =1

2

l∑

i=1

l∑

j=1

yiyj(xi)Txjλiλj −l∑

i=1

λi

t.c.l∑

i=1

λiyi = 0

λi ≥ 0 i = 1, . . . , l

(41)

Osserviamo che:

• l’esistenza della soluzione ottima (w⋆, b⋆) del problema (37) e le proposizioni 15 e 3assicurano che il problema (40) ammette almeno una soluzione ottima λ⋆;

• dalla formulazione (39) segue che il vettore w⋆ puo essere determinato come segue

w⋆ =l∑

i=1

λ⋆i y

ixi;

• w⋆ dipende esclusivamente dai vettori di training xi (vettori di supporto) i cui cor-rispondenti moltiplicatori λ⋆

i sono diversi da zero;

• l’asserzione (iii) della Proposizione 4 assicura che (w⋆, b⋆, λ⋆) costituisce una coppia(soluzione ottima-vettore di moltiplicatori di lagrange), per cui valgono le seguenticondizioni di complementarita

λ⋆i

[

yi(

(w⋆)Txi + b⋆)

− 1]

= 0 i = 1, . . . , l (42)

• noto w⋆ e considerato un qualsiasi moltiplicatore λ⋆i 6= 0, lo scalare b⋆ puo essere

determinato utilizzando la corrispondente condizione definita nella (42).

• il problema (41) e un problema di programmazione quadratica convessa; infatti, posto

X =[

y1x1, . . . , ylxl]

, λT =[

λ1, . . . , λl]

, il problema assume la forma

min Γ(λ) =1

2λTXTXλ− eTλ

t.c.l∑

i=1

λiyi = 0

λi ≥ 0 i = 1, . . . , l,

dove eT = [1, . . . , 1];

• la funzione di decisione risulta essere

f(x) = sgn(

(w∗)Tx+ b⋆)

= sgn

(

l∑

i=1

λ⋆i y

i(xi)Tx+ b⋆)

18

3.2 Il caso non separabile linearmente

Siano A e B due insiemi disgiunti di punti in Rn, e si assuma che A e B non sianolinearmente separabili, ossia il sistema

wTxi + b ≥ 1, ∀xi ∈ AwTxj + b ≤ −1, ∀xj ∈ B

(43)

non ammette soluzione. Si introducano nel sistema (43) delle variabili positive slack ξh,con h = 1, . . . , l:

wTxi + b ≥ 1 − ξi, ∀xi ∈ AwTxj + b ≤ −1 + ξj, ∀xj ∈ Bξh ≥ 0, h = 1, . . . , l

(44)

Si noti che, se un vettore di ingresso xi non e classificato correttamente (ad esempio, xi ∈ Ae quindi deve risultare wTxi + b > 0) la corrispondente variabile ξi risulta maggiore di 1.Quindi, il termine

l∑

i=1

ξi

e un upper bound del numero di errori di classificazione dei vettori di training. Appare

naturale percio aggiungere alla funzione obiettivo del problema (37) il termine Cl∑

i=1

ξi, in

cui C > 0 e un parametro che “pesa” l’errore di training. Il problema primale assume laseguente forma

minF (w, ξ) =1

2‖w‖2 + C

l∑

i=1

ξi

t.c. yi[

wTxi + b]

− 1 + ξi ≥ 0 i = 1, . . . , l

ξi ≥ 0 i = 1, . . . , l

(45)

19

Il duale di (45) e il problema

max L(w, b, ξ, λ, µ) =1

2‖w‖2 + C

l∑

i=1

ξi −l∑

i=1

λi[yi(wTxi + b) − 1 + ξi] −

l∑

i=1

µiξi

t.c. ∇wL(w, b, ξ, λ, µ) = 0

∂L(w, b, ξ, λ, µ)

∂b= 0

∂L(w, b, ξ, λ, µ)

∂ξi= 0 i = 1, . . . , l

λ ≥ 0

µ ≥ 0,

ossia

max L(w, b, ξ, λ, µ) =1

2‖w‖2 + C

l∑

i=1

ξi −l∑

i=1

λi[yi(wTxi + b) − 1 + ξi] −

l∑

i=1

µiξi

t.c. w =l∑

i=1

λiyixi

l∑

i=1

λiyi = 0

C − λi − µi = 0 i = 1, . . . , l

λ ≥ 0

µ ≥ 0,

che puo essere scritto nella forma

min Γ(λ) =1

2

l∑

i=1

l∑

j=1

yiyj(xi)Txjλiλj −l∑

i=1

λi

t.c.l∑

i=1

λiyi = 0

0 ≤ λi ≤ C i = 1, . . . , l

(46)

20

I vincoli λi ≤ C, per i = 1, . . . , l, derivano dalle relazioni λi = C − µi, µi ≥ 0.Osserviamo che:

• il vettore w⋆ puo essere determinato come segue

w⋆ =l∑

i=1

λ⋆i y

ixi;

• in corrispondenza della soluzione ottima (w⋆, b⋆, ξ⋆λ⋆, µ⋆) valgono le seguenti con-dizioni di complementarita

λ⋆i

[

yi(

(w⋆)Txi + b⋆)

− 1 + ξ⋆i

]

= 0 i = 1, . . . , l (47)

µ⋆i ξ

⋆i = 0 i = 1, . . . , l (48)

• noto w⋆ e considerato un qualsiasi moltiplicatore 0 < λ⋆i < C, lo scalare b⋆ puo

essere determinato utilizzando la corrispondente condizione definita nella (47);

• nel caso in cui λ⋆i ∈ {0, C} per i = 1, . . . , l, la soluzione e detta degenere;

• il problema (46) e un problema di programmazione quadratica convessa;

• la funzione di decisione risulta essere

f(x) = sgn(

(w∗)Tx+ b⋆)

= sgn

(

l∑

i=1

λ⋆i y

i(xi)Tx+ b⋆)

4 SVM non lineari

Verra considerato il problema di classificare gli elementi di due insiemi di punti di Rn

mediante superfici di separazione non lineari.

Funzioni kernel

Si chiama prodotto scalare in uno spazio lineare reale V una funzione 〈x, y〉 definita perogni coppia di elementi (x, y) ∈ V e soddisfacente alle seguenti condizioni:

(i) 〈x, y〉 = 〈y, x〉;

(ii) 〈x1 + x2, y〉 = 〈x1, y〉 + 〈x2, y〉;

(iii) 〈λx, y〉 = λ 〈x, y〉;

(iv) 〈x, x〉 ≥ 0, inoltre 〈x, x〉 = 0 soltanto se x = 0.

21

Dato un insieme X ⊆ Rn, una funzione

k : X ×X → R

e un kernel se soddisfa la seguente proprieta

k(x, y) = 〈φ(x), φ(y)〉 ∀x, y ∈ X, (49)

dove φ e un’applicazione X → H e H e uno spazio Euclideo, cioe uno spazio lineare conun prodotto scalare fissato in esso.

Osserviamo che un kernel e una funzione necessariamente simmetrica.

Proposizione 5 Sia k : X × X → R un kernel. Comunque si scelgano ℓ elementix1, . . . , xℓ in X la matrice

K = [k(xi, xj)]i,j=1,...,ℓ

risulta simmetrica e semidefinita positiva.

Dim. La simmetria di K segue dalla simmetria del kernel k. Per ogni vettore v ∈ Rℓ siha

vTKv =ℓ∑

i=1

ℓ∑

j=1

vivjk(xi, xj) =ℓ∑

i=1

ℓ∑

j=1

vivj 〈φ(xi), φ(xj)〉 =

⟨

ℓ∑

i=1

viφ(xi),ℓ∑

j=1

vjφ(xj)

⟩

= 〈z, z〉 ≥ 0. 2

Proposizione 6 Sia k : X × X → R una funzione simmetrica tale che, comunque siscelgano ℓ elementi x1, . . . , xℓ in X, la matrice

K = [k(xi, xj)]i,j=1,...,ℓ

risulta simmetrica e definita positiva. Allora k e un kernel.

Dim. Si consideri lo spazio lineare di funzioni

Fk(X) = lin{k(·, y) : y ∈ X}

e la funzione ρ : Fk(X) × Fk(X) → R definita come segue

ρ

N∑

i=1

αik(·, xi),M∑

j=1

βjk(·, xj)

=N∑

i=1

M∑

j=1

αiβjk(xi, xj). (50)

Mostreremo che la funzione ρ e un prodotto scalare in Fk(X).

22

Le proprieta (i)-(iii) del prodotto scalare sono immediatamente verificabili. Al finedi dimostrare la proprieta (iv), si consideri una generica funzione f ∈ Fk(X), cioe unafunzione del tipo

f =N∑

i=1

αik(·, xi),

con f 6= 0. Allora risulta

ρ(f, f) = ρ

N∑

i=1

αik(·, xi),N∑

j=1

αjk(·, xj)

=N∑

i=1

N∑

j=1

αiαjk(xi, xj) = αTKα > 0,

dove la disuguaglianza stretta segue dall’ipotesi.Si consideri ora l’elemento φ in Fk(X) definito come segue

φ(x) = k(·, x).

Comunque si scelgano due elementi x, y ∈ X, dalla (50) otteniamo immediatamente

k(x, y) = ρ (φ(x), φ(y)) = 〈φ(x), φ(y)〉 ,

dove l’ultima uguaglianza segue dal fatto che la funzione ρ e un prodotto scalare in Fk(X),e quindi e dimostrato che k e un kernel. 2

Siano xi ∈ Rn, i = 1, . . . , l i vettori di training e yi ∈ {−1, 1} le corrispondenti etichetteche individuano la classe di appartenenza di ciascun vettore.

Si consideri un’applicazioneφ : Rn → H

in cui H e uno spazio Euclideo a dimensione maggiore di n (eventualmente infinita). Lospazio H viene denominato feature space (spazio delle caratteristiche). Si considerino i“trasformati” φ(xi) dei vettori di training xi, con i = 1, . . . , l e il problema della determi-nazione dell’iperpiano ottimo nel feature space H in cui “esistono” i vettori “trasformati”φ(xi), i = 1, . . . , l.

Si puo pensare di applicare la metodologia, descritta precedentemente, sostituendo xi

con φ(xi). In particolare:

• il corrispondente del problema duale (46) e il seguente

min Γ(λ) = 12

l∑

i=1

l∑

j=1

yiyjφ(xi)Tφ(xj)λiλj −l∑

i=1

λi

t.c.l∑

i=1

λiyi = 0

0 ≤ λi ≤ C i = 1, . . . , l

(51)

23

• il vettore w⋆ risulta definito nel seguente modo

w⋆ =l∑

i=1

λ⋆i y

iφ(xi)

• noto w⋆ e considerato un qualsiasi moltiplicatore 0 < λ⋆i < C, lo scalare b⋆ puo

essere determinato utilizzando la corrispondente condizione di complementarita

yi

l∑

j=1

λ⋆jy

jφ(xj)Tφ(xi) + b⋆

− 1 = yj

l∑

j=1

λ⋆jy

jk(xj, xi) + b⋆

− 1 = 0; (52)

• la funzione di decisione assume la seguente forma

f(x) = sgn(

(w∗)Tφ(x) + b⋆)

= sgn

(

l∑

i=1

λ⋆i y

ik(xi, x) + b⋆)

. (53)

Osservazione. La (53) mostra che la superficie di separazione e:

- di tipo lineare nel feature space;

- di tipo non lineare nell’ input space.

Si noti inoltre che sia nella formulazione del problema duale (51) che nell’espressione (53)della funzione di decisione non e necessario conoscere la rappresentazione esplicita dellatrasformazione φ, ma e sufficiente utilizzare una funzione kernel k, cioe una funzione taleche per x, z ∈ Rn si ha

k(x, z) = 〈φ(x), φ(z)〉 = φ(x)Tφ(z). 2

Abbiamo visto che una funzione k(x, z) e un kernel solo se la matrice l × l

(

k(xi, xj))l

i,j=1=

k(x1, x1) . . . k(x1, xl)...

k(xl, x1) . . . k(xl, xl)

risulta semidefinita positiva per ogni insieme di vettori di training {x1, . . . , xl}. (Nellaletteratura le funzioni kernel sono spesso denominate kernel di tipo Mercer). Il problema(51) puo quindi essere scritto nella forma equivalente

min Γ(λ) = 12

l∑

i=1

l∑

j=1

yiyjk(xi, xj)λiλj −l∑

i=1

λi

t.c.l∑

i=1

λiyi = 0

0 ≤ λi ≤ C i = 1, . . . , l

(54)

24

Si noti che il problema (51), nel caso di kernel di tipo Mercer, risulta essere un problemadi programmazione quadratica convessa.Esempi di funzioni kernel sono:

k(x, z) = (xT z + 1)p kernel polinomiale (p intero ≥1)

k(x, z) = e−‖x−z‖2/2σ2

kernel gaussiano (σ > 0)

k(x, z) = tanh(βxT z + γ) kernel di tipo tangente iperbolica (opportuni valori di β e γ)

La funzione di decisione puo essere scritta nella forma

f(x) = sgn

(

l∑

i=1

λ⋆i y

ik(x, xi) + b⋆)

Osserviamo che una SVM con kernel gaussiano corrisponde ad una rete neurale di funzionidi base radiali, in cui il numero di funzioni e i loro centri sono determinati automaticamentedal numero di support vector e dai loro valori. Analogamente, nel caso di SVM con kerneldi tipo tangente iperbolica, si ha una rete neurale multi-layer, con uno strato di neuroni“nascosti”, in cui il numero di neuroni ed il valore dei pesi ad essi associati sono determinatiautomaticamente dal numero di support vector e dai loro valori.

5 SVM per problemi di regressione

In un problema di regressione, ogni osservazione del training set e costituita da una coppia(xi, yi), in cui il pattern xi ∈ Rn e l’etichetta yi ∈ R. Si consideri un modello ingresso-uscita lineare, cioe una funzione f : Rn → R della forma

f(x;w, b) = wTx+ b.

Sia ǫ > 0 il grado di precisione desiderato con il quale si vuole approssimare la funzionerappresentata dai campioni del training set, mediante il modello f . La stima del modellorelativa ad un pattern xi e considerata “corretta” se risulta

|yi − wTxi − b| ≤ ǫ.

Introduciamo la loss function

|y − f(x;w, b)|ǫ = max{0, |y − f(x;w, b)| − ǫ} (55)

e definiamo l’errore di training

E =l∑

i=1

|yi − f(xi;w, b)|ǫ.

25

L’errore di training e nullo se e solo se il seguente sistema di disequazioni e soddisfatto

wTxi + b− yi ≤ ǫ

yi − wTxi − b ≤ ǫ

i = 1, . . . , l.

(56)

Si introducano in (56) le variabili artificiali ξi, ξi, con i = 1, . . . , l:

wTxi + b− yi ≤ ǫ+ ξi

yi − wTxi − b ≤ ǫ+ ξi

ξi, ξi ≥ 0, i = 1, . . . , l.

Si noti che la quantital∑

i=1

(

ξi + ξi)

costituisce un upper bound dell’errore di training. Si puo procedere percio come nel casodi SVM lineari per problemi di classificazione, e considerare quindi il problema

minw,b,ξ,ξ

12‖w‖2 + C

l∑

i=1

(

ξi + ξi)

wTxi + b− yi ≤ ǫ+ ξi

yi − wTxi − b ≤ ǫ+ ξi

ξi, ξi ≥ 0, i = 1, . . . l.

(57)

26

Il duale del problema (57) e il seguente problema

max L(w, b, ξ, ξ, λ, λ, µ, µ) =1

2‖w‖2 + C

l∑

i=1

(

ξi + ξi)

−l∑

i=1

µiξi −l∑

i=1

µiξi

+l∑

i=1

λi[wTxi + b− yi − ǫ− ξi] +

l∑

i=1

λi[yi − wTxi − b− ǫ− ξi]

t.c. ∇wL = 0

∂L

∂b= 0

∂L

∂ξi= 0 i = 1, . . . , l

∂L

∂ξi= 0 i = 1, . . . , l

λ, λ ≥ 0

µ, µ ≥ 0,

27

ossia

max L(w, b, ξ, ξ, λ, λ, µ, µ) =1

2‖w‖2 + C

l∑

i=1

(

ξi + ξi)

−l∑

i=1

µiξi −l∑

i=1

µiξi

+l∑

i=1

λi[wTxi + b− yi − ǫ− ξi] −

l∑

i=1

λi[yi − wTxi − b− ǫ− ξi]

t.c. w =l∑

i=1

(

λi − λi

)

xi

l∑

i=1

(

λi − λi

)

= 0

C − λi − µi = 0 i = 1, . . . , l

C − λi − µi = 0 i = 1, . . . , l

λ, λ ≥ 0

µ, µ ≥ 0,

che puo essere scritto nella forma

minλ,λ

Γ(λ, λ) = 12

l∑

i=1

l∑

j=1

(λi − λi)(λj − λj)(xi)Txj −

l∑

i=1

(

λi − λi

)

yi + ǫl∑

i=1

(

λi + λi

)

l∑

i=1

(

λi − λi

)

= 0

0 ≤ λ ≤ C i = 1, . . . , l

0 ≤ λ ≤ C i = 1, . . . , l.

La teoria della dualita e l’impiego di funzioni kernel consentono di generalizzare la trat-tazione al caso di modelli di regressione non lineari, in analogia con quanto fatto inproblemi di classificazione. In particolare, il problema di addestramento di una SVM perla regressione non lineare risulta definito come segue

28

minλ,λ

Γ(λ, λ) = 12

l∑

i=1

l∑

j=1

(λi − λi)(λj − λj)k(xi, xj) −

l∑

i=1

(

λi − λi

)

yi + ǫl∑

i=1

(

λi + λi

)

l∑

i=1

(

λi − λi

)

= 0

0 ≤ λ ≤ C i = 1, . . . , l

0 ≤ λ ≤ C i = 1, . . . , l,

dove k(x, z) e una funzione kernel. Il problema formulato e un problema di program-mazione quadratica convessa, la cui soluzione (λ⋆, λ⋆) permette di definire la funzione diregressione nella forma

f(x) =l∑

i=1

(

λ⋆i − λ⋆

i

)

k(x, xi) + b⋆,

in cui b⋆ puo essere determinato utilizzando le condizioni di complementarita. Le strutturedei problemi di addestramento di SVM per la regressione e per la classificazione sonosimili. Tuttavia, in pratica l’addestramento di SVM per problemi di regressione e piucomplesso dell’addestramento di SVM per la classificazione, a causa del fatto che occorredeterminare simultaneamente i valori “ottimali” di due parametri, cioe di ǫ e di C. Ingenere il tuning di tali parametri viene effettuato con tecniche di cross-validation.

6 Algoritmi di decomposizione per l’addestramento

di SVM

La formulazione del problema di addestramento (nel caso di classificazione) di una SVMe la seguente

min f(α) = 12αTQα− eTα

t.c. yTα = 0

0 ≤ α ≤ C,

(58)

dove α ∈ Rl, Q e una matrice l× l simmetrica e semidefinita positiva, e ∈ Rl e il vettore icui elementi sono pari a uno, y ∈ {−1, 1}l e C e uno scalare positivo. Il generico elementoqij della matrice Q e yiyjk(x

i, xj), dove k(x, z) = φ(x)Tφ(z) e la funzione kernel associataall’applicazione φ dallo spazio di ingresso al feature space.

29

La matrice Hessiana Q e una matrice densa e la sua memorizzazione diventa proibitivaper problemi di dimensione elevata, cioe per problemi in cui il numero l di dati di adde-stramento e elevato. Gli algoritmi che prenderemo in considerazione per la soluzione delproblema (58) sono algoritmi di decomposizione, che non richiedono la memorizzazionedella matrice Hessiana Q.

In uno schema generale di decomposizione, ad ogni iterazione k, il vettore delle variabiliαk e partizionato in due sottovettori (αk

W , αkW

), dove W ⊂ {1, . . . , l} identifica le variabili

del sottoproblema che deve essere risolto ed e denominato working set, e W = {1, . . . , l} \W (per non appesantire la notazione la dipendenza di W e W dal contatore di iterazionik e omessa).

A partire dalla soluzione corrente αk = (αkW , α

kW

), che e un punto ammissibile, il

sottovettore αk+1W e determinato calcolando la soluzione del sottoproblema

minαW

f(αW , αkW

)

yTWαW = −yT

Wαk

W

0 ≤ αW ≤ C.

(59)

Il sottovettore αk+1W

non viene modificato, cioe αk+1W

= αkW

, e la soluzione corrente viene

aggiornata ponendo αk+1 = (αk+1W , αk+1

W).

Osservazione. La cardinalita q del working set, cioe la dimensione del sottoproblema,deve essere necessariamente maggiore di 2, perche altrimenti, per la presenza del vincololineare di uguaglianza, si avrebbe αk+1 = αk. Infatti, con q = 1 e W = {i}, se αk e unpunto ammissibile abbiamo

yiαki = −yT

Wαk

W

e affinche anche αk+1 sia ammissibile deve risultare

yiαk+1i = −yT

Wαk

W

e quindi αk+1 = αk. 2

La regola di selezione del working set e importante per assicurare proprieta di convergenzadella sequenza {αk}.

Riportiamo di seguito uno schema generale di algoritmo di decomposizione.

30

Schema di decomposizione

Dati. Un punto ammissibile α0 (in genere α0 = 0).

Inizializzazione. Poni k = 0.

While ( il criterio d’arresto non e soddisfatto)

1. seleziona il working set W k secondo una regola di Working Set Selection(WSS);

2. poni W = W k e determina una soluzione α∗W del problema (59);

3. poni αk+1i =

α∗i se i ∈W

αki altrimenti;

4. poni k = k + 1.

end while

Return α∗ = αk

6.1 Condizioni di ottimalita

Verranno definite le condizioni di ottimalita per il problema (58) in una forma che sarautilizzata nel seguito per motivare l’algoritmo di decomposizione, noto come AlgoritmoSVMlight, che costituisce uno dei metodi maggiormente impiegati.

Indichiamo con F l’insieme ammissibile del problema (58), cioe

F = {α ∈ Rl : yTα = 0, 0 ≤ α ≤ C}.

L’insieme delle direzioni ammissibili in un punto α ∈ F e il seguente cono

D(α) = {d ∈ Rl : yTd = 0, di ≥ 0, ∀ i ∈ L(α), e di ≤ 0, ∀ i ∈ U(α)}.

Dato un vettore α ∈ Rl e un insieme di indici W ⊆ {1, . . . , l}, abbiamo gia introdotto lanotazione αW ∈ R|W | per indicare il sottovettore di α costituito dalle componenti αi coni ∈ W .

Poiche f e convessa e i vincoli sono lineari, un punto ammissibile α∗ e una soluzione delproblema (58) se e solo se le condizioni KKT sono soddisfatte. Si introduca la funzioneLagrangiana

L(α, λ, ξ, ξ) =1

2αTQα− eTα+ λyTα− ξTα+ ξT (α− C),

31

dove α ∈ Rl, λ ∈ R, ξ, ξ ∈ Rl. Per ogni punto ammissibile α, denotiamo gli insiemi degliindici (lower e upper) dei vincoli di box attivi

L(α) = {i : αi = 0}, U(α) = {i : αi = C}.

Per maggiore generalita, nelle seguenti proposizioni assumeremo che la funzione obiettivof sia una funzione convessa continuamente differenziabile.

Proposizione 7 Un punto ammissibile α⋆ e una soluzione del problema (58) se e solo seesiste uno scalare λ∗ tale che

(∇f(α∗))i + λ∗yi

≥ 0 if i ∈ L(α∗)≤ 0 if i ∈ U(α∗)= 0 if i /∈ L(α∗) ∪ U(α∗).

(60)

Dim. Poiche la funzione obiettivo e convessa e i vincoli sono lineari, un punto ammissibileα⋆ e una soluzione del problema (58) se e solo se esistono moltiplicatori di Lagrangeλ⋆ ∈ R, ξ⋆, ξ⋆ ∈ Rl tali che

∇f(α⋆) + λ⋆y − ξ⋆ + ξ⋆ = 0 (61)

(ξ⋆)Tα⋆ = 0 (62)

(ξ⋆)T (α⋆ − C) = 0 (63)

ξ⋆, ξ⋆ ≥ 0. (64)

Dimostreremo che le condizioni (61)-(64) sono soddisfatte se e solo se vale la (60).(a) Supponiamo che α⋆ sia ammissibile e che siano verificate le (61)-(64).Sia α⋆

i = 0, e quindi i ∈ L(α⋆). La condizione di complementarita (63) implica ξ⋆i = 0,

per cui dalla (61) e dalla (64) si ottiene

(∇f(α∗))i + λ∗yi = ξ⋆i ≥ 0.

Analogamente, sia α⋆i = C, e quindi i ∈ U(α⋆). La condizione di complementarita (62)

implica ξ⋆i = 0, per cui dalla (61) e dalla (64) si ottiene

(∇f(α∗))i + λ∗yi = −ξ⋆i ≤ 0.

Infine, sia 0 < α⋆i < C, e quindi i /∈ L(α∗) ∪ U(α∗). Le condizioni di complementarita

(62) e (63) implicano ξ⋆i , ξ

⋆i = 0, per cui dalla (61) si ottiene

(∇f(α∗))i + λ∗yi = 0.

(b) Supponiamo che α⋆ sia ammissibile e che la (60) sia verificata.Per i = 1, . . . , l:

- se α⋆i = 0 si ponga ξ⋆

i = 0 e

ξ⋆i = (∇f(α∗))i + λ∗yi;

32

- se α⋆i = C si ponga ξ⋆

i = 0 e

ξ⋆i = − [(∇f(α∗))i + λ∗yi] ;

- se 0 < α⋆i < C si ponga ξ⋆

i = 0 e ξ⋆i = 0.

Si puo verificare facilmente che le (61)-(64) risultano soddisfatte. 2

Le condizioni KKT possono essere scritte in un’altra forma. Partizioniamo gli insiemi Le U nei sottoinsiemi L−, L+, e U−, U+ rispettivamente, dove

L−(α) = {i ∈ L(α) : yi < 0}, L+(α) = {i ∈ L(α) : yi > 0}

U−(α) = {i ∈ U(α) : yi < 0}, U+(α) = {i ∈ U(α) : yi > 0}.

Dalla proposizione 7 si ottiene immediatamente il seguente risultato.

Proposizione 8 Un punto α∗ ∈ F e soluzione del problema (58) se e solo se esiste unoscalare λ∗ tale che

λ∗ ≥ −(∇f(α∗))i

yi

∀ i ∈ L+(α∗) ∪ U−(α∗)

λ∗ ≤ −(∇f(α∗))i

yi

∀ i ∈ L−(α∗) ∪ U+(α∗)

λ∗ = −(∇f(α∗))i

yi

∀ i /∈ L(α∗) ∪ U(α∗).

(65)

In corrispondenza di un punto ammissibile α, definiamo i seguenti insiemi

R(α) = L+(α) ∪ U−(α) ∪ {i : 0 < αi < C}

S(α) = L−(α) ∪ U+(α) ∪ {i : 0 < αi < C}.(66)

Si osservi che

R(α) ∩ S(α) = {i : 0 < αi < C} R(α) ∪ S(α) = {1, . . . , l}.

Enunciamo una condizione sufficiente di ottimalita.

Proposizione 9 Sia α∗ un punto ammissibile e si assuma che uno dei due insiemi R(α⋆),S(α⋆) sia vuoto. Allora α∗ e soluzione del problema (58).

Dim. Supponiamo S(α⋆) = ∅ (il caso R(α⋆) = ∅ e perfettamente analogo). Si ponga

λ⋆ = maxi∈R(α⋆)

{

−(∇f(α⋆))i

yi

}

= maxi∈L+(α∗)∪U−(α∗)

{

−(∇f(α⋆))i

yi

}

.

Le relazioni della (65) risultano verificate e quindi α⋆ e soluzione del problema (58). 2

33

Proposizione 10 Un punto ammissibile α∗ tale che R(α⋆) e S(α⋆) sono entrambi nonvuoti e soluzione del problema (58) se e solo se

maxi∈R(α⋆)

{

−(∇f(α⋆))i

yi

}

≤ minj∈S(α⋆)

{

−(∇f(α⋆))j

yj

}

. (67)

Dim. (a) Assumiamo che il punto ammissibile α∗ sia soluzione.La proposizione 8 implica l’esistenza di un moltiplicatore λ∗ tale che la coppia (α∗, λ∗)soddisfa le condizioni (65) che possono essere scritte come segue

maxi∈L+(α∗)∪U−(α∗)

{

−(∇f(α∗))i

yi

}

≤ λ∗ ≤ mini∈L−(α∗)∪U+(α∗)

{

−(∇f(α∗))i

yi

}

λ∗ = −(∇f(α∗))i

yi

∀ i /∈ L(α∗) ∪ U(α∗).

Dalla definizione degli insiemi R(α∗) e S(α∗) si ottiene

maxi∈R(α∗)

{

−(∇f(α∗))i

yi

}

≤ minj∈S(α∗)

{

−(∇f(α∗))j

yj

}

,

e quindi la (67) e verificata.(b) Assumiamo che valga la (67).Possiamo definire un moltiplicatore λ∗ tale che

maxi∈R(α∗)

{

−(∇f(α∗))i

yi

}

≤ λ∗ ≤ mini∈S(α∗)

{

−(∇f(α∗))i

yi

}

, (68)

e quindi le relazioni di disuguaglianza della (65) sono soddisfatte. D’altra parte ladefinizione degli insiemi R(α∗), S(α∗) e la scelta del moltiplicatore λ∗ (per cui vale la(68)) implicano

max{i: 0<αi<C}

{

−(∇f(α∗))i

yi

}

≤ λ∗ ≤ min{i: 0<αi<C}

{

−(∇f(α∗))i

yi

}

,

e quindi anche le relazioni di uguaglianza della (65) sono verificate. 2

Proposizione 11 Sia α un punto ammissibile e sia (i, j) ∈ {1, . . . , l}, i 6= j, una coppiadi indici. Allora la direzione di,j ∈ Rl tale che

di,jh =

1/yi se h = i−1/yj se h = j0 altrimenti

(i) e una direzione ammissibile nel punto α se e solo se i ∈ R(α) e j ∈ S(α);

(ii) la direzione di,j e una direzione di discesa per f in α se e solo se

(∇f(α))i

yi

−(∇f(α))j

yj

< 0. (69)

34

Dim. (ia) Assumiamo che di,j sia ammissibile. Mostreremo che necessariamente i ∈ R(α)e j ∈ S(α). Supponiamo per assurdo che i ∈ R(α) e j /∈ S(α), cioe j ∈ L+(α) ∪ U−(α).

Se j ∈ L+(α) allora αj = 0 e yj = 1, per cui dj < 0 e quindi di,j non e una direzioneammissibile. Analogamente, se j ∈ U−(α) allora αj = C e yj = −1, per cui dj > 0 equindi di,j e una direzione ammissibile.

(ib) Assumiamo che i ∈ R(α) e j ∈ S(α). Occorre dimostrare che la direzione di,j e taleche

yTdi,j = 0 e di,jh ≥ 0 ∀h ∈ L(α) e di,j

h ≤ 0 ∀h ∈ U(α).

Dalla definizione di di,j segue immediatamente yTd = yidi,ji + yjd

i,jj = 0. Inoltre, abbiamo

i ∈ R(α), e quindi se i ∈ L(α), allora la (66) implica i ∈ L+(α), ossia di = 1/yi > 0.Analogamente, abbiamo j ∈ S(α), e quindi se j ∈ U(α), allora j ∈ U+(α), ossia

dj = −1/yj < 0.Le stesse conclusioni possono essere tratte nel caso in cui i ∈ U(α) e j ∈ L(α).

(ii) Poiche la funzione f e convessa e continuamente differenziabile la condizione

∇f(α)Tdi,j =(∇f(α))i

yi

−(∇f(α))j

yj

< 0

e condizione necessaria e sufficiente affinche di,j sia una direzione di discesa per f in α. 2

6.2 L’Algoritmo SVMlight

L’Algoritmo SVMlight e l’algoritmo di decomposizione che usualmente viene utilizzato perla soluzione di problemi di addestramento di SVM di dimensione elevata.

In corrispondenza di un punto ammissibile α, abbiamo gia introdotto i due insiemi

R(α) = L+(α) ∪ U−(α) ∪ {i : 0 < αi < C}

S(α) = L−(α) ∪ U+(α) ∪ {i : 0 < αi < C}.

Se la dimensione del working set q e pari a 2, in un generico algoritmo di decomposizioneoccorre risolvere, ad ogni iterazione, un sottoproblema del tipo

min q(αi, αj) =1

2

(

αi αj

)T

qii qij

qji qjj

(

αi

αj

)

− α1 − α2

t.c. yiαi + yjαj = 0

0 ≤ αh ≤ C h = i, j

(70)

E importante osservare che la soluzione di un sottoproblema a due variabili del tipo (70)puo essere ottenuta con una regola molto semplice (verra mostrato in appendice), e cio

35

motiva l’interesse nella definizione di metodi di decomposizione basati sull’aggiornamento,ad ogni iterazione, di due variabili.

Descriviamo di seguito la versione dell’Algoritmo SVMlight in cui la dimensione delworking set q e pari a 2. Preliminarmente introduciamo, in corrispondenza di un genericopunto ammissibile α, i due insiemi di indici

I(α) =

{

i : i = argmaxh∈R(α)

−(∇f(α))h

yh

}

, J(α) =

{

j : j = argminh∈S(α)

−(∇f(α))h

yh

}

. (71)

Osserviamo che:

• gli insiemi di indici I(α) e J(α) sono ben definiti se entrambi gli insiemi R(α) eS(α) sono non vuoti;

• se uno dei due insiemi R(α), S(α) e vuoto allora dalla proposizione 9 segue che α esoluzione ottima;

• se α non e soluzione ottima allora dalla proposizione 10 segue che

maxh∈R(α)

{

−(∇f(α))h

yh

}

> minh∈S(α)

{

−(∇f(α))h

yh

}

;

• se α non e soluzione allora una direzione di,j ∈ Rn, con i ∈ I(α) e j ∈ J(α), e unadirezione ammissibile e di discesa per f in α (segue dalla proposizione 11); inoltre,tra tutte le direzioni ammissibili e di discesa aventi due componenti diverse da zeroe uguali a +1 e/o -1 e quella (eventualmente non l’unica) con derivata direzionaleminore. Infatti, per ogni s ∈ R(α) e t ∈ S(α) abbiamo

−(∇f(α))i

yi

≥ −(∇f(α))s

ys

−(∇f(α))j

yj

≤ −(∇f(α))t

yt

,

da cui segue∇f(α)Tdi,j ≤ ∇f(α)Tds,t.

Quindi la coppia di indici (i, j) con i ∈ I(α) e j ∈ J(α) individua, tra tutte ledirezioni ammissibili e di discesa aventi due componenti diverse da zero e uguali a+1 e/o -1, quella di “massima discesa”.

Sulla base di queste osservazioni possiamo introdurre l’Algoritmo SVMlight.

36

Algoritmo SVMlight

Dati. Il punto iniziale α0 = 0 e il gradiente ∇f(α0) = e.

Inizializzazione. Poni k = 0.

While ( il criterio d’arresto non e soddisfatto)

1. seleziona i ∈ I(αk), j ∈ J(αk), e poni W = {i, j};

2. determina una soluzione α∗ =(

α⋆i α⋆

j

)Tdel problema (70);

3. poni αk+1h =

α∗i per h = i

α∗j per h = j

αkk altrimenti;

4. poni ∇f(αk+1) = ∇f(αk) + (αk+1i − αk

i )Qi + (αk+1j − αk

j )Qj;

5. poni k = k + 1.

end while

Return α∗ = αk

Si noti che lo schema descritto richiede la memorizzazione di un vettore di dimensione l(il gradiente ∇f(αk)) e l’estrazione di due colonne, Qi e Qj, della matrice Q. La regoladi aggiornamento del gradiente deriva dal fatto che la funzione obiettivo e quadratica percui risulta

∇f(αk+1) = Qαk +Q(

αk+1 − αk)

− e = ∇f(αk) +Q(

αk+1 − αk)

.

Per quanto riguarda le proprieta di convergenza dell’algoritmo, vale il seguente risultatola cui dimostrazione e molto tecnica ed e stata omessa.

Proposizione 12 Si assuma che la matrice Q sia simmetrica e semidefinita positiva esia {αk} la sequenza generata dall’ Algoritmo SVMlight. Ogni punto limite della sequenza{αk} e soluzione del Problema (58).

37

Criterio d’arresto

Si introducano le funzioni m(α), M(α) : F → R:

m(α) =

maxh∈R(α)

−(∇f(α))h

yh

if R(α) 6= ∅

−∞ altrimenti

M(α) =

minh∈S(α)

−(∇f(α))h

yh

if S(α) 6= ∅

+∞ altrimenti

dove R(α) e S(α) sono gli insiemi di indici precedentemente definiti. Dalla definizione dim(α) e M(α), e dalla proposizione 10, segue che α e soluzione del problema (58) se e solose m(α) ≤M(α).

Si consideri una sequenza di punti ammissibili {αk} convergente ad una soluzione α.Ad ogni iterazione k, se αk non e soluzione, segue (nuovamente dalla proposizione 10) chem(αk) > M(αk).

Uno dei criteri proposti em(αk) ≤M(αk) + ǫ, (72)

con ǫ > 0.Si osservi che le funzioni m(α) e M(α) non sono continue. Infatti, anche assumendo

αk → α per k → ∞, puo accadere che R(αk) 6= R(α) oppure S(αk) 6= S(α) per ksufficientemente grande, di conseguenza il limite

limk→∞

m(αk) = m(α)

oppure il limitelimk→∞

M(αk) = M(α)

potrebbe non essere verificato.In generale puo accadere che un punto limite α sia soluzione del problema (58), ma il

criterio (72) non e mai soddisfatto.Sotto opportune ipotesi sulla matrice Q e stato dimostrato che l’Algoritmo SVMlight

genera una sequenza {αk} tale che m(αk)−M(αk) → 0 per k → ∞. Di conseguenza, perqualsiasi valore di ǫ, l’Algoritmo SVMlight soddisfa il criterio d’arresto (72) in un numerofinito di iterazioni.

38

7 Appendice A: richiami di ottimizzazione

Combinazioni affini di vettori

Definizione 5 Si definisce sottospazio affine di uno spazio lineare V la traslazione di unsottospazio lineare W ⊆ V , ossia un insieme del tipo

S = {x0} +W= {x = x0 + w,w ∈W}.

Definizione 6 Siano x1, . . . , xm elementi di V . L’elemento di V definito da

x =m∑

i=1

αixi

tale chem∑

i=1

αi = 1

si dice combinazione affine di x1, . . . , xm.

Definizione 7 Siano x1, . . . , xm elementi di V . Si dice che x1, . . . , xm sono affinementedipendenti se esistono scalari α1, . . . , αm non tutti nulli tali che

m∑

i=1

αixi = 0m∑

i=1

αi = 0.

Vale la seguente proprieta.

I vettori x1, . . . , xm sono affinemente dipendenti (indipendenti) se e solo se i vettori xi−xj,i = 1, . . . ,m, i 6= j sono linearmente dipendenti (indipendenti).

Direzioni di discesa e direzioni ammissibili

Si consideri il problemamin f(x)x ∈ S

dove f : Rn → R e S ⊆ Rn.

Definizione 8 Si dice che un vettore d ∈ Rn, d 6= 0 e una direzione di discesa per f inx se esiste t > 0 tale che

f(x+ td) < f(x) per ogni t ∈ (0, t].

Definizione 9 Sia x ∈ S. Si dice che un vettore d ∈ Rn, d 6= 0 e una direzione ammis-sibile per S in x se esiste t > 0 tale che

x+ td ∈ S per ogni t ∈ [0, t].

39

Proposizione 13 Supponiamo che f sia continuamente differenziabile nell’intorno di unpunto x ∈ Rn e sia d ∈ Rn un vettore non nullo. Allora se risulta

∇f(x)Td < 0,

la direzione d e una direzione di discesa per f in x.

Proposizione 14 Supponiamo che f sia una funzione convessa continuamente differen-ziabile nell’intorno di un punto x ∈ Rn e sia d ∈ Rn un vettore non nullo. Allora ladirezione d e una direzione di discesa per f in x se e solo se

∇f(x)Td < 0.

Condizioni di Karush-Kuhn-Tucker

Si consideri il problema

min f(x)gi(x) ≤ 0 i = 1, . . . ,mhj(x) = 0 j = 1, . . . , p

(73)

dove f : Rn → R, g : Rn → Rm, h : Rn → Rp sono funzioni continuamente differenziabili.Si definisce funzione lagrangiana L : Rn+m+p → R la funzione

L(x, λ, µ) = f(x) +m∑

i=1

λigi(x) +p∑

j=1

µjhj.

Sia x un punto ammissibile per il problema (73). Una coppia di vettori (λ, µ) ∈ Rm ×Rp,costituisce una coppia di moltiplicatori di lagrange se soddisfa le seguenti condizioni notecome condizioni di Karush-Kuhn-Tucker (KKT)

∇xL(x, λ, µ) = 0

λTg(x) = 0

λ ≥ 0.

Si consideri il problema

min f(x)aT

i x− bi ≤ 0 i = 1, . . . ,mcTj x− dj = 0 j = 1, . . . , p.

(74)

Proposizione 15 Sia x⋆ un punto di minimo locale del problema (74). Allora x⋆ e unpunto ammissibile ed esiste una coppia di moltiplicatori di lagrange, cioe una coppia divettori (λ⋆, µ⋆) ∈ Rm ×Rp tali che

∇xL(x⋆, λ⋆, µ⋆) = 0

λ⋆i ≥ 0 λ⋆

i (aTi x

⋆ − bi) = 0 i = 1, . . . , r.(75)

40

Proposizione 16 Si assuma che la funzione f sia convessa. Condizione necessaria esufficiente affinche x⋆ sia un punto di minimo globale del problema (74) e che x⋆ siaammissibile e che esista una coppia di moltiplicatori di lagrange, cioe una coppia di vettori(λ⋆, µ⋆) ∈ Rm ×Rp tali che

∇xL(x⋆, λ⋆, µ⋆) = 0

λ⋆i ≥ 0 λ⋆

i (aTi x

⋆ − bi) = 0 i = 1, . . . , r.(76)

Distanza punto-iperpiano

Sia S ⊆ Rn un insieme convesso chiuso non vuoto, sia x ∈ Rn un punto assegnato e sia‖ · ‖ la norma euclidea. Si consideri il problema

min{‖x− y‖ y ∈ S}, (77)

ossia il problema di determinare un punto di S a distanza minima da x.

Proposizione 17 Sia S ⊆ Rn un insieme non vuoto, chiuso e convesso. Per ogni x ∈ Rn

esiste un unico vettore y⋆ ∈ S soluzione del problema (77).

Sia x ∈ Rn un punto assegnato e si consideri l’iperpiano H = {x ∈ Rn : wTx + b = 0}.La distanza di x dall’insieme convesso H, cioe la distanza di x dalla sua proiezione su H,e indicata con d(x, H) e risulta

d(x, H) =|wT x+ b|

‖w‖.

Infatti, la proiezione di x su H e la soluzione del seguente problema

miny12‖x− y‖2

wTy + b = 0

La funzione lagrangiana assume l’espressione

L(y, λ) =1

2‖x− y‖2 + λ(wTy + b),

e le condizioni KKT (in questo caso necessarie e sufficienti) possone essere scritte comesegue

∇yL(y⋆, λ⋆) = −x+ y⋆ + λw = 0

wTy⋆ + b = 0,

dalle quali si ricava

λ⋆ = −wT x+ b

‖w‖2‖x− y⋆‖ = |λ⋆|‖w‖ =

|wT x+ b|

‖w‖.

41

Programmazione convessa

Proposizione 18 Sia S un sottoinsieme convesso di Rn e sia x un qualsiasi punto di S.Allora, se S 6= {x}, comunque si fissi x ∈ S tale che x 6= x, la direzione d = x− x e unadirezione ammissibile per S in x.

Proposizione 19 Sia S un sottoinsieme convesso di Rn e supponiamo che f sia una fun-zione convessa continuamente differenziabile su un insieme aperto contenente S. Allorax⋆ ∈ S e un punto di minimo globale del problema min{f(x), x ∈ S} se e solo se

∇f(x⋆)Td ≥ 0 per ogni direzione d ammissibile in x⋆.

Proposizione 20 Sia S un sottoinsieme convesso di Rn e supponiamo che f sia una fun-zione convessa continuamente differenziabile su un insieme aperto contenente S. Allorax⋆ ∈ S e un punto di minimo globale del problema min{f(x), x ∈ S} se e solo se

∇f(x⋆)T (x− x⋆) ≥ 0 per ogni x ∈ S.

42

8 Appendice B: Calcolo della soluzione analitica per

problemi a due variabili

Si consideri il problema

min f(α) = 12αTQα− eTα

t.c. y1α1 + y2α2 = 0

0 ≤ αi ≤ C i = 1, 2,

(78)

dove Q e una matrice 2 × 2 simmetrica semidefinita positiva, y1, y2 ∈ {−1, 1}.L’insieme delle direzioni ammissibili in un punto ammissibile α e il seguente cono

D(α) = {d ∈ Rl : yTd = 0, di ≥ 0, ∀ i ∈ L(α), e di ≤ 0, ∀ i ∈ U(α)},

doveL(α) = {i : αi = 0} U(α) = {i : αi = 0}.

Dato un punto ammissibile α e una direzione d ∈ D(α), indichiamo con β il massimopasso ammissibile lungo d a partire da α, ossia

- se d1 > 0 e d2 > 0, β = min{C − α1, C − α2};

- se d1 < 0 e d2 < 0, β = min{α1, α2};

- se d1 > 0 e d2 < 0, β = min{C − α1, α2};

- se d1 < 0 e d2 > 0, β = min{α1, C − α2}.

Sia d+ =

(

1/y1

−1/y2

)

. Riportiamo di seguito uno schema di calcolo di una soluzione

ottima del problema (78).

Procedura di calcolo della soluzione analitica (PSA)

1. Se ∇f(α)Td+ = 0 poni α⋆ = α e stop;

2. Se ∇f(α)Td+ < 0 poni d⋆ = d+;

3. Se ∇f(α)Td+ > 0 poni d⋆ = −d+;

4. Calcola il massimo passo ammissibile β lungo d⋆:

4a. se β = 0 poni α⋆ = α e stop;

4b. se (d⋆)TQd⋆ = 0 poni β⋆ = β, altrimenti

calcola βnv =−∇f(α)Td⋆

(d⋆)TQd⋆e poni β⋆ = min{β, βnv};

4c. poni α⋆ = α+ β⋆d⋆ e stop.

43

Proposizione 21 La procedura PSA fornisce un vettore α⋆ che e soluzione ottima delproblema (78).

Dim. Osserviamo preliminarmente che

(i) lo spazio lineare Γ = {d ∈ R2 : yTd = 0} ha dimensione 1;

(ii) il vettore d+ =

(

1/y1

−1/y2

)

appartiene a Γ e quindi e una base di Γ;

(iii) per ogni d ∈ D(α) esiste un t > 0 tale che

d = td+ e d+ ∈ D(α), oppure d = td− e d− ∈ D(α)

(infatti, d ∈ D(α) implica yTd = 0, cioe d ∈ Γ, e quindi d = ud+, con u 6= 0, essendod+ una base di Γ);

(iv) se entrambi i vettori d+ e d− non appartengono a D(α) allora D(α) e vuoto e α euna soluzione di (78).

Si noti che la Procedura PSA termina al passo 1, oppure ai passi 4a e 4c. Analizziamo ivari casi di terminazione della procedura.

(1.) In questo caso, dalla (iii) segue ∇f(α)Td = 0 per ogni d ∈ D(α) e quindi laproposizione 19 implica che α e soluzione di (78).

Supponiamo quindi che una delle seguenti condizioni sia soddisfatta

(I) ∇f(α)Td+ < 0;

(II) ∇f(α)Td− < 0.

Si ponga d⋆ = d+ se vale la (I) e d⋆ = d− altrimenti.(4a.) In questo caso, cioe quando il massimo passo ammissibile e nullo, abbiamo che d⋆

non e una direzione ammissibile. Quindi, dalla (iii), per ogni d ∈ D(α) abbiamo d = −td⋆

con t > 0 e di conseguenza ∇f(α)Td > 0, per cui dalla proposizione 19 otteniamo che αe soluzione di (78).

Supponiamo quindi β > 0. Si noti che dalla definizione di β segue che la direzioned⋆ non e una direzione ammissibile nel punto α + βd⋆; viceversa, la direzione −d⋆ e unadirezione ammissibile nel punto α+ βd⋆ (infatti, dalla convessita dell’insieme ammissibilee dalla Proposizione 18 segue che la direzione (α−α⋆) e ammissibile in α⋆, inoltre −d⋆ =1β(α− α⋆)).

Si consideri la funzione di una variabile

φ(β) = f(α+ βd⋆) = f(α) + β∇f(α)Td⋆ +1

2β2(d⋆)TQd⋆.

Si puo facilmente verificare che

- se (d⋆)TQd⋆ = 0 allora, posto β⋆ = β, risulta φ′

(β) < 0 per ogni β ≤ β⋆;

44

- se (d⋆)TQd⋆ > 0 allora, posto

βnv =−∇f(α)Td⋆

(d⋆)TQd⋆,

e β⋆ = min{

β, βnv

}

, abbiamo φ′

(βnv) = 0, φ′

(β) < 0 per ogni β < β⋆.

Osserviamo che β⋆ e l’unica soluzione del problema unidimensionale

minφ(β)0 ≤ β ≤ β.

Mostreremo ora che il punto α⋆ = α + β⋆d⋆ e soluzione del problema (78). Il punto α⋆ eammissibile e abbiamo due possibilita: β⋆ = βnv oppure β⋆ < βnv. In particolare

- se β∗ = βnv allora∇f(α⋆)Td⋆ = φ

′

(βnv) = 0

e quindi la (iii) implica

∇f(α⋆)Td = 0 per ogni d ∈ D(α⋆),

per cui, dalla Proposizione 19 si ottiene che α⋆ e soluzione del problema (78);

- se β∗ = β < βnv allora∇f(α⋆)Td⋆ = φ

′(

β)

< 0;

tenendo conto che d⋆ /∈ D(α⋆) e −d⋆ ∈ D(α⋆), dalla (iii) segue che per ogni d ∈D(α⋆) abbiamo d = −td⋆ con t > 0 e quindi

∇f(α⋆)Td > 0 per ogni d ∈ D(α⋆);

la precedente relazione e la Proposizione 19 implicano che α⋆ e soluzione del prob-lema (78). 2

Riferimenti bibliografici

[1] Burges, C.J.C. (1998), “A tutorial on support vector machines for pattern recogni-tion,” Data Mining and Knowledge Discovery, vol. 2, pp. 121-167.

[2] Vapnik, V.N. (1995), The Nature of Statistical Learning Theory, Springer-Verlag,New York.

[3] Vapnik, V.N. (1998), Statistical Learning Theory, Wiley, New York.

45