Learning in Markov Random Fields using Tempered Transitions

Ruslan SalakhutdinovNeurIPS 2009 · OpenReview

Introduction

Markov Random Fields (MRFs), or undirected graphical models, provide a highly flexible framework for modeling complex dependencies among random variables. They are a cornerstone of machine learning for tasks involving high-dimensional, richly structured data. However, learning the parameters for large, complex MRFs is notoriously difficult due to the partition function—a global normalizing constant that requires summing over an exponentially large number of possible configurations.

Because exact Maximum Likelihood learning is intractable for large models, researchers typically rely on Markov Chain Monte Carlo (MCMC) methods to approximate the necessary gradients. This paper addresses a critical flaw in standard MCMC approaches: the tendency to get trapped in local optima when dealing with highly multimodal data distributions, and introduces a robust solution using tempered transitions.

The Multimodality Bottleneck

Real-world data, such as images, is often highly multimodal. The probability landscape resembles a mountain range with many high, narrow peaks separated by deep, wide valleys. A standard MCMC sampler (like a Gibbs sampler) acts like a hiker who climbs the nearest peak and stays there, completely unaware of other, potentially taller peaks miles away.

Consequently, the learning algorithm only explores a tiny fraction of the data's underlying structure. This leads to biased parameter estimates, poor generative performance, and models that fail to capture the true diversity of the training data.

Overcoming Local Optima with Tempered Transitions

To solve this, the paper builds upon the Stochastic Approximation Procedure (SAP), a Robbins-Monro type algorithm that maintains a set of "sample particles" updated via MCMC steps during training.

The core innovation is replacing standard random walks with Tempered Transitions. Instead of getting stuck in a single mode, the algorithm performs a "tempering" run to jump between isolated peaks:

  1. The Forward Pass: The sampler moves through a sequence of intermediate distributions, gradually "heating up" the target distribution. This flattens the probability landscape, making it easier for the sampler to traverse the entire state space.
  2. The Backward Pass: The sampler then moves back through the sequence, "cooling" the distribution down to the original, complex target.
  3. Acceptance: A new state is accepted or rejected based on a specific ratio that ensures the Markov chain remains valid and converges to the correct distribution.

Because tempered transitions are computationally expensive, the author proposes Trans-SAP, an algorithm that alternates between many cheap Gibbs updates and occasional expensive tempered transitions. This "refreshes" the particles, providing the exploratory power of tempering without prohibitive computational overhead.

Experimental Setup and Key Findings

The approach was evaluated on two classic high-dimensional benchmarks: the MNIST dataset of handwritten digits and the NORB dataset of 3D toy objects under various lighting and viewpoints. The models tested included Restricted Boltzmann Machines (RBMs) and more complex Semi-restricted Boltzmann Machines.

Model architectures and performance comparisons showing the superiority of Tempered Transitions over standard Stochastic Approximation.

The quantitative results demonstrate a clear advantage for the tempered approach:

  • Generative Quality (MNIST): On a semi-restricted BM with 700,000 parameters, Trans-SAP achieved an average test log-probability of -85.91 nats, significantly outperforming the -87.12 nats achieved by plain SAP.
  • Classification Accuracy (NORB): When using learned features for object recognition, the model trained with tempered transitions reduced the classification error rate from 8.7% to 8.4%. This outperformed standard baselines like SVMs (11.6%) and K-nearest neighbors (18.4%) by a wide margin.

Escaping the "Unbalanced Model" Trap

One of the most compelling arguments for tempered transitions is visual. Without tempering, SAP often produces models that are "unbalanced." For example, a model trained on MNIST might place almost all its probability mass on a single digit (like the number "4") simply because the sampler got stuck in that specific mode during training.

Visual comparison of samples before and after tempered transitions, demonstrating how the model escapes local modes (e.g., generating only 4s) to produce diverse, high-quality digits.

Tempering forces the model to acknowledge the full distribution of the data. By sampling from the entire distribution rather than just one local neighborhood, the algorithm obtains a much more accurate estimate of the expected "sufficient statistics." As a result, models trained with tempered transitions capture sharp, diverse object regularities rather than blurry or repetitive artifacts.

Limitations and Future Directions

While highly effective, tempered transitions come with trade-offs:

  • Computational Cost: Even with the alternating Trans-SAP schedule, tempered transitions are slower than standard Gibbs sampling. Furthermore, finding the optimal schedule of temperatures ($\beta$ values) remains a manual tuning task.
  • Scaling: The paper successfully demonstrates the method on models with up to 16 million parameters (NORB). However, as models grow even larger, more sophisticated sampling techniques, such as parallel tempering, may be required to maintain efficiency.

Ultimately, this research proves that integrating tempered MCMC operators into stochastic approximation algorithms drastically improves parameter estimation in large, densely-connected MRFs. These operators are highly adaptable and can be integrated into various existing MCMC-based learning frameworks, paving the way for more robust generative modeling of complex data.

Summary updated

Abstract

Markov random fields (MRFs), or undirected graphical models, provide a powerful framework for modeling complex dependencies among random variables. Maximum likelihood learning in MRFs is hard due to the presence of the global normalizing constant. In this paper we consider a class of stochastic approximation algorithms of Robbins-Monro type that uses Markov chain Monte Carlo to do approximate maximum likelihood learning. We show that using MCMC operators based on tempered transitions enables the stochastic approximation algorithm to better explore highly multimodal distributions, which considerably improves parameter estimates in large densely-connected MRFs. Our results on MNIST and NORB datasets demonstrate that we can successfully learn good generative models of high-dimensional, richly structured data and perform well on digit and object recognition tasks.
BibTeX
@inproceedings{salakhutdinov2009learning,
  author = {Ruslan Salakhutdinov},
  title = {{Learning in Markov Random Fields using Tempered Transitions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=HkZrIv-dZH},
}
Figure