| |
Abstract:
We develop a tree-based reparameterization framework that
provides a new conceptual view of a large class of iterative
algorithms for computing approximate marginals in graphs with
cycles. It includes
belief propagation
(BP), which can be reformulated as a very local form of
reparameterization. More generally, we consider algorithms that
perform exact computations over spanning trees of the full graph.
On the practical side, we find that such tree reparameterization
(TRP) algorithms have convergence properties superior to BP. The
reparameterization perspective also provides a number of
theoretical insights into approximate inference, including a new
characterization of fixed points; and an invariance intrinsic to
TRP/BP. These two properties enable us to analyze and bound the
error between the TRP/BP approximations and the actual marginals.
While our results arise naturally from the TRP perspective, most
of them apply in an algorithm-independent manner to any local
minimum of the Bethe free energy. Our results also have natural
extensions to more structured approximations [e.g., 1, 2].
References
[1] J. Yedidia, W. T. Freeman, and Y. Weiss. Generalized
belief propagation. In
NIPS 13
, pages 689-695. MIT Press, 2001.
[2] T. P. Minka. A family of algorithms for approximate
Bayesian inference. PhD thesis, MIT Media Lab, 2001.
|
