Variational Algorithms for Marginal MAP

Qiang Liu, Alexander T. Ihler
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:510-519, 2011.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-liu11a, title = {Variational Algorithms for Marginal {MAP}}, author = {Liu, Qiang and Ihler, Alexander T.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {510--519}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/liu11a/liu11a.pdf}, url = {https://proceedings.mlr.press/r9/liu11a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Variational Algorithms for Marginal MAP %A Qiang Liu %A Alexander T. Ihler %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-liu11a %I PMLR %P 510--519 %U https://proceedings.mlr.press/r9/liu11a.html %V R9 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Liu, Q. & Ihler, A.T.. (2011). Variational Algorithms for Marginal MAP. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:510-519 Available from https://proceedings.mlr.press/r9/liu11a.html. Reissued by PMLR on 04 October 2026.

Related Material