Kernel trick — ingegnerismo.it

Il kernel trick è una tecnica dei metodi kernel: quando un algoritmo dipende dai dati solo tramite prodotti scalari, quei prodotti possono essere sostituiti da una funzione kernel senza costruire esplicitamente le coordinate dello spazio trasformato.

L’idea è applicare implicitamente una mappa di feature $\Phi$ e usare

\langle x_i,x_j\rangle \quad\longrightarrow\quad K(x_i,x_j)=\langle \Phi(x_i),\Phi(x_j)\rangle_{\mathcal F}.

In questo modo un metodo lineare nello spazio $\mathcal F$ può produrre una frontiera non lineare nello spazio originario.

Idea centrale

Il kernel trick non è un algoritmo autonomo: è una sostituzione algebrica lecita in algoritmi formulati con prodotti scalari o matrici di Gram.

Oggetto	Formula	Significato
Dati originali	$\displaystyle x_i,x_j\in\mathbb R^p$	Osservazioni nello spazio misurato.
Mappa di feature	$\displaystyle \Phi:\mathbb R^p\to\mathcal F$	Trasformazione, spesso non scritta esplicitamente.
Kernel	$\displaystyle K(x_i,x_j)=\langle \Phi(x_i),\Phi(x_j)\rangle_{\mathcal F}$	Prodotto scalare nello spazio trasformato.
Matrice di Gram	$\displaystyle G_{ij}=K(x_i,x_j)$	Riassume tutte le similarità usate dall’algoritmo.

La condizione matematica essenziale è che $K$ sia un kernel positivo semidefinito: per ogni insieme finito di punti, la matrice di Gram deve essere semidefinita positiva. Questa proprietà garantisce l’esistenza di uno spazio di Hilbert a kernel riproducente associato.

Schema operativo

Passo	Azione	Controllo
1	Scrivere l’algoritmo in termini di prodotti scalari	Deve comparire solo $\displaystyle \langle x_i,x_j\rangle$ o una matrice di Gram.
2	Scegliere un kernel $\displaystyle K$	Deve essere positivo semidefinito sul dominio dei dati.
3	Costruire $\displaystyle G_{ij}=K(x_i,x_j)$	La matrice sostituisce i prodotti scalari espliciti.
4	Risolvere il problema con $\displaystyle G$	L’ottimizzazione resta nel linguaggio dei dati osservati.
5	Valutare un nuovo punto $\displaystyle x$	Si usano i valori $\displaystyle K(x_i,x)$ rispetto ai punti di training.

Questa struttura è centrale nelle support vector machine, nella Kernel PCA e in molti stimatori regolarizzati.

Esempio polinomiale

Per $x,y\in\mathbb R^2$ , il kernel polinomiale di grado 2

K(x,y)=(1+x^T y)^2

corrisponde a un prodotto scalare in uno spazio di feature più grande. Infatti, ponendo

\Phi(x)= \left( 1,\sqrt{2}x_1,\sqrt{2}x_2,x_1^2,\sqrt{2}x_1x_2,x_2^2 \right),

si ottiene

\langle \Phi(x),\Phi(y)\rangle = 1+2x_1y_1+2x_2y_2+x_1^2y_1^2+2x_1x_2y_1y_2+x_2^2y_2^2 = (1+x^T y)^2.

Il vantaggio pratico appare quando $\Phi$ è molto grande o infinito-dimensionale: si calcola $K(x,y)$ direttamente, senza manipolare tutte le feature.

Kernel tipici

Kernel	Formula	Nota operativa
Lineare	$\displaystyle K(x,y)=x^T y$	Nessuna trasformazione non lineare implicita.
Polinomiale	$\displaystyle K(x,y)=(x^T y+c)^d$	Introduce interazioni fino al grado $\displaystyle d$ .
Gaussiano RBF	$\displaystyle K(x,y)=\exp(-\gamma\lVert x-y\rVert^2)$	Produce feature implicite infinito-dimensionali e frontiere lisce.
Sigmoide	$\displaystyle K(x,y)=\tanh(\alpha x^T y+c)$	Non è sempre positivo semidefinito; va usato solo in regimi parametrici validi.

La scelta del kernel non è un dettaglio numerico: definisce geometria, regolarità e nozione di similarità del modello.

Limiti pratici

Rischio	Effetto	Rimedi
Kernel non valido	La matrice di Gram può non rappresentare un prodotto scalare.	Verificare positiva semidefinitezza o usare famiglie note.
Costo quadratico	Memoria dell’ordine di $\displaystyle n^2$ per la matrice di Gram.	Random Fourier features, metodo di Nyström, mini-batch o metodi lineari.
Scala delle variabili	Distanze e prodotti scalari diventano dominati da alcune feature.	Standardizzare o normalizzare prima di costruire il kernel.
Iperparametri sensibili	Valori di $\displaystyle \gamma$ , $\displaystyle c$ o $\displaystyle d$ possono sovra-adattare.	Validazione incrociata e controllo della complessità.

Errori comuni

Chiamare kernel qualsiasi misura di similarità: per il kernel trick serve una funzione compatibile con un prodotto scalare implicito.
Pensare che il kernel trick elimini il costo computazionale: evita feature esplicite, ma introduce spesso una matrice di Gram grande.
Dimenticare la standardizzazione: con kernel basati su distanze, scale diverse alterano radicalmente la geometria.
Confondere kernel trick e RKHS: il kernel trick è la sostituzione operativa; l’RKHS è il quadro funzionale che la giustifica.

Vedi anche: mappa di feature, Random Fourier features, metodo di Nyström, matrice di Gram, Kernel PCA, spazio di Hilbert a kernel riproducente, support vector machine, funzione positiva-definita, analisi delle componenti principali.