Solving Marginal MAP Problems with NP Oracles and Parity Constraints
  Arising from many applications at the intersection of decision making and
machine learning, Marginal Maximum A Posteriori (Marginal MAP) Problems unify
the two main classes of inference, namely maximization (optimization) and
marginal inference (counting), and are believed to have higher complexity than
both of them. We propose XOR_MMAP, a novel approach to solve the Marginal MAP
Problem, which represents the intractable counting subproblem with queries to
NP oracles, subject to additional parity constraints. XOR_MMAP provides a
constant factor approximation to the Marginal MAP Problem, by encoding it as a
single optimization in polynomial size of the original problem. We evaluate our
approach in several machine learning and decision making applications, and show
that our approach outperforms several state-of-the-art Marginal MAP solvers.
