Pairwise decomposition for combinatorial optimization in graphical models
Aurélie Favier and Simon de Givry
We propose a new additive decomposition of probability tables that preserves equivalence of the joint distribution while reducing the size of the potentials, without adding extra variables. We reformulate the problem of finding the Most Probable Explanation (MPE) in belief networks into a Weighted Constraint Satisfaction Problem (WCSP). Our pairwise decomposition allows to replace a cost function with smaller-arity cost functions. The resulting pairwise decomposed WCSP is then easier to be solved using state-of-the-art WCSP techniques. Although testing pairwise decomposition is equivalent to testing pairwise independence in the original belief network, we show an efficient way to do it in the WCSP framework, and to enforce it, even in the presence of hard constraints (i.e. determinism). Furthermore, after enforcing pairwise decomposition, we can still infer valuable information from the resulting nonbinary cost functions by projecting&subtracting them on binary cost functions. We observed very large improvements using pairwise decomposition and project&subtract compared to the current state-of-the-art solvers on two difficult benchmarks used in the UAI'08 MPE Evaluation contest.