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

It was described by Stuart and Donald Geman in 1984, in a work 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 the posterior distribution of graphical models and Bayesian networks. In AI it shows up in two well-known places: fitting topic models such as LDA, via a variant called collapsed Gibbs sampling, and training restricted Boltzmann machines.

Its limits

The method has conditions and weak points. It requires being able to sample from all the full conditionals. And, above all, its convergence becomes slow when the variables are strongly correlated: updating one at a time makes the chain move in tiny steps and explore the space poorly. Moreover, knowing when it has converged is not trivial; diagnostics such as the Gelman-Rubin statistic or the effective sample size are used.