Timezone: »

 
Poster
An Integer Polynomial Programming Based Framework for Lifted MAP Inference
Somdeb Sarkhel · Deepak Venugopal · Parag Singla · Vibhav G Gogate

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None
in Poster Session »

In this paper, we present a new approach for lifted MAP inference in Markov logic networks (MLNs). The key idea in our approach is to compactly encode the MAP inference problem as an Integer Polynomial Program (IPP) by schematically applying three lifted inference steps to the MLN: lifted decomposition, lifted conditioning, and partial grounding. Our IPP encoding is lifted in the sense that an integer assignment to a variable in the IPP may represent a truth-assignment to multiple indistinguishable ground atoms in the MLN. We show how to solve the IPP by first converting it to an Integer Linear Program (ILP) and then solving the latter using state-of-the-art ILP techniques. Experiments on several benchmark MLNs show that our new algorithm is substantially superior to ground inference and existing methods in terms of computational efficiency and solution quality.

Author Information

Somdeb Sarkhel (University of Texas at Dallas)
Deepak Venugopal (The University of Texas at Dallas (UT Dallas))
Parag Singla (Indian Institute of Technology Delhi)
Vibhav G Gogate (UT Dallas)

More from the Same Authors