Efficiently Searching for Frustrated Cycles in MAP Inference

David Sontag, Do Kook Choe, Yitao Li
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:794-803, 2012.

Abstract

Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-sontag12a, title = {Efficiently Searching for Frustrated Cycles in {MAP} Inference}, author = {Sontag, David and Choe, Do Kook and Li, Yitao}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {794--803}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/sontag12a/sontag12a.pdf}, url = {https://proceedings.mlr.press/r10/sontag12a.html}, abstract = {Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficiently Searching for Frustrated Cycles in MAP Inference %A David Sontag %A Do Kook Choe %A Yitao Li %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-sontag12a %I PMLR %P 794--803 %U https://proceedings.mlr.press/r10/sontag12a.html %V R10 %X Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision. %Z Reissued by PMLR on 04 October 2026.
APA
Sontag, D., Choe, D.K. & Li, Y.. (2012). Efficiently Searching for Frustrated Cycles in MAP Inference. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:794-803 Available from https://proceedings.mlr.press/r10/sontag12a.html. Reissued by PMLR on 04 October 2026.

Related Material