Probabilistic inference is an attractive approach to uncertain reasoning and empirical learning in artificial intelligence. Computational difficulties arise, however, because probabilistic models with the necessary realism and exibility lead to complex distributions over high-dimensional spaces. | Probabilistic Inference Using Markov Chain Monte Carlo Metho ds Radford M. Neal Technical Rep ort CRG-TR-93-1 Department of Computer Science UniversityofToronto E-mail: radford@ 25 Septemb er 1993 c Copyright 1993 by Radford M. Neal Abstract Probabilistic inference is an attractive approach to uncertain reasoning and em- pirical learning in arti cial intelligence. Computational di culties arise, however, b ecause probabilistic mo dels with the necessary realism and exibility lead to com- plex distributions over high-dimensional spaces. Related problems in other elds have b een tackled using Monte Carlo metho ds based on sampling using Markovchains, providing a rich arrayoftechniques that can b e applied to problems in arti cial intelligence. The \Metrop olis algorithm" has b een used to solve di cult problems in statistical physics for over fortyyears, and, in the last few years, the related metho d of \Gibbs sampling" has b een applied to problems of statistical inference. Concurrently, an alternative metho d for solving problems in statistical physics by means of dynamical simulation has b een develop ed as well, and has recently b een uni ed with the Metrop olis algorithm to pro duce the \hybrid Monte Carlo" metho d. In computer science, Markovchain sampling is the basis of the heuristic optimization technique of \simulated annealing", and has recently b een 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 Markovchains, and describ e various Markovchain Monte Carlo algorithms, along with a numb er of supp orting techniques. I try to presenta comprehensive picture of the range of metho ds that have b een develop ed, including techniques from the varied literature that have not yet seen wide application in arti cial intelligence, but which app ear relevant. As illustrative examples, I use the problems of .
