Lifted MAP Inference for Markov Logic Networks

In this paper, we present a new approach for lifted MAP inference in Markov Logic Networks (MLNs). Our approach is based on the following key result that we prove in the paper: if an MLN has no shared terms then MAP inference over it can be reduced to MAP inference over a Markov network having the following properties: (i) the number of random variables in the Markov net-work is equal to the number of first-order atoms in the MLN; and (ii) the domain size of each variable in the Markov network is equal to the number of groundings of the corresponding first-order atom. We show that inference over this Markov network is exponentially more efficient than ground inference, namely inference over the Markov network obtained by grounding all first-order atoms in the MLN. We improve this result further by showing that if non-shared MLNs con-tain no self joins, namely every atom appears at most once in each of its formulas, then all vari-ables in the corresponding Markov network need only be bi-valued. Our approach is quite general and can be eas-ily applied to an arbitrary MLN by simply grounding all of its shared terms. The key fea-ture of our approach is that because we reduce lifted inference to propositional inference, we can use any propositional MAP inference al-gorithm for performing lifted MAP inference. Within our approach, we experimented with two propositional MAP inference algorithms: Gurobi and MaxWalkSAT. Our experiments on several benchmark MLNs clearly demonstrate our ap-proach is superior to ground MAP inference in terms of scalability and solution quality