Asymptotic Efficiency of Deterministic Estimators for Discrete Energy-Based Models: Ratio Matching and Pseudolikelihood

Benjamin M. Marlin, Nando de Freitas

Introduction

Discrete Energy-Based Models (EBMs), such as Markov Random Fields and Boltzmann Machines, are fundamental tools in machine learning for modeling complex dependencies in discrete data. However, their application is often hindered by the computational intractability of the partition function—the normalization constant required to calculate exact probabilities. While Maximum Likelihood (ML) estimation is the statistically efficient "gold standard," it is often unusable in practice due to this "Catch-22."

To circumvent this, researchers have developed deterministic alternatives like Pseudolikelihood (PL) and Ratio Matching (RM). These methods avoid the partition function by focusing on ratios of conditional probabilities. Despite their popularity, the relative statistical efficiency of these methods—how much accuracy is sacrificed for computational speed—remained poorly understood until now.

A Unified Framework for Deterministic Estimators

This research introduces a Generalized Estimator framework that unifies several popular deterministic methods. The authors demonstrate that most of these estimators can be defined by three primary components:

  1. A Neighborhood ($N$): The set of states to which a given state is compared.
  2. A Transfer Function ($g$): A function that penalizes the discrepancy between predicted probability ratios and observed data.
  3. Components ($C$): The number of comparisons aggregated in the final objective function.

By framing these as M-estimators, the authors derived a generic expression for the asymptotic covariance matrix, allowing for a rigorous comparison of their statistical properties.

The fundamental difference between Pseudolikelihood and Ratio Matching lies in their transfer functions: PL uses a logarithmic function, while RM uses a squared difference.

As shown in Figure 1, the core distinction between PL and RM is the choice of the transfer function $g$. PL utilizes $\log(R)$, whereas RM utilizes a squared difference $-(1-R)^2$. This single mathematical choice dictates the estimator's behavior across different probability landscapes.

The Efficiency Seesaw

A key theoretical contribution of this work is the derivation of bounds on the relative efficiency of these estimators. The authors prove that the performance gap between PL and RM is fundamentally linked to the "peakiness" of the model's conditional distributions.

If the conditional probabilities are near uniform, the estimators perform almost identically. However, as the distributions become more "peaky" (probabilities approaching 0 or 1), the potential variance difference between the two grows. Crucially, the paper proves that neither PL nor RM is strictly superior; for a given model, one might estimate certain parameters more accurately while the other excels elsewhere.

Empirical Results and Scaling

To validate these theoretical insights, the authors conducted simulations using a third-order binary Boltzmann machine. Because the model was small, the "true" ML could be calculated as a baseline.

Scatter plots showing the difference in Log-Determinant of the asymptotic covariance matrices between PL, RM, and ML as a function of the model's bound width.

As illustrated in Figure 2, several key trends emerge:

  • ML Dominance: As predicted by theory, Maximum Likelihood consistently achieves the lowest variance (highest efficiency).
  • Bound Width Correlation: The "Bound Width" represents the range of conditional probabilities in the model. As this width increases, the variance gap between the deterministic estimators and ML grows significantly.
  • Indefinite Ordering: The comparison between RM and PL (Figure 2c) shows points distributed around zero, confirming that neither estimator is universally better than the other across all parameter settings.

Conclusion

By providing a unified mathematical template, this work clarifies the trade-offs involved in choosing deterministic estimators for EBMs. The results suggest that the choice between Pseudolikelihood and Ratio Matching should be informed by the expected "peakiness" of the data distribution. Furthermore, this framework opens the door for "engineering" new transfer functions tailored to specific graphical models, potentially leading to even more efficient deterministic estimators in the future.

Summary updated

Abstract

Standard maximum likelihood estimation cannot be applied to discrete energy-based models in the general case because the computation of exact model probabilities is intractable. Recent research has seen the proposal of several new estimators designed specifically to overcome this intractability, but virtually nothing is known about their theoretical properties. In this paper, we present a generalized estimator that unifies many of the classical and recently proposed estimators. We use results from the standard asymptotic theory for M-estimators to derive a generic expression for the asymptotic covariance matrix of our generalized estimator. We apply these results to study the relative statistical efficiency of classical pseudolikelihood and the recently-proposed ratio matching estimator.
BibTeX
@misc{marlin2011asymptotic,
  author = {Benjamin M. Marlin and Nando de Freitas},
  title = {{Asymptotic Efficiency of Deterministic Estimators for Discrete Energy-Based Models: Ratio Matching and Pseudolikelihood}},
  year = {2011},
  eprint = {1202.3746},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1202.3746},
}
Figure