Convergent and Correct Message Passing Schemes for Optimization Problems over Graphical Models
Nicholas Ruozzi, Sekhar Tatikonda
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.
PDF Link: /papers/10/p500-ruozzi.pdf
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"