AND/OR Search for Marginal MAP

Radu Marinescu, Rina Dechter, Alexander Ihler
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:106-115, 2014.

Abstract

Marginal MAP problems are known to be very difficult tasks for graphical models and are so far solved exactly by systematic search guided by a join-tree upper bound. In this paper, we develop new AND/OR branch and bound algorithms for marginal MAP that use heuristics extracted from weighted mini-buckets enhanced with message- passing updates. We demonstrate the effective- ness of the resulting search algorithms against previous join-tree based approaches, which we also extend to accommodate high induced width models, through extensive empirical evaluations. Our results show not only orders-of-magnitude improvements over the state-of-the-art, but also the ability to solve problem instances well be- yond the reach of previous approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-marinescu14a, title = {{AND}/{OR} Search for Marginal {MAP}}, author = {Marinescu, Radu and Dechter, Rina and Ihler, Alexander}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {106--115}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/marinescu14a/marinescu14a.pdf}, url = {https://proceedings.mlr.press/r12/marinescu14a.html}, abstract = {Marginal MAP problems are known to be very difficult tasks for graphical models and are so far solved exactly by systematic search guided by a join-tree upper bound. In this paper, we develop new AND/OR branch and bound algorithms for marginal MAP that use heuristics extracted from weighted mini-buckets enhanced with message- passing updates. We demonstrate the effective- ness of the resulting search algorithms against previous join-tree based approaches, which we also extend to accommodate high induced width models, through extensive empirical evaluations. Our results show not only orders-of-magnitude improvements over the state-of-the-art, but also the ability to solve problem instances well be- yond the reach of previous approaches.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T AND/OR Search for Marginal MAP %A Radu Marinescu %A Rina Dechter %A Alexander Ihler %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-marinescu14a %I PMLR %P 106--115 %U https://proceedings.mlr.press/r12/marinescu14a.html %V R12 %X Marginal MAP problems are known to be very difficult tasks for graphical models and are so far solved exactly by systematic search guided by a join-tree upper bound. In this paper, we develop new AND/OR branch and bound algorithms for marginal MAP that use heuristics extracted from weighted mini-buckets enhanced with message- passing updates. We demonstrate the effective- ness of the resulting search algorithms against previous join-tree based approaches, which we also extend to accommodate high induced width models, through extensive empirical evaluations. Our results show not only orders-of-magnitude improvements over the state-of-the-art, but also the ability to solve problem instances well be- yond the reach of previous approaches. %Z Reissued by PMLR on 04 October 2026.
APA
Marinescu, R., Dechter, R. & Ihler, A.. (2014). AND/OR Search for Marginal MAP. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:106-115 Available from https://proceedings.mlr.press/r12/marinescu14a.html. Reissued by PMLR on 04 October 2026.

Related Material