Undirected graphical models and energy-based models (EBMs) offer a powerful framework for capturing complex, high-dimensional data distributions. Unlike directed models, which specify a generative story step-by-step, undirected models define the probability of a state $x$ globally via an energy function $E(x)$:
$$P(x) = \frac{e^{-E(x)}}{Z(\theta)}$$
Here, $Z(\theta) = \sum_x e^{-E(x)}$ is the partition function, a global normalizing constant that ensures the probabilities sum to one. While conceptually elegant, this formulation introduces a massive computational bottleneck during learning. To maximize the log-likelihood of the observed data, we compute the gradient with respect to the model parameters $\theta$. This gradient splits into two opposing forces:
$$\nabla_\theta \log P(x) = -\nabla_\theta E(x) + \mathbb{E}_{x' \sim P}[ \nabla_\theta E(x') ]$$
The first term, known as the positive phase, minimizes the energy of the observed data points, creating deep valleys where real data resides. The second term, the negative phase, calculates the expectation of the gradient across the model's entire distribution, effectively pulling up the energy of all states to ensure the distribution integrates to one.
Computing this expectation requires generating samples from the model's current distribution. Standard Markov Chain Monte Carlo (MCMC) methods, such as Gibbs sampling, can achieve this, but they must be run for thousands of steps until the chain reaches thermal equilibrium (its stationary distribution). Doing this at every single training iteration is computationally paralyzing.
Following the Initial Drift
To bypass the equilibrium bottleneck, we do not actually need to map the model's entire distribution across the universe of all possible states. Instead, we only need to identify and eliminate the model's immediate errors near the data distribution.
This is the core insight behind Contrastive Divergence (CD). As Geoffrey E. Hinton argued in What kind of graphical model is the brain?, instead of initializing an MCMC chain from a random state and waiting for it to reach equilibrium, we can initialize the chain exactly at the observed data points and run it for only a few steps—often just a single step (denoted as CD-1).
Imagine the energy landscape as a flexible sheet. The positive phase pushes down on the locations of the real data points. If the model is imperfect, it will have created spurious, low-energy valleys nearby, pulling probability mass away from the true data. By starting a Markov chain at a real data point and letting it take a few steps, the sample will naturally begin to drift down the nearest slope toward the model's preferred spurious states.
As Max Welling et al. demonstrated in Energy-Based Models for Sparse Overcomplete Representations, observing this initial drift provides a highly efficient proxy for the true gradient. By pushing the energy of the starting data point down and pulling the energy of the short-run reconstruction up, the algorithm corrects the local landscape, neutralizing the drift before the chain ever needs to reach equilibrium.
Navigating Bias and Non-Convergence
Because the Markov chain is truncated early, the samples used in the negative phase do not come from the true model distribution. This means the CD update is not an exact gradient of the log-likelihood.
In a rigorous theoretical analysis, Tijmen Tieleman proved in On the Convergence Properties of Contrastive Divergence that the CD update vector is not the gradient of any objective function, meaning it can theoretically lead to optimization cycles. Furthermore, Asja Fischer et al. highlighted in Training RBMs based on the signs of the CD approximation of the log-likelihood derivatives that this truncation introduces a systematic bias because the chain fails to explore the model's true global equilibrium.
Why, then, does it work so well in practice? The answer lies in the nature of stochastic optimization. Amar Shah et al. showed in An Empirical Study of Stochastic Variational Inference Algorithms for the Beta Bernoulli Process that global parameter optimization is remarkably resilient to biased gradients derived from non-converged local samplers. Even a highly truncated, non-converged chain provides a sufficiently accurate directional signal to guide the model toward high-quality global solutions, trading exactness for massive computational speedups. This trade-off is so favorable that even single-step approximations are sufficient to train highly effective generative classifiers, as shown by Hugo Larochelle et al. in Learning Algorithms for the Classification Restricted Boltzmann Machine.
Persistent Chains: Tracking the Moving Equilibrium
To mitigate the bias of restarting at the data, an alternative variation called Persistent Contrastive Divergence (PCD) changes the initialization strategy. Instead of resetting the Markov chain to the data points at each gradient step, PCD maintains a "persistent" chain across iterations. As the model parameters $\theta$ are updated, the chain is simply advanced by a few steps from its previous state.
The intuition here is elegant: because the optimization step size is small, the model's energy landscape changes very slowly between iterations. Therefore, a Markov chain that was close to equilibrium at step $t$ will remain very close to the new equilibrium at step $t+1$, even after only a few steps of simulation.
The authors of Learning Heterogeneous Hidden Markov Random Fields leveraged this mechanism to optimize complex, heterogeneous graphical models where the partition function varies across sites. Similarly, John Ingraham et al. demonstrated in Variational Inference for Sparse and Undirected Models that tracking the log-partition function's gradient via persistent chains enables scalable Bayesian inference in sparse undirected models without ever explicitly computing the intractable normalizing constant.
Widespread Application Across Architectures
The strategy of short-run Markov chain approximation has proven versatile across a vast array of probabilistic architectures:
- Hierarchical and Overcomplete Models: It allows for the efficient training of stacked bipartite networks like Products of Experts (Guy Mayraz et al. in Recognizing Hand-written Digits Using Hierarchical Products of Experts) and overcomplete filter sets like those explored in Learning Sparse Topographic Representations with Products of Student-t Distributions.
- Generalized Distributions: Max Welling et al. extended the technique to Exponential Family Harmoniums in Exponential Family Harmoniums with an Application to Information Retrieval, generalizing the approach beyond binary variables to any exponential family distribution. Qinliang Su further adapted it in Unsupervised Learning with Truncated Gaussian Graphical Models to handle truncated Gaussian hidden units, enabling stable training of continuous, non-linear hidden features.
- Sequential and Structured Data: For time-series and structured domains, the algorithm enables gradient descent in Products of Hidden Markov Models (Graham W. Taylor et al. in Products of Hidden Markov Models: It Takes N>1 to Tango), Predictive State Representations (Nan Jiang et al. in Improving Predictive State Representations via Gradient Descent.), and hierarchical tree-structured networks (Aakanksha Gagrani et al. in Image Modeling Using Tree Structured Conditional Random Fields).
Furthermore, the method scales to high-order interactions and specialized domains. Martin Renqiang Min et al. paired short-run approximations with mean-field updates to make high-order Boltzmann machines practical in Interpretable Sparse High-Order Boltzmann Machines. It has also been successfully applied to model complex biological systems, such as neural population spiking activity (Frank D. Wood et al. in Modeling Neural Population Spiking Activity with Gibbs Distributions), unsupervised metric learning for histograms (Tam Le et al. in Unsupervised Riemannian Metric Learning for Histograms Using Aitchison Transformations), and high-dimensional video mapping (Matthew D. Zeiler et al. in Facial Expression Transfer with Input-Output Temporal Restricted Boltzmann Machines).
Key Foundational Work
Rate-coded Restricted Boltzmann Machines for Face Recognition (2000) — contributed 1 concept elements to this direction.
Recognizing Hand-written Digits Using Hierarchical Products of Experts (2000) — contributed 1 concept elements to this direction.
Unsupervised learning of distributions on binary vectors using two layer networks (1991) — contributed 1 concept elements to this direction.