Gibbs Sampling

Gibbs sampling is a Markov chain Monte Carlo (MCMC) algorithm used to obtain samples from a joint probability distribution of several variables when sampling it directly is hard, but sampling each variable separately is feasible. It is a basic tool of computational Bayesian statistics.

How it works

The idea is to break a hard problem into many easy ones. Instead of sampling all the variables at once, the algorithm goes through them one by one, updating each from its full conditional distribution: its distribution given the current values of all the others. Repeating this sweep many times generates a chain of samples that, after an initial burn-in period that is usually discarded, approximates the joint distribution being sought.

Where it comes from

Stuart and Donald Geman described it in 1984 in a paper on Bayesian image restoration published in IEEE Transactions on Pattern Analysis and Machine Intelligence. The name pays homage to the physicist Josiah Willard Gibbs, for the analogy with statistical mechanics. Technically, Gibbs sampling is a special case of the Metropolis-Hastings algorithm in which every proposal—drawn from the conditional itself—is always accepted.

What it is used for

It is a workhorse of Bayesian inference, especially for sampling posterior distributions in graphical models. In AI it appears in two well-known places. Griffiths and Steyvers used collapsed Gibbs sampling to infer topics, integrating out some parameters before updating each word's topic assignment. In products of experts with a bipartite structure—the structure of a restricted Boltzmann machine—Hinton described alternating Gibbs sweeps that update hidden and visible units in parallel. “Using Gibbs” does not by itself specify the training objective or how many steps are sufficient.

Its limits

The method has conditions and weak points. It requires being able to sample from every full conditional. When variables are strongly correlated, one-at-a-time updates can make the chain inch along a narrow region. An analysis of finite mixtures gives a concrete case in which correlated latent variables converge very slowly and blocked sampling reduces autocorrelation. Diagnosing convergence is not a mechanical reading either: Gill documents diagnostics that can disagree and dimensions that appear to converge while others do not. Reparameterizing, blocking variables, and comparing several chains are responses, not automatic certificates.