  The marginal maximum a posteriori probability (MAP) estimation problem, which
calculates the mode of the marginal posterior distribution of a subset of
variables with the remaining variables marginalized, is an important inference
problem in many models, such as those with hidden variables or uncertain
parameters. Unfortunately, marginal MAP can be NP-hard even on trees, and has
attracted less attention in the literature compared to the joint MAP
(maximization) and marginalization problems. We derive a general dual
representation for marginal MAP that naturally integrates the marginalization
and maximization operations into a joint variational optimization problem,
making it possible to easily extend most or all variational-based algorithms to
marginal MAP. In particular, we derive a set of "mixed-product" message passing
algorithms for marginal MAP, whose form is a hybrid of max-product, sum-product
and a novel "argmax-product" message updates. We also derive a class of
convergent algorithms based on proximal point methods, including one that
transforms the marginal MAP problem into a sequence of standard marginalization
problems. Theoretically, we provide guarantees under which our algorithms give
globally or locally optimal solutions, and provide novel upper bounds on the
optimal objectives. Empirically, we demonstrate that our algorithms
significantly outperform the existing approaches, including a state-of-the-art
algorithm based on local search methods.
