Title: New Rules for Domain Independent Lifted MAP Inference

Speaker: Happy Mittal

Abstract: We present two new rules for lifting MAP inference in a large class of Markov Logic Network (MLN) models. We identify equivalence classes of variables which have at most a single variable appearing in any given formula and are referred to as single occurrence equivalence classes. Our first inference rule states that MAP inference over the original theory can be equivalently formulated over a reduced theory where single occurrence classes have been reduced to unary sized domains. Our approach is domain independent when every equivalence class in the theory is single occurrence. The MAP solution in such cases is found at extreme i.e. when every grounding of a predicate takes the same (true/false) value. Our second inference rule states that any formula which becomes tautology at extreme assignments can be removed from the theory for the purpose of MAP inference when the remaining theory is single occurrence. This includes many difficult to lift formulas such as symmetry and transitivity. Experiments over benchmark MLNs validate that our approach results in superior performance and highly scalable solutions compared to the state of the art.