Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.inrae.fr/hal-02744726
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 07:48:37
Dernière modification le : lundi 21 septembre 2020 - 19:32:01

Fichier

JFPC 2011 - TC_1
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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⟩

Partager

Métriques

Consultations de la notice

6

Téléchargements de fichiers

10