Gibbs sampling

Gibbs sampling
Name	Gibbs sampling
Class	Markov chain Monte Carlo
Author	Stuart Geman, Donald Geman
Year	1984
Based on	Metropolis–Hastings algorithm
Related	Metropolis–Hastings algorithm, Hamiltonian Monte Carlo

Gibbs sampling. It is a Markov chain Monte Carlo algorithm used to obtain a sequence of observations from a specified multivariate probability distribution when direct sampling is difficult. The method is widely used in Bayesian statistics, computational physics, and machine learning for approximating joint distributions through conditional sampling. It is named after the physicist Josiah Willard Gibbs, due to its connections to statistical mechanics.

Overview

The technique was formally introduced by Stuart Geman and Donald Geman in their 1984 paper on image processing, where it was applied to Gibbs random fields. It simplifies complex sampling problems by breaking them into a sequence of lower-dimensional conditional distributions. This approach is particularly powerful in Bayesian inference for estimating posterior distributions of model parameters. The algorithm's utility in hidden Markov models and latent Dirichlet allocation has cemented its importance in modern data science.

Algorithm

Given a target joint distribution, the procedure initializes all variables to arbitrary starting values. It then iteratively samples each variable from its conditional distribution, given the current values of all other variables, as defined by Bayes' theorem. This process generates a Markov chain whose stationary distribution is the desired joint distribution. Common implementations involve block Gibbs sampling, where groups of variables are updated simultaneously. The sequence of samples, after a sufficient burn-in period, is used for Monte Carlo integration.

Mathematical foundation

The method is a special case of the Metropolis–Hastings algorithm where every proposed sample is accepted. This acceptance rate of one is achieved because proposals are drawn directly from the full conditional distributions. The algorithm's correctness relies on the Hammersley–Clifford theorem, which establishes the equivalence between Markov random fields and Gibbs random fields. Convergence to the target distribution is governed by the properties of the underlying Markov chain, specifically its irreducibility and aperiodicity.

Convergence properties

Theoretical analysis of convergence often involves spectral gap estimates and coupling from the past techniques. The rate of convergence can be slow in high-dimensional spaces or when variables are strongly correlated, a phenomenon known as slow mixing. Diagnostic tools like Gelman–Rubin statistic and trace plots are used in practice to assess convergence. Research into improving convergence includes methods like over-relaxation and reparameterization.

Applications

It is extensively used in Bayesian hierarchical models, such as those in epidemiology and genetics. In natural language processing, it underpins algorithms for topic models like latent Dirichlet allocation. The COSMOS survey and Planck (spacecraft) data analysis have employed it for cosmological parameter estimation. Other fields include bioinformatics for protein structure prediction and econometrics for vector autoregression models.

Variants and extensions

Several adaptations address limitations of the basic method. Collapsed Gibbs sampling integrates out some variables analytically to improve efficiency. Particle Gibbs combines the approach with sequential Monte Carlo for state-space models. The No-U-Turn Sampler, an extension of Hamiltonian Monte Carlo, is often more efficient for complex posteriors. Software libraries like Stan (software) and PyMC3 implement these advanced MCMC methods.

Category:Monte Carlo methods Category:Bayesian statistics Category:Computational statistics