A conditional game for comparing approximations

Frederik EatonAISTATS 2011

Abstract

This paper introduces a formal "conditional game" to rank the accuracy of approximate inference algorithms without requiring ground-truth probabilities. By framing inference as a competition between a "marginal player" and a "conditional player," the authors demonstrate that the more accurate algorithm consistently prevails. This provides a robust benchmark for large-scale probabilistic models where exact solutions are computationally intractable.

Introduction

In Bayesian machine learning, calculating marginal probabilities in complex models is often computationally impossible, leading to a reliance on approximations like Belief Propagation or Gibbs sampling. A significant challenge arises in evaluating these approximations: how can we determine which algorithm is superior without access to the ground-truth distribution? Existing methods, such as internal heuristics or small-scale benchmarks, often fail to generalize or detect significant errors like missed modes. We propose a game-theoretic framework to address this "meta-problem."

Methods

The authors propose a two-player Conditional Game (CG) played on a factor graph. The "Marginal Player" (MP) provides estimated probabilities for variables, while the "Conditional Player" (CP) chooses specific values for those variables.

Example of the turn-based conditional game steps between the Marginal Player (MP) and Conditional Player (CP).

As illustrated above, players take turns. At each step $i$, the MP suggests a marginal probability for variable $x_i$, and the CP "clamps" that variable to a specific value $x_i^*$. This continues until all variables are fixed. The game value is calculated based on the ratio of the MP’s suggested probabilities to the model’s underlying factors. Theoretically, if the MP uses exact inference, the game value equals the negative log partition function ($-\log Z$), regardless of the CP's actions. If the MP is inexact, a strategic CP can force a lower value. To compare two algorithms, we use a "four-way score" ($S_4$), which involves a series of games where algorithms swap roles and objectives to ensure a fair and robust comparison.

Experimental Evaluation

The method was evaluated using the Alarm graph benchmark and synthetic factor graphs. Key findings include:

  • Ranking Accuracy: The $S_4$ score correctly ranked five different inference algorithms on the Alarm graph, remaining consistent with robust error measures even when average errors were close.
  • Correlation with Ground Truth: When comparing Generalized Belief Propagation (GBP) approximations, the game agreed with the true $L_1^{\log}$ error metric 75.4% of the time.
  • Tournament Performance: In a single-elimination tournament, the $S_4$ score successfully identified the most accurate algorithms as they progressed through rounds.
Algorithm performance across tournament rounds compared to the exact log-error.

The game is particularly sensitive to errors in the logarithm of marginals ($L_1^{\log}$ error). This is crucial because, in probabilistic modeling, underestimating a small probability is often more catastrophic than a larger absolute error in a high-probability region.

Discussion and Conclusion

The conditional game offers a theoretically grounded approach to benchmarking inference by treating it as a form of "argument" or debate between intelligent systems. While the computational cost is higher than single-run inference—requiring re-running inference as variables are clamped—the ability to rank algorithms without ground truth is a significant advancement. Future work includes developing "local" versions of the game for massive models and integrating the game into the learning process to evolve better algorithms.

Summary updated

BibTeX
@article{eaton2011conditional,
  author = {Frederik Eaton},
  title = {{A conditional game for comparing approximations}},
  journal = {AISTATS},
  year = {2011},
}

Loading related content...

Figure