Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Lifted Message Passing as Reparametrization of Graphical Models
Martin Mladenov, Amir Globerson, Kristian Kersting
Abstract:
Lifted inference approaches can considerably speed up probabilistic inference in Markov ran- dom fields (MRFs) with symmetries. Given ev- idence, they essentially form a lifted, i.e., re- duced factor graph by grouping together indistin- guishable variables and factors. Typically, how- ever, lifted factor graphs are not amenable to off- the-shelf message passing (MP) approaches, and hence requires one to use either generic opti- mization tools, which would be slow for these problems, or design modified MP algorithms. Here, we demonstrate that the reliance on mod- ified MP can be eliminated for the class of MP algorithms arising from MAP-LP relaxations of pairwise MRFs. Specifically, we show that a given MRF induces a whole family of MRFs of different sizes sharing essentially the same MAP- LP solution. In turn, we give an efficient algo- rithm to compute from them the smallest one that can be solved using off-the-shelf MP. This incurs no major overhead: the selected MRF is at most twice as large as the fully lifted factor graph. This has several implications for lifted inference. For instance, running MPLP results in the first con- vergent lifted MP approach for MAP-LP relax- ations. Doing so can be faster than solving the MAP-LP using lifted linear programming. Most importantly, it suggests a novel view on lifted in- ference: it can be viewed as standard inference in a reparametrized model.
Keywords:
Pages: 603-612
PS Link:
PDF Link: /papers/14/p603-mladenov.pdf
BibTex:
@INPROCEEDINGS{Mladenov14,
AUTHOR = "Martin Mladenov and Amir Globerson and Kristian Kersting",
TITLE = "Lifted Message Passing as Reparametrization of Graphical Models",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "603--612"
}


hosted by DSL   •   site info   •   help