Sintesi Tecnica: Inferenza Discreta Amortizzata Dipendente dal Percorso

Definizione del Problema

Il saggio affronta la sfida di campionare oggetti composizionali e discreti (ad esempio, grafi, sequenze, alberi filogenetici) da una data distribuzione posteriore non normalizzata. Sebbene i recenti progressi nelle Generative Flow Networks (GFlowNets) abbiano inquadrato questo problema come l'apprendimento di un processo decisionale di Markov (MDP) che costruisce oggetti passo dopo passo, gli autori identificano criticità fondamentali nell'assunzione Markoviana standard. La proprietà di Markov — in cui la policy dipende unicamente dallo stato corrente — può ostacolare la propagazione del segnale durante l'addestramento e portare al state aliasing (ambiguità di stato). Nel caso di state aliasing, stati distinti diventano rappresentazionalmente indistinguibili per l'agente, causando il fallimento del campionatore appreso nel distinguere le azioni ottimali per diversi percorsi che convergono allo stesso stato. Questo problema è particolarmente acuto in ambienti con ricompense sparse o complesse dipendenze strutturali, dove le standard reti neurali profonde possono mancare dell'espressività necessaria per rappresentare la policy ottimale.

Metodologia

Per superare tali limitazioni, gli autori propongono l'Inferenza Discreta Amortizzata Dipendente dal Percorso. La metodologia centrale consiste nel "sollevare" (lifting) lo spazio degli stati originale dell'MDP introducendo un sistema dinamico latente condizionato dallo stato e apprendibile $\{W_t\}_{t \ge 1}$.

1. DAG Puntato Sollevato (Lifted Pointed DAG)

Invece di un normale grafo di stato $G = (S, X, E)$, il metodo opera su un DAG puntato sollevato $G^\star$. Lo spazio degli stati è esteso da $S$ a $S^\star \subseteq S \times \Omega$, dove $\Omega$ è uno spazio latente (tipicamente $\mathbb{R}^d$).

• Dinamica Latente: La variabile latente $W_t$ evolve deterministicamente in base allo stato corrente $s_t$ e allo stato latente precedente $W_{t-1}$ tramite un campo vettoriale $\phi$ apprendibile:
  $$W_t = W_{t-1} + \phi(s_t, W_{t-1})$$
• Dipendenza della Policy: La policy forward $p_F$ diventa dipendente dal percorso, condizionata alla coppia $(s_t, W_t)$. Ciò consente alla policy di distinguere tra diversi percorsi che conducono allo stesso stato $s_t$, rompendo efficacementamente il vincolo Markoviano dello spazio degli stati originale.

2. Architettura: Matrice di Pesi Autoriflessiva (SRWM)

Per implementare il sistema dinamico latente in modo efficiente, gli autori utilizzano una Matrice di Pesi Autoriflessiva (SRWM) modificata.

• La regola di aggiornamento per lo stato latente (rappresentato come una matrice di pesi $W_t$) segue una specifica ricorrenza:
  $$q_t, k_t, v_t, \beta_t = W \psi(s_t) + b$$
  $$\bar{v}_t = W_{t-1} \zeta(k_t)$$
  $$W_t = W_{t-1} R + \sigma(\beta_t) \cdot (v_t - \bar{v}_t) \otimes \zeta(q_t)$$
• Meccanismo Chiave: L'inclusione di una matrice di rotazione $R$ fissa ed ergodica è cruciale. Essa ruota gli autovettori della matrice di pesi durante l'intero rollout del percorso. Questo meccanismo è progettato per imporre diversità nelle rappresentazioni nascoste della policy, mitigando così lo state aliasing in modo più efficace rispetto alle architetture ricorrenti standard come LSTM o GRU.

3. Obiettivi di Apprendimento

Gli autori dimostrano che gli algoritmi di apprendimento esistenti per le GFlowNets possono essere estesi a questo contesto sollevato. Dimostrano che le condizioni di Trajectorial Balance (TB), Subtrajectory Balance (SubTB) e Contrastive Balance (CB) rimangono valide per il DAG sollevato.

• Il processo di apprendimento minimizza l'aspettativa del logaritmo del quadrato della differenza tra i due lati delle equazioni di bilancio.
• Fondamentalmente, il campo vettoriale $\phi$ e la rete della policy sono appresi congiuntamente tramite discesa del gradiente stocastico su una singola funzione di perdita.
• I risultati teorici (Proposizione 4.8) indicano che se la policy backward $p_B$ è Markoviana (indipendente da $W_t$), anche la policy forward $p_F$ ottimale sarà Markoviana rispetto allo stato non sollevato. Tuttavia, quando $p_B$ è dipendente dal percorso, $p_F$ può sfruttare l'intera storia per ottenere una migliore espressività.

Contributi Chiave

1. Algoritmo Dipendente dal Percorso: L'introdure di un algoritmo general-purpose per l'inferenza amortizzata in spazi discreti e composizionali, affrontando esplicitamente i limiti di espressività dei campionatori Markoviani.
2. Dimostrazioni di Espressività Teorica:
   • Policy Lineari: Gli autori dimostrano (Proposizione 3.1) che, per le policy lineari, lo spazio delle distribuzioni apprendibili in un contesto dipendente dal percorso è strettamente maggiore rispetto a quello in un contesto Markoviano.
   • Policy GNN: Estendono questo risultato alle Graph Neural Networks (Proposizione 3.2), mostrando che le parametrizzazioni dipendenti dal percorso possono distinguere stati che le GNN 1-WL non possono distinguere (ad esempio, distinguere archi aggiunti in tempi diversi), migliorando quindi strettamente l'espressività.
3. Estensione della Teoria dell'Apprendimento: Il saggio fornisce una prova formale (Proposizione 4.5 e Corollari 4.6, 4.7) che gli obiettivi di apprendimento standard delle GFlowNet (TB, SubTB, CB) sono sufficienti per garantire un campionamento corretto nel contesto sollevato e dipendente dal percorso.
4. Validazione Empirica: Esperimenti estesi su benchmark standard (Generazione di Set, Design di Sequenze, Grid World, Modelli di Ising, ecc.) dimostrano che l'approccio dipendente dal percorso raggiunge una convergenza più rapida e una migliore bontà di adattamento (misurata tramite la distanza di Variazione Totale e il punteggio di Coerenza del Flusso) rispetto ai modelli Markoviani con parametri simili.

Risultati

L'analisi empirica evidenzia diverse scoperte coerenti:

• Espressività: Nell'ambiente "LINES" e nei compiti strutturati a grafo, i campionatori Markoviani hanno fallito nel apprendere distribuzioni non uniformi o nel distinguere tra stati strutturalmente simili, mentre i modelli dipendenti dal percorso hanno ottenuto adattamenti quasi perfetti.
• Convergenza: I modelli dipendenti dal percorso hanno costantemente converguto più velocemente. Ad esempio, nell'ambiente sparso LINES, una rete ReLU Markoviana ha impiegato circa 100 volte più iterazioni per separare le policy per stati distinti rispetto alla controparte dipendente dal percorso.
• Efficienza dell'Architettura: La SRWM con matrice di rotazione ha superato le standard reti RNN con gate (LSTM, GRU) in termini di velocità di convergenza e prestazioni finali, grazie alla sua capacità di mitigare lo state aliasing tramite il meccanismo di rotazione.
• Robustezza: Il metodo ha mostrato prestazioni superiori in compiti diversi, inclusi il design di sequenze biologiche (affinità di legame al DNA), l'apprendimento delle preferenze e le simulazioni del modello di Ising.

Significato e Rivendicazioni

Il saggio sostiene che sollevare lo spazio degli stati con un sistema dinamico latente è una strategia necessaria per il campionamento discreto amortizzato, analogamente a come l'Hamiltonian Monte Carlo (HMC) aumenta gli spazi continui con variabili di quantità di moto per accelerare la convergenza. Gli autori sostengono che:

• Lo State Aliasing è un Collo di Bottiglia Fondamentale: L'incapacità dei campionatori Markoviani di distinguere gli stati in base alla storia del percorso è una causa primaria delle scarse prestazioni in spazi composizionali complessi.
• La Dipendenza dal Percorso è Provabilmente Superiore: I risultati teorici confermano che le parametrizzazioni dipendenti dal percorso espandono strettamente la classe di ipotesi delle distribuzioni apprendibili.
• Applicabilità Pratica: Il metodo proposto è un sostituto diretto per l'addestramento standard delle GFlowNet, richiedendo solo la modifica della rappresentazione dello stato e l'uso di specifici obiettivi di apprendimento che rimangono validi nello spazio sollevato.

Gli autori concludono che gli algoritmi progettati per i processi decisionali parzialmente osservabili (POMDP) sono ben adatti al campionamento discreto amortizzato. Notano che, sebbene si siano concentrati su dinamiche latenti deterministiche, la fattibilità di dinamiche stocastiche rimane una questione aperta per la ricerca futura. Il lavoro non pretende di risolvere tutti i problemi di campionamento discreto, ma offre un framework general-purpose per mitigare i limiti specifici degli attuali approcci Markoviani.