Pairwise decomposition for combinatorial optimization in graphical models - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Pairwise decomposition for combinatorial optimization in graphical models

Résumé

We propose a new additive decomposition of probabilitytables 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 nonbinarycost functions by projecting&subtracting them on binary functions. We observed huge improvements by preprocessing with pairwise decomposition andproject&subtract compared to the current state-ofthe-art solvers on two difficult sets of benchmark.
Fichier principal
Vignette du fichier
IJCAI 2011 - TS_1 (219.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02744861 , version 1 (03-06-2020)

Identifiants

  • HAL Id : hal-02744861 , version 1
  • PRODINRA : 164653

Citer

Aurélie Favier, Simon de Givry, Andres Legarra, Thomas Schiex. Pairwise decomposition for combinatorial optimization in graphical models. IJCAI 2011 - Twenty-second International Joint Conference on Artificial Intelligence, Labo/service de l'auteur, Ville service, Pays service., 2011, Barcelona, Spain. ⟨hal-02744861⟩
23 Consultations
17 Téléchargements

Partager

Gmail Facebook X LinkedIn More