Skip to Main content Skip to Navigation
Conference papers

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

Résumé : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inrae.fr/hal-02744726
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Wednesday, June 3, 2020 - 7:48:37 AM
Last modification on : Tuesday, July 20, 2021 - 5:08:03 PM
Long-term archiving on: : Friday, December 4, 2020 - 8:52:05 PM

File

JFPC 2011 - TC_1
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

20

Files downloads

22