Paper Info
Title
Convergent message passing algorithms: a unifying view
Abstract
Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.
Year
Venue
Keywords
2012
UAI '09 Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence
convergent message-passing algorithm,abstract algorithm,tcbo algorithm,novel convergent algorithm,algorithms converge,existing convergent algorithm,provably convergent,unifying view,non-convergent sum-product algorithm,message-passing algorithm,popular algorithm
DocType
Volume
Citations 
Journal
abs/1205.2625
52
PageRank 
References 
Authors
1.83
12
3
Name
Order
Citations
PageRank
Talya Meltzer141522.18
Amir Globerson21515117.72
Yair Weiss310240834.60