Dictionary learning for Kernel EDMD

1. Formulação do Problema

O estudo de sistemas dinâmicos não lineares frequentemente depende do framework do operador de Koopman, que transforma dinâmicas não lineares em uma evolução linear, de dimensão infinita, de observáveis. Para aproximar este operador em dimensões finitas, a Decomposição Dinâmica de Modo Estendida (EDMD) é comumente utilizada. No entanto, a EDMD requer um "dicionário" de observáveis selecionado manualmente. Se o dicionário for muito pequeno, a aproximação é pobre; se for muito grande, incorre em altos custos computacionais e instabilidade numérica (poluição espectral).

A EDMD de Kernel (kEDMD) aborda o gargalo computacional definindo implicitamente o dicionário por meio de uma função de kernel, permitindo que o tamanho da aproximação seja limitado pelo número de instantâneos ($N$) em vez do tamanho do dicionário ($M$). Contudo, a kEDMD introduz um novo desafio: selecionar o kernel apropriado e ajustar seus hiperparâmetros. Tradicionalmente, isso depende de intuição e ajuste manual. Embora o "aprendizado de dicionário" (otimização de parâmetros do dicionário via gradientes) exista para a EDMD padrão, ele não pode ser aplicado diretamente à kEDMD porque o dicionário na kEDMD é implícito e não pode ser avaliado ou diferenciado explicitamente da maneira padrão.

O Problema Central: Como automatizar a seleção e parametrização de kernels na kEDMD usando otimização baseada em gradientes (aprendizado de dicionário) sem acesso ao dicionário explícito, garantindo ao mesmo tempo a viabilidade computacional.

2. Metodologia

Os autores propõem um framework chamado kEDMD-DL (Aprendizado de Dicionário para EDMD de Kernel) que preenche a lacuna entre o aprendizado de dicionário padrão e os métodos de kernel.

A. Simplificação Teórica (kEDMD Simplificada)

Os autores demonstram primeiro que a kEDMD padrão (que usa SVD truncada para reduzir a dimensionalidade) é matematicamente equivalente a uma kEDMD Simplificada (skEDMD).

• kEDMD Padrão: Usa um grande dicionário implícito e projeta-o via SVD para uma matriz $N \times N$ ($\hat{K}$).
• kEDMD Simplificada (skEDMD): Define o dicionário explicitamente como o conjunto de funções de kernel centradas nos pontos de instantâneo: $\Psi = \{g(\cdot, x_1), \dots, g(\cdot, x_N)\}$.
• Equivalência: Eles provam (Proposição 2) que a aproximação do Operador de Koopman $K_{sk}$ derivada deste dicionário específico está linearmente relacionada à aproximação via SVD truncada $K_{tr}$. Esta equivalência permite que os autores apliquem funções de perda padrão da EDMD diretamente aos parâmetros do kernel, contornando a necessidade de diferenciação implícita complexa da projeção SVD.

B. Funções de Perda e Otimização

Como o dicionário na skEDMD é explícito (avaliado em pontos de dados), os autores podem definir várias funções de perda para o descenso de gradiente:

1. Perda de Previsão ($L_{pred}$): Minimiza o erro na previsão de estados futuros ($Y^T \approx C_p K \Psi(X)$).
2. Perda de Dicionário ($L_{dict}$): Minimiza o resíduo da equação de Koopman ($\|\Psi(Y) - K\Psi(X)\|^2$).
3. Perda de Previsão de Autovalor ($L_{eig-pred}$): Minimiza o erro usando modos de Koopman e autovalores.

Descoberta Chave: Experimentos mostram que a Perda de Previsão ($L_{pred}$) é a mais robusta e eficaz para treinamento, enquanto perdas de dicionário padrão frequentemente sofrem de soluções triviais ou instabilidade, especialmente com kernels de parâmetro único.

C. Mistura de Kernels e Esparsidade

Para evitar a dificuldade de adivinhar o "tipo" correto de kernel, o método usa uma soma ponderada de múltiplos kernels:
$$g_\theta(x, y) = \sum_{i=1}^{M_g} \tilde{w}_i^2 g_{\theta_i}(x, y)$$

• Parâmetros Externos ($w_i$): Pesos para cada tipo de kernel.
• Parâmetros Internos ($\theta_i$): Hiperparâmetros de kernels individuais (ex.: largura RBF $\sigma$, coeficientes lineares).
• Esparsidade via Poda: Os autores aplicam regularização $L_1$ aos pesos externos ($w_i$) e regularização $L_2$ aos parâmetros internos. Isso incentiva a otimização a levar os pesos de kernels não importantes a zero. Após o treinamento, kernels com pesos negligenciáveis são podados (removidos), resultando em uma representação de kernel esparsa e eficiente.

D. Melhorias Computacionais

Para tornar o treinamento viável para grandes conjuntos de dados:

• Descenso de Gradiente Estocástico (SGD): Usa mini-lotes para melhorar a generalização e navegar em paisagens de perda acidentadas.
• Subamostragem: A matriz de Koopman é computada em um conjunto subamostrado de pontos ($\tilde{N} \ll N$) para reduzir o custo computacional.
• Agendador de Regularização: Um agendador ajusta dinamicamente a constante de regularização para a inversão da matriz de Koopman. Começa alto para estabilizar o treinamento com kernels iniciais ruins e diminui à medida que o kernel melhora, prevenindo explosão de perda ou platô prematuro.

3. Contribuições Principais

1. Extensão do Aprendizado de Dicionário para Kernels: O artigo adapta com sucesso o aprendizado de dicionário (anteriormente limitado a dicionários explícitos como redes neurais) ao cenário implícito da kEDMD, provando a equivalência entre a kEDMD padrão e uma formulação simplificada de EDMD baseada em kernel.
2. Seleção Automatizada de Kernel: Introduz um método para aprender simultaneamente o tipo de kernel (via somas ponderadas) e os hiperparâmetros, removendo a necessidade de seleção manual de kernel.
3. Representação Esparsa de Kernel: Ao utilizar regularização $L_1$ nos pesos do kernel, o método identifica e remove automaticamente kernels irrelevantes, levando a modelos parcimoniosos.
4. Robustez à Inicialização: O agendador e as funções de perda propostos permitem que o algoritmo convirja mesmo quando inicializado com kernels "ruins" (ex.: aqueles que produzem autovalores muito fora do círculo unitário), um ponto de falha comum em métodos anteriores.

4. Resultados Experimentais

O método foi avaliado em três sistemas dinâmicos distintos:

• Oscilador de Duffing (Kernel Único):

  • Treinou um único kernel RBF.
  • Resultado: O algoritmo aprendeu com sucesso a largura ótima $\sigma$, transformando um kernel inicial pobre, semelhante a linear, em um que capturou com precisão a dinâmica do sistema e os autovalores. A perda de previsão mostrou-se superior à perda de dicionário para otimização.

• Sistema de Módulo (Seleção de Kernel):

  • Um sistema com um salto descontínuo ($x_{t+1} = (x_t + \omega) \mod 2\pi$).
  • Resultado: O algoritmo começou com uma mistura de kernels RBF, linear, cosseno e baseados em incorporação. Identificou corretamente que o kernel baseado em incorporação (que mapeia o ângulo para um círculo) era o único útil, levando os pesos dos outros três kernels a valores próximos de zero. O modelo podado alcançou autovalores exatamente no círculo unitário, correspondendo ao espectro teórico.

• PDE Kuramoto-Sivashinsky (Sistema Complexo):

  • Uma equação diferencial parcial caótica.
  • Resultado: O método aprendeu uma mistura de kernels RBF, cosseno, linear e Processo Gaussiano de Rede Neural (NNGP).
  • Poda: Após o treinamento, os kernels RBF (com $\sigma$ específico) e NNGP foram retidos, enquanto os outros foram podados.
  • Desempenho: O kernel aprendido reduziu significativamente o resíduo dos autovalores e previu trajetórias com precisão, superando o kernel aleatório inicial. Os autores notaram que um treinamento em duas etapas (pequeno $\tilde{N}$ para aprendizado inicial/poda, seguido de ajuste fino em $\tilde{N}$ maior) foi uma estratégia eficaz para equilibrar custo e precisão.

5. Significado

Este trabalho representa um passo significativo em direção à modelagem totalmente automatizada e orientada por dados de sistemas dinâmicos não lineares.

• Ponte entre Teoria e Prática: Resolve a lacuna teórica que impedia o aprendizado de dicionário em métodos de kernel, tornando a kEDMD uma ferramenta amigável ao "caixa-preta", onde o usuário não precisa de conhecimento profundo de domínio para selecionar kernels.
• Eficiência: Ao permitir a poda de kernels não importantes, produz modelos compactos que são computacionalmente eficientes para previsão e controle.
• Escalabilidade: O uso de subamostragem e SGD torna a abordagem aplicável a sistemas de alta dimensionalidade (como EDPs), onde a EDMD tradicional seria intratável.
• Impacto Futuro: O framework abre portas para integrar fluxos de kernel avançados e métodos não paramétricos na análise de sistemas dinâmicos, potencialmente substituindo a engenharia de características manual por representações aprendidas.