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

Per permettere la separazione, normalmente lo spazio $\mathcal{F}$ è di dimensioni maggiori dello spazio $\mathcal{X}$. Questo aumento di dimensioni provoca un aumento della complessità computazionale del problema e la richiesta di risorse. I metodi Kernel risolvono questo problema.

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

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

La funzione discriminante assume pertanto la forma

$$\begin{array}{rl} f(\mathbf{x}) & = \sum_i \alpha_i \phi... ... \sum_i \alpha_i k(\mathbf{x}, \mathbf{x}_i) + b \end{array}$$ (4.32)

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.

Il bias si calcola istantaneamente dall'equazione (4.32), mediando

$$b = \E[ y_j - \sum_i \alpha_i k(\mathbf{x}_j, \mathbf{x}_i) ]$$ (4.33)

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 }$$ (4.34)

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

e nel caso $d=1$ la formulazione si riconduce al caso 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.

È da notare che le predizione $f(\mathbf{x})=\mathbf{w}^{\top} \phi(\mathbf{x})$ assume la forma

$$\phi(\mathbf{x}) = \left[ k_1(\mathbf{x}, \mathbf{x}_1), \ldots, k_n(\mathbf{x}, \mathbf{x}_n) \right]$$ (4.36)

dove $\mathbf{x}_i$ rappresenta un sottoinsieme dell'addestramento. I modelli scritto in questa forma di fatto eseguono un template matching tra il campione $\mathbf {x}$ da valutare e i prototipi $\mathbf{x}_i$.