Décomposition par paire pour l'optimisation combinatoire dans les modèles graphiques - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2011

Décomposition par paire pour l'optimisation combinatoire dans les modèles graphiques

Abstract

Nous proposons une nouvelle décomposition additive des tables de probabilités qui préserve l'équivalence de la distribution jointe permettant de réduire la taille des potentiels, sans ajout de nouvelles variables. Nousformulons le problème de Most Probable Explanation(MPE) dans les réseaux probabilistes comme un problème de satisfaction de contraintes pondérées (Weighted Constraint Satisfaction Problem WCSP). Notre décomposition par paire permet de remplacer une fonction de coûts par des fonctions d'arités plus petites. Le WCSP résultant de cette décomposition est plus facile à résoudre par les techniques de l'état de l'art des WCSP. Même si tester la décomposition par paire est équivalent à tester l'indépendance de paire du réseau de croyances original, nous montrons comment le tester efficacement et l'appliquer, même avec des contraintes dures. De plus, nous inférons une information supplémentaire à partir des fonctions de coûts non binaires réultantes par projection&soustraction dans leurs fonctions binaires. Nous observons d'importantes améliorations grâce au pré-traitement avec la décompostion de paire et la projection&soustraction comparée aux sol-veurs actuels de l'état de l'art sur deux ensembles deproblèmes difficiles.
Fichier principal
Vignette du fichier
JFPC 2011 - TC_1 (287.11 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : hal-02744726 , version 1
  • PRODINRA : 164657

Cite

Aurélie Favier, Simon de Givry, Andres Legarra, Thomas Schiex. Décomposition par paire pour l'optimisation combinatoire dans les modèles graphiques. JFPC 2011 - Septièmes Journées Francophones de Programmation par Contraintes, Labo/service de l'auteur, Ville service, Pays service., 2011, Lyon, France. ⟨hal-02744726⟩
17 View
7 Download

Share

Gmail Facebook X LinkedIn More