SVM

Figura 5.3: Iperpiano di separazione tra due classi ottenuto attraverso SVM. I punti sul margine (tratteggiato) sono i Support Vectors.

Sia LDA che la regressione logistica conducono ad una frontiera decisionale lineare. Tuttavia i criteri utilizzati per determinare tale frontiera sono profondamente differenti.

SVM (CV95), come LDA e la regressione logistica, permette di ottenere un classificatore lineare basato su una funzione discriminante della forma mostrata in equazione (5.6). Tuttavia l'approccio seguito è differente. L'obiettivo di SVM consiste infatti nel determinare, tra tutti gli iperpiani che separano correttamente le due classi, quello che massimizza il margine di separazione tra gli esempi di addestramento e la frontiera decisionale (decision boundary). L'idea alla base di questo approccio è che un margine più ampio conduca generalmente ad una migliore capacità di generalizzazione del classificatore e ad una maggiore robustezza rispetto alle variazioni presenti nei dati.

Si considerino le etichette di un problema binario nella forma $y_i \in \{+1,-1\}$ e si faccia riferimento all'iperpiano di formula (5.5). Supponiamo che esistano dei parametri $(\mathbf{w}_0,b_0)$ ottimi tali che soddisfino il vincolo

$$\begin{array}{ll} \mathbf{x}_i \cdot \mathbf{w}_0 + b_0 \ge... ...athbf{w}_0 + b_0 \leq -1 & \text{per } y_i = -1 \\ \end{array}$$ (5.42)

ovvero, in forma più compatta:

$$y_i ( \mathbf{x}_i \cdot \mathbf{w}_0 + b_0 ) - 1 \geq 0$$ (5.43)

per ogni campione $(y_i, \mathbf{x}_i)$ fornito durante la fase di addestramento.

Si può supporre che esistano, per ognuna delle categorie, uno o più vettori $\mathbf{x}_i$ per i quali il vincolo (5.43) sia soddisfatto con uguaglianza. Tali elementi prendono il nome di Support Vectors. Essi sono i campioni che determinano il margine di separazione e, come verrà mostrato in seguito attraverso le condizioni KKT, sono gli unici campioni associati a moltiplicatori di Lagrange non nulli.

La distanza $\rho$ punto-piano (cfr. eq.(1.88)) vale

$$\rho = \frac{ \Vert \mathbf{w} \cdot \mathbf{x} + b \Vert } { \Vert \mathbf{w} \Vert }$$ (5.44)

Dati due punti di classe opposta che soddisfino l'uguaglianza (5.43), il margine può essere ricavato dall'equazione (5.44), e vale

$$\rho = \frac{2}{\Vert \mathbf{w}_0 \Vert}$$ (5.45)

Per massimizzare il margine $\rho$ dell'equazione (5.45) bisogna minimizzare la sua inversa, ovvero

$$\min_{\mathbf{w},b} \frac{1}{2} \Vert \mathbf{w} \Vert^2$$ (5.46)

sotto la serie di vincoli espressi dalla diseguaglianza (5.43). Questo è quello che viene definito come problema di ottimizzazione primale in forma standard dell'SVM.

Questa classe di problemi di ottimizzazione vincolata, caratterizzati dalla presenza di vincoli di uguaglianza o disuguaglianza, può essere studiata mediante i moltiplicatori di Lagrange. Nel caso di vincoli di disuguaglianza, le condizioni di Karush-Kuhn-Tucker (KKT) forniscono le condizioni di ottimalità del problema. Introducendo i moltiplicatori di Lagrange $\alpha_i \ge 0$ associati ai vincoli dell'equazione (5.43), si ottiene la funzione lagrangiana

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol\alpha) = \frac{1}{2}... ...i \left( y_i ( \mathbf{x}_i \cdot \mathbf{w} + b ) - 1 \right)$$ (5.47)

da minimizzare in $\mathbf{w}$ e $b$ e massimizzare in $\boldsymbol\alpha$. I pesi $\alpha_i \geq 0$ sono i moltiplicatori di Lagrange. Dall'annullamento delle derivate parziali si ottiene

$$\frac{\partial \mathcal{L} }{\partial b} = 0 \rightarrow \sum y_i \alpha_i = 0$$ (5.48)

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0 \rightarrow \mathbf{w} = \sum \alpha_i y_i \mathbf{x}_i$$ (5.49)

Sostituendo tali risultati (le variabili primali) all'interno della lagrangiana (5.47) questa diventa funzione dei soli moltiplicatori, da cui si ottiene la forma duale di Wolfe:

$$\Psi (\boldsymbol\alpha) = \sum \alpha_i -\frac{1}{2} \sum_... ...um_j \alpha_i \alpha_j y_i y_j \mathbf{x}_i \cdot \mathbf{x}_j$$ (5.50)

sotto i vincoli $\alpha_i \ge 0$ e $\sum \alpha_i y_i = 0$. La soluzione del problema duale consiste nel determinare il vettore $\boldsymbol\alpha^\star$ che massimizza la funzione $\Psi(\boldsymbol\alpha)$. I coefficienti $\alpha_i^\star$ così ottenuti sono associati ai campioni di addestramento $\mathbf{x}_i$ e permettono di ricostruire la soluzione del problema primale.

Su questa relazione sono valide le condizioni KKT tra le quali è di notevole importanza il vincolo, detto di Complementary slackness,

$$\alpha_i \left( y_i ( \mathbf{x}_i \cdot \mathbf{w} + b ) - 1 \right) = 0$$ (5.51)

La condizione di complementary slackness stabilisce che, all'ottimo, per ogni campione almeno uno tra il moltiplicatore $\alpha_i$ e lo slack del vincolo deve essere nullo. In particolare

$$\alpha_i > 0 \quad\Longrightarrow\quad y_i(\mathbf{x}_i\cdot\mathbf{w}+b)=1$$ (5.52)

I campioni associati a moltiplicatori non nulli giacciono quindi esattamente sul margine e prendono il nome di Support Vectors. Tutti gli altri campioni possiedono $\alpha_i=0$ e non contribuiscono direttamente alla soluzione.

Risolvendo il problema quadratico (5.50), sotto il vincolo (5.48) e $\alpha_i \geq 0$, i campioni associati a coefficienti $\alpha_i\neq 0$ costituiscono i Support Vectors. Tali coefficienti, inseriti nelle equazioni (5.49) e (5.51), permettono di ricavare l'iperpiano di massimo margine.

Il metodo più usato per risolvere questo problema QP è il Sequential Minimal Optimization (SMO). Per una trattazione approfondita delle tematiche legate a SVM si può fare riferimento a (SS02).