Previous: 24th January 2005 — MLJC planning and Intrinsic Dimensionality
Next: 14th February 2005 — Mixtures of Experts. Automatic relevance determination

7th February 2005 — Annealing Review

Iain and David will review annealing methods, focussing on Bayesian uses.

Please take a look at sections 6.1 and 6.2 of Probabilistic Inference Using Markov Chain Monte Carlo Methods, Radford M. Neal, 1993.

If you are unfamiliar with normal MCMC methods, such as the Metropolis algorithm, read up on that instead as it will not be reviewed. Try either the review above or David’s book.

For reference the papers Iain used were:

• Simulated Anealing:
  • Probabilistic Inference Using Markov Chain Monte Carlo Methods, Radford M. Neal, 1993. url
  • Numerical Recipes in C. Press et al. url
• Cluster Replica / Metropolis coupled Markov chains:
  • Low-temperature properties of the +/-J Ising spin glass in two dimensions. Jian-Sheng Wang and Robert H. Swendsen. Phys Review B 38(7) 1988. url
  • …should have looked at others.
• Expanded ensembles / Simulated tempering:
  • New approach to Monte Carlo calculation of the free energy: Method of expanded ensembles. A. P. Lyubartsev et al. J. Chem. Phys. 96(3) 1992. url
  • Simulated Tempering: A new Monte Carlo Scheme. Marinari and Parisi. 1992. url
• Tempered transitions. AIC:
  • Sampling from Multimodal Distributions Using Tempered Transitions. Radford M. Neal. Technical Report 9421 Department of Statistics, Toronto. 1994. url
  • Annealed Importance Sampling. Radford M. Neal. Technical Report 9805, Department of Statistics, Toronto. 1988. url
• Multicanoncial Ensemble (or umbrella sampling):
  • Multicanonial Ensemble: A New Approach to Simulate First-Order Phase Transitions. Berg and Neuhaus. Phys Rev Let. 68(1) 1992. url
  • New Approach to Spin-Glass Simulations. Berg and Celik. Phys Rev Let. 69(15) 1992. url

Particularly recommended is “Tempered transitions” for its discussion.

“Regeneration” has been applied to simulated tempering and multicanonical ensemble methods. Perhaps allows “pre-simulation” for weights to be a bit less wasteful. I’m afraid you’ll have to chase the references yourself. Naively it is probably fairly easy to apply.

Also recommended is the following review paper shown to him afterwards:

• Extended Ensemble Monte Carlo. Y Iba. Int J Mod Phys C [Computational Physics and Physical Computation] 12(5):623-656. 2001. arxiv, journal.

And this oft-cited paper:

• Simulating normalizing constants: from importance sampling to bridge sampling to path sampling, Andrew Gelman and Xiao-Li Meng, Statist. Sci. 13 (1998), no. 2, 163-185.

Note that we did not cover the neat methods in BayeSys or Nested Sampling, acceptance ratio methods (as such), Hamiltonian Monte Carlo (as found in fbm), Dragging fast variables, a bunch of classical techniques, some newer variations of the above methods, or probably a zillion other annealing-related ideas.

Iain Murray.