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.