Abstract
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 unknown, non-constant normalization terms; for example, the posterior over parameters of an undirected graphical model. An ingenious auxiliary-variable scheme (Møller et al., Biometrika 93(2):451–458, 2006) offered the first valid MCMC algorithm for this problem. Exact sampling (Propp and Wilson, Rand. Struct. Alg. 9(1&2):223–252 1996) is used to sample from a Metropolis–Hastings proposal for which the acceptance probability is tractable. Unfortunately these expensive proposals can have a low acceptance rate.
We recently (Proc. UAI 2006) generalized the Møller et al. algorithm and introduced an easier-to-implement alternative, which often performs better. Here we describe more general versions of these algorithms with simpler derivations.
Related Links
- http://www.gatsby.ucl.ac.uk/~iam23/pub/06doubly_intractable/doubly_intractable.pdf - Paper describing earlier work.