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
theshelf 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 MAPLP 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 offtheshelf 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 MAPLP relax
ations. Doing so can be faster than solving the
MAPLP 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: 603612
PS Link:
PDF Link: /papers/14/p603mladenov.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 (UAI14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "603612"
}

