Probabilistic Inference Using Markov Chain Monte Carlo Methods

Probabilistic inference is an attractive approach to uncertain reasoning and empiricallearning in artificial intelligence. Computational difficulties arise, however,because probabilistic models with the necessary realism and exibility lead to complexdistributions over high-dimensional spaces.
Nội dung trích xuất từ tài liệu:
Probabilistic Inference Using Markov Chain Monte Carlo Methods Probabilistic Inference UsingMarkov Chain Monte Carlo Methods Radford M. Neal Technical Report CRG-TR-93-1 Department of Computer Science University of Toronto E-mail: radford@cs.toronto.edu 25 September 1993 Copyright 1993 by Radford M. Neal c AbstractProbabilistic inference is an attractive approach to uncertain reasoning and em-pirical learning in articial intelligence. Computational diculties arise, however,because probabilistic models with the necessary realism and exibility lead to com-plex distributions over high-dimensional spaces.Related problems in other elds have been tackled using Monte Carlo methods basedon sampling using Markov chains, providing a rich array of techniques that can beapplied to problems in articial intelligence. The \Metropolis algorithm has beenused to solve dicult problems in statistical physics for over forty years, and, in thelast few years, the related method of \Gibbs sampling has been applied to problemsof statistical inference. Concurrently, an alternative method for solving problemsin statistical physics by means of dynamical simulation has been developed as well,and has recently been unied with the Metropolis algorithm to produce the \hybridMonte Carlo method. In computer science, Markov chain sampling is the basisof the heuristic optimization technique of \simulated annealing, and has recentlybeen used in randomized algorithms for approximate counting of large sets.In this review, I outline the role of probabilistic inference in articial intelligence,present the theory of Markov chains, and describe various Markov chain MonteCarlo algorithms, along with a number of supporting techniques. I try to present acomprehensive picture of the range of methods that have been developed, includingtechniques from the varied literature that have not yet seen wide application inarticial intelligence, but which appear relevant. As illustrative examples, I use theproblems of probabilistic inference in expert systems, discovery of latent classes fromdata, and Bayesian learning for neural networks. AcknowledgementsI thank David MacKay, Richard Mann, Chris Williams, and the members of myPh.D committee, Georey Hinton, Rudi Mathon, Demetri Terzopoulos, and RobTibshirani, for their helpful comments on this review. This work was supportedby the Natural Sciences and Engineering Research Council of Canada and by theOntario Information Technology Research Centre. Contents1. Introduction 12. Probabilistic Inference for Articial Intelligence 4 2.1 Probabilistic inference with a fully-specied model : : : : : : : : : : : : : : : 5 2.2 Statistical inference for model parameters : : : : : : : : : : : : : : : : : : : : 13 2.3 Bayesian model comparison : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 2.4 Statistical physics : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 253. Background on the Problem and its Solution 30 3.1 Denition of the problem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 3.2 Approaches to solving the problem : : : : : : : : : : : : : : : : : : : : : : : : 32 3.3 Theory of Markov chains : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 364. The Metropolis and Gibbs Sampling Algorithms 47 4.1 Gibbs sampling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 47 4.2 The Metropolis algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 4.3 Variations on the Metropolis algorithm : : : : : : : : : : : : : : : : : : : : : : 59 4.4 Analysis of the Metropolis and Gibbs sampling algorithms : : : : : : : : : : : 645. The Dynamical and Hybrid Monte Carlo Methods 70 5.1 The stochastic dynamics method : : : : : : : : : : : : : : : : : : : : : : : : : 70 5.2 The hybrid Monte Carlo algorithm : : : : : : : : : : : : : : : : : : : : : : : : 77 5.3 Other dynamical methods : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81 5.4 Analysis of the hybrid Monte Carlo algorithm : : : : : : : : : : : : : : : : : : 836. Extensions and Renements 87 6.1 Simulated annealing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87 6.2 Free energy estimation : : : : : : : : : : : : : ...