Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models
Nicholas Ruozzi, Sekhar Tatikonda
Abstract:
The max-product algorithm, which attempts to compute the most probable assignment (MAP) of a given probability distribution, has recently found applications in quadratic minimization and combinatorial optimiza- tion. Unfortunately, the max-product algo- rithm is not guaranteed to converge and, even if it does, is not guaranteed to produce the MAP assignment. In this work, we provide a simple derivation of a new family of message passing algorithms by "splitting" the factors of our graphical model. We prove that, for any objective function that attains its maxi- mum value over its domain, this new family of message passing algorithms always contains a message passing scheme that guarantees cor- rectness upon convergence to a unique es- timate. Finally, we adopt an asynchronous message passing schedule and prove that, un- der mild assumptions, such a schedule guar- antees the convergence of our algorithm.
Keywords:
Pages: 500-500
PS Link:
PDF Link: /papers/10/p500-ruozzi.pdf
BibTex:
@INPROCEEDINGS{Ruozzi10,
AUTHOR = "Nicholas Ruozzi and Sekhar Tatikonda",
TITLE = "Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "500--500"
}


hosted by DSL   •   site info   •   help