Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Convergent Propagation Algorithms via Oriented Trees
Amir Globerson, Tommi Jaakkola
Abstract:
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.
Keywords:
Pages: 133-140
PS Link:
PDF Link: /papers/07/p133-globerson.pdf
BibTex:
@INPROCEEDINGS{Globerson07,
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"
}


hosted by DSL   •   site info   •   help