Progetto di architetture digitali di machine learning su logica programmabile per applicazioni automotive

si effettua il training.
Assegnati il compito di apprendere e un numero finito di esempi per l’ad-
destramento (training set), la capacita` di generalizzazione ottimale si ottiene
bilanciando l’accuratezza acquisita nell’apprendere lo specifico insieme di ad-
destramento e l’abilita` di apprendere un qualunque insieme di dati, limitando
il fenomeno dell’overfitting.
Alcune applicazioni per cui le SVM sono state utilizzate con successo
sono:
• OCR (optical character recognition, dove in breve le SVM divennero
competitive con i migliori metodi utilizzati);
• identificazione di facce in immagini [12];
• identificazione di pedoni;
• classificazione di testi.
1.1 Teoria matematica di Support Vector Ma-
chine
Supponiamo di avere un vettore in ingresso “xi” (per i = 1, 2, . . . l) di dimen-
sioni d, che rappresenta una classe “yi” (indicata con il tag -1 o 1 a seconda
del tipo); in pratica nel caso di riconoscimento di facce questo significa che
xi potrebbero essere i pixel del viso in una immagine (figura 1.1), mentre yi e`
un’etichetta che esprime se -1 che non si tratta di un viso, mentre se 1 allora
il vettore rappresenta un viso.
Dato un insieme di vettori xi che formano un set di dati di entrambe le classi,
si puo` pensare che questi siano disposti in uno spazio a d dimensioni; lo scopo
della classificazione e` quello di trovare una superficie di decisione che separa
gli insiemi di punti che rappresentano una classe da quelli che rappresentano
l’altra (figura 1.1) [6].
3
Figura 1.1: Esempio di classificazione di pixel che rappresentano facce in
un’immagine (a sinistra) e superficie di decisione per la classe delle facce (a
destra).
1.1.1 Dati separabili linearmente
La superficie di decisione e` un iperpiano i cui punti soddisfano l’equazione
~w · ~x + b = 0, inoltre si possono definire i termini d+ e d− rispettivamente
come la distanza dell’iperpiano separatore dal piu` vicino esempio x di classe
+1 e -1. Per l’apprendimento mediante SVM e` molto importante il concetto
di “margine” dell’iperpiano (figura 1.2), definito come d+ + d−.
In prima approssimazione (se i dati sono linearmente separabili) si puo`
dire che l’algoritmo di apprendimento individua l’iperpiano separatore con il
margine piu` grande (figura 1.3).
Per poter assegnare la giusta etichetta yi ad un generico ingresso xi si
puo` pensare di trovare dei parametri “{~w, b}” tali che:
~w · ~xi + b ≥ +1 per yi = +1 (1.1)
~w · ~xi + b ≤ −1 per yi = −1 (1.2)
Queste si possono combinare in modo tale da ottenere una unica espressione
4
Figura 1.2: Raffigurazione del concetto di “Margine”.
Figura 1.3: Margine non ottimale (a sinistra) con maggiore probabilita` di
overfitting. Margine ottimale (a destra) con minore probabilita` di overfitting.
yi (~w · ~xi + b)− 1 ≥ 0 ∀i (1.3)
Si definiscono “Support Vector” (SV) i punti per cui vale l’uguaglianza
nell’espressione (1.3); in termini pratici si puo` dire che i SV sono i punti
che delimitano il margine (indicati con un cerchio aggiuntivo in figura 1.2).
5
Inoltre si ha che d+ = d− = 1‖~w‖ e, di conseguenza, il margine e` dato da 2‖~w‖ .
La funzione di decisione individua la classe di un generico dato indi-
viduando se si trova da un lato o dall’altro dell’iperpiano ed ha quindi la
forma:
f(~x, ~w, b) = sgn(~w · ~xi + b) (1.4)
Dato il concetto di margine e la sua espressione analitica 2‖~w‖ , il processo
di apprendimento di SVM trova i parametri dell’iperpiano separatore con il
margine maggiore; questo e` un problema di ottimizzazione vincolata in cui
bisogna massimizzare la funzione costo 2‖~w‖ con i vincoli (1.3). Per comodita`,
invece di massimizzare il margine, si puo` minimizzare l’inverso dell’espres-
sione e introdurre dei moltiplicatori di Lagrange αi per indicare i vincoli da
soddisfare.
L’espressione da minimizzare diventa quindi:
LP =
1
2
‖~w‖2 −
l∑
i=1
αiyi (~w · ~xi + b) +
l∑
i=1
αi (1.5)
con αi ≥ 0.
Si puo` definire una forma duale della formulazione del problema se si
considera che il gradiente della funzione Lagrangiana LP (calcolato rispetto
ai parametri da trovare, cioe` ~w e b) deve essere nullo. In questo modo si
introducono due condizioni per cui questo avvenga:
~w =
l∑
i=1
αiyi~xi (1.6)
l∑
i=1
αiyi~xi = 0 (1.7)
Sostituendo nell’equazione (1.5) si ottiene il problema duale LD
LD =
l∑
i=1
αi −
1
2
l∑
i=1
l∑
j=1
αiαjyiyj (~xi · ~xj) (1.8)
6
La soluzione ottenuta minimizzando LP e` la stessa che si ottiene massimiz-
zando LD con αi ≥ 0 ed i vincoli (1.6) e (1.7). E’ da notare che e` associato
un moltiplicatore di lagrange αi per ogni vettore xi che e` nullo per tutti i
vettori tranne che per i Support Vector.
Un esempio di separazione di dati con una funzione lineare e` evidenziato in
figura 1.4.
Figura 1.4: Esempio di iperpiano ottenuto per dati linearmente separabili.
1.1.2 Dati non separabili linearmente
Se non e` possibile separare perfettamente con un iperpiano i dati e` necessario
modificare le espressioni (1.1) e (1.2) per poter includere dei termini di errore
sulla classificazione di alcuni punti.
Si possono percio` includere delle variabili ξi per “rilassare” i vincoli di
perfetta separabilita` (figura 1.5).
7
~w · ~xi + b ≥ +1− ξi per yi = +1 (1.9)
~w · ~xi + b ≤ −1 + ξi per yi = −1 (1.10)
con ξi ≥ 0.
Figura 1.5: Variabili aggiuntive ξi per la funzione costo.
La funzione costo da minimizzare e`:
‖~w‖
2
+ C
(
l∑
i=1
ξi
)
Il parametro “C” indica il peso che viene dato ai punti che vengono classificati
nel modo sbagliato; in particolare se C ha un valore piccolo il processo di
apprendimento tende a trovare un iperpiano separatore con margine grande e
molti punti che rappresentano errori di classificazione, mentre se C e` grande
si da molta importanza al fatto di non commettere errori di classificazione
8
ma il margine dell’iperpiano puo` essere piccolo e si rischia l’overfitting sui
dati.
Anche in questo caso e` necessario massimizzare l’espressione
LD =
l∑
i=1
αi −
1
2
l∑
i=1
l∑
j=1
αiαjyiyj (~xi · ~xj) (1.11)
Soggetta ai vincoli:
0 ≤ αi ≤ C (1.12)
l∑
i=1
αiyi~xi = 0 (1.13)
1.1.3 Support Vector Machine non lineari
Nella grande maggioranza dei casi reali di pattern recognition, i dati non
sono linearmente separabili e trovare una funzione di decisione lineare che
separi i dati delle due classi non e` sufficiente per avere buone prestazioni di
classificazione, percio` si ricorre a funzioni non lineari.
Supponiamo che nello spazio dei dati Rd non sia possibile separare i dati in
modo lineare, si puo` pensare che se lo spazio avesse dimensioni maggiori e, di
conseguenza, piu` gradi di liberta`, gli stessi dati potrebbero essere linearmente
separabili. Questo nuovo spazio H e` legato allo spazio originario da una
trasformazione Φ:
Φ : Rd 7−→ H
Ogni dato dello spazio di input deve essere trasformato con Φ per ottenere
un dato del nuovo spazio, o anche chiamato spazio delle features (figura
1.6); tuttavia nell’espressione della funzione costo della forma duale (1.8)
non appare il vettore singolarmente come termine ma e` presente il prodotto
scalare tra due vettori ~xi · ~xj.
Si puo` allora pensare di definire una “funzione kernel” K(~xi, ~xj) tale che:
9
Figura 1.6: Trasformazione da uno spazio di input originario ad uno spazio
delle features in cui i dati sono separabili.
K(~xi, ~xj) = Φ (~xi) · Φ (~xj) (1.14)
Nell’algoritmo di training e` quindi sufficiente sapere la funzione kernel e non
la trasformazione che porta nello spazio delle features (“kernel trick”).
Inoltre non e` necessario sapere la funzione Φ neanche per effettuare una
decisione su un nuovo dato, dal momento che per l’equazione (1.6), ossia
~w =
l∑
i=1
αiyi~xi
sostituendo nella (1.4) si ha che la funzione di decisione e`:
f(~x,~s, b) = sgn
( Ns∑
i=1
αiyiΦ(~si) · Φ(~x) + b
)
(1.15)
= sgn
( Ns∑
i=1
αiyiK(~si, ~x) + b
)
(1.16)
Infatti gli αi sono tutti nulli tranne quelli dei Support Vector si, e cioe` un
numero pari a Ns.
10
1.1.4 La funzione kernel
Una funzione kernel K(~x, ~y) per essere tale deve soddisfare le condizioni di
Mercer, ossia per ogni funzione g(~x) per cui:
∫
g(~x) d~x e` un valore finito
deve valere la condizione
∫
K(~x, ~y)g(~x)g(~y) d~xd~y ≥ 0 (1.17)
Esistono vari tipi di kernel comunemente usati nella pratica, ad esempio:
- Polinomiale di grado “p”
K(~x, ~y) = (~x · ~y + 1)p (1.18)
- Gaussiano o Radial Basis Funcion (RBF)
K(~x, ~y) = e− ‖~x−~y‖
2
2σ2 (1.19)
(1.20)
Il risultato dell’applicazione di uno di questi kernel equivale rispettivamente
a costruire un classificatore polinomiale o un classificatore Gaussiano radial
basis function In questo modo e` possibile costruire delle superfici di decisione
non lineari tramite lo stesso processo di minimizzazione del caso lineare, e`
infatti sufficiente sostituire la funzione kernel K(~x, ~y) al prodotto scalare ~x·~y,
mantenendo quindi il problema di ottimizzazione di una funzione convessa
per il training di SVM.
Un esempio qualitativo della potenzialita` di SVM non lineari e` visibile in
figura 1.7 in cui viene applicato un kernel RBF.
11
Figura 1.7: Esempio di separazione di dati con il kernel RBF.
La funzione Kernel va scelta accuratamente per un tipo di problema:
e` sempre possibile mappare l’input in uno spazio di dimensione maggiore
del numero di punti del training set e produrre un classificatore perfetto;
tuttavia questo non avrebbe la capacita` di generalizzare su dati nuovi, per
via dell’overfitting.
Una SVM e` sostanzialmente composta da due moduli:
• un modulo generale di apprendimento;
• una funzione kernel specifica per il problema da affrontare.
SVM puo` operare con qualsiasi kernel e avere prestazioni diverse a seconda del
tipo di funzione utilizzata. Sfruttando il “kernel trick” e` possibile costruire
superfici di decisione per i dati molto diverse tra loro, come nel caso del
training set di figura 1.8.
12
Figura 1.8: Esempio di separazione di con il kernel polinomiale di grado 2
rispettivamente con C =∞ e C = 2 (prima riga); e polinomiale di grado 10
con C =∞ e RBF con σ = 1.0 e C =∞ (seconda riga).
13