Approximate inference using conditional entropy decompositions

Amir Globerson, Tommi S. JaakkolaAISTATS 2007 · OpenReview

Abstract

We introduce a novel method for estimating the partition function and marginals of distributions defined using graphical models. The method uses the entropy chain rule to obtain an upper bound on the log-partition function. By strategically discarding conditioning variables, we derive a convex optimization problem that provides tighter bounds and more accurate marginals than existing techniques like Tree Re-weighting (TRW).

Introduction

In probabilistic graphical models, calculating the partition function ($Z$) and computing marginal probabilities are fundamental but computationally intractable tasks. These operations require summing over an exponential number of states, making exact inference impossible for large-scale models. Variational inference addresses this by framing inference as an optimization problem, typically involving an approximation of the distribution's entropy. While methods like Loopy Belief Propagation (BP) are popular, they lack convergence guarantees and bounding properties. Tree Re-weighting (TRW) provides a convex upper bound but is limited by its reliance on tree-structured distributions.

The Conditional Entropy Decomposition (CED) Method

The core innovation of this work is Conditional Entropy Decomposition (CED). The method leverages the exact entropy chain rule:

$$H(X_1, \dots, X_n) = \sum_{i=1}^n H(X_i | X_1, \dots, X_{i-1})$$

Because conditioning never increases entropy, removing variables from the conditioning set creates a rigorous upper bound on the total entropy. By defining "restricted elimination neighborhoods"—small, tractable subsets of variables to condition on—the authors transform the entropy estimation into a convex optimization problem.

Key features of CED include:

  • Convexity: Unlike non-convex methods like Generalized Belief Propagation, CED is guaranteed to converge to a global optimum.
  • Generalization: The authors demonstrate that TRW is a special case of CED, where CED's flexibility allows for conditioning on arbitrary subsets rather than just tree structures.
  • Duality: The optimization problem's dual is a Geometric Program, which can be solved efficiently using standard numerical solvers.

Experimental Evaluation

The method was evaluated on a 2D Ising Model (a $10 \times 10$ grid), a standard benchmark in statistical physics. The experiments compared CED against TRW, BP, and a variant called CEDF across various interaction strengths and field types (attractive and mixed).

Key Results

Error in the log-partition function (log Z) for various Ising model configurations.

As shown in the log-partition function error plots, CED consistently provides a significantly tighter upper bound on $\log Z$ compared to TRW. While BP often yields low error, it is not a guaranteed bound and frequently fails to converge as interaction strength increases. The CEDF variant, while accurate in some regimes, also lacks the formal bounding guarantee of the primary CED method.

Marginal error comparison between CED, TRW, and BP.

In terms of marginal accuracy, CED outperforms TRW across nearly all tested parameters. While BP can be highly accurate for low-interaction models, its performance degrades or becomes unstable in high-interaction regimes. CED remains robust and stable even when interactions are strong, providing a reliable alternative for complex graphical models.

Conclusion and Future Work

Conditional Entropy Decomposition offers a powerful new framework for variational inference. By providing a tighter, convex upper bound on the partition function, it improves upon the limitations of TRW while maintaining computational tractability. Future research directions include optimizing the choice of elimination orders and weights, scaling the method to larger conditioning clusters, and developing specialized message-passing algorithms to enhance speed for large-scale applications.

Summary updated

Abstract

We introduce a novel method for estimating the partition function and marginals of distributions defined using graphical models. The method uses the entropy chain rule to obtain an upper bound on t...
BibTeX
@inproceedings{globerson2007approximate,
  author = {Amir Globerson and Tommi S. Jaakkola},
  title = {{Approximate inference using conditional entropy decompositions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=j7tfyXNO_Qs},
}
Figure