Dictionary learning for Kernel EDMD

1. Enunciato del Problema

Lo studio dei sistemi dinamici non lineari si basa spesso sul framework dell'operatore di Koopman, che trasforma la dinamica non lineare in un'evoluzione lineare, a dimensione infinita, di osservabili. Per approssimare tale operatore in dimensioni finite, si utilizza comunemente la Decomposizione Dinamica delle Modalità Estesa (EDMD). Tuttavia, l'EDMD richiede una "dizionario" di osservabili selezionato manualmente. Se il dizionario è troppo piccolo, l'approssimazione è scarsa; se è troppo grande, comporta elevati costi computazionali e instabilità numerica (inquinamento spettrale).

La kEDMD (Kernel EDMD) affronta il collo di bottiglia computazionale definendo implicitamente il dizionario tramite una funzione kernel, permettendo alla dimensione dell'approssimazione di essere limitata dal numero di snapshot ($N$) piuttosto che dalla dimensione del dizionario ($M$). Tuttavia, la kEDMD introduce una nuova sfida: selezionare il kernel appropriato e sintonizzare i suoi iperparametri. Tradizionalmente, questo dipende dall'intuizione e dalla sintonizzazione manuale. Sebbene esista il "dictionary learning" (ottimizzazione dei parametri del dizionario tramite gradienti) per l'EDMD standard, non può essere applicato direttamente alla kEDMD perché il dizionario nella kEDMD è implicito e non può essere valutato o differenziato esplicitamente nel modo standard.

Il Problema Centrale: Come automatizzare la selezione e la parametrizzazione dei kernel nella kEDMD utilizzando l'ottimizzazione basata sui gradienti (dictionary learning) senza accesso al dizionario esplicito, garantendo al contempo la fattibilità computazionale.

2. Metodologia

Gli autori propongono un framework chiamato kEDMD-DL (Dictionary Learning for Kernel EDMD) che colma il divario tra il dictionary learning standard e i metodi kernel.

A. Semplificazione Teorica (kEDMD Semplificata)

Gli autori dimostrano innanzitutto che la kEDMD standard (che utilizza la SVD troncata per ridurre la dimensionalità) è matematicamente equivalente a una kEDMD Semplificata (skEDMD).

• kEDMD Standard: Utilizza un grande dizionario implicito e lo proietta tramite SVD su una matrice $N \times N$ ($\hat{K}$).
• kEDMD Semplificata (skEDMD): Definisce il dizionario esplicitamente come l'insieme delle funzioni kernel centrate sui punti degli snapshot: $\Psi = \{g(\cdot, x_1), \dots, g(\cdot, x_N)\}$.
• Equivalenza: Dimostrano (Proposizione 2) che l'approssimazione di Koopman $K_{sk}$ derivata da questo specifico dizionario è linearmente correlata all'approssimazione $K_{tr}$ ottenuta tramite SVD troncata. Questa equivalenza permette agli autori di applicare direttamente le funzioni di perdita dell'EDMD standard ai parametri del kernel, bypassando la necessità di una differenziazione implicita complessa della proiezione SVD.

B. Funzioni di Perdita e Ottimizzazione

Poiché il dizionario nella skEDMD è esplicito (valutato sui punti dei dati), gli autori possono definire varie funzioni di perdita per la discesa del gradiente:

1. Perdita di Previsione ($L_{pred}$): Minimizza l'errore nella previsione degli stati futuri ($Y^T \approx C_p K \Psi(X)$).
2. Perdita del Dizionario ($L_{dict}$): Minimizza il residuo dell'equazione di Koopman ($\|\Psi(Y) - K\Psi(X)\|^2$).
3. Perdita di Previsione degli Autovalori ($L_{eig-pred}$): Minimizza l'errore utilizzando modi di Koopman e autovalori.

Risultato Chiave: Gli esperimenti mostrano che la Perdita di Previsione ($L_{pred}$) è la più robusta ed efficace per l'addestramento, mentre le perdite del dizionario standard soffrono spesso di soluzioni banali o instabilità, specialmente con kernel a singolo parametro.

C. Miscela di Kernel e Sparsità

Per evitare la difficoltà di indovinare il "tipo" corretto di kernel, il metodo utilizza una somma pesata di più kernel:
$$g_\theta(x, y) = \sum_{i=1}^{M_g} \tilde{w}_i^2 g_{\theta_i}(x, y)$$

• Parametri Esteri ($w_i$): Pesi per ogni tipo di kernel.
• Parametri Interni ($\theta_i$): Iperparametri dei singoli kernel (ad es. larghezza RBF $\sigma$, coefficienti lineari).
• Sparsità tramite Potatura: Gli autori applicano la regolarizzazione $L_1$ ai pesi esterni ($w_i$) e la regolarizzazione $L_2$ ai parametri interni. Questo incoraggia l'ottimizzazione a portare i pesi dei kernel non importanti a zero. Dopo l'addestramento, i kernel con pesi trascurabili vengono potati (rimossi), risultando in una rappresentazione del kernel sparsa ed efficiente.

D. Miglioramenti Computazionali

Per rendere l'addestramento fattibile per grandi dataset:

• Discesa Stocastica del Gradiente (SGD): Utilizza mini-batch per migliorare la generalizzazione e navigare paesaggi di perdita accidentati.
• Sottocampionamento: La matrice di Koopman viene calcolata su un sottoinsieme di punti ($\tilde{N} \ll N$) per ridurre il costo computazionale.
• Programmatore di Regolarizzazione: Un programmatore regola dinamicamente la costante di regolarizzazione per l'inversione della matrice di Koopman. Inizia con un valore alto per stabilizzare l'addestramento con kernel iniziali scadenti e diminuisce man mano che il kernel migliora, prevenendo l'esplosione della perdita o il raggiungimento prematuro di un plateau.

3. Contributi Chiave

1. Estensione del Dictionary Learning ai Kernel: Il documento adatta con successo il dictionary learning (precedentemente limitato a dizionari espliciti come le reti neurali) al contesto implicito della kEDMD, dimostrando l'equivalenza tra kEDMD standard e una formulazione EDMD basata su kernel semplificata.
2. Selezione Automatica del Kernel: Introduce un metodo per apprendere simultaneamente sia il tipo di kernel (tramite somme pesate) sia gli iperparametri, eliminando la necessità di una selezione manuale del kernel.
3. Rappresentazione Sparsa del Kernel: Sfruttando la regolarizzazione $L_1$ sui pesi del kernel, il metodo identifica e rimuove automaticamente i kernel irrilevanti, portando a modelli parsimoniosi.
4. Robustezza all'Inizializzazione: Il programmatore e le funzioni di perdita proposti permettono all'algoritmo di convergere anche quando inizializzato con kernel "cattivi" (ad es. quelli che producono autovalori ben al di fuori del cerchio unitario), un punto di fallimento comune nei metodi precedenti.

4. Risultati Sperimentali

Il metodo è stato valutato su tre sistemi dinamici distinti:

• Oscillatore di Duffing (Singolo Kernel):

  • Addestrato un singolo kernel RBF.
  • Risultato: L'algoritmo ha appreso con successo la banda ottimale $\sigma$, trasformando un kernel iniziale simile a una linea in uno che cattura accuratamente la dinamica del sistema e gli autovalori. È stato dimostrato che la perdita di previsione è superiore alla perdita del dizionario per l'ottimizzazione.

• Sistema Modulo (Selezione del Kernel):

  • Un sistema con un salto discontinuo ($x_{t+1} = (x_t + \omega) \mod 2\pi$).
  • Risultato: L'algoritmo è partito con una miscela di kernel RBF, lineari, coseno e basati su embedding. Ha correttamente identificato che il kernel basato su embedding (che mappa l'angolo su un cerchio) era l'unico utile, portando i pesi degli altri tre kernel a valori prossimi allo zero. Il modello potato ha raggiunto autovalori esattamente sul cerchio unitario, corrispondenti allo spettro teorico.

• PDE di Kuramoto-Sivashinsky (Sistema Complesso):

  • Un'equazione differenziale parziale caotica.
  • Risultato: Il metodo ha appreso una miscela di kernel RBF, coseno, lineari e Neural Network Gaussian Process (NNGP).
  • Potatura: Dopo l'addestramento, sono stati mantenuti i kernel RBF (con specifico $\sigma$) e NNGP, mentre gli altri sono stati potati.
  • Prestazioni: Il kernel appreso ha ridotto significativamente il residuo degli autovalori e ha previsto con precisione le traiettorie, superando il kernel iniziale casuale. Gli autori hanno notato che un addestramento in due fasi (piccolo $\tilde{N}$ per l'apprendimento iniziale/potatura, seguito da affinamento su $\tilde{N}$ più grande) è stata una strategia efficace per bilanciare costo e accuratezza.

5. Significato

Questo lavoro rappresenta un passo significativo verso la modellazione completamente automatizzata e guidata dai dati dei sistemi dinamici non lineari.

• Colmare il Divario tra Teoria e Pratica: Risolve il divario teorico che impediva il dictionary learning nei metodi kernel, rendendo la kEDMD uno strumento "black-box" amichevole, dove l'utente non ha bisogno di una profonda conoscenza di dominio per selezionare i kernel.
• Efficienza: Abilitando la potatura dei kernel non importanti, produce modelli compatti che sono computazionalmente efficienti per la previsione e il controllo.
• Scalabilità: L'uso del sottocampionamento e della SGD rende l'approccio applicabile a sistemi ad alta dimensionalità (come le PDE) dove l'EDMD tradizionale sarebbe intrattabile.
• Impatto Futuro: Il framework apre la porta all'integrazione di flussi kernel avanzati e metodi non parametrici nell'analisi dei sistemi dinamici, potenzialmente sostituendo l'ingegneria delle caratteristiche manuale con rappresentazioni apprese.