Représentations graphiques, indépendance
Les modèles graphiques sont des outils de représentation de connaissances en présence d'incertitude, de plus en plus utilisés dans différents domaines de recherche et en particulier en Intelligence Artificielle. Le succès de ces modèles est fortement lié à leur caractère intuitif et à leur capacité à représenter et manipuler les relations d'indépendance qui sont importantes pour une gestion efficace des informations incertaines.
L'un des objectifs de nos travaux de recherche est de développer des réseaux qualitatifs permettant la gestion des relations d'indépendance, la représentation de l'incertitude ordinale et la manipulation naturelle des variables non-binaires.
Pour cela, nous avons analysé la notion d'indépendance entre variables dans le cadre d'une représentation qualitative de l'incertitude. On distingue deux types d'indépendance :
- une indépendance de nature décompositionnelle qui est vérifiée lorsque l'on arrive à décomposer sans perte d'informations la relation préférentielle définie globalement sur tout le référentiel en plusieurs relations définies localement et reliant des sous-ensembles de variables.
- une indépendance de nature causale où deux variables (ou ensembles de variables) sont dites indépendantes lorsque apprendre qu'une variable est devenue vraie ne modifie pas notre croyance sur l'autre variable.
Après l'étude des relations d'indépendance, nous avons proposé un algorithme ``anytime'' de propagation dans les réseaux causaux possibilistes. Un réseau causal possibiliste est un graphe acyclique orienté où les noeuds représentent les variables (par exemple les symptômes et les maladies) et les arcs codent les liens causaux qui existent entre les variables. L'incertitude est représentée par les possibilités conditionnelles de chaque noeud dans le contexte de ses parents. Nous avons établi le passage entre les réseaux causaux possibilistes et les bases de croyances possibilistes. Ces correspondances sont importantes dans une perspective de fusion d'informations hétérogènes.
Par ailleurs, nous avons montré qu'on peut, pour tester la validité d'inférences dans un grand nombre de formalismes logiques, utiliser des techniques efficaces de réduction similaires à celles qui ont permis le succès des réseaux causaux. Nous avons pour cela défini le graphe représentant les interactions entre les différentes variables logiques, et les opérations de réduction pour entre autre la logique classique, certaines logiques modales ou conditionnelles, un fragment de la logique possibiliste. Nous avons aussi montré comment ces résultats peuvent être appliqués pour tester, indirectement, la validité d'inférences dans une logique non monotone particulière : la circonscription.
Enfin, nous avons étudié en profondeur, du double point de vue de l'expressivité et du calcul, diverses notions d'indépendance en logique propositionnelle.
Un premier type d'indépendance, dite ``formule-variable'', s'attache à déterminer les variables propositionnelles concernées par une formule, et le type d'influence (positive et/ou négative) que cette formule a sur ces variables. Un second type d'indépendance (dite ``conditionnelle'') est l'équivalent purement propositionnel de la notion d'indépendance décompositionnelle citée plus haut. Un troisième type, appelé définissabilité, est une dépendance forte de nature informationnelle (une variable x dépend d'une autre, y, si y est utile pour définir x). Nous avons montré en quoi ces différentes relations de dépendance ont un intérêt pour le diagnostic et la mise à jour de croyances.
contacts: S. Benferhat, J. Lang, J. Mengin.
quelques publications récentes
- N. Ben Amor, S. Benferhat, D. Dubois, H. Geffner, H. Prade. Independence in qualitative uncertainty frameworks. Proc.7th Int.Conf.on Principles of Knowledge Representation and Reasoning (KR 2000), Breckenridge, Morgan Kaufmann, 235-246, 2000.
- S. Benferhat, D. Dubois, S. Kaci, H. Prade. Graphical readings of possibilisitc logic bases. Dans: Proc.of the 17th Conference Uncertainty in Artificial Intelligence (UAI01) , Seattle, Aug. 2 - 5, Morgan Kaufmann Publishers, 24-31, 2001 .
- J. Lang et P. Marquis. Complexity results for independence and definability in propositional logic. Proceeedings of KR'98, Morgan Kaufmann, 356-367, 1998.
- N. Wilson et J. Mengin. Embedding logics in the local computation framework, Journal of Applied Non-Classical Logics, Vol. 11, n° 3-4, p. 239-267, 2001.
