Estimating the Partition Function by Discriminance Sampling.

Qiang Liu, Jian Peng, Alexander T. Ihler, John W. Fisher IiiUAI 2015 · OpenReview

Abstract

Estimating the partition function $Z$ is a fundamental challenge in probabilistic machine learning, particularly for models like Markov Random Fields and Deep Boltzmann Machines. We present Discriminance Sampling (DS), a method that treats partition function estimation as a binary classification task between a target and a proposal distribution. By maximizing the conditional likelihood of labels, DS provides a robust estimator that avoids the one-sided biases of traditional Importance Sampling (IS) and Reverse Importance Sampling (RIS). We further introduce Annealed Discriminance Sampling (ADS), demonstrating its superior performance and efficiency on Gaussian models, Markov Random Fields, and Deep Boltzmann Machines.

Introduction

In probabilistic graphical models, we often encounter unnormalized probabilities. To obtain a valid distribution, we must compute the partition function $Z$, which involves an often intractable summation or integration over all possible states. Standard techniques like Importance Sampling (IS) and its reverse counterpart (RIS) are sensitive to the "peakedness" of the proposal distribution relative to the target. IS tends to underestimate $Z$ when the proposal is too narrow, while RIS tends to overestimate it when the target is too narrow. This lack of robustness necessitates a more symmetric approach.

Methodology: Discriminance Sampling

The core innovation of this work is framing partition function estimation as a classification problem.

The DS Framework

Discriminance Sampling (DS) utilizes samples from both the target distribution $p(x)$ (labeled $y=1$) and a known proposal distribution $p_0(x)$ (labeled $y=0$). The authors demonstrate that the optimal classifier for distinguishing these samples depends directly on the ratio of their normalizing constants. By maximizing the conditional likelihood of these labels—effectively a specialized form of logistic regression—the unknown partition function $Z$ can be solved for directly.

Annealed Discriminance Sampling (ADS)

To handle complex distributions where a single proposal is insufficient, the method is extended to Annealed Discriminance Sampling (ADS). Similar to Annealed Importance Sampling (AIS), ADS uses a sequence of intermediate "tempered" distributions to bridge the gap between the proposal and the target. ADS can be implemented as a multi-class classification problem across all temperatures or a sequence of binary classifications between adjacent temperatures.

Figure 1: Robustness of DS compared to IS and RIS in a Gaussian toy example where the proposal variance $\sigma_0$ is varied.

Experimental Results

The researchers evaluated DS and ADS across several benchmarks, including Gaussian toy examples, pairwise Markov Random Fields (MRF), and Restricted/Deep Boltzmann Machines trained on MNIST.

Robustness to Distribution Mismatch

In Gaussian experiments, DS maintained a low Mean Squared Error (MSE) regardless of whether the proposal was more or less peaked than the target. In contrast, IS and RIS failed significantly when variances were mismatched, as shown in Figure 1. Unlike traditional methods, DS uses information from both distributions simultaneously, which cancels out one-sided biases.

Convergence and Efficiency in Deep Models

On Deep Boltzmann Machines (DBM), ADS demonstrated faster convergence and higher accuracy than AIS and Reverse AIS (RAISE). Notably, ADS requires significantly less computational overhead—approximately one-third the cost—because it avoids the need for separate forward and backward sampling chains. As shown in Figure 2, ADS reaches a stable, accurate estimate much faster than its competitors as the number of intermediate temperatures increases.

Figure 2: Convergence of ADS variants compared to AIS and RIS as the number of intermediate temperatures increases.

Key Insights

  • Symmetry is Strength: By using information from both distributions, DS avoids the "Goldilocks" problem of needing a proposal that is perfectly matched to the target's peakedness.
  • Milder Requirements: DS only requires that the two distributions overlap. It doesn't care which one is more peaked, making it far more robust to poor choices of proposal distributions.
  • Discriminative Learning: The method connects partition function estimation to the well-oiled machinery of discriminative classification, allowing for efficient optimization.

Conclusion

Discriminance Sampling offers a powerful and robust alternative to traditional importance sampling methods. By reframing a difficult estimation problem as a well-understood classification task, the authors provide a tool that is both more accurate and more computationally efficient for modern deep generative models. Future work may extend this framework to other partition-function-free learning algorithms, such as Score Matching or Contrastive Divergence.

Summary updated

BibTeX
@inproceedings{liu2015estimating,
  author = {Qiang Liu and Jian Peng and Alexander T. Ihler and John W. Fisher III},
  title = {{Estimating the Partition Function by Discriminance Sampling.}},
  booktitle = {UAI},
  year = {2015},
  url = {https://openreview.net/forum?id=XPbN2tUSoBE},
}
Figure