Lifted Marginal MAP Inference
  Lifted inference reduces the complexity of inference in relational
probabilistic models by identifying groups of constants (or atoms) which behave
symmetric to each other. A number of techniques have been proposed in the
literature for lifting marginal as well MAP inference. We present the first
application of lifting rules for marginal-MAP (MMAP), an important inference
problem in models having latent (random) variables. Our main contribution is
two fold: (1) we define a new equivalence class of (logical) variables, called
Single Occurrence for MAX (SOM), and show that solution lies at extreme with
respect to the SOM variables, i.e., predicate groundings differing only in the
instantiation of the SOM variables take the same truth value (2) we define a
sub-class {\em SOM-R} (SOM Reduce) and exploit properties of extreme
assignments to show that MMAP inference can be performed by reducing the domain
of SOM-R variables to a single constant.We refer to our lifting technique as
the {\em SOM-R} rule for lifted MMAP. Combined with existing rules such as
decomposer and binomial, this results in a powerful framework for lifted MMAP.
Experiments on three benchmark domains show significant gains in both time and
memory compared to ground inference as well as lifted approaches not using
SOM-R.
