SVM e funzioni kernel

Nonostante il Soft Margin, alcuni problemi sono intrinsecamente non separabili nello spazio delle feature. Tuttavia, dalla conoscenza del problema, è possibile intuire che una trasformazione non lineare $\phi:X \to F$ trasforma lo spazio delle feature di input $\mathcal{X}$ nello spazio delle feature $\mathcal{F}$ dove l'iperpiano di separazione permette di discriminare meglio le categorie. La funzione discriminante nello spazio $\mathcal{F}$ è

$$f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) + b$$ (5.59)

Per permettere la separazione, normalmente lo spazio $\mathcal{F}$ è di dimensioni maggiori dello spazio $\mathcal{X}$. Questo aumento di dimensioni renderebbe costoso calcolare esplicitamente le coordinate dei campioni nello spazio $\mathcal{F}$. I metodi Kernel permettono di lavorare nello spazio trasformato senza doverne calcolare esplicitamente le coordinate.

Il vettore $\mathbf{w}$ è una combinazione lineare dei campioni di addestramento (i support vector nel caso hard margin):

$$\mathbf{w} = \sum_i \alpha_i y_i \phi(\mathbf{x}_i)$$ (5.60)

La funzione discriminante assume pertanto la forma

$$\begin{array}{rl} f(\mathbf{x}) &= \sum_i \alpha_i y_i \p... ...um_i \alpha_i y_i k(\mathbf{x},\mathbf{x}_i) +b. \end{array}$$ (5.61)

con la valutazione della funzione kernel $k(\mathbf{x},\mathbf{x}')$.

Al momento della valutazione della funzione discriminante pertanto è richiesto l'utilizzo dei vettori di supporto (almeno quelli con un parametro $\alpha_i$ associato non trascurabile). Di fatto SVM con kernel individua alcuni campioni dell'insieme di addestramento come informazione utile per capire quanto vicino a loro è il campione di valutazione in esame.

Per un vettore di supporto $\mathbf{x}_j$ che soddisfa le condizioni di margine, il termine di bias può essere ottenuto da

$$b = y_j - \sum_i \alpha_i y_i k(\mathbf{x}_i,\mathbf{x}_j).$$ (5.62)

Nella pratica si utilizza spesso una media dei valori ottenuti dai diversi vettori di supporto.

I kernel più diffusi, in quanto semplici da valutare, sono i kernel gaussiani nella forma

$$k(\mathbf{x},\mathbf{x}') = e^{-\gamma \Vert\mathbf{x}-\mathbf{x}'\Vert^2 }$$ (5.63)

con $\gamma$ parametro da impostare, e i kernel polinomiali di grado $d$ nella forma

$$k(\mathbf{x},\mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + 1)^d$$ (5.64)

e nel caso $d=1$ si ottiene un kernel affine

$$k(\mathbf{x},\mathbf{x}') = \mathbf{x}^{\top}\mathbf{x}' + 1,$$ (5.65)

strettamente correlato al kernel lineare.

L'utilizzo di funzioni kernel, unita alla possibilità di precalcolare tutte le combinazioni $k(\mathbf{x}_i,\mathbf{x}_j)$, permette di definire un'interfaccia comune tra gli addestramenti lineari e i non lineari, mantenendo di fatto lo stesso grado di prestazioni.

È interessante osservare che la funzione discriminante può essere espressa esclusivamente mediante valutazioni della funzione kernel

$$f(\mathbf{x}) = \sum_i \alpha_i y_i k(\mathbf{x},\mathbf{x}_i) + b,$$ (5.66)

dove i campioni $\mathbf{x}_i$ corrispondono ai vettori di supporto. La classificazione di un nuovo campione dipende quindi dalla sua somiglianza con i vettori di supporto misurata dalla funzione kernel.

Da questo punto di vista, il classificatore realizza una forma di template matching, nella quale il campione $\mathbf {x}$ viene confrontato con i vettori di supporto mediante la funzione kernel.

Abbiamo quindi visto come un classificatore possa essere costruito imponendo direttamente una geometria della separazione tra le classi. La formulazione mediante hinge loss permette tuttavia di ricondurre anche SVM al quadro più generale della minimizzazione del rischio empirico che verrà introdotto nella sezione successiva.