SVM

LDA si pone come obiettivo quello di massimizzare la distanza statistica tra le classi ma non cerca di valutare quale sia l'effettivo margine di separazione tra di loro.

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

SVM (CV95), come LDA, permette di ottenere un classificatore lineare basato su una funzione discriminante nella stessa forma mostrata in equazione (4.5). SVM però va oltre: l'iperpiano ottimo in $\mathbb{R}^{n}$ viene generato in maniera tale da separare “fisicamente” (decision boundary) gli elementi del problema di classificazione binario ovvero si pone come obiettivo quello di massimizzare il margine di separazione tra le classi. Questo ragionamento premia molto per quanto riguarda la generalizzazione del classificatore.

Siano pertanto definite come classi di classificazione quelle tipiche di un problema binario nella forma $y_i = \{+1,-1\}$ e si faccia riferimento all'iperpiano di formula (4.4). 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 ... ...bf{w}_0 + b_0 \leq -1 & \text{per } y_i = -1 \\ \end{array}$$ (4.16)

ovvero, in forma più compatta:

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

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

Si può supporre che esistano, per ognuna delle categorie, uno o più vettori $\mathbf{x}_i$ dove le disuguaglianze (4.17) diventano uguaglianze. Tali elementi, chiamati Support Vectors, sono i punti più estremi della distribuzione e la loro distanza rappresenta la misura del margine di separazione tra le due categorie.

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

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

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

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

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

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

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

Questa classe di problemi (minimizzazione con vincoli come disuguaglianze o primal optimization problem) si risolvono utilizzando l'approccio di Karush-Kuhn-Tucker che è il metodo dei moltiplicatori di Lagrange generalizzato a disuguaglianze. Attraverso le condizioni KKT si ottiene la funzione lagrangiana:

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

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$$ (4.22)

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

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

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

sotto i vincoli $\alpha_i \ge 0$ e $\sum \alpha_i y_i = 0$. Il massimo della funzione $\Psi$ calcolato su $\boldsymbol\alpha$ sono gli $\alpha_i$ associati a ogni vettore di addestramento $\mathbf{x}_i$. Tale massimo permette di trovare la soluzione del problema originale.

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$$ (4.25)

Questo vincolo dice che il massimo della lagrangiana o è sul bordo del vincolo ( $\alpha_i\neq 0$) o è un minimo locale ($\alpha_i = 0$). Come conseguenza solo gli $\alpha_i$ sul limite sono non nulli e contribuiscono alla soluzione: tutti gli altri campioni di addestramento sono di fatto ininfluenti. Tali vettori, associati agli $\alpha_i > 0$, sono i Support Vectors.

Risolvendo il problema quadratico (4.24), sotto il vincolo (4.22) e $\alpha_i \geq 0$, i pesi che presentano $\alpha_i\neq 0$ saranno i Support Vectors. Tali pesi, inseriti nelle equazioni (4.23) e (4.25), porteranno a 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).