Dictionary learning for Kernel EDMD

1. Probleemstelling

De studie van niet-lineaire dynamische systemen maakt vaak gebruik van het Koopman-operatorraamwerk, dat niet-lineaire dynamica omzet in een lineaire, oneindig-dimensionale evolutie van observabelen. Om deze operator in eindige dimensies te benaderen, wordt veelvuldig gebruikgemaakt van Extended Dynamic Mode Decomposition (EDMD). EDMD vereist echter een handmatig geselecteerd "woordenboek" van observabelen. Als het woordenboek te klein is, is de benadering slecht; als het te groot is, leidt dit tot hoge rekenkosten en numerieke instabiliteit (spectrale vervuiling).

Kernel EDMD (kEDMD) lost de rekenkundige bottleneck op door het woordenboek impliciet te definiëren via een kernelfunctie, waardoor de grootte van de benadering wordt begrensd door het aantal snapshots ($N$) in plaats van de woordenboekgrootte ($M$). kEDMD introduceert echter een nieuwe uitdaging: het selecteren van de geschikte kernel en het afstemmen van de hyperparameters. Traditioneel berust dit op intuïtie en handmatige afstelling. Hoewel "woordenboekleren" (optimalisatie van woordenboekparameters via gradiënten) bestaat voor standaard EDMD, kan dit niet direct worden toegepast op kEDMD, omdat het woordenboek in kEDMD impliciet is en niet op de gebruikelijke manier expliciet kan worden geëvalueerd of gedifferentieerd.

Het Kernprobleem: Hoe kan de selectie en parameterisatie van kernels in kEDMD worden geautomatiseerd met behulp van gradiëntgebaseerde optimalisatie (woordenboekleren) zonder toegang tot het expliciete woordenboek, terwijl rekenkundige haalbaarheid wordt gewaarborgd?

2. Methodologie

De auteurs stellen een raamwerk voor genaamd kEDMD-DL (Dictionary Learning for Kernel EDMD) dat de kloof overbrugt tussen standaard woordenboekleren en kernelmethoden.

A. Theoretische Vereenvoudiging (Vereenvoudigde kEDMD)

De auteurs tonen eerst aan dat de standaard kEDMD (die gebruikmaakt van afgeknotte SVD om de dimensionaliteit te reduceren) wiskundig equivalent is aan een Vereenvoudigde kEDMD (skEDMD).

• Standaard kEDMD: Gebruikt een groot impliciet woordenboek en projecteert dit via SVD naar een $N \times N$ matrix ($\hat{K}$).
• Vereenvoudigde kEDMD (skEDMD): Definieert het woordenboek expliciet als de verzameling kernelfuncties gecentreerd op de snapshotpunten: $\Psi = \{g(\cdot, x_1), \dots, g(\cdot, x_N)\}$.
• Equivalentie: Zij bewijzen (Propositie 2) dat de Koopman-benadering $K_{sk}$ die uit dit specifieke woordenboek voortkomt, lineair gerelateerd is aan de afgeknotte SVD-benadering $K_{tr}$. Deze equivalentie stelt de auteurs in staat om standaard EDMD-verliesfuncties direct toe te passen op de kernelparameters, waardoor de noodzaak voor complexe impliciete differentiatie van de SVD-projectie wordt omzeild.

B. Verliesfuncties en Optimalisatie

Omdat het woordenboek in skEDMD expliciet is (geëvalueerd op datapunten), kunnen de auteurs diverse verliesfuncties definiëren voor gradiëntafdaal:

1. Voorspellingsverlies ($L_{pred}$): Minimaliseert de fout bij het voorspellen van toekomstige toestanden ($Y^T \approx C_p K \Psi(X)$).
2. Woordenboekverlies ($L_{dict}$): Minimaliseert het residu van de Koopman-vergelijking ($\|\Psi(Y) - K\Psi(X)\|^2$).
3. Eigen-voorspellingsverlies ($L_{eig-pred}$): Minimaliseert de fout met behulp van Koopman-modes en eigenwaarden.

Belangrijkste Bevinding: Experimenten tonen aan dat Voorspellingsverlies ($L_{pred}$) het meest robuust en effectief is voor training, terwijl standaard woordenboekverliezen vaak lijden aan triviale oplossingen of instabiliteit, vooral bij single-parameter kernels.

C. Kernelmix en Sparsiteit

Om de moeilijkheid te omzeilen om het "juiste" kerntype te raden, maakt de methode gebruik van een gewogen som van meerdere kernels:
$$g_\theta(x, y) = \sum_{i=1}^{M_g} \tilde{w}_i^2 g_{\theta_i}(x, y)$$

• Buitenste Parameters ($w_i$): Gewichten voor elk kerntype.
• Binnenste Parameters ($\theta_i$): Hyperparameters van individuele kernels (bijv. RBF-breedte $\sigma$, lineaire coëfficiënten).
• Sparsiteit via Snoeien: De auteurs passen $L_1$-regularisatie toe op de buitenste gewichten ($w_i$) en $L_2$-regularisatie op binnenste parameters. Dit stimuleert de optimalisatie om de gewichten van onbelangrijke kernels naar nul te drijven. Na training worden kernels met verwaarloosbare gewichten gesnoeid (verwijderd), wat resulteert in een sparsere, efficiënte kernelrepresentatie.

D. Rekenkundige Verbeteringen

Om de training haalbaar te maken voor grote datasets:

• Stochastic Gradient Descent (SGD): Gebruikt mini-batches om generalisatie te verbeteren en ruwe verlieslandschappen te navigeren.
• Subsampling: De Koopman-matrix wordt berekend op een gesubsamplede set punten ($\tilde{N} \ll N$) om de rekenkosten te verlagen.
• Regularisatieplanner: Een planner past dynamisch de regularisatieconstante voor de inversie van de Koopman-matrix aan. Deze begint hoog om training te stabiliseren met slechte initiële kernels en neemt af naarmate de kernel verbetert, waardoor verliesexplosie of voortijdige plateauvorming wordt voorkomen.

3. Belangrijkste Bijdragen

1. Uitbreiding van Woordenboekleren naar Kernels: Het artikel past woordenboekleren (voorheen beperkt tot expliciete woordenboeken zoals neurale netwerken) succesvol toe op de impliciete setting van kEDMD door de equivalentie tussen standaard kEDMD en een vereenvoudigde op kernel gebaseerde EDMD-formulering te bewijzen.
2. Geautomatiseerde Kernelselectie: Het introduceert een methode om zowel het type kernel (via gewogen sommen) als de hyperparameters gelijktijdig te leren, waardoor de behoefte aan handmatige kernelselectie wordt weggenomen.
3. Sparsere Kernelrepresentatie: Door gebruik te maken van $L_1$-regularisatie op kernelgewichten, identificeert en verwijdert de methode automatisch irrelevante kernels, wat leidt tot parsimonische modellen.
4. Robuustheid ten opzichte van Initialisatie: De voorgestelde planner en verliesfuncties stellen het algoritme in staat te convergeren, zelfs wanneer geïnitieerd met "slechte" kernels (bijv. die eigenwaarden produceren ver buiten de eenheidscirkel), een veelvoorkomend faalpunt in eerdere methoden.

4. Experimentele Resultaten

De methode werd geëvalueerd op drie verschillende dynamische systemen:

• Duffing-oscillator (Enkele Kernel):

  • Er werd een enkele RBF-kernel getraind.
  • Resultaat: Het algoritme leerde succesvol de optimale bandbreedte $\sigma$, waardoor een slechte initiële, lineair-achtige kernel werd getransformeerd in een kernel die de dynamica en eigenwaarden van het systeem nauwkeurig vastlegde. Voorspellingsverlies bleek superieur aan woordenboekverlies voor optimalisatie.

• Modulo-systeem (Kernelselectie):

  • Een systeem met een discontinu spring ($x_{t+1} = (x_t + \omega) \mod 2\pi$).
  • Resultaat: Het algoritme begon met een mix van RBF-, lineaire, cosinus- en op embedding gebaseerde kernels. Het identificeerde correct dat de op embedding gebaseerde kernel (die de hoek afbeeldt op een cirkel) de enige nuttige was, waardoor de gewichten van de andere drie kernels naar bijna nul werden gedreven. Het gesnoeide model bereikte eigenwaarden exact op de eenheidscirkel, overeenkomend met het theoretische spectrum.

• Kuramoto-Sivashinsky PDE (Complex Systeem):

  • Een chaotische partiële differentiaalvergelijking.
  • Resultaat: De methode leerde een mix van RBF-, cosinus-, lineaire en Neural Network Gaussian Process (NNGP) kernels.
  • Snoeien: Na training werden de RBF (met specifieke $\sigma$) en NNGP-kernels behouden, terwijl andere werden gesnoeid.
  • Prestatie: De geleerde kernel verlaagde het residu van eigenwaarden aanzienlijk en voorspelde trajecten nauwkeurig, presterend beter dan de initiële willekeurige kernel. De auteurs merkten op dat een twee-traps training (kleine $\tilde{N}$ voor initiële leer/snoeiing, gevolgd door fijne afstelling op grotere $\tilde{N}$) een effectieve strategie was om kosten en nauwkeurigheid in evenwicht te brengen.

5. Betekenis

Dit werk vormt een belangrijke stap richting volledig geautomatiseerde, datagedreven modellering van niet-lineaire dynamische systemen.

• Brug tussen Theorie en Praktijk: Het lost de theoretische kloof op die woordenboekleren in kernelmethoden verhinderde, waardoor kEDMD een "black-box"-vriendelijk instrument wordt waarbij de gebruiker geen diepgaande domeinkennis nodig heeft om kernels te selecteren.
• Efficiëntie: Door het mogelijk maken van het snoeien van onbelangrijke kernels, worden compacte modellen geproduceerd die rekenkundig efficiënt zijn voor voorspelling en besturing.
• Schaalbaarheid: Het gebruik van subsampling en SGD maakt de aanpak toepasbaar op hoog-dimensionale systemen (zoals PDE's) waar traditionele EDMD onuitvoerbaar zou zijn.
• Toekomstige Impact: Het raamwerk opent de deur tot het integreren van geavanceerde kernelstromen en niet-parametrische methoden in de analyse van dynamische systemen, waarbij handmatige feature-engineering potentieel wordt vervangen door geleerde representaties.