Proceedings

Pairwise Decomposition for Combinatorial Optimization in Graphical Models

Aurélie Favier, Simon de Givry, Andrés Legarra, Thomas Schiex

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2126-2131.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-355

Abstract

We propose a new additive decomposition of probability tables that preserves equivalence of the joint distribution while reducing the size of potentials, without extra variables. We formulate the Most Probable Explanation (MPE) problem in belief networks as a Weighted Constraint Satisfaction Problem (WCSP). Our pairwise decomposition allows to replace a cost function with smaller-arity functions. The resulting pairwise decomposed WCSP is then easier to solve using state-of-the-art WCSP techniques. Although testing pairwise decomposition is equivalent to testing pairwise independence in the original belief network, we show how to efficiently test and enforce it, even in the presence of hard constraints. Furthermore, we infer additional information from the resulting nonbinary cost functions by projecting and subtracting them on binary functions. We observed huge improvements by preprocessing with pairwise decomposition and project&subtract compared to the current state-of-the-art solvers on two difficult sets of benchmark.

Aurélie Favier, Simon de Givry, Andrés Legarra, and Thomas Schiex. 2011. Pairwise Decomposition for Combinatorial Optimization in Graphical Models. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2126–2131. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-355
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards