Markov chain Monte Carlo
||This article may be too technical for most readers to understand. (December 2014)|
In mathematics, more specifically in statistics, Markov chain Monte Carlo (MCMC) methods are a class of algorithms for sampling from a probability distribution based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a number of steps is then used as a sample of the desired distribution. The quality of the sample improves as a function of the number of steps.
Random walk Monte Carlo methods make up a large subclass of MCMC methods.
- MCMC methods are primarily used for calculating numerical approximations of multi-dimensional integrals, for example in Bayesian statistics, computational physics, computational biology and computational linguistics.
- They are also used for generating samples that gradually populate the rare failure region in rare event sampling.
Random walk Monte Carlo methods
When an MCMC method is used for approximating a multi-dimensional integral, an ensemble of "walkers" move around randomly. At each point where a walker steps, the integrand value at that point is counted towards the integral. The walker then may make a number of tentative steps around the area, looking for a place with a reasonably high contribution to the integral to move into next.
Random walk Monte Carlo methods are a kind of random simulation or Monte Carlo method. However, whereas the random samples of the integrand used in a conventional Monte Carlo integration are statistically independent, those used in MCMC methods are correlated. A Markov chain is constructed in such a way as to have the integrand as its equilibrium distribution.
Examples of random walk Monte Carlo methods include the following:
- Metropolis–Hastings algorithm: This method generates a random walk using a proposal density and a method for rejecting some of the proposed moves.
- Gibbs sampling: This method requires all the conditional distributions of the target distribution to be sampled exactly. It is popular partly because it does not require any 'tuning'.
- Slice sampling: This method depends on the principle that one can sample from a distribution by sampling uniformly from the region under the plot of its density function. It alternates uniform sampling in the vertical direction with uniform sampling from the horizontal 'slice' defined by the current vertical position.
- Multiple-try Metropolis: This method is a variation of the Metropolis–Hastings algorithm that allows multiple trials at each point. By making it possible to take larger steps at each iteration, it helps address the curse of dimensionality.
- Reversible-jump: This method is a variant of the Metropolis–Hastings algorithm that allows proposals that change the dimensionality of the space. MCMC methods that change dimensionality have long been used in statistical physics applications, where for some problems a distribution that is a grand canonical ensemble is used (e.g., when the number of molecules in a box is variable). But the reversible-jump variant is useful when doing MCMC or Gibbs sampling over nonparametric Bayesian models such as those involving the Dirichlet process or Chinese restaurant process, where the number of mixing components/clusters/etc. is automatically inferred from the data.
Other MCMC methods
More sophisticated methods use various ways of reducing the correlation between successive samples. These algorithms may be harder to implement, but they usually exhibit faster convergence (i.e. fewer steps for an accurate result).
Examples of non-random walk MCMC methods include the following:
- Hybrid Monte Carlo (HMC): Tries to avoid random walk behaviour by introducing an auxiliary momentum vector and implementing Hamiltonian dynamics, so the potential energy function is the target density. The momentum samples are discarded after sampling. The end result of Hybrid Monte Carlo is that proposals move across the sample space in larger steps; they are therefore less correlated and converge to the target distribution more rapidly.
- Some variations on slice sampling also avoid random walks.
- Langevin MCMC and other methods that rely on the gradient (and possibly second derivative) of the log posterior avoid random walks by making proposals that are more likely to be in the direction of higher probability density.
Usually it is not hard to construct a Markov chain with the desired properties. The more difficult problem is to determine how many steps are needed to converge to the stationary distribution within an acceptable error. A good chain will have rapid mixing: the stationary distribution is reached quickly starting from an arbitrary position.
Typically, MCMC sampling can only approximate the target distribution, as there is always some residual effect of the starting position. More sophisticated MCMC-based algorithms such as coupling from the past can produce exact samples, at the cost of additional computation and an unbounded (though finite in expectation) running time.
Many random walk Monte Carlo methods move around the equilibrium distribution in relatively small steps, with no tendency for the steps to proceed in the same direction. These methods are easy to implement and analyze, but unfortunately it can take a long time for the walker to explore all of the space. The walker will often double back and cover ground already covered.
- Bayesian inference
- Coupling from the past
- Gibbs sampling
- Hybrid Monte Carlo
- Metropolis–Hastings algorithm
- Multiple-try Metropolis
- Particle filter
- Slice sampling
- See Gill 2008.
- See Robert & Casella 2004.
- See Green 1995.
- See Neal 2003.
- See Stramer 1999.
- Christophe Andrieu et al., An Introduction to MCMC for Machine Learning, 2003
- Asmussen, Søren; Glynn, Peter W. (2007). Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability 57. Springer.
- Atzberger, P. "An Introduction to Monte-Carlo Methods".
- Berg, Bernd A. (2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis. World Scientific.
- Bolstad, William M. (2010). Understanding Computational Bayesian Statistics. Wiley. ISBN 0-470-04609-0.
- Casella, George; George, Edward I. (1992). "Explaining the Gibbs sampler". The American Statistician 46: 167–174. doi:10.2307/2685208. (Basic summary and many references.)
- Gelfand, A.E.; Smith, A.F.M. (1990). "Sampling-Based Approaches to Calculating Marginal Densities". Journal of the American Statistical Association 85: 398–409. doi:10.1080/01621459.1990.10476213.
- Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. (1995). Bayesian Data Analysis (1st ed.). Chapman and Hall. (See Chapter 11.)
- Geman, S.; Geman, D. (1984). "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence 6: 721–741.
- Gilks, W.R.; Richardson, S.; Spiegelhalter, D.J. (1996). Markov Chain Monte Carlo in Practice. Chapman and Hall/CRC.
- Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach (2nd ed.). Chapman and Hall/CRC. ISBN 1-58488-562-9.
- Green, P.J. (1995). "Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination". Biometrika 82 (4): 711–732. doi:10.1093/biomet/82.4.711.
- Neal, Radford M. (2003). "Slice Sampling". Annals of Statistics 31 (3): 705–767. doi:10.1214/aos/1056562461. JSTOR 3448413.
- Neal, Radford M. (1993). "Probabilistic Inference Using Markov Chain Monte Carlo Methods".
- Robert, Christian P.; Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). Springer. ISBN 0-387-21239-6.
- Rubinstein, R.Y.; Kroese, D.P. (2007). Simulation and the Monte Carlo Method (2nd ed.). Wiley. ISBN 978-0-470-17794-5.
- Smith, R.L. (1984). "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions". Operations Research 32: 1296–1308. doi:10.1287/opre.32.6.1296.
- Spall, J.C. (April 2003). "Estimation via Markov Chain Monte Carlo". IEEE Control Systems Magazine 23 (2): 34–45. doi:10.1109/mcs.2003.1188770.
- Stramer, O.; Tweedie, R. (1999). "Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms". Methodology and Computing in Applied Probability 1 (3): 307–328. doi:10.1023/A:1010090512027.
- Diaconis, Persi (April 2009). "The Markov chain Monte Carlo revolution". Bull. Amer. Math. Soc. 46 (2): 179–205. doi:10.1090/s0273-0979-08-01238-x. S 0273-0979(08)01238-X.
- Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007), "Section 15.8. Markov Chain Monte Carlo", Numerical Recipes: The Art of Scientific Computing (3rd ed.), Cambridge University Press, ISBN 978-0-521-88068-8
- Richey, Matthew (May 2010). "The Evolution of Markov Chain Monte Carlo Methods". The American Mathematical Monthly 117 (5): 383–413. doi:10.4169/000298910x485923.
- MCMC sampling and other methods in a basic overview, by Alexander Mantzaris (original link - now broken)
- Visual demonstration of MCMC sampling methods (Java applet), by Laird Breyer
- A Toy Example of MCMC sampling, by Zhiyuan Weng
- MCL - a cluster algorithm for graphs, by Stijn van Dongen
- PyMC - Python module implementing Bayesian statistical models and fitting algorithms, including Markov chain Monte Carlo.