Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models

1. Il Problema

Il lavoro affronta il problema della predizione causale non lineare in scenari in cui le osservazioni sono generate da un modello nascosto di Markov (HMM). L'obiettivo specifico è calcolare la probabilità condizionale del prossimo token (osservazione) data una sequenza finita di osservazioni passate:
$$P(Z_{T+1} = z \mid Z_1, Z_2, \dots, Z_T)$$
dove $Z_t$ appartiene a un vocabolario finito $\mathcal{O}$.

Sebbene gli architetture Transformer (in particolare quelli "decoder-only") siano lo stato dell'arte per questo compito, la loro natura è spesso vista come una "scatola nera" appresa dai dati. L'obiettivo degli autori non è modellare matematicamente un Transformer esistente, ma derivare da primi principi un'architettura di inferenza che risolva lo stesso problema di predizione, ispirandosi alla struttura del Transformer ma basandosi su fondamenti teorici rigorosi (teoria del controllo ottimo e filtraggio stocastico).

2. Metodologia

L'approccio proposto si basa su una riformulazione del problema di predizione come un problema di controllo ottimo.

A. Rappresentazione del Predittore Non Lineare

Gli autori propongono una nuova rappresentazione per la misura condizionale (il filtro non lineare $\pi_T$) sotto forma di una somma pesata delle osservazioni passate:
$$\pi_T(F) = (\text{costante}) - \sum_{t=1}^{T} U_{t-1}^T e(Z_t)$$
dove:

• $e(Z_t)$ è una mappatura dei token in uno spazio vettoriale (simile al one-hot encoding ma con una struttura specifica per garantire la ben-postezza).
• $U_{t-1}$ sono pesi stocastici adattati alle osservazioni passate (a differenza dei pesi deterministici dei filtri lineari come il filtro di Wiener).

B. Dualità tra Filtraggio e Controllo Ottimo

Il cuore teorico del lavoro è l'introduzione di una dualità tra il problema del filtraggio non lineare (minimizzazione dell'errore quadratico medio, MMSE) e un problema di controllo ottimo.

1. Vincolo Dinamico: Viene definita un'equazione alle differenze stocastiche retrograda (BS$\Delta$E) che lega la condizione terminale alla condizione iniziale attraverso un input di controllo $U$.
2. Obiettivo di Controllo: Viene formulato un funzionale di costo che, quando minimizzato, corrisponde esattamente all'errore MMSE del filtro non lineare.
3. Soluzione: Attraverso la teoria della dualità, viene derivata una formula esplicita per il controllo ottimo $U^{(opt)}_t$. Questa formula dipende dalla misura condizionale corrente $\pi_t$, creando una relazione di punto fisso.

C. L'Algoritmo Dual Filter

Per risolvere l'equazione di punto fisso risultante, gli autori introducono l'algoritmo Dual Filter.

• Trasformazione di Layer: Viene definita una mappatura $N^{(dfltr)}$ che trasforma una sequenza di misure di probabilità in un'altra sequenza. La soluzione corretta $\pi$ è un punto fisso di questa mappatura: $\pi = N^{(dfltr)}(\pi)$.
• Algoritmi di Risoluzione:
  1. Algoritmo Iterativo: Simula l'applicazione ripetuta del layer $N^{(dfltr)}$, analogamente ai layer di un Transformer.
  2. Algoritmo "Single-Shot": Una versione più efficiente che risolve il problema in un'unica passata (un singolo ciclo di calcolo retrogrado), calcolando le misure condizionali per tutti i tempi $t$ in modo sequenziale.
• Complessità: La complessità computazionale è $O(d^2 T)$, dove $d$ è la dimensione dello stato nascosto e $T$ la lunghezza della sequenza. È indipendente dalla dimensione del vocabolario $m$, rendendolo scalabile per vocabolari molto grandi.

3. Contributi Chiave

1. Nuova Rappresentazione Teorica: La formula (1) per il predittore non lineare causale è una novità, che generalizza i predittori lineari (Wiener) al caso non lineare tramite pesi stocastici adattivi.
2. Teoria della Dualità per HMM: Risoluzione di un problema aperto nella teoria del controllo, estendendo la dualità a varianza minima (tipica dei sistemi lineari gaussiani) agli HMM discreti con osservazioni discrete.
3. Architettura Ispirata al Transformer: Definizione di un layer di trasformazione su spazi di misure di probabilità che mima strutturalmente l'architettura dei Transformer decoder-only, fornendo un'interpretazione matematica rigorosa del meccanismo di inferenza.
4. Algoritmo Efficiente: Sviluppo del "Dual Filter", un algoritmo che calcola la predizione esatta (o approssimata numericamente) senza necessità di apprendimento (training), basato solo sui parametri del modello HMM.

4. Risultati Sperimentali

Gli esperimenti numerici sono stati condotti utilizzando parametri tipici dei modelli Transformer su scala di ricerca (dimensione embedding $d=384$, vocabolario $m=65$, lunghezza contesto $T=256$), simulando un HMM con parametri noti.

• Confronto con il Filtro Non Lineare (Ground Truth): L'algoritmo Dual Filter (sia nella versione iterativa che single-shot) è stato confrontato con il filtro non lineare classico (algoritmo forward). I risultati mostrano che il Dual Filter converge rapidamente alla soluzione esatta, con errori di predizione trascurabili.
• Analisi degli Input di Controllo: L'analisi dei pesi ottimali $U_t$ rivela come l'algoritmo gestisca le correlazioni temporali:
  • Per dinamiche rapide (mixing veloce), il controllo è significativo solo per le osservazioni recenti.
  • Per dinamiche deterministiche o con correlazioni a lungo raggio, il controllo si estende su un orizzonte temporale più ampio, riflettendo la dipendenza dal passato.
• Confronto con NanoGPT (Transformer appreso): Gli autori hanno addestrato un modello NanoGPT su dati generati dallo stesso HMM.
  • In alcuni casi ("favorabili"), il Transformer appreso si avvicina alle prestazioni del Dual Filter.
  • In altri casi ("sfavorevoli"), il Transformer fallisce nel convergere verso la distribuzione di probabilità corretta, evidenziando che l'apprendimento dei Transformer non garantisce sempre la soluzione ottimale del problema di inferenza, specialmente quando la complessità del compito supera la capacità di generalizzazione del modello o la struttura dei dati.

5. Significato e Implicazioni

Questo lavoro è significativo per diversi motivi:

• Interpretabilità: Fornisce una base matematica solida per comprendere cosa fanno i Transformer durante l'inferenza, collegandoli alla teoria classica del filtraggio stocastico e del controllo ottimo.
• Separazione Inference/Learning: Dimostra che è possibile costruire architetture di inferenza ottimali per modelli generativi noti senza bisogno di addestramento, offrendo un benchmark teorico per valutare le prestazioni dei modelli basati su apprendimento.
• Scalabilità: La complessità indipendente dal vocabolario suggerisce potenziali vantaggi per applicazioni con spazi di stati o vocabolari estremamente grandi, dove i metodi basati su attenzione standard potrebbero diventare proibitivi.
• Futuro: Apre la strada a nuove direzioni di ricerca per l'apprendimento di rappresentazioni storiche (history-based) in processi decisionali parzialmente osservabili (POMDP), utilizzando la struttura del Dual Filter come base teorica.

In sintesi, il paper propone un ponte teorico elegante tra la teoria del controllo stocastico classica e le moderne architetture di Deep Learning, dimostrando che le prestazioni dei Transformer possono essere derivate e replicate (in contesti modellistici) attraverso principi di ottimizzazione rigorosi.