Efficiently Searching for Frustrated Cycles in MAP Inference

• DOI: 10.48550/arxiv.1210.4902
• Publication Date: 2012-01-01
• Authors: David Sontag; Do Kook Choe; Yitao Li
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Statistics - Machine Learning; Computer Science - Data Structures and Algorithms; 0202 electrical engineering, electronic engineering, information engineering; Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML); 02 engineering and technology; Machine Learning (cs.LG)

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