MCMC for Doubly-intractable Distributions

Iain Murray, Zoubin Ghahramani, David J. C. MacKayUAI 2006

TL;DR

This paper introduces new Markov Chain Monte Carlo (MCMC) algorithms, MAVM and an "exchange algorithm," to tackle a challenging class of probability distributions called "doubly-intractable distributions." These new methods offer improved acceptance rates and simpler implementation compared to existing techniques, making it more feasible to perform Bayesian inference on complex models where standard MCMC methods fail.

What Problem Does This Paper Address?

Bayesian inference often involves estimating parameters of a model by sampling from a posterior distribution. Standard MCMC methods are well-suited for distributions where the "normalization constant" (a value that ensures the distribution sums to 1) is unknown. However, a more difficult problem arises with "doubly-intractable distributions," where not only is the normalization constant unknown, but it also depends on the model parameters themselves. This is common in models like undirected graphical models or spatial point processes. Existing solutions, like the Single Auxiliary Variable Method (SAVM), use auxiliary variables to approximate the intractable normalization constant, but this can lead to low acceptance rates in the MCMC sampler, making inference slow and inefficient. This paper aims to improve upon SAVM by developing methods that achieve better acceptance probabilities and are easier to use.

Methods

The paper builds upon the Single Auxiliary Variable Method (SAVM) by Møller et al. (2004). SAVM introduces an auxiliary variable to create a joint distribution where the intractable normalization constant cancels out in the Metropolis-Hastings acceptance ratio.

The authors propose two main advancements:

  • Multiple Auxiliary Variable Method (MAVM): This method extends SAVM by introducing a sequence of auxiliary variables that "bridge" between the initial distribution and the target distribution. This bridging is achieved through transition operators that gradually transform the auxiliary variables. This allows for a more refined estimation of the normalization constant ratio, leading to higher acceptance rates, at the cost of a fixed number of additional steps per iteration.
  • Exchange Algorithm: This algorithm offers a simpler and more direct approach. It conceptualizes a scenario with multiple possible parameter settings, each generating its own set of "unobserved data." The MCMC step then involves proposing a new parameter setting and "exchanging" the observed data for a sample from the proposed parameter's distribution. This method is shown to be a valid MCMC algorithm and, in many cases, performs better and is easier to implement than MAVM.

Both methods leverage the ability to draw exact samples from certain proposal distributions, a capability that is feasible for some complex models.

Datasets

Not discussed in the paper. The paper uses a synthetic Gaussian example and a toroidal square Ising lattice for evaluation.

Key Insights and Ideas

  • Bridging for Better Acceptance: The core idea of MAVM is that by introducing intermediate steps (bridging) between the proposal and target distributions, the implicit estimation of the normalization constant ratio becomes more accurate, leading to higher acceptance rates.
  • The "Exchange" Perspective: The exchange algorithm offers a novel and intuitive way to think about sampling from doubly-intractable distributions. By framing it as an exchange of data between competing parameter settings, it simplifies the MCMC update and often leads to superior performance.
  • Simplicity vs. Performance Trade-off: While MAVM offers a systematic way to improve acceptance via bridging, the exchange algorithm achieves similar or better performance with a simpler update rule and without requiring an initial estimate of the parameters.
  • The Importance of Proposals: The paper highlights how the quality of the proposal distribution significantly impacts the performance of MCMC methods, especially for doubly-intractable distributions. The exchange algorithm, in particular, seems to benefit from exploiting the local nature of proposals.

Key Results

  • Both MAVM and the exchange algorithm consistently outperform the baseline SAVM method in terms of acceptance rates across various scenarios.
  • In a synthetic Gaussian example, both methods achieve acceptance rates close to 1 (the theoretical maximum) with a sufficient number of bridging levels (K) or for the exchange algorithm.
  • For a more realistic Ising model, the exchange algorithm demonstrates significantly better mixing times and acceptance rates compared to SAVM and MAVM, especially when using a less ideal Gaussian proposal distribution.
  • The exchange algorithm is shown to be simpler to implement than MAVM, as it does not require an initial parameter estimate.

Limitations and Future Work

  • Computational Cost: While the proposed methods improve acceptance rates, they still rely on exact sampling from proposal distributions, which can be computationally expensive for very large or complex models.
  • Choice of Bridging Operators: The performance of MAVM depends on the choice of bridging transition operators. Finding optimal operators for complex distributions might be challenging.
  • Future Work: The authors suggest exploring the trade-off between acceptance rate and computational cost with more bridging levels, and investigating the application of these methods to other complex models. They also note that the exchange algorithm's performance is robust to the quality of the initial parameter estimate, suggesting it might be a more generally applicable solution.

Summary updated

BibTeX
@inproceedings{murray2006mcmc,
  author = {Iain Murray and Zoubin Ghahramani and David J. C. MacKay},
  title = {{MCMC for Doubly-intractable Distributions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2006},
}

Loading related content...

Figure