Structured Region Graphs: Morphing EP into GBP
This provides a foundational framework for improving approximate inference in machine learning, though it is incremental in bridging existing methods.
The paper tackles the problem of choosing appropriate approximation structures for GBP and EP algorithms in probabilistic inference by introducing structured region graphs, which unify the two strategies and reveal that all EP approximations on discrete variables are special cases of GBP, and vice versa for some GBP approximations like overlapping squares.
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