Accurate and conservative estimates of MRF log-likelihood using reverse annealing

Yuri Burda, Roger B. Grosse, Ruslan Salakhutdinov

Abstract

Evaluating Markov Random Fields (MRFs) is a fundamental challenge in generative modeling due to the intractability of the partition function. While Annealed Importance Sampling (AIS) is the standard estimation tool, it typically provides optimistic upper bounds on log-likelihood. We introduce RAISE (Reverse AIS Estimator), an algorithm that provides a stochastic lower bound. By combining AIS and RAISE, researchers can "sandwich" the true log-likelihood, providing a reliable measure of model performance and a robust means to detect estimation failure.

Introduction

Generative models such as Restricted Boltzmann Machines (RBMs) and Deep Boltzmann Machines (DBMs) are powerful for unsupervised learning, but their evaluation depends on the partition function ($Z$), a normalizing constant that requires summing over an exponential number of states. Standard AIS estimates $Z$ by transitioning from a simple, tractable distribution to the complex target model. However, AIS tends to underestimate $Z$, which mathematically results in an overestimate of the log-likelihood. This inherent optimism can lead to false confidence in a model's performance without a clear way to detect errors.

The RAISE Algorithm

RAISE addresses this limitation by reversing the annealing process. Instead of starting from a simple prior, RAISE begins with a sample from the target model (or a test data point) and "melts" it back toward a tractable distribution.

The annealing process in RAISE involves transitions between a simple distribution $p_0$ and the complex target $p_K$. Clamping the visible units $\mathbf{v}$ allows for the reverse transitions $\tilde{T}_k^{(\mathbf{v})}$ used in the estimator.

Stochastic Lower Bound

RAISE estimates the log-likelihood of an "annealing model"—a directed graphical model that approximates the original MRF. As the number of intermediate distributions ($K$) increases, this approximation converges to the true MRF. By applying importance sampling in the reverse direction, RAISE produces an unbiased estimate of probability under the annealing model. According to Jensen’s Inequality, the logarithm of this estimate serves as a stochastic lower bound on the log-likelihood.

To maintain computational efficiency, the authors employ control variates. This variance reduction technique allows for accurate estimation across a dataset by processing only a small subset of test points individually, making the method practical for large-scale benchmarks.

Results and the "Sandwich" Effect

The primary advantage of RAISE is its role as a conservative counterpart to AIS. When the optimistic AIS estimate and the conservative RAISE estimate converge, the true log-likelihood is effectively "sandwiched," providing high confidence in the model's true performance.

Convergence of AIS and RAISE estimates on the MNIST dataset using Data Base Rate (DBR) initialization. The two bounds converge as the number of intermediate distributions increases, providing a tight "sandwich" of the true log-likelihood.

Key Insights

  • Initialization Strategy: The choice of the initial "simple" distribution is critical. Using a "Data Base Rate" (DBR) distribution—which reflects the average pixel intensities of the training data—significantly improves convergence speed and agreement between bounds compared to a uniform prior.
  • Failure Detection: RAISE is particularly effective at identifying cases where AIS fails. In experiments with models trained using limited Contrastive Divergence (CD-1), AIS often yielded suspiciously high scores. RAISE revealed massive gaps (up to 44 nats), exposing these AIS estimates as untrustworthy.
  • Architectural Versatility: The method was successfully validated on RBMs, DBMs, and Deep Belief Networks (DBNs) using the MNIST and Omniglot datasets, consistently providing more accurate conservative estimates than previous methods like CSL.

Conclusion

RAISE provides a critical tool for the rigorous evaluation of MRFs. By offering a conservative lower bound, it complements the optimistic bias of AIS and enables researchers to verify the accuracy of their likelihood estimates. Furthermore, the interpretation of RAISE as "unrolling" an MRF into a deep directed model suggests potential future directions for training undirected models by directly optimizing the RAISE lower bound, similar to the training objectives of Variational Autoencoders.

Summary updated

Abstract

Markov random fields (MRFs) are difficult to evaluate as generative models because computing the test log-probabilities requires the intractable partition function. Annealed importance sampling (AI...
BibTeX
@inproceedings{burda2015accurate,
  author = {Yuri Burda and Roger B. Grosse and Ruslan Salakhutdinov},
  title = {{Accurate and conservative estimates of MRF log-likelihood using reverse annealing}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=qJ54-UW4eR1},
}
Figure