Soft Margin SVM

In applicazioni reali non sempre esiste un margine, ovvero non sempre le classi sono linearmente separabili nello spazio delle features attraverso un iperpiano. Il concetto alla base del Soft Margin permette di ovviare a questo limite, introducendo una variabile $\xi$ aggiuntiva per ogni campione, in modo da rilassare (slack) il vincolo sul margine

$$\begin{array}{l} y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \ge 1 - \xi_i \\ \xi_i \ge 0, \forall i \end{array}$$ (4.26)

Il parametro $\xi$ rappresenta la slackness associata al campione. Quando $0<\xi\le 1$ il campione è correttamente classificato ma è all'interno dell'area di margine. Quando $\xi>1$ il campione entra nello spazio di decisione della classe opposta e perciò verrà classificato in maniera errata.

Per cercare ancora un iperpiano di separazione in qualche modo ottimo, la funzione costo da minimizzare deve considerare anche la distanza tra il campione e il margine:

$$\min \frac{1}{2} \Vert \mathbf{w} \Vert^2 + C \sum \xi_i$$ (4.27)

soggetta ai vincoli (4.26). Il parametro $C$ è un grado di libertà del problema per indicare quanto un campione deve pagare il violare il vincolo sul margine. Quando $C$ è piccolo, il margine è ampio, mentre quando $C$ è prossimo a infinito si ricade alla formulazione Hard Margin di SVM vista in precedenza.

Ogni campione $\mathbf{x}_i$ può ricadere in uno di tre possibili stati:

• può stare oltre il margine $y_i(\mathbf{w}^\top \mathbf{x}_i + b)>1$ e di conseguenza non contribuire alla funzione;
• può stare sul margine $y_i (\mathbf{w}^\top \mathbf{x}_i + b)=1$ non partecipando direttamente alla minimizzazione ma solo come support vector,
• può infine cadere all'interno del margine ed essere penalizzato tanto quanto si discosta dai vincoli forti.

La lagrangiana del sistema (4.27), con i vincoli introdotti dalle variabili $\xi$, è

$$\mathcal{L}(\mathbf{w},b,\xi,\alpha) = \frac{1}{2} \Vert\m... ... \cdot \mathbf{x}_i + b) - 1 + \xi_i) - \sum_i \gamma_i \xi_i$$ (4.28)

Con l'aumento del numero di vincoli, le variabili duali sono sia $\bm{\alpha}$ che $\bm{\gamma}$.

Il risultato notevole è che, applicate le derivate, la formulazione duale di (4.28) diventa esattamente uguale alla duale del caso Hard Margin: le variabili $\xi_i$ infatti non compaiono nella formulazione duale e l'unica differenza tra il caso Hard Margin e il caso Soft Margin è nel vincolo sui parametri $\alpha_i$, in questo caso limitati tra

$$0 \le \alpha_i \le C$$ (4.29)

invece che con la semplice diseguaglianza $\alpha_i \ge 0$. Il grande vantaggio di questa formulazione è proprio nella elevata semplicità dei vincoli e nel fatto che permetta di ricondurre il caso Hard Margin a un caso particolare ($C=\infty$) del Soft Margin. La costante $C$ è un limite superiore al valore che gli $\alpha_i$ possono assumere.