Probabilistic inference is an attractive approach to uncertain reasoning and empirical
learning in arti cial intelligence. Computational diculties arise, however,
because probabilistic models with the necessary realism and
exibility lead to complex
distributions over high-dimensional spaces.
Related problems in other elds have been tackled using Monte Carlo methods based
on sampling using Markov chains, providing a rich array of techniques that can be
applied to problems in arti cial intelligence. The \Metropolis algorithm" has been
used to solve dicult problems in statistical physics for over forty years, and, in the
last few years, the related method of \Gibbs sampling" has been applied to problems
of statistical inference. Concurrently, an alternative method for solving problems
in statistical physics by means of dynamical simulation has been developed as well,
and has recently been uni ed with the Metropolis algorithm to produce the \hybrid
Monte Carlo" method. In computer science, Markov chain sampling is the basis
of the heuristic optimization technique of \simulated annealing", and has recently
been used in randomized algorithms for approximate counting of large sets.
In this review, I outline the role of probabilistic inference in arti cial intelligence,
present the theory of Markov chains, and describe various Markov chain Monte
Carlo algorithms, along with a number of supporting techniques. I try to present a
comprehensive picture of the range of methods that have been developed, including
techniques from the varied literature that have not yet seen wide application in
arti cial intelligence, but which appear relevant. As illustrative examples, I use the
problems of probabilistic inference in expert systems, discovery of latent classes from
data, and Bayesian learning for neural networks