Contents
1. Introduction 1
2. Probabilistic Inference for Articial Intelligence 4
2.1 Probabilistic inference with a fully-specied model : : : : : : : : : : : : : : : 5
2.2 Statistical inference for model parameters : : : : : : : : : : : : : : : : : : : : 13
2.3 Bayesian model comparison : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23
2.4 Statistical physics : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25
3. Background on the Problem and its Solution 30
3.1 Denition of the problem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30
3.2 Approaches to solving the problem : : : : : : : : : : : : : : : : : : : : : : : : 32
3.3 Theory of Markov chains : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36
4. 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 : : : : : : : : : : : 64
5. 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 : : : : : : : : : : : : : : : : : : 83
6. Extensions and Renements 87
6.1 Simulated annealing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87
6.2 Free energy estimation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 94
6.3 Error assessment and reduction : : : : : : : : : : : : : : : : : : : : : : : : : : 102
6.4 Parallel implementation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114
7. Directions for Research 116
7.1 Improvements in the algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : 116
7.2 Scope for applications : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118
8. Annotated Bibliography 121