Christoffel Adaptive Sampling for Sparse Random Feature Expansions

1. Il Problema

Nel calcolo scientifico e nell'apprendimento automatico scientifico (Scientific Machine Learning), l'approssimazione di funzioni multivariate complesse è spesso ostacolata dalla scarsità di dati. In molti contesti (simulazioni numeriche, esperimenti fisici, risoluzione di equazioni differenziali), l'acquisizione di dati è costosa o limitata.
I Random Feature Models (RFM) sono strumenti potenti per l'approssimazione, ma richiedono tipicamente dataset di grandi dimensioni (spesso più grandi del numero di parametri addestrabili) per garantire alta accuratezza. Le Espansioni di Caratteristiche Random Sparse (SRFE) hanno cercato di risolvere questo problema introducendo la sparsità, permettendo di lavorare con dataset ridotti. Tuttavia, le implementazioni precedenti di SRFE si basavano su strategie di campionamento non adattive (campionamento Monte Carlo casuale), che possono essere inefficienti quando i dati sono scarsi, poiché non sfruttano le informazioni strutturali della funzione target per guidare la raccolta di nuovi punti.

2. Metodologia

Il paper propone un framework integrato che combina l'apprendimento attivo con le espansioni sparse di caratteristiche random, guidato dal Campionamento Adattivo di Christoffel (CAS).

A. Concetti Fondamentali

• SRFE (Sparse Random Feature Expansions): Utilizza un insieme ampio di caratteristiche random (es. Fourier Random) ma ne seleziona un sottoinsieme sparso tramite algoritmi di recupero sparsa (come OMP o HTP) per approssimare la funzione. Questo permette di avere più caratteristiche candidate ($N$) rispetto ai punti di dati disponibili ($m$).
• Funzione di Christoffel: In teoria dell'approssimazione, la funzione di Christoffel $K(x)$ di uno spazio lineare è definita come il massimo del quadrato di un polinomio normalizzato in quel punto. È strettamente legata alla densità di probabilità ottimale per il campionamento ai minimi quadrati pesati.
• Campionamento di Christoffel (CS): Per spazi lineari, campionare i punti secondo la misura di probabilità proporzionale alla funzione di Christoffel garantisce una complessità di campionamento quasi ottimale ($O(n \log n)$).

B. L'Algoritmo CAS-SRFE

Il contributo principale è l'estensione del CS a spazi di approssimazione non lineari (come quelli generati dagli RFM) attraverso un processo iterativo adattivo:

1. Inizializzazione: Si parte con un piccolo set di punti campionati inizialmente in modo casuale (Monte Carlo) secondo la misura di base $\rho$.
2. Iterazione Adattiva:
   • Step 1 (Approssimazione Sparsa): Dati i punti attuali, si risolve un problema di recupero sparsa (usando algoritmi come Orthogonal Matching Pursuit - OMP o Hard Thresholding Pursuit - HTP) per trovare una rappresentazione sparsa della funzione. Si identifica il sottospazio lineare $P_i$ generato dalle caratteristiche selezionate (quelle con coefficienti non nulli).
   • Step 2 (Costruzione della Misura): Si calcola la funzione di Christoffel $K_{P_i}(x)$ per il sottospazio $P_i$ appena trovato. Questo richiede la costruzione della matrice di Gram delle caratteristiche selezionate e la sua decomposizione agli autovalori per ottenere una base ortonormale stabile.
   • Step 3 (Campionamento Adattivo): Si generano nuovi punti di campionamento secondo la misura di Christoffel $\mu_i$, che è proporzionale a $K_{P_i}(x)$.
3. Implementazione Efficiente del Campionamento:
   • Un problema critico nel CS è campionare dalla misura di Christoffel, che non ha una forma chiusa semplice.
   • Gli autori evitano la discretizzazione su griglie fini (che è computazionalmente proibitiva in alta dimensione) proponendo un metodo basato sull'algoritmo Metropolis-Hastings (MH).
   • Viene utilizzata una distribuzione proposta Gaussiana e un meccanismo di tuning adattivo del parametro di scala $\sigma_1$ per mantenere un tasso di accettazione ottimale (tra 0.2 e 0.45).
4. Boosting: Per migliorare la stabilità numerica, viene implementata una procedura di "boosting" che genera più set di candidati e seleziona quello che massimizza la costante di stabilità discreta (il minimo valore singolare della matrice dei minimi quadrati).

3. Contributi Chiave

1. CAS-SRFE: Introduzione di un framework unificato che integra l'apprendimento attivo (CAS) con le espansioni sparse di caratteristiche random (SRFE), superando i limiti del campionamento Monte Carlo statico.
2. Estensione a Spazi Non Lineari: Dimostrazione che la strategia di campionamento di Christoffel, originariamente teorizzata per spazi lineari, può essere efficacemente applicata a spazi non lineari attraverso un processo iterativo che aggiorna dinamicamente il sottospazio di approssimazione.
3. Metodo di Campionamento Efficiente: Sviluppo di un metodo basato su Metropolis-Hastings per campionare direttamente dalla misura di Christoffel continua, evitando i colli di bottiglia computazionali delle griglie finite e rendendo il metodo scalabile per problemi multidimensionali.
4. Analisi Numerica Completa: Confronto estensivo tra CAS-SRFE e SRFE non adattivo (NAS) su una vasta gamma di funzioni sintetiche e problemi fisici reali.

4. Risultati

Gli esperimenti numerici mostrano risultati promettenti:

• Miglioramento dell'Accuratezza: In quasi tutti i casi testati (funzioni sintetiche e modelli fisici), CAS-SRFE raggiunge un errore di approssimazione significativamente inferiore rispetto al campionamento non adattivo (NAS) a parità di numero di campioni. In molti casi, l'errore è ridotto di un ordine di grandezza.
• Efficienza dei Dati: Il metodo è particolarmente efficace in scenari a bassa disponibilità di dati, permettendo di ottenere approssimazioni accurate con meno punti di campionamento.
• Algoritmi di Recupero: La variante che utilizza HTP (Hard Thresholding Pursuit) tende spesso a performare meglio di quella con OMP, sebbene non sempre.
• Limiti in Alta Dimensione: Come previsto dalla teoria, le prestazioni degradano all'aumentare della dimensionalità ($d$). Per dimensioni molto elevate (es. $d=5$), sia CAS che NAS faticano a raggiungere alta accuratezza, suggerendo che il limite principale risiede nell'espressività del modello RFM stesso piuttosto che nella strategia di campionamento. Tuttavia, CAS mantiene comunque un vantaggio marginale rispetto a NAS.
• Applicazioni Fisiche: Il metodo è stato testato con successo su modelli di adsorbimento superficiale, oscillatori di Duffing e oscillatori armonici smorzati, dimostrando la sua utilità nella costruzione di modelli surrogati efficienti per sistemi fisici.

5. Significato e Implicazioni

Questo lavoro è significativo per il campo del calcolo scientifico perché:

• Riduce i Costi Computazionali: Offrendo un modo per ottenere alta accuratezza con meno simulazioni o esperimenti, riduce drasticamente i costi in applicazioni dove la valutazione della funzione è onerosa.
• Ponte tra Teoria e Pratica: Colma il divario tra la teoria dell'approssimazione ottimale (funzioni di Christoffel) e le moderne tecniche di machine learning (RFM, recupero sparsa), fornendo un algoritmo pratico e implementabile.
• Flessibilità: Il framework è generale e può essere adattato ad altri schemi di approssimazione non lineare oltre agli RFM, aprendo la strada a future ricerche nell'ottimizzazione del campionamento per reti neurali e altri modelli complessi.

In sintesi, il paper dimostra che l'uso intelligente e adattivo dei punti di dati, guidato dalla struttura geometrica dello spazio di approssimazione corrente, è fondamentale per superare le limitazioni imposte dalla scarsità di dati nel calcolo scientifico moderno.