Timezone: »
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 Gogate (UT Dallas)
More from the Same Authors
-
2019 Poster: A Primal Dual Formulation For Deep Learning With Constraints »
Yatin Nandwani · Abhishek Pathak · Mausam · Parag Singla -
2018 : Spotlights 2 »
Mausam · Ankit Anand · Parag Singla · Tarik Koc · Tim Klinger · Habibeh Naderi · Sungwon Lyu · Saeed Amizadeh · Kshitij Dwivedi · Songpeng Zu · Wei Feng · Balaraman Ravindran · Edouard Pineau · Abdulkadir Celikkanat · Deepak Venugopal -
2015 Poster: Bounding the Cost of Search-Based Lifted Inference »
David B Smith · Vibhav Gogate -
2015 Poster: Fast Lifted MAP Inference via Partitioning »
Somdeb Sarkhel · Parag Singla · Vibhav Gogate -
2015 Poster: Lifted Inference Rules With Constraints »
Happy Mittal · Anuj Mahajan · Vibhav Gogate · Parag Singla -
2015 Poster: Lifted Symmetry Detection and Breaking for MAP Inference »
Timothy Kopp · Parag Singla · Henry Kautz -
2014 Poster: New Rules for Domain Independent Lifted MAP Inference »
Happy Mittal · Prasoon Goyal · Vibhav Gogate · Parag Singla -
2014 Poster: Scaling-up Importance Sampling for Markov Logic Networks »
Deepak Venugopal · Vibhav Gogate -
2012 Poster: On Lifting the Gibbs Sampling Algorithm »
Deepak Venugopal · Vibhav Gogate -
2010 Poster: Learning Efficient Markov Networks »
Vibhav Gogate · William A Webb · Pedro Domingos -
2010 Poster: Lifted Inference Seen from the Other Side : The Tractable Features »
Abhay Jha · Vibhav Gogate · Alexandra Meliou · Dan Suciu