Le Random Fourier features sono una tecnica per trasformare un kernel non lineare in una mappa di feature esplicita e finito-dimensionale. L’idea è approssimare un kernel invariante per traslazione
con un prodotto scalare tra vettori casuali
In questo modo un algoritmo kernel può essere sostituito, almeno in parte, da un modello lineare sulle feature z(x), evitando di memorizzare l’intera matrice di Gram.
Schema concettuale
| Oggetto | Formula | Ruolo |
|---|---|---|
| Kernel stazionario | \displaystyle K(x,y)=\kappa(x-y) | La similarità dipende solo dalla differenza tra i punti. |
| Misura spettrale | \displaystyle p(\omega) | Distribuzione delle frequenze associata al kernel. |
| Frequenze casuali | \displaystyle \omega_\ell\sim p | Campioni Monte Carlo nello spazio delle frequenze. |
| Fasi casuali | \displaystyle b_\ell\sim\operatorname{Unif}(0,2\pi) | Rendono reale la rappresentazione sinusoidale. |
| Feature esplicite | \displaystyle z_\ell(x)=\sqrt{\dfrac{2}{m}}\cos(\omega_\ell^T x+b_\ell) | Coordinate finite usate dal modello lineare. |
| Approssimazione | \displaystyle z(x)^Tz(y)\approx K(x,y) | Il prodotto scalare sostituisce il kernel. |
La tecnica è quindi una mappa di feature casuale: non costruisce lo spazio RKHS completo, ma produce una rappresentazione finita che ne approssima la geometria.
Da Bochner alla mappa casuale
Il teorema di Bochner stabilisce che un kernel continuo, positivo-definito e invariante per traslazione può essere rappresentato come trasformata di Fourier di una misura positiva. Se il kernel è normalizzato, si può scrivere
Per \delta=x-y, questa identità diventa
Le Random Fourier features sostituiscono l’integrale con una media Monte Carlo. Campionando \omega_1,\ldots,\omega_m e b_1,\ldots,b_m, si definisce
Allora
Esempio: kernel gaussiano RBF
Per il kernel gaussiano
la distribuzione spettrale è gaussiana:
La mappa casuale è quindi ottenuta campionando frequenze gaussiane e fasi uniformi:
| Passaggio | Formula | Significato |
|---|---|---|
| Kernel | \displaystyle K(x,y)=\exp(-\gamma\lVert x-y\rVert^2) | Similarità locale e liscia. |
| Frequenze | \displaystyle \omega_\ell\sim\mathcal N(0,2\gamma I_d) | Frequenze coerenti con lo spettro RBF. |
| Fasi | \displaystyle b_\ell\sim\operatorname{Unif}(0,2\pi) | Sfasamenti indipendenti. |
| Feature | \displaystyle z_\ell(x)=\sqrt{\dfrac{2}{m}}\cos(\omega_\ell^Tx+b_\ell) | Coordinate esplicite della rappresentazione. |
| Gram approssimata | \displaystyle \widehat G=ZZ^T | Approssima la matrice kernel esatta. |
Il parametro m controlla il compromesso: più feature riducono l’errore di approssimazione, ma aumentano memoria e costo del modello lineare.
Confronto con kernel trick e Nyström
| Metodo | Oggetto approssimato | Formula tipica | Quando usarlo |
|---|---|---|---|
| Kernel trick esatto | Spazio di feature implicito | \displaystyle G_{ij}=K(x_i,x_j) | Dataset piccoli o medi, quando la matrice kernel è gestibile. |
| Random Fourier features | Kernel stazionario | \displaystyle K(x,y)\approx z(x)^Tz(y) | Dataset grandi con kernel RBF o altri kernel invarianti per traslazione. |
| Metodo di Nyström | Matrice kernel | \displaystyle G\approx CW^\dagger C^T | Quando si vuole approssimare direttamente la matrice di Gram con landmark. |
| Modello lineare | Feature osservate | \displaystyle K(x,y)=x^Ty | Quando la non linearità del kernel non è necessaria. |
Le Random Fourier features sono diverse dal metodo di Nyström: approssimano la funzione kernel tramite campionamento nello spazio delle frequenze, mentre Nyström approssima una matrice kernel già valutata su un campione di punti.
Schema operativo
| Passo | Azione | Controllo |
|---|---|---|
| 1 | Scegliere un kernel stazionario \displaystyle K(x,y)=\kappa(x-y) | Deve essere positivo-definito. |
| 2 | Ricavare o conoscere la distribuzione \displaystyle p(\omega) | È la misura spettrale indicata da Bochner. |
| 3 | Campionare \displaystyle \omega_1,\ldots,\omega_m e \displaystyle b_1,\ldots,b_m | I campioni devono essere indipendenti. |
| 4 | Costruire la matrice \displaystyle Z con righe \displaystyle z(x_i)^T | Si ottiene una rappresentazione esplicita dei dati. |
| 5 | Addestrare un modello lineare su \displaystyle Z | Il kernel viene sostituito da prodotti scalari ordinari. |
| 6 | Validare \displaystyle m e gli iperparametri del kernel | Troppo poche feature introducono errore; troppe aumentano costo e overfitting. |
Vantaggi e limiti
| Aspetto | Vantaggio | Limite |
|---|---|---|
| Memoria | Evita una matrice kernel \displaystyle n\times n | Serve memorizzare \displaystyle n\times m feature. |
| Addestramento | Permette solutori lineari scalabili | L’approssimazione introduce varianza Monte Carlo. |
| Generalizzazione | Mantiene una geometria kernel non lineare | Il numero \displaystyle m va scelto con validazione. |
| Interpretazione | Rende esplicita la mappa usata dal modello | Le singole feature sinusoidali raramente sono interpretabili. |
Errori comuni
- Usarle per qualunque kernel: la costruzione classica vale per kernel invarianti per traslazione e positivi-definiti.
- Confondere feature casuali e selezione delle feature: qui si generano nuove coordinate sinusoidali, non si scelgono variabili già presenti.
- Dimenticare la standardizzazione dei dati: nei kernel basati su distanze, scale diverse cambiano lo spettro effettivo del problema.
- Scegliere m solo per comodità computazionale: poche feature possono produrre una geometria troppo rumorosa.
- Credere che l’approssimazione elimini la validazione del kernel: restano da scegliere \gamma, regolarizzazione e numero di feature.
Vedi anche: mappa di feature, kernel trick, metodo di Nyström, matrice di Gram, teorema di Bochner, funzione positiva-definita, spazio di Hilbert a kernel riproducente, support vector machine.