Carte de compilation des diagrammes de décision ordonnés a valeurs réelles

Hélène Fargier (1, 2) , Pierre Marquis (3) , Alexandre Niveau (4) , Nicolas Schmidt (1, 3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CNRS - Centre National de la Recherche Scientifique
3 CRIL - Centre de Recherche en Informatique de Lens
4 Equipe MAD - Laboratoire GREYC - UMR6072

Valued decision diagrams (VDDs) are data structures that represent functions mapping variable-value assignments to non-negative real numbers. They prove useful to compile cost functions, utility functions, or probability distributions. While the complexity of some queries (notably optimization) and transformations (notably conditioning) on VDD languages has been known for some time, there remain many significant queries and transformations, such as the various kinds of cuts, marginalizations, and combinations, the complexity of which has not been identified so far. This paper contributes to filling this gap and completing previous results about the time and space efficiency of VDD languages, thus leading to a knowledge compilation map for real-valued functions. Our results show that many tasks that are hard on valued CSPs are actually tractable on VDDs.

Les diagrammes de décision valués (VDDs) sont des structures de données représentant des fonctions à valeurs réelles positives. Ces structures sont utiles pour la compilation de fonctions de coût ou d'utilité, ou encore de distributions de probabilités. Si la complexité de certaines requêtes (comme l'optimisation) et de certaines transformations (comme le conditionnement) sur de tels langages est bien connue, il reste de nombreuses requêtes et transformations importantes dont la complexité n'a pas encore été identifiée ; figurent parmi elles différents types de coupes, marginalisations, ou encore combinaisons. En établissant une carte de compilation des diagrammes de décision ordonnés à valeurs réelles, cet article contribue à combler ce manque. Nos résultats montrent que beaucoup de tâches difficiles à partir de CSPs valués sont traitables à partir de VDDs.

Domaines: Intelligence artificielle [cs.AI]; Complexité [cs.CC]; Algorithme et structure de données [cs.DS]

Hélène Fargier, Pierre Marquis, Alexandre Niveau, Nicolas Schmidt. Carte de compilation des diagrammes de décision ordonnés a valeurs réelles. 8èmes Journées de l'Intelligence Artificielle Fondamentale (JIAF 2014), Jun 2014, Angers, France. pp.1--11. ⟨hal-01095577⟩