MCMC for Doubly-intractable Distributions

By Iain Murray, Zoubin Ghahramani, David John Cameron MacKay. Conference on Uncertainty in Artificial Intelligence, 2006

440 citations recorded by the source corpus.

Markov Chain Monte Carlo (MCMC) algorithms are routinely used to draw samples from distributions with intractable normalization constants. However, standard MCMC algorithms do not apply to doubly-intractable distributions in which there are additional parameter-dependent normalization terms; for example, the posterior over parameters of an undirected graphical model. An ingenious auxiliary-variable scheme (Moller et al., 2004) offers a solution: exact sampling (Propp and Wilson, 1996) is used to sample from a Metropolis-Hastings proposal for which the acceptance probability is tractable. Unfortunately the acceptance probability of these expensive updates can be low. This paper provides a generalization of M0ller et al. (2004) and a new MCMC algorithm, which obtains better acceptance probabilities for the same amount of exact sampling, and removes the need to estimate model parameters before sampling begins.

Subfields: Computational Theory and Mathematics, Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/818113f890557e876dea8729e1b183567bab344b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs (2014, background): “While auxiliary variable techniques can make sampling tractable in special cases [23], Murray and Ghahramani [22] conjecture that for general undirected models, there exists no tractable MCMC scheme that results in the correct stationary distribution.”
A double Metropolis–Hastings sampler for spatial models with intractable normalizing constants (2010, background): “[11] proposed auxiliary variable MCMC algorithms for simulating from the distribution (2).”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “Another situation where the target density π(·|y) cannot be directly computed is the case of the “doubly intractable” likelihood (Murray et al. 2006a), when the likelihood function `(θ|y) ∝ g(y|θ) itself contains a term that is intractable, in that it makes the normalising constant”
An Introduction to Conditional Random Fields (2010, methodology): “p(yjx;)p() Q N i=1 p(y (i)jx(i);)d. This integral over needs to be approximated, for example, by MCMC. In general, it is dicult to formulate ecient Bayesian methods for undirected models; see [83, 82] for some of the few examples in this regard. A few papers have specially considered approximate in”
Randomized Optimum Models for Structured Prediction (2012, background): “A curious computational phenomenon is that there are important and useful classes of energy-based models in which summing over all states is diﬃcult, but optimizing is easy.”
Likelihood-based inference for Matérn type-III repulsive point processes (2009, background): “Despite notable recent progress in the study of Gibbs random fields [20], [21], the problem of making likelihood-based inference for repulsive point processes remains challenging.”
On Nesting Monte Carlo Estimators (2017, background): “A common class of nested expectations is doubly-intractable inference problems (Murray et al., 2006; Liang, 2010), where the likelihood is only known up to a parameter-dependent normalizing constant.”
MCMC Using Hamiltonian Dynamics (2011, methodology): “In closing, we should mention that the method discussed here is only one among a number of promising attempts that have been made to couple the power of traditional MCMC with the precision of perfect sampling such as in [40] and [43].”
Robust generalised Bayesian inference for intractable likelihoods (2021, positive): “…et al., 1997), (2) auxiliary variable MCMC (such as the exchange algorithm and pseudo-marginal MCMC; Andrieu & Roberts, 2009; M ⊘ ller et al., 2006; Murray et al., 2006; Park & Haran, 2018), and (3) approximate likelihood methods (such as pseudo-likelihood and composite likelihood ; Besag, 1974;…”
Bayesian Regression Using a Prior on the Model Fit: The R2-D2 Shrinkage Prior (2016, methodology): “This is the so-called “Exchange Algorithm” proposed by Murray, Ghahramani, and MacKay (2006) for doubly intractable distributions, and also used by Fallaize and Kypraios (2016) for Bayesian inference of the Bingham distribution.”
Variational Inference for Sparse and Undirected Models (2016, background): “This requirement for an an intractable calculation embedded within already-intractable nonconjugate inference has led some to term Bayesian learning of undirected graphical models “doubly intractable” (Murray et al., 2006).”
Bayesian exponential family projections for coupled data sources (2010, methodology): “We apply the exchange algorithm of Murray et al. (2006).”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “Both the approaches of Murray et al. (2006a) and Møller et al. (2006) require sampling data from the likelihood, which limits their applicability.”
Inverse Reward Design (2017, background): “This is an example of what is referred to as a doubly-intractable likelihood (Murray et al., 2006).”
Nesting Probabilistic Programs (2018, background): “Such problems fall under a more general framework of nested inference [15] or equivalently inference for so-called doubly (or multiply) intractable distributions [18, 26].”
Bayesian Parameter Estimation for Latent Markov Random Fields and Social Networks (2012, methodology): “In application, this study finds the use of the extended version of the exchange algorithm described in Murray, Ghahramani, and MacKay (2006) to be essential to ensure that the MCMC can move freely in the problems considered.”
Tractable nonparametric Bayesian inference in Poisson processes with Gaussian process intensities (2009, background): “This posterior distribution is doubly-intractable (Murray et al., 2006), due to the presence of an intractable integral over T in the numerator and an intractable integral over g in the denominator.”
A Structural Model of Segregation in Social Networks (2010, methodology): “As R → ∞ the algorithm converges to the exact exchange algorithm of Murray et al. (2006), producing exact samples from the posterior distribution.”