Convergent Propagation Algorithms via Oriented Trees
Amir Globerson, Tommi Jaakkola
Inference problems in graphical models are often approximated by casting them as con- strained optimization problems. Message passing algorithms, such as belief propaga- tion, have previously been suggested as meth- ods for solving these optimization problems. However, there are few convergence guaran- tees for such algorithms, and the algorithms are therefore not guaranteed to solve the cor- responding optimization problem. Here we present an oriented tree decomposition al- gorithm that is guaranteed to converge to the global optimum of the Tree-Reweighted (TRW) variational problem. Our algorithm performs local updates in the convex dual of the TRW problem - an unconstrained generalized geometric program. Primal up- dates, also local, correspond to oriented reparametrization operations that leave the distribution intact.
PDF Link: /papers/07/p133-globerson.pdf
AUTHOR = "Amir Globerson
and Tommi Jaakkola",
TITLE = "Convergent Propagation Algorithms via Oriented Trees",
BOOKTITLE = "Proceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2007",
PAGES = "133--140"