Timezone: »
Lifted inference algorithms for probabilistic firstorder logic frameworks such as Markov logic networks (MLNs) have received significant attention in recent years. These algorithms use so called lifting rules to identify symmetries in the firstorder representation and reduce the inference problem over a large probabilistic model to an inference problem over a much smaller model. In this paper, we present two new lifting rules, which enable fast MAP inference in a large class of MLNs. Our first rule uses the concept of single occurrence equivalence class of logical variables, which we define in the paper. The rule states that the MAP assignment over an MLN can be recovered from a much smaller MLN, in which each logical variable in each single occurrence equivalence class is replaced by a constant (i.e., an object in the domain of the variable). Our second rule states that we can safely remove a subset of formulas from the MLN if all equivalence classes of variables in the remaining MLN are single occurrence and all formulas in the subset are tautology (i.e., evaluate to true) at extremes (i.e., assignments with identical truth value for groundings of a predicate). We prove that our two new rules are sound and demonstrate via a detailed experimental evaluation that our approach is superior in terms of scalability and MAP solution quality to the state of the art approaches.
Author Information
Happy Mittal (IIT Delhi)
Prasoon Goyal (New York University)
Vibhav Gogate (UT Dallas)
Parag Singla (Indian Institute of Technology Delhi)
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 SearchBased 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: An Integer Polynomial Programming Based Framework for Lifted MAP Inference »
Somdeb Sarkhel · Deepak Venugopal · Parag Singla · Vibhav Gogate 
2014 Poster: Scalingup 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