Exact and Approximate MCMC for Doubly-intractable Probabilistic Graphical Models Leveraging the Underlying Independence Model

1. Il Problema: Modelli Grafici a Doppia Intrattabilità

Il lavoro si concentra sull'inferenza bayesiana per modelli grafici probabilistici a distribuzione esponenziale a coppie (PEGM), come il modello di Ising, il modello di Potts e i modelli grafici di Poisson.
La sfida principale risiede nella natura "doppiamente intrattabile" di questi modelli:

1. Intrattabilità della costante di normalizzazione: La distribuzione congiunta è data da $p(x; \theta) = f(x; \theta) / z(\theta)$. Il calcolo della costante di normalizzazione $z(\theta)$ richiede la somma (o l'integrale) su tutte le possibili configurazioni delle variabili, un problema di complessità esponenziale ($2^p$ per variabili binarie) che rende il calcolo analitico impossibile per $p$ elevato.
2. Intrattabilità del rapporto di accettazione: Gli algoritmi MCMC standard (come Metropolis-Hastings) richiedono il calcolo del rapporto di accettazione, che include il rapporto $z(\theta)/z(\theta')$. Poiché $z(\theta)$ è intrattabile, questo rapporto non può essere calcolato direttamente.

Le soluzioni esistenti (come l'algoritmo di Exchange o i metodi Pseudo-marginal) presentano limiti significativi:

• Richiedono spesso campionatori perfetti (Perfect Samplers) o catene di Gibbs interne, che diventano computazionalmente proibitivi in alta dimensione.
• Soffrono di scarsa miscelazione (poor mixing) in spazi ad alta dimensionalità.
• I metodi Pseudo-marginal esistenti richiedono stime non distorte della costante di normalizzazione che spesso dipendono da tecniche costose come il Sequential Monte Carlo (SMC).

2. Metodologia Proposta

Gli autori propongono un approccio innovativo che sfrutta la struttura del modello sottostante per costruire stime efficienti senza bisogno di campionatori perfetti o sequenziali.

L'Idea Chiave: Il Modello di Indipendenza

Osservano che se si impostano tutti i parametri di interazione a zero (mantenendo solo i termini diagonali $\theta_{jj}$), il modello complesso si riduce a un modello di indipendenza (dove le variabili sono indipendenti tra loro).

• Per questo modello semplificato (denotato con parametro $\phi = \text{diag}(\theta)$), la costante di normalizzazione $z(\phi)$ è trattabile (calcolabile come prodotto di marginali univariate).
• Il campionamento da $p(x; \phi)$ è banale (basta campionare variabili Bernoulli indipendenti).

Approccio 1: MCMC Pseudo-Marginal Esatto

Per gestire il caso generale, gli autori costruiscono uno stimatore non distorto (unbiased) per la potenza negativa della costante di normalizzazione $[z(\theta)]^{-n}$ necessaria nell'inferenza bayesiana.

1. Riformulazione: Esprimono $[z(\theta)]^{-n}$ come una serie di Taylor basata sul rapporto $\mu = z(\theta)/z(\phi)$.
2. Stimatore di Importanza: Utilizzano il modello di indipendenza come distribuzione di importanza per stimare $\mu$ tramite campionamento diretto (non sequenziale).
3. Troncamento Randomizzato: Per gestire la serie infinita, utilizzano un metodo di troncamento randomizzato (basato su una variabile geometrica $R$) per ottenere uno stimatore non distorto $T$ di $[z(\theta)]^{-n}$.
4. Algoritmo: Questo stimatore viene inserito nell'algoritmo Metropolis-Hastings pseudo-marginal. Sebbene lo stimatore possa essere negativo (tipico degli stimatori randomizzati), l'algoritmo mantiene la distribuzione target corretta utilizzando un ri-pesaggio basato sul segno dello stimatore.

Approccio 2: Campionatore "Rumoroso" (Noisy Sampler)

Per modelli ad alta dimensionalità dove il calcolo esatto dello stimatore diventa costoso, gli autori propongono un'approssimazione:

• Invece di stimare il rapporto di accettazione in modo non distorto, stimano il logaritmo del rapporto di accettazione.
• Sfruttano la consistenza asintotica dello stimatore $\hat{T}$ per approssimare il termine $z(\theta)$.
• Dimostrano teoricamente che, sotto condizioni di supporto limitato (soddisfatte da modelli come Ising), questa catena approssimata eredita le proprietà di ergodicità uniforme della catena originale al crescere del numero di campioni Monte Carlo ($N$).

3. Contributi Chiave

1. Nuovo Stimatore Non Distorto: Sviluppo di uno stimatore per l'inverso della costante di normalizzazione che non richiede campionatori perfetti né sequenziali, sfruttando il modello di indipendenza sottostante.
2. Scalabilità: Il metodo evita i colli di bottiglia computazionali degli algoritmi di Exchange in alta dimensione, poiché il campionamento dal modello di indipendenza è parallelo e veloce.
3. Due Varianti: Fornisce sia un metodo esatto (pseudo-marginal) che garantisce la convergenza alla distribuzione a posteriori corretta, sia un metodo approssimato (rumoroso) ottimizzato per l'efficienza computazionale in alta dimensione.
4. Proposte Basate su Gradiente: L'approccio si integra naturalmente con proposte basate sul gradiente (Langevin, HMC), migliorando ulteriormente la miscelazione.

4. Risultati Sperimentali

Gli autori hanno testato i metodi su modelli di Ising con dimensioni variabili ($p = 3, 5, \dots, 100$) e su un dataset reale (MovieLens 32M).

• Miscelazione (Mixing): Il campionatore pseudo-marginal (PM) mostra proprietà di miscelazione significativamente superiori rispetto all'algoritmo di Exchange (EX) e al campionatore rumoroso (N), specialmente in alta dimensione. Le dimensioni efficaci del campione (ESS) per PM sono molto più elevate.
• Tempo di Esecuzione:
  • Il metodo PM è più lento per iterazione rispetto a EX e N a causa del calcolo dello stimatore, ma la sua migliore miscelazione lo rende più efficiente in termini di ESS per minuto.
  • Il campionatore rumoroso (N) ha tempi di esecuzione comparabili all'algoritmo di Exchange, ma con una qualità di campionamento superiore in alta dimensione.
• Recupero dei Parametri: Tutti i metodi recuperano accuratamente i parametri veri ($\theta_0$), ma le proposte basate su gradiente (Langevin) convergono molto più velocemente delle random walk.
• Applicazione Reale: Sul dataset MovieLens, il metodo PM ha mostrato la maggiore coerenza con il metodo rumoroso nel recupero della struttura di dipendenza (segno dei parametri), superando l'algoritmo di Exchange.

5. Significato e Conclusione

Questo lavoro rappresenta un avanzamento significativo nell'inferenza bayesiana per modelli grafici intrattabili.

• Superamento dei Limiti Attuali: Risolve il problema della dipendenza dai campionatori perfetti o dalle catene interne costose, rendendo l'inferenza scalabile a dimensioni elevate ($p=100+$).
• Flessibilità: Offre un quadro unificato che supporta sia l'inferenza esatta (quando il budget computazionale lo permette) sia quella approssimata (per grandi dataset).
• Impatto Pratico: La capacità di utilizzare modelli complessi come Ising su dati reali (es. raccomandazione di film) con una buona efficienza computazionale apre nuove possibilità per l'applicazione di modelli grafici in campi dove la dipendenza tra variabili è cruciale ma difficile da modellare.

In sintesi, gli autori dimostrano che sfruttare la struttura di indipendenza sottostante di un modello complesso permette di costruire stime Monte Carlo efficienti e scalabili, superando le barriere computazionali che hanno finora limitato l'uso pratico di questi modelli in alta dimensione.