mplp2
Efficiently Searching for Frustrated Cycles in MAP Inference. 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
Keywords for this software
References in zbMATH (referenced in 6 articles )
Showing results 1 to 6 of 6.
Sorted by year (- Ouali, Abdelkader; Allouche, David; de Givry, Simon; Loudni, Samir; Lebbah, Yahia; Loukil, Lakhdar; Boizumault, Patrice: Variable neighborhood search for graphical model energy minimization (2020)
- Bach, Stephen H.; Broecheler, Matthias; Huang, Bert; Getoor, Lise: Hinge-loss Markov random fields and probabilistic soft logic (2017)
- Flerova, Natalia; Marinescu, Radu; Dechter, Rina: Weighted heuristic anytime search: new schemes for optimization over graphical models (2017)
- Furtlehner, Cyril; Decelle, Aurélien: Cycle-based cluster variational method for direct and inverse inference (2016)
- Hurley, Barry; O’Sullivan, Barry; Allouche, David; Katsirelos, George; Schiex, Thomas; Zytnicki, Matthias; de Givry, Simon: Multi-language evaluation of exact solvers in graphical model discrete optimization (2016)
- Allouche, David; André, Isabelle; Barbe, Sophie; Davies, Jessica; de Givry, Simon; Katsirelos, George; O’Sullivan, Barry; Prestwich, Steve; Schiex, Thomas; Traoré, Seydou: Computational protein design as an optimization problem (2014)