TY - GEN

T1 - Efficiently searching for frustrated cycles in MAP inference

AU - Sontag, David

AU - Choe, Do Kook

AU - Li, Yitao

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84886049973&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84886049973&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84886049973

SN - 9780974903989

T3 - Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012

SP - 795

EP - 804

BT - Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012

T2 - 28th Conference on Uncertainty in Artificial Intelligence, UAI 2012

Y2 - 15 August 2012 through 17 August 2012

ER -