Probabilistic Inference Using Markov Chain Monte Carlo Methods - R. Neal
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 probabilistic inference in exp ert systems, discovery of latent classes from
data, and Bayesian learning for neural networks.
- PDF: 344 pages
- Technical Rep ort CRG-TR-93-1 Department of Computer Science UniversityofToronto: 25 September 1993
- Language: English
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 probabilistic inference in exp ert systems, discovery of latent classes from
data, and Bayesian learning for neural networks.
