Variational Algorithms for Marginal MAP
  Marginal MAP problems are notoriously difficult tasks for graphical models.
We derive a general variational framework for solving marginal MAP problems, in
which we apply analogues of the Bethe, tree-reweighted, and mean field
approximations. We then derive a "mixed" message passing algorithm and a
convergent alternative using CCCP to solve the BP-type approximations.
Theoretically, we give conditions under which the decoded solution is a global
or local optimum, and obtain novel upper bounds on solutions. Experimentally we
demonstrate that our algorithms outperform related approaches. We also show
that EM and variational EM comprise a special case of our framework.
