Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Tightness Results for Local Consistency Relaxations in Continuous MRFs
Yoav Wald, Amir Globerson
Abstract:
Finding the MAP assignment in graphical mod- els is a challenging task that generally requires approximations. One popular approximation ap- proach is to use linear programming relaxations that enforce local consistency. While these are commonly used for discrete variable models, they are much less understood for models with continuous variables. Here we define local consistency relaxations of MAP for continuous pairwise Markov Random Fields (MRFs), and analyze their properties. We begin by providing a characterization of models for which this relaxation is tight. These turn out to be models that can be reparameterized as a sum of local convex functions. We also provide a simple formulation of this relaxation for Gaus- sian MRFs. Next, we show how the above insights can be used to obtain optimality certificates for loopy belief propagation (LBP) in such models. Specif- ically, we show that the messages of LBP can be used to calculate upper and lower bounds on the MAP value, and that these bounds coincide at convergence, yielding a natural stopping crite- rion which was not previously available. Finally, our results illustrate a close connection between local consistency relaxations of MAP and LBP. They demonstrate that in the continu- ous case, whenever LBP is provably optimal so is the local consistency relaxation.
Keywords:
Pages: 839-848
PS Link:
PDF Link: /papers/14/p839-wald.pdf
BibTex:
@INPROCEEDINGS{Wald14,
AUTHOR = "Yoav Wald and Amir Globerson",
TITLE = "Tightness Results for Local Consistency Relaxations in Continuous MRFs",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "839--848"
}


hosted by DSL   •   site info   •   help