Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Tightening LP Relaxations for MAP using Message Passing
David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, Yair Weiss
Abstract:
Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved efficiently using message-passing algorithms such as belief propagation and, when the relaxation is tight, provably find the MAP configuration. The standard LP relaxation is not tight enough in many real-world problems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponentially with the size of the clusters and limits the number and type of clusters we can use. We propose to solve the cluster selection problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solution. Our dual message-passing algorithm finds the MAP configuration in protein sidechain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails.
Keywords:
Pages: 503-510
PS Link:
PDF Link: /papers/08/p503-sontag.pdf
BibTex:
@INPROCEEDINGS{Sontag08,
AUTHOR = "David Sontag and Talya Meltzer and Amir Globerson and Tommi Jaakkola and Yair Weiss",
TITLE = "Tightening LP Relaxations for MAP using Message Passing",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "503--510"
}


hosted by DSL   •   site info   •   help