Structured Region Graphs: Morphing EP into GBP

arXiv (Cornell University)Published 4 July 2012Open access

Max Welling, Thomas P. Minka, Yee Whye Teh

DOI10.48550/arxiv.1207.1426

Citations32

TL;DR

"structured region graphs," a formalism which marries these two strategies, reveals a deep connection between them, and suggests how to choose good approximation structures, which is a convenient framework for producing high-quality approximations with a user-adjustable level of complexity.

Abstract

GBP and EP are two successful algorithms for approximate probabilistic inference, which are based on different approximation strategies. An open problem in both algorithms has been how to choose an appropriate approximation structure. We introduce 'structured region graphs', a formalism which marries these two strategies, reveals a deep connection between them, and suggests how to choose good approximation structures. In this formalism, each region has an internal structure which defines an exponential family, whose sufficient statistics must be matched by the parent region. Reduction operators on these structures allow conversion between EP and GBP free energies. Thus it is revealed that all EP approximations on discrete variables are special cases of GBP, and conversely that some wellknown GBP approximations, such as overlapping squares, are special cases of EP. Furthermore, region graphs derived from EP have a number of good structural properties, including maxent-normality and overall counting number of one. The result is a convenient framework for producing high-quality approximations with a user-adjustable level of complexity

Keywords

Computer Science

IEEE Transactions on Information TheoryConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms

1,627 Citations2005Jonathan S. Yedidia, William T. Freeman +1 more

This work explains how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms, and describes empirical results showing that GBP can significantly outperform BP.

arXiv (Cornell University)Expectation Propagation for approximate Bayesian inference

1,457 Citations2013Thomas P. Minka

View PDF

Neural Information Processing SystemsTree-structured Approximations by Expectation Propagation

76 Citations2003Yuan Qi, Tom Minka

Belief propagation is extended to represent factors with tree approximations, by way of the expectation propagation framework, which results in more accurate inferences and more frequent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms.

Neural ComputationEstimation and Marginalization Using the Kikuchi Approximation Methods

52 Citations2005Payam Pakzad, Venkat Anantharam

This letter examines a general method of approximation for finding the marginals of a product distribution, as well as the corresponding partition function, and shows that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically.

Uncertainty in Artificial IntelligenceOn the choice of regions for generalized belief propagation

48 Citations2004Max Welling

This paper proposes a sequential approach to adding new clusters of nodes and their interactions (i.e. "regions") to the approximation of generalized belief propagation, and proposes "weakly irreducible" regions as the natural candidates to be added to the approximation.

The IMA volumes in mathematics and its applicationsBelief Propagation on Partially Ordered Sets

41 Citations2003Robert J. McEliece, Muhammed A. Yıldırım

It is shown that PBP can be thought of as an algorithm for minimizing a certain “free energy” function, and by exploiting this interpretation, a one-to-one correspondence between the fixed points of PBP and the stationary points of the free energy is exhibited.

Data Archiving and Networked Services (DANS)Generalized belief propagation for approximate inference in hybrid Bayesian networks

21 Citations2003Tom Heskes, Onno Zoeter

View PDF