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

Probleemstelling

Het paper adresseert een fundamentele uitdaging in de Bayesiaanse inferentie voor dubbel onberekenbare (doubly-intractable) probabilistische grafische modellen, specifiek binnen de klasse van paarsgewijze exponentiële familie grafische modellen (PEGMs).

• De Oorzaak: De gezamenlijke verdeling van deze modellen wordt gegeven door $p(x; \theta) = f(x; \theta) / z(\theta)$, waarbij $z(\theta)$ de normaliserende constante is. Voor de meeste modellen (zoals het Ising-model, Potts-model, Poisson-grafische modellen) is $z(\theta)$ onberekenbaar omdat het een som vereist over een exponentieel groot aantal configuraties ($2^p$ voor $p$ variabelen).
• Het Moeilijkheidsprobleem: Standaard MCMC-methoden, zoals de Metropolis-Hastings (M-H) algoritme, vereisen de berekening van de verhouding van acceptatiekansen. Deze verhouding bevat de term $z(\theta)/z(\theta')$, die analytisch niet kan worden opgelost.
• Beperkingen van Bestaande Oplossingen:
  • Exacte methoden (zoals het Exchange-algoritme of hulpvariabele-methoden) vereisen vaak het trekken van perfecte steekproeven uit de modelverdeling $p(y|\theta)$. Dit is in hoge dimensies computationeel onhaalbaar of vereist sequentiële Monte Carlo (SMC) methoden die slecht mengen (poor mixing).
  • Benaderende methoden (zoals Noisy MCMC) vermijden de onberekenbare term vaak door benaderingen, maar kunnen leiden tot een afwijkende stationaire verdeling of vereisen nog steeds dure innerlijke loops.

Methodologie

De auteurs ontwikkelen een nieuwe aanpak die de onafhankelijkheidsstructuur onderliggend aan het complexe model benut om een onbevooroordeelde schatter van de likelihood te construeren, zonder dat er perfecte steekproeven nodig zijn.

1. Het Onderliggende Onafhankelijkheidsmodel
Voor een PEGM met parameter $\theta$, definieert men een speciaal geval $\phi = \text{diag}(\theta)$ (alleen diagonaalelementen, alle kruisproducten zijn nul).

• Voor $\phi$ is het model een onafhankelijkheidsmodel: $p(x; \phi) = \prod_j p(x_j; \phi)$.
• De normaliserende constante $z(\phi)$ is hierin berekenbaar (via univariate marginalisaties).
• Het is triviaal om te steekproeven uit $p(x; \phi)$ (onafhankelijke Bernoulli-variabelen).

2. Exacte Pseudo-marginal MCMC (PM-MCMC)
De kern van de exacte methode is het construeren van een onbevooroordeelde schatter voor $[z(\theta)]^{-n}$ (waarbij $n$ het aantal observaties is).

• Taylor-ontwikkeling: De auteurs schrijven $[z(\theta)]^{-n}$ om als een Taylor-reeks rondom het onafhankelijkheidsmodel. Ze definiëren $\mu = z(\theta)/z(\phi)$.
• Schatter voor $\mu$: Ze gebruiken importance sampling met $p(\cdot; \phi)$ als verdelingsfunctie om een onbevooroordeelde schatter $\hat{\mu}$ te krijgen:
  $$\hat{\mu} = \frac{1}{N} \sum_{i=1}^N \frac{f(y_i; \theta)}{f(y_i; \phi)}, \quad y_i \sim p(\cdot; \phi)$$
• Randomized Sum Estimator: Om de inverse macht van de normaliserende constante te schatten, gebruiken ze een willekeurige truncatie van de oneindige reeks (gebaseerd op Lyne et al., 2015). Ze trekken een willekeurig getal $R$ en schatten de som tot $R$.
• Resultaat: Dit levert een schatter $T$ op met $E[T] = [z(\theta)]^{-n}$. Omdat deze schatter onbevooroordeeld is, garandeert de pseudo-marginal MCMC theorie dat de Markovketen convergeert naar de exacte posteriorverdeling, zelfs als de schatter variatie heeft.

3. Noisy Sampler (Benaderende MCMC)
Voor zeer hoge dimensies kan de berekening van de exacte schatter te duur worden. De auteurs stellen een "noisy" alternatief voor:

• In plaats van de exacte verhouding te schatten, wordt de acceptatiekansen in log-schaal benaderd.
• Ze gebruiken de consistente schatter $\hat{\mu}$ direct in de log-likelihood verhouding.
• Ergodiciteit: Hoewel deze keten niet exact naar de posterior convergeert, bewijzen de auteurs dat de keten uniform ergodisch is en dat de afstand tot de ware posterior afneemt als het aantal Monte Carlo steekproeven $N$ toeneemt ($O(1/\sqrt{N})$).

4. Proposal Mechanismen
De methode is compatibel met geavanceerde proposal-verdelingen, zoals Langevin en Hamiltonian Monte Carlo (HMC), die gebruikmaken van gradiënten. Dit is cruciaal voor schaalbaarheid in hoge dimensies.

Belangrijkste Bijdragen

1. Nieuwe Exacte Pseudo-marginal Methode: Een methode die de exacte posterior target zonder dat er perfecte steekproeven of sequentiële samplers nodig zijn. Dit wordt bereikt door het benutten van het onderliggende onafhankelijkheidsmodel.
2. Schaalbaarheid: De methode vermijdt de "inner loops" die typisch zijn voor het Exchange-algoritme in hoge dimensies. De complexiteit van het schatten van de normaliserende constante schaalt lineair met de dimensie ($O(p)$) in plaats van exponentieel.
3. Noisy Alternatief: Een computatievriendelijkere, benaderende versie die bewezen ergodisch is en goed presteert in hoge dimensies.
4. Gradiënt-gebaseerde Proposals: De integratie van gradiënt-informatie (Langevin/HMC) in deze framework, wat een natuurlijke uitbreiding is van hun algemene procedure.

Resultaten

De auteurs testen hun methoden op het Ising-model in verschillende dimensies ($p = 3$ tot $p = 100$) en vergelijken ze met het Exchange-algoritme (EX).

• Mixing (Efficiëntie):
  • De Exacte Pseudo-marginal (PM) methode toont aanzienlijk betere mixing (hogere Effectieve Steekproefgrootte - ESS) dan zowel het Exchange-algoritme als de Noisy methode, vooral in hogere dimensies.
  • In hoge dimensies ($p=70, 100$) faalt het Exchange-algoritme met een simpele Random Walk (RW) volledig (geen mixing), terwijl de PM-methode met Langevin-proposals uitstekend presteert.
• Rekentijd:
  • De Exacte PM-methode is per iteratie duurder dan het Exchange-algoritme (vanwege de schatting van de normaliserende constante).
  • Echter, door de superieure mixing, is de ESS per minuut voor de PM-methode in hoge dimensies veel hoger (bijv. factor 3 tot 6 beter bij $p=100$).
  • De Noisy methode heeft een rekentijd vergelijkbaar met het Exchange-algoritme maar biedt betere mixing dan EX.
• Parameterherstel: Alle methoden herstellen de ware parameters ($\theta_0$) met vergelijkbare nauwkeurigheid (lage Mean Squared Error), mits de keten goed mengt.
• Toepassing op Real Data: Op de MovieLens dataset (50 films, 448 gebruikers) toont de PM-methode de hoogste overeenkomst in tekenen van de geschatte parameters met de Noisy methode, wat de stabiliteit van de schattingen bevestigt.

Significantie

Dit werk is significant omdat het een langdurig probleem in de statistische inferentie voor grafische modellen oplost: hoe je Bayesiaanse inferentie uitvoert zonder de normaliserende constante te hoeven berekenen, zonder afhankelijk te zijn van onpraktische perfecte steekproeven.

• Schaalbaarheid: Het maakt Bayesiaanse inferentie voor complexe, hoogdimensionale grafische modellen (zoals Ising-modellen voor sociale netwerken of biologische data) praktisch uitvoerbaar.
• Theoretische Zuiverheid: Het biedt een exacte oplossing (via PM) die theoretisch gegarandeerd convergeert naar de juiste posterior, in tegenstelling tot veel bestaande benaderingen die een bias introduceren.
• Flexibiliteit: De aanpak is breed toepasbaar op elke PEGM die een onafhankelijkheidsmodel als substructuur heeft (waaronder Potts, Poisson, Boltzmann Machines), en kan worden gecombineerd met moderne gradiënt-gebaseerde MCMC technieken.

Kortom, de auteurs bieden een robuust, schaalbaar en theoretisch onderbouwd framework dat de barrière voor het toepassen van Bayesiaanse methoden op complexe, onberekenbare modellen verlaagt.