Variational Algorithms for Marginal MAP

Qiang Liu, Alexander T. Ihler

Abstract

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.
BibTeX
@inproceedings{liu2011variational,
  author = {Qiang Liu and Alexander T. Ihler},
  title = {{Variational Algorithms for Marginal MAP}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=ojvMO2T4jUx},
}

Loading related content...

Figure