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

1. Problemstellung

Das Paper adressiert das Problem der bayesschen Inferenz bei doppelt-intraktiven probabilistischen grafischen Modellen (doubly-intractable models), insbesondere bei paarweisen exponentiellen Familien-Graphischen Modellen (PEGMs), wie dem Ising-Modell.

• Die Intraktabilität: Die gemeinsame Verteilung hat die Form $p(x; \theta) = f(x; \theta) / z(\theta)$. Das Problem besteht darin, dass die Normierungskonstante $z(\theta)$ (die Partitionsfunktion) nicht analytisch berechenbar ist, da sie eine Summe über alle $2^p$ möglichen Konfigurationen der Variablen erfordert. Dies führt zu einer kombinatorischen Explosion, insbesondere in hohen Dimensionen ($p$).
• Die Herausforderung für MCMC: Standard-MCMC-Verfahren wie der Metropolis-Hastings-Algorithmus (M-H) benötigen das Verhältnis der Wahrscheinlichkeiten, was den Quotienten $z(\theta)/z(\theta')$ beinhaltet. Da $z(\theta)$ unbekannt ist, kann die Akzeptanzwahrscheinlichkeit nicht berechnet werden.
• Limitationen bestehender Methoden:
  • Exakte Methoden (z. B. Exchange Algorithm): Erfordern oft das Ziehen von Stichproben aus der gleichen Verteilung $p(\cdot; \theta')$ (perfektes Sampling). In hohen Dimensionen ist dies rechnerisch unmöglich oder erfordert innere Gibbs-Schleifen, die die theoretische Gültigkeit zerstören oder zu schlechter Mischung (poor mixing) führen.
  • Approximative Methoden: Nutzen oft Schätzer, die verzerrt sind oder teure sequentielle Monte-Carlo-Verfahren (SMC) benötigen, um die Normierungskonstante zu schätzen.

2. Methodik

Die Autoren entwickeln einen neuen Ansatz, der die zugrundeliegende Unabhängigkeitsstruktur des Modells nutzt, um einen unverzerrten Schätzer für die Likelihood-Funktion zu konstruieren, ohne auf perfekte Sampler oder innere MCMC-Schleifen angewiesen zu sein.

Kernidee: Das Unabhängigkeitsmodell

Für jedes PEGM-Modell mit Parametern $\theta$ existiert ein spezieller Parametervektor $\phi = \text{diag}(\theta)$, bei dem alle nicht-diagonalen Elemente (Interaktionen) null gesetzt werden.

• Unter $\phi$ wird das Modell zu einem Unabhängigkeitsmodell (jedes $X_j$ ist unabhängig).
• Die Normierungskonstante $z(\phi)$ ist hier leicht berechenbar (Produkt univariater Marginalverteilungen).
• Das Ziehen von Stichproben aus $p(x; \phi)$ ist trivial (Batch-Ziehen unabhängiger Bernoulli-Variablen).

A. Exakter Pseudo-Rand-MCMC (Exact Pseudo-marginal MCMC)

Dieser Ansatz zielt darauf ab, die exakte Posterior-Verteilung zu erhalten, indem ein unverzerrter Schätzer für $[z(\theta)]^{-n}$ konstruiert wird.

1. Taylor-Entwicklung: Die Autoren nutzen die Identität $[z(\theta)]^{-n} = [\frac{\nu}{z(\phi)}]^n (1 - (1 - \nu \mu))^{-n}$, wobei $\mu = z(\theta)/z(\phi)$ und $\nu$ ein Tuning-Parameter ist.
2. Unverzerrter Schätzer für $\mu$: $\mu$ wird durch Importance Sampling geschätzt:
   $$\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)$$
   Da $p(\cdot; \phi)$ einfach zu sampeln ist, ist dies effizient.
3. Randomisierte Summation: Um den Term $(1 - \nu \mu)^{-n}$ zu schätzen, wird eine Taylor-Reihe um 0 entwickelt. Um die unendliche Reihe abzubrechen, wird eine Zufallsvariable $R$ (geometrisch verteilt) verwendet, um die Summe zufällig zu truncieren. Dies erzeugt einen unverzerrten Schätzer $T$ für $[z(\theta)]^{-n}$.
4. Algorithmus: Ein Pseudo-Rand-MCMC-Algorithmus verwendet diesen Schätzer $T$ anstelle der wahren Likelihood. Um negative Werte des Schätzers zu handhaben (was bei randomisierten Summen vorkommen kann), wird eine gewichtete Posterior-Verteilung mit Vorzeichenkorrektur verwendet.

B. Rauschbehafteter Sampler (Noisy Sampler)

Für hohe Dimensionen, wo die Berechnung des exakten unverzerrten Schätzers zu teuer wird, schlagen die Autoren einen approximativen Ansatz vor.

• Statt den M-H-Ratio unverzerrt zu schätzen, wird der Log-Ratio approximiert.
• Der Schätzer nutzt $\log(\hat{\mu})$ anstelle von $\hat{\mu}$.
• Theoretische Eigenschaft: Unter bestimmten Bedingungen (beschränkter Träger der Verteilung, wie beim Ising-Modell) erbt die approximative Kette die Ergodizitätseigenschaften der ursprünglichen Kette, wenn die Anzahl der Monte-Carlo-Stichproben $N \to \infty$ geht.

3. Wichtige Beiträge

1. Neue Schätzer für intraktable Modelle: Entwicklung eines unverzerrten Schätzers für die inverse Normierungskonstante, der explizit das zugrundeliegende Unabhängigkeitsmodell nutzt. Dies eliminiert die Notwendigkeit von perfekten Samplern oder sequentiellen Samplern (SMC).
2. Skalierbarkeit: Der Ansatz ist skalierbar in hohen Dimensionen, da das Sampling aus dem Unabhängigkeitsmodell ($\phi$) parallelisierbar und kostengünstig ist. Die benötigte Anzahl an Importance-Samples $N$ skaliert nur linear mit der Dimension $p$ ($N = O(p)$).
3. Zwei Varianten: Bereitstellung sowohl einer exakten Methode (Pseudo-marginal) als auch einer effizienten approximativen Methode (Noisy), die beide auf derselben Grundidee basieren.
4. Gradientenbasierte Erweiterungen: Die Methode ist kompatibel mit gradientenbasierten Proposal-Verteilungen (Langevin, Hamiltonian Monte Carlo), was die Mischung in komplexen Posterior-Verteilungen verbessert.

4. Ergebnisse

Die Autoren testen ihre Methoden am Ising-Modell in verschiedenen Dimensionen ($p = 3$ bis $100$) und vergleichen sie mit dem Exchange Algorithmus (EX).

• Mischung (Mixing):
  • Der Pseudo-Rand-Sampler (PM) zeigt deutlich bessere Mischungseigenschaften (höhere Effective Sample Sizes, ESS) als der Exchange Algorithmus, insbesondere in hohen Dimensionen.
  • Der Exchange Algorithmus leidet unter schlechter Mischung, wenn er mit inneren Gibbs-Samplern implementiert wird (was in der Praxis oft nötig ist, da perfektes Sampling unmöglich ist).
• Rechenzeit:
  • Der exakte PM-Sampler ist rechenintensiver als EX.
  • Der Noisy-Sampler hat eine Rechenzeit, die mit dem Exchange Algorithmus vergleichbar ist, aber eine viel bessere Mischung liefert.
• Genauigkeit:
  • Alle Methoden können den wahren Parameter $\theta_0$ ähnlich gut rekonstruieren (gemessen am mittleren quadratischen Fehler).
  • In hohen Dimensionen ($p \ge 70$) ist der Noisy-Sampler mit gradientenbasierten Proposals (Langevin) die überlegene Wahl, da er die Posterior-Regionen schneller erreicht.
• Anwendungsfall (MovieLens):
  • Anwendung auf ein reales Datenset (MovieLens 32M) zur Schätzung von Präferenzmustern zwischen Filmen.
  • Die Ergebnisse der PM- und Noisy-Methoden stimmen signifikant besser überein (62% Übereinstimmung in den Vorzeichen der Parameter) als mit dem Exchange Algorithmus.

5. Bedeutung und Fazit

Das Paper stellt einen wichtigen Fortschritt in der bayesschen Inferenz für doppelt-intraktive Modelle dar.

• Paradigmenwechsel: Statt zu versuchen, die gesamte komplexe Verteilung zu sampeln (wie beim Exchange Algorithmus), nutzt der neue Ansatz die einfache Struktur des Unabhängigkeitsmodells als "Anker" für die Schätzung der schwer zu berechnenden Normierungskonstante.
• Praktische Relevanz: Die Methode macht die Inferenz in hochdimensionalen grafischen Modellen (z. B. für Bildanalyse, Genetik oder Empfehlungssysteme) praktikabel, wo bisherige Methoden entweder zu langsam waren oder keine theoretische Garantie boten.
• Zukunftsausblick: Die Autoren weisen darauf hin, dass der Ansatz auf andere Modelle wie das Potts-Modell, Poisson-Graphische Modelle und Boltzmann-Maschinen übertragbar ist und auch mit fortschrittlicheren Sampling-Techniken wie Hamiltonian Monte Carlo kombiniert werden kann.

Zusammenfassend bieten die Autoren eine robuste, skalierbare und theoretisch fundierte Lösung für ein jahrzehntealtes Problem in der statistischen Physik und maschinellem Lernen, indem sie die zugrundeliegende Unabhängigkeitsstruktur clever ausnutzen.