Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

Riepilogo Tecnico: Kernel di Bernstein–Schur tramite Modulazione Schizzata e Randomizzazione Radiale

1. Definizione del Problema

I metodi kernel (ad esempio, SVM, Kernel Ridge Regression, Processi Gaussiani e strati di attenzione dei Transformer) si basano sulla matrice di Gram $N \times N$ $K_{ij} = k(x_i, x_j)$. La scalabilità di questi metodi su grandi dataset ($N > 10^5$) è ostacolata dai costi di archiviazione $O(N^2)$ e di fattorizzazione $O(N^3)$. Le mappe di caratteristiche casuali (random feature maps), che approssimano $k(x, w) \approx z(x)^\top z(w)$ con una dimensione ridotta $z$, offrono un'alternativa $O(NM)$.

Tuttavia, le attuali costruzioni di caratteristiche casuali sono strutturalmente limitate:

• Random Fourier Features (RFF) si applicano a kernel shift-invariant tramite il teorema di Bochner.
• Sketches Polinomiali (ad esempio, TensorSketch) si applicano a kernel di prodotto scalare (dot-product).
• Metodi Nyström si basano sul decadimento spettrale veloce e sono dipendenti dai dati.

Il documento affronta il kernel $\mathcal{T}$-biased:
$$k_{\mathcal{T},b}(w, x) = \frac{(w^\top x + b)^2}{\|w - x\|^2 + \varepsilon}, \quad b \ge 0, \varepsilon > 0$$
Questo kernel accoppia l'allineamento (prodotto scalare al quadrato nel numeratore) e la prossimità (inverso della distanza al quadrato nel denominatore). Crucialmente, esso non è né shift-invariant né un kernel di prodotto scalare (eccetto che sulla sfera unitaria dove distanza e prodotto scalare sono biettivi). Di conseguenza, RFF standard e lo sketching polinomiale non possono essere applicati direttamente al kernel completo, costringendo a un ritorno alla computazione intrattabile della matrice di Gram $O(N^2)$ per il calcolo esatto.

2. Metodologia: Caratteristiche Casuali di Bernstein–Schur

Gli autori propongono RAY (Random Approximation of the $\mathcal{T}$-kernel), una costruzione di caratteristiche casuali per una classe più ampia di kernel di Bernstein–Schur. Questi sono definiti come il prodotto di Schur (prodotto elemento per elemento) di un kernel a caratteristiche finite e di un kernel shift-invariant completamente monotono.

La metodologia decompone il kernel $\mathcal{T}$ in due fattori trattabili:

1. Modulazione Polinomiale: $p_b(w, x) = (w^\top x + b)^2$. Questo possiede una mappa di caratteristiche esatta a dimensione finita $p_b(x) \in \mathbb{R}^{d^2+d+1}$.
2. Fattore Radiale: $h_\varepsilon(w, x) = (\|w - x\|^2 + \varepsilon)^{-1}$. Questo è completamente monotono in $\|w-x\|^2$ e ammette una rappresentazione Bernstein–Widder come un mix di kernel gaussiani su un singolo parametro di scala $t \sim \text{Exp}(\varepsilon)$.

I passaggi della costruzione:

1. Fattorizzazione: Esprimere $k_{\mathcal{T},b} = p_b \cdot h_\varepsilon$.
2. Campionamento Radiale: Campionare il parametro di scala $t_j \sim \text{Exp}(\varepsilon)$.
3. RFF Gaussiana: Per ogni $t_j$, applicare le Random Fourier Features al risultante kernel gaussiano $e^{-t_j \|x-w\|^2}$.
4. Modulazione via Sketching: Invece di utilizzare la caratteristica polinomiale esatta $O(d^2)$ $p_b(x)$, applicare un TensorSketch (grado-2) per comprimere la modulazione in una dimensione $m$.
5. Prodotto Tensoriale: La mappa di caratteristiche finale $z(x)$ è la concatenazione del prodotto tensoriale della modulazione schizzata e delle RFF radiali.

La dimensione delle caratteristiche risultante è $D \times m$, dove $D$ è il numero di campionamenti radiali e $m$ è la dimensione dello sketch. Questa dimensione è priva del limite inferiore $O(d^2)$ associato alla caratteristica polinomiale esatta.

3. Contributi Chiave

Il documento presenta i seguenti contributi teorici ed empirici:

• Una Nuova Classe di Kernel (Bernstein–Schur): Gli autori definiscono una classe di kernel formati dal prodotto di un kernel a caratteristiche finite e di un kernel radiale completamente monotono. Forniscono un estimatore di caratteristiche casuali unificato per l'intera classe, non solo per il kernel $\mathcal{T}$.
• Analisi di Unbiasedness e Varianza:
  • Dimostrano che l'estimatore è non distorto (unbiased) ($E[z(x)^\top z(w)] = k(x, w)$).
  • Derivano una formula esatta della varianza per l'estimatore "flat" (una frequenza per scala), mostrando che scala con $(R^2 + b)^4 / (D\varepsilon^2)$.
  • Dimostrano che l'uso di una sola frequenza per scala ($D'=1$) è ottimale in termini di varianza all'interno del budget gerarchico.
• Garanzie della Norma dell'Operatore:
  • Stabiliscono un limite della norma dell'operatore di matrice-Bernstein atteso per l'approssimazione della matrice di Gram. A differenza dei banali limiti elemento per elemento che scalano con $N$, questo limite dipende dalla dimensione intrinseca e dagli autovalori superiori delle matrici di Gram del kernel e della modulazione.
  • Dimostrano la stabilità spettrale relativa deterministica per la Kernel Ridge Regression (KRR) sotto questa approssimazione.
• Estimatore Doppiamente Randomizzato (RAY):
  • Introducono lo sketching del fattore di modulazione. L'analisi teorica mostra che il condizionamento sullo sketch preserva la garanzia della norma dell'operatore della dimensione intrinseca, aggiungendo solo un singolo termine di errore additivo regolabile controllato dalla dimensione dello sketch $m$.
  • Dimostrano che questo approccio rimuove la barriera della dimensione delle caratteristiche $O(d^2)$, rendendo il metodo scalabile ad alte dimensioni.
• Decomposizione dell'Errore: Forniscono una decomposizione dell'errore tra modulazione e radiale, mostrando come il rumore radiale sia modulato dal fattore di allineamento, mentre l'errore di modulazione sia localizzato dalla prossimità radiale. Ciò spiega perché il prodotto rimane efficace anche quando la modulazione è compressa.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti principalmente in regimi off-sphere (sfere limitate con norme variabili), dove il kernel $\mathcal{T}$ è genuinamente non dot-product.

• Performance Off-Sphere: Su una sfera limitata con norme variabili, RAY mantiene un tasso di convergenza $O(1/\sqrt{D})$ indipendentemente dalla dimensione $d$. Al contrario, i metodi Nyström uniformi e k-means degradano significativamente all'aumentare di $d$, anche con un numero di landmark equivalente.
• Confronto a Costo Pari: Quando confrontato a costi di rappresentazione equivalenti, i metodi Nyström adattivi (dipendenti dai dati) possono essere più accurati di RAY per valori moderati di $N$. Tuttavia, RAY offre caratteristiche indipendenti dai dati, non distorte e in streaming, cosa che Nyström non può offrire.
• Preferenza per Target Accoppiati: In test controllati con target sintetici che richiedono sia allineamento che prossimità, il kernel $\mathcal{T}$ (approssimato da RAY) ha superato i kernel che modellano solo uno dei due fattori (Gaussian, IMQ o Polynomial da soli). Ciò valida il bias induttivo del kernel.
• Attenzione a Tempo Lineare: RAY è stato applicato come primitiva di attenzione a tempo lineare. Ha approssimato con successo l'attenzione $\mathcal{T}$-esatta con un errore mediano che decresce all'aumentare della dimensione delle caratteristiche $M$, mantenendo al contempo una memoria $O(NM)$ e consentendo la decodifica causale e in streaming (impossibile per i metodi basati su landmark).
• Addestramento su Larga Scala: Sul dataset HIGGS (11 milioni di esempi), RAY ha permesso l'addestramento in modalità primal in un contesto di streaming dove la matrice di Gram è impossibile da memorizzare, superando i limiti della modulazione esatta a parità di budget.

5. Significato e Rivendicazioni

Il documento rivendica importanza in tre aree principali:

1. Colmare i Gap Strutturali: Fornisce la prima costruzione di caratteristiche casuali per kernel che non sono né shift-invariant né dot-product, fattorizzandoli in componenti che sono suscettibili agli strumenti standard (sketching e RFF).
2. Scalabilità senza Dipendenza dai Dati: Offre un'alternativa in streaming e indipendente dai dati ai metodi Nyström per kernel non stazionari, evitando simultaneamente la matrice di Gram $O(N^2)$ e la barriera della dimensione delle caratteristiche $O(d^2)$.
3. Rigore Teorico: L'analisi va oltre i semplici limiti elemento per elemento per fornire garanzie sulla norma dell'operatore controllate dalle dimensioni intrinseche, offrendo una comprensione più sfumata dell'errore di approssimazione per kernel strutturati.

Gli autori notano con modestia che, sebbene RAY sia altamente efficace per contesti streaming e su larga scala, i metodi Nyström adattivi possono comunque essere superiori per problemi con budget fisso e $N$ moderato, dove la dipendenza dai dati è accettabile. Il metodo richiede input a norma limitata per garantire la stabilità, e la costante di varianza è più alta rispetto alle RFF standard a causa del fattore polinomiale.