Markov Chain Monte Carlo > Gibbs Sampling
What is Gibbs Sampling?
Gibbs sampling (also called alternating conditional sampling) is a Markov Chain Monte Carlo algorithm for high-dimensional data such as image processing and micro arrays. It is called Monte Carlo because it draws samples from specified probability distributions; the Markov chain comes from the fact that each sample is dependent on the previous sample. Gibbs sampling is relatively easy to implement. However, it is less efficient than direct simulation from the distribution.
The method is based on each parameter’s posterior density, conditional on the other parameters. This gives an accurate representation of marginal posterior densities. In order for the algorithm to work, you must be able to sample from all of the conditional distributions for all the model’s parameters (Segura & Braun, 2004). In practice, this isn’t always possible, so the required conditional distributions have to be approximated by another algorithm like Metropolis Hastings or slice sampling.
How It Works
Gibbs sampling is an efficient way of reducing a multi-dimensional problem to a lower-dimensional problem. The entire parameter vector is subdivided into smaller subvectors (e.g. vectors with a single parameter). One iteration of the algorithm results in each subvector randomly sampled using the subvector’s posterior density, conditional on the other subvector’s current values (Duchateau & Janssen, 2007, p.234). In cases where the parameter vector is very large, and subdivided into very small pieces, the sampling can take a very long time to converge.
Origins
Gibbs sampling is a special case of the Metropolis-Hastings algorithm, invented to simulate complex systems in solid-state physics (Metropolis et. al, 1953). The name comes from by Geman and Geman’s 1984 paper, which offered the algorithm as a particular case of the Gibbs distribution. It was developed to reconstruct a noisy image (Bolstad, 2011).
References
Bolstad, W. (2011). Understanding Computational Bayesian Statistics. John Wiley & Sons,
Duchateau, L. & Janssen, P. (2007). The Frailty Model. Springer Science & Business Media.
Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transaction on Pattern Analysis and Machine Intelligence. 6, 721-41.
Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. (1953). “Equations of State Calculations by Fast Computing Machines”. Journal of Chemical Physics. 21 (6): 1087–1092.
Segura, J. & Braun, C. (2004). An Eponymous Dictionary of Economics: A Guide to Laws and Theorems Named After Economists. Edward Elgar Publishing.