//img.uscri.be/pth/2a9109d8eb55a29eb1c4ee3b9ffec446eb9bb45a
Cette publication ne fait pas partie de la bibliothèque YouScribe
Elle est disponible uniquement à l'achat (la librairie de YouScribe)
Achetez pour : 20,99 € Lire un extrait

Lecture en ligne (cet ouvrage ne se télécharge pas)

REVISION, COGNITION ET INTERACTION (n°11-12)

342 pages
Tout changement dans le temps (évolution, mouvement transformation...) exige, pour la viabilité-même de ce qui change, qu’une certaine cohérence soit maintenue. Ceci implique des mécanismes de mise à jour, de réexamen, de révision. Ce numéro met en perspectives un certain nombre de travaux qui, de près ou de loin ont trait à cette notion de révision : ces recherches se répartissent en deux ensembles, les unes relevant de l’intelligence artificielle, les autres des sciences humaines.
Voir plus Voir moins

RÉVISION, COGNITION ET INTERACTION

Directeur de publication Alain Trognon

Rédacteur en chef Michel Musiol

Comité de rédaction
Nadine Bertoni Christian Brassac Daniel Brixhe Pascale Marro Christine Sorsana Edy Veneziano

Comité scientifique
Nicolas Balacheff, Grenoble Janine Beaudichon, Paris Josie Bernicot, Paris Alain Blanchet, Paris Marcel Bromberg, Paris Pina Boggi-Cavallo, Salerne Jean Caelen, Grenoble Luigia Camaioni, Rome Claude Chabrol, Paris Patrick Charaudeau, Paris Gina Conti-Ramsden, Manchester Alain Coulon, Paris Marcelo Dascal, Tel Aviv Nicole Dubois, Nancy Loekiie Elbers, Utrecht Jean Erceau, Toulouse Joseph Glick, New-York Patricia Greefield, Los Angeles Eric Grillo, Paris Marie-Christine Hardy-Baylé, Paris Francis Jacques, Paris Catherine Kerbrat-Orecchioni, Lyon Katia Kostulski, Paris Pierre Livet, Aix-en-Provence David Middleton, Manchester Jacques Moeschler, Genève Bernard Pachoud, Amiens Herman Parret, Louvain Frederico Pereira, Lisbonne Anne-Nelly Perret-Clermont, Neufchâtel Clotilde Pontecorvo, Rome François Récanati, Paris Laureen Resnick, Pittsburgh Eddy Roulet, Genève Roger Saljo, Linkoping Anne Sinclair, Genève Daniel Vanderveken, Trois-Rivières Denis Vernant, Grenoble Jean Vivier, Caen Daniel Widlocher, Paris

Mise en page
Pascal Guérin

Sous la direction de Pierre Marquis & Christian Brassac

Révision, cognition et interaction

L'Harmattan 5-7, rue de l'École Polytechnique 75005 Paris FRANCE

L'Harmattan Hongrie Hargita u. 3 1026 Budapest HONGRIE

L'Harmattan Italia Via Bava, 37 10214 Torino ITALIE

SOMMAIRE
RÉVISION, COGNITION ET INTERACTION
PIERRE MARQUIS & CHRISTIAN BRASSAC, Révision, cognition et interaction 5 PIERRE MARQUIS, La révision en intelligence artificielle: pa radigmes BRIGITTE BESSANT, Révision versus Mise à Jour deux .11 39

NATHALIE CHAIGNAUD & FRANÇOIS LÉVY, Planification et révision 61 SYLVIE CaSTE-MARQUIS, Une application de la révision en reconnaissance automatique de la parole 101 LAURENCE CHOLVY, Fusion de croyances et révision PIERRE LIVET, La coordination des discours: révision. 123 information et ....157

CHRISTIAN BRAS SAC, L'engendrement du sens en conversation: une constructibilité par défaut ..187 ALAIN TROGNON, Les groupes favorisent-ils la révision des jugen'lents individuels? 205 MICHAEL BAKER, Les attitudes et leurs révisions dans le dialogue: le cas de la résolution coopérative de problèmes 229

ARTICLES HORS. THÈMES
CHRISTINE SORSANA, Contextes et "formatage" des situations de comnlunication. A propos de l'ouvrage de Bernicot et al. (1998). De l'usage des gestes et des mots chez l'enfant. Paris: A rmand CoIin 269 MICHÈLE GUIDETTI, Production de messages d'acquiescement et de refus chez le jeune enfant: étude développementale 293 LUC VANDROMME, L'adaptation à un interlocuteur déficient chez l'enfant de 7 à 10 ans: étude comparative des modalités d' interaction avec un partenaire autistique ou un partenaire triso11l 21 ique .........319

(Ç)L'Harmattan, 2001 ISBN: 2-7475-1107-3

Révision. cognition et interaction

Pierre Marquis*, Christian Brassac**
* CRIL / Université d'Artois rue de l'Université - S.P. 16 62307 Lens Cedex marquis@cri1.univ-artois.fr ** LPI-GRC / Université Nancy2 B.P. 33-97, 54014 Nancy Cedex brassac@clsh.univ-nancy2.fr

Psychologie de l ' interaction, N° Il & 12, 2000, 5-10

Pierre Marquis, Christian Brassac

1. La réflexion qui se développe en sciences cognitives laisse de plus en plus place à des approches qui font la part belle à l'indétermination, à l'indécision ou au caractère non figé des phénomènes étudiés. L'expert n'est pas aussi expert que cela, il doit accepter de remettre en cause ses connaissances, il doit concéder à d'autres experts la pertinence d'un regard légèrement autre. Le raisonnement est rarement linéaire, de la cause au conséquent; la preuve n'a pas un statut immuable. La perception n'est pas seulement unidirectionnelle, du monde à l'organe percevant. L'interprétation n'est pas un mécanisme de découverte d'un sens qui lui préexiste. Les états intentionnels ne sont pas fixes par intervalle de temps. La planification n'est pas une stratégie sourde aux événements qui surviennent au cours de la mise en œuvre. On ne peut plus s'en tenir à une conception fixiste de la cognition. Plus exactement, on s'accorde à envisager une radicale continuité entre la production cognitive (que ce soit la perception, le raisonnement, l'interprétation, la planification d'actions, etc.) et l'altération progressive de l'état de choses dans lequel elle se produit. Il devient évident que l'analyse de l'appareillage cognitif en fonctionnement doit appréhender ce dernier en tant qu'il est situé dans un environnement radicalement évolutif. Toute analyse doit alors être conçue à travers une dynamique de changement dialectique entre monde et cognition. Il est aisé de trouver derrière ces affirmations successives de nombreux auteurs qui ont pour point commun de ne pas (ou ne plus) concevoir la cognition comme un traitement de l'information préexistant dans un monde extérieur (Bruner, Maturana et Varela, Stewart, pour n'en citer que quelques-uns). Cela dit, adopter une conception dynamicointeractionniste (car évolutive et dépendante d'un couplage appareil cognitif-monde) des mécanismes étudiés au sein des sciences de la cognition mène directement à appréhender un aspect central de toute dynamique: le changement. Qui dit déroulement dans le temps d'un phénomène, dit, sauf à 6

Révision, cognition et interaction

observer une fonction constante avec le temps ce qui n'est pas vraiment une caractéristique du domaine du vivant, évolution, mouvement, correction, modification, transformation. Et la viabilité de l'entité en variation repose sur un maintien de la cohérence qui implique des mécanismes de mise à jour, de réexamen ou autre révision. De fait, la problématique de la révision se développe-t-elle autant dans des domaines tels la logique (en s'inscrivant dans l'imposant ensemble des logiques non monotones), l'intelligence artificielle (en particulier, la planification, la reconnaissance des formes) et les bases de données, que dans des champs d'étude plus ancrés en sciences humaines et sociales (philosophie, psychologie sociale, didactique par exemple). C'est cet état de fait qui est à l'origine du travail dont ce texte constitue l'introduction. Il s'agit de confronter, de mettre en perspectives un certain nombre de travaux 1 qui, d'une façon ou d'une autre, ont trait à cette notion de révision. Le rapport que les recherches que nous avons rassemblées ici entretiennent avec ce mode de réévaluation des cognitions au cours de leur devenir est très différencié. Elles se répartissent en deux ensembles, les unes relevant de l'intelligence artificielle, les autres des sciences humaines.

2. Dans le premier de ces ensembles, une partie des recherches prennent la révision pour objet d'étude spécifique.
Ainsi, Pierre Marquis met l'accent sur les difficultés que pose la modélisation de la révision et rappelle les choix qu'un point de vue purement logique sur la révision laisse ouverts. Il indique également comment des informations extra-logiques peuvent être utilisées pour conduire à des révisions plausibles selon les deux grandes approches de la révision proposées jusqu'ici. Brigitte Bessant présente les principales différences

1 Les articles composant ce numéro étaient tous écrits et acceptés pour publication en fin d'année 1998. 7

Pierre Marquis, Christian Brassac

existant entre révision (stricto sensu) et mise à jour de connaissances. Réviser ses croyances, c'est intégrer des informations plus précises ou plus plausibles sur le monde réel (statique) dans la représentation dont on dispose de façon à ce que celle-ci colle au plus près au monde modélisé. Mettre à jour ses connaissances, c'est modifier sa représentation du monde pour prendre en compte l'évolution du dit monde (évolution résultant, par exemple, de l'exécution d'une action ou simplement du temps qui passe).

Pour les autres recherches de cet ensemble la prise en compte de la notion de révision fait partie de l'aspect méthodologique de la recherche.
Nathalie Chaignaud et François Lévy montrent en quoi la notion de révision peut éclairer la problématique de la planification. Ils expliquent d'abord dans quelle mesure la prise en compte d'une action peut être considérée comme une forme de révision. Ils comparent ensuite « l'approche classique» de la planification dans laquelle génération de plan et contrôle de l'exécution du plan sont deux phases séparées avec une approche plus réaliste dans laquelle planifier, c'est réviser des plans partiels. Nathalie Chaignaud et François Lévy mettent en évidence le caractère cognitivement plausible de cette approche de la planification.

Sylvie Caste-Marquis présente une application de la notion de révision à la reconnaissance automatique de la parole continue suivant une approche à base de connaissances. Dans un tel cadre, des hypothèses diverses (de sons, de frontières entre mots, de mots...) doivent être émises aux différents niveaux de la reconnaissance (en particulier, au niveau du décodage acoustico-phonétique et au niveau lexical). Lorsqu'aucune explication cohérente des hypothèses émises à un niveau de reconnaissance ne peut être fournie par le niveau supérieur, une révision est nécessaire. Celle-ci peut remettre en cause l'ensemble des hypothèses émises avant révision. L'apport d'une telle étape de révision à la phase de décodage acoustico-

8

Révision, cognition et interaction

phonétique tivement.

est analysé qualitativement

et quantita-

Laurence Cholvy décrit plusieurs formalismes logiques pour la fusion de croyances et sa relation à la révision. Le problème abordé traite de l'inférence à partir de plusieurs bases de données contenant des informations contradictoires. Plusieurs politiques de fusion sont présentées: approche suspicieuse, approche confiante, prise en compte des thèmes des informations. Laurence Cholvy analyse également les liens existant entre fusion et révision; elle montre comment la prise en compte des thèmes des informations permet d'étendre la notion de révision classiquement définie.

3. Dans l'autre ensemble de recherches, la notion de révision est nécessairement moins formalisée sans pour autant qu'elle prenne des acceptions très différentes de celles présentées dans la première partie. Deux des contributions mobilisent l'idée de révision pour étudier précisément les mécanismes survenant dans les dialogues entre sujets humains.
Pierre Livet propose d'envisager la communication humaine comme une suite dialoguée d'énoncés interprétables soit comme des informations soit comme des révisions de croyances. Ceci l'amène à revisiter la catégorisation bien connue des actes illocutoires de Searle et Vanderveken et à proposer un « carré dialogique des actes de langage».
Colinéairement à cette perspective, Christian Brassac s'intéresse à la construction du sens en conversation. Il s'agit de défendre une position radicalement dialogique de l'interlocution en montrant comment une logique des défauts peut permettre la modélisation de l'engendrement des cognitions conjointement élaborées par les interactan ts.

Les deux autres contributeurs s'intéressent moins précisément à la notion d'actions réalisées au moyen de la
9

Pierre

Marquis, Christian Brassac

profération d'énoncés en contexte tout en considérant le dialogue comme lieu central d'actualisation de phénomènes intersubjectifs.
En psychologue social, Alain Trognon se place résolument au niveau du groupe. En envisageant les processus de décision, il pose la question de la révision des croyances en situation groupale ; il le fait en explorant très complètement la littérature relative à ce sujet et en interrogeant la dialectique individu-groupe.

Pour sa part, c'est en adoptant une attitude de didacticien que Michael Baker aborde la question des révisions des attitudes d'élèves en situation de résolution de problème. C'est la négociation de la solution, étayée sur la production de cognitions au long de l'interlocution, qui fait l'objet d'une analyse fondée sur un modèle de l'activité sociale des interactants.

4. On se sera rendu compte, au terme du parcours, du différentiel marquant l'ensemble des prises en compte de la notion qui nous intéresse tous ici, celle de révision. Gageons qu'il n'aura pas nui à la mise en perspectives que les auteurs de cette introduction ont voulu ouverte et constructive. Cette rencontre entre disciplines certes connexes mais cependant étrangères (psychologie sociale et cognitive de l'interaction, d'une part, et logique et intelligence artificielle, d'autre part) trace une convergence d'intérêts pour (et d'usages d') un même concept. La livraison de la revue" Psychologie de l'interaction" qui accueille cet enselnble d'articles a pour objectif de montrer, encore une fois et sur un thème précis, que le travail interdisciplinaire est non seulement souhaitable mais aussi producteur d'idées nouvelles en sciences cognitives pour peu qu'on laisse réellement les auteurs se rencontrer et interagir.

10

La révision en intelligence artificielle: deux paradigmes

Pierre Marquis
CRIL / Université d'Artois rue de l'université - S.P. 16 62307 Lens Cedex
marquis @ cri!. uni v -artois .fr

Résumé. Cet article est une introduction à la problématique de la révision des bases de connaissances propositionnelles en intelligence artificielle. Il est centré essentiellement sur les problèmes de modélisation que pose la révision. Après une introduction dans laquelle nous situons la révision dans le cadre du raisonnement en intelligence artificielle, mettons en évidence la difficulté du problème et les choix qu'un point de vue purement logique sur la révision laisse ouverts, nous présentons successivement les deux grandes approches proposées jusqu'ici: l'approche fondée sur la cohérence et l'approche fondationnelle. Dans les deux cas, nous indiquons comment des informations extra-logiques peuvent être utilisées pour effectuer des choix conduisant à des bases révisées plausibles. Enfin, nous comparons brièvement les deux approches.

Psychologie de l'interaction, N° 11&12,2000, 11-37

Pierre Marquis

1. Introduction Réviser ses connaissances et ses croyances!, c'est étymologiquement les regarder à nouveau. Un processus de révision apparaît dès lors que l'apport de nouvelles informations (ou, plus généralement, un facteur déclenchant quelconque comme le temps qui passe) nous invite à remettre en cause nos connaissances, i.e. les modifier de façon à ce qu'elles soient autant que possible en phase avec une certaine réalité perçue. En particulier, lorsque nos croyances sont contredites par l'évidence, il est nécessaire de les remettre en question. La notion de révision peut difficilement être séparée de la notion d'intelligence chez l'être humain. Réviser ses connaissances et ses croyances est une activité fréquente pour l'homme, même s'il n'en a pas toujours conscience. Cette faculté lui est indispensable pour tenter de mieux appréhender le monde dans lequel il vit (s'en forger une image mentale), raisonner sur lui et donc agir en conséquence. Par exemple, si je suppose qu'il pleut, que lorsqu'il pleut, la chaussée est mouillée et que j'observe que la chaussée n'est pas mouillée, je vais légitimement remettre en question ma supposition. Un autre exemple est celui de l'expérience d'Einstein: Einstein a montré que la mécanique de Newton devait être remise en cause (du moins en tant que théorie « universelle») car elle ne permet pas d'expliquer certains phénomènes observés (intuitivement, la lumière ne se « déplace» pas en ligne droite). Ainsi, la problématique de la révision prend place aussi bien dans le raisonnement «de bon sens» portant sur le monde dans lequel nous vivons, que dans les raisonnements sophistiqués sur des abstractions de ce dernier et utilisés dans telle ou telle discipline scientifique. A ce titre, elle joue un rôle important en philosophie des Sciences en ce qui concerne les processus de découverte scientifique.
! Bien que distinctes, nous ne séparerons pas ces deux notions dans cet article. 12

La révision en intelligence artificielle: deux paradigmes

La notion de révision n'a d'existence que parce que nos connaissances et nos croyances ne décrivent pas fidèlement et complètement un univers idéal, stable et mathématisé. Nos connaissances sont souvent imparfaites: incomplètes, imprécises et entachées d'erreur. Leur statut est donc hypothétique ~ainsi, rien ne permet de prouver (au sens de la théorie de la preuve) que la mécanique d'Einstein modélise fidèlement notre Univers. De ce fait, l'activité de raisonnement chez l'homme ne se résume pas à l'inférence déductive telle qu'elle est décrite par les logiciens. En revanche, elle peut être vue comme un processus consistant à effectuer des déductions (licites) sur la base d'hypothèses2 pour produire en fin de compte des inférences qui ne sont pas valides (du moins du point de vue de la logique mathématique), mais non monotones et révisables. De ce point de vue, la révision trouve sa place dans un cadre de modélisation du raisonnement assez vaste (et qui permet de rendre compte de nombreuses formes de raisonnement en intelligence artificielle, comme le raisonnement par défaut, l'abduction, la généralisation inductive et de nombreuses autres formes d'inférence non monotone). En effet, il ne suffit pas de produire des hypothèses pertinentes pour compléter ses connaissances et aller plus loin dans le raisonnement, il faut également pouvoir remettre en cause ces hypothèses lorsqu'elles deviennent insuffisamment justifiées ou contredites par l'évidence. Pour Gardenfors et Makinson (1988), révision et inférence non monotone sont l'endroit et l'envers d'une même pièce. Dire qu'une inférence est non monotone, c'est exactement admettre que sa conclusion est révisable. En dépit du fait que la révision constitue un problème épistémique central, il n'existe pas une approche unique, universelle et consensuelle de la révision. L'ensemble des approches proposées vise à définir un modèle de remise en cause des connaissances d'un agent suite à l'apport de nouvelles informations, plus fiables, plus précises ou plus
2 Piaget parle de raisonnement hypothético-déductif.

13

Pierre Marquis

pertinentes, qui, typiquement, viennent contredire tout ou partie des connaissances de l'agent3. Un tel modèle doit indiquer comment rétablir la cohérence en supprimant certaines d'entre elles et en en ajoutant d'autres. Ainsi, la révision est-elle indissociablement liée aux deux autres opérateurs utilisés pour traduire la dynamique des états de croyance d'un agent rationnel: la contraction et l'expansion. L'expansion d'un état de croyance avec une information est l'état de croyance obtenu en ajoutant cette information à l'état de croyance initial, même si l'état résultant est incohérent. La contraction d'un état de croyance avec une information est l'état de croyance obtenu en supprimant cette information de l'état de croyance original. Réviser un état de croyance avec une information nouvelle, c'est d'abord contracter cet état de croyance de manière à supprimer toute connaissance qui contredit l'information nouvelle à incorporer, puis étendre l'état résultant avec cette information nouvelle. Contrairement à l'expansion qui possède une définition naturelle immédiate, la contraction et la révision n'en possèdent pas. Toutefois, comme les connaissances sont précieuses et difficiles à acquérir, on préférera en général en supprimer un minimum (juste ce qu'il faut pour lever la contradiction). On voit ici apparaître un principe d'inertie (on ne se prive de connaissances que si l'on est contraint à le faire), qui semble tout à fait raisonnable. Ce qui rend la chose plutôt délicate est qu'il n'y a pas une seule façon de mettre ce principe en œuvre. Considérons à nouveau l'exemple évoqué plus haut. Soit un agent rationnel disposant des connaissances suivantes:

.

. .

il pleut ~ s'il pleut, la chaussée est mouillée ~ s'il pleut, mon jardin est mouillé.

(1) (2) (3)

3 Typiquement seulement. Il peut être nécessaire de réviser ses connaissances dans le cas où aucune contradiction n'apparaît. 14

La révision en intelligence artificielle: deux paradigmes

Sur la base de ces connaissances, l'agent peut légitimement conclure que la chaussée est mouillée et que son jardin l'est aussi. Survient alors une nouvelle information (par exemple, l'agent regarde par la fenêtre) :

. la chaussée n'est pas mouillée.

(4)

Une révision s'impose puisque, à la lueur de cette nouvelle information, les connaissances de l'agent sont contradictoires. Il faut donc remettre en cause certaines d'entre elles. Une des difficultés est qu'il y a plusieurs façons de faire. Par exemple:

.

. .

supprimer toute connaissance de l'agent. Cela n'est pas nécessaire et viole le principe d'inertie: (3) ne participe nullement à la contradiction, il n'y a pas de raison a priori de supprimer cette connaissance. Supprimer (1) et (2) conjointement est également plus que nécessaire; supprimer (1) ; supprimer (2).

En l'absence d'informations complémentaires (de nature extra-logique) sur quelle connaissance préserver (critères de préférence), ces deux dernières possibilités correspondent à des choix aussi rationnels l'un que l'autre. Une quatrième possibilité serait de rejeter (4) ; bien entendu, cela ne doit pas être systématique (ce serait la politique de l'autruche !). La plupart des approches existantes accordent à la connaissance par laquelle la révision survient un statut prioritaire: elle doit nécessairement faire partie des connaissances de l'agent après révision. Une autre difficulté réside dans le traitement des faits dérivés (i.e. des conséquences logiques des connaissances) : sur l'exemple précédent, si l'on décide de supprimer ( 1) pour restaurer la cohérence, doit-on aussi supprimer le fait dérivé: . mon jardin est mouillé? (5)
15

Pierre Marquis

En effet, en l'absence de (1), (5) n'est plus inférable. Il peut donc sembler normal de l'éliminer. Deux cas sont alors possibles: mon jardin est mouillé devient contingent (undetermined) dans la base révisée, autrement dit l'agent ne sait pas si cette proposition est vraie ou fausse après révision, ou alors mon jardin est mouillé devient fausse (ce qui est le cas si la seule cause possible de mon jardin est mouillé est il pleut et l'on suppose que les conséquences ne survivent pas à leurs causes, i.e. on a attendu suffisamment longtemps pour que l'eau s'évapore). Seul donc le cas où mon jardin est mouillé reste vrai après révision semble irrationnel. Cependant, l'ensemble des connaissances de (1)+(2)+(3) est logiquement équivalent à la conjonction des trois faits4 :

. . .

il pleut; mon jardin est mouillé; la chaussée est mouillée.

(1) (5) (6)

Sur la base de ces trois faits (1)+(5)+(6), la prise en compte de (4) conduit bien entendu encore à une contradiction. Pour la lever, il suffit de supprimer (6) de l'ensemble des connaissances disponibles. Supprimer (5) est maintenant peu naturel et superflu; pire, il ne faut pas supprimer (5) si l'on souhaite satisfaire au principe d'inertie. Ainsi, la présentation des connaissances (1)+(5)+(6) conduit à percevoir les trois faits comme indépendants: en conséquence, il est raisonnable que supprimer (6) n'ait aucune influence sur (1) et (5). Tout se passe comme si l'humidité du jardin n'était pas due à la pluie (le jardin peut être couvert) mais, par exemple, à un arrosage automatique. Comme cet exemple le montre, la seule donnée de connaissances de nature logique (dans un cadre classique) ne suffit pas à régler le problème des faits dérivés puisque deux ensembles de connaissances logiquement équivalents devront naturellement être révisés différemment. En
4 On suppose ici que les conditionnelles sont représentées par des implications matérielles en logique classique. 16

La révision en intelligence artificielle: deux paradigmes

particulier, il n'existe pas de connecteurs en logique classique qui traduisent fidèlement la notion de causalité: tel fait est produit par tel ou tel autre(s) faites), et en l'absence de cause, il n'y a pas d'effets sauf si ceux-ci persistent, i.e. survivent à leur(s) causees). Pour pallier ce problème, plusieurs voies ont été proposées. L'une d'entre elles consiste à considérer un cadre sémantique plus fin que le cadre classique et accorder une certaine importance à la syntaxe: deux connaissances logiquement équivalentes ne seront pas toujours équivalentes dans un tel cadre. Une autre voie consiste à considérer, en plus des connaissances logiques, des connaissances extra-logiques permettant de représenter des préférences entre faits à préserver. Une troisième voie consiste à munir les connaissances d'une structure extra-logique permettant de coder une notion de causalité entre croyances. Dans la mesure où elles visent à un même objectif, il n'est pas surprenant que ces voies se recouvrent partiellement. Cet article a pour thème central la révision en intelligence artificielle. Dans ce cadre, l'objectif poursuivi est la simulation d'un processus de révision rationnel sur un ordinateur. Cet objectif pose donc des problèmes de modélisation de nature épistémique et logique (Qu'est-ce qu'un processus de révision rationnel ?) mais aussi des problèmes liés à la mise en œuvre d'un tel processus, de nature algorithmique (Comment simuler la révision sur un ordinateur? Quelle est la complexité algorithmique sousjacente ?). Comme c'est souvent le cas dans cette discipline, il est nécessaire d'établir un compromis (intuitivement, les modèles offrant un pouvoir d'expression élevé sont souvent ceux qui « coûtent cher» à mettre en œuvre). Nous nous intéresserons principalement aux problèmes de modélisation et focaliserons notre attention sur deux approches dont les justifications sont bien distinctes: il s'agit de l'approche fondée sur la cohérence introduite par Alchourron, Gardenfors et Makinson (1985) et de l'approche fondationnelle introduite par Doyle (1979). Elles sont assurément parmi les mieux connues à l'heure actuelle.

17

Pierre

Marquis

Après une présentation des fondements de chacune des deux approches, nous montrerons en quoi elles diffèrent et en quoi elles se ressemblent.

2. L'approche fondée sur la cohérence L'approche fondée sur la cohérence, initiée par Alchourron, Gardenfors et Makinson (1985) et étendue par Katsuno et Mendelzon (1991), est un cadre de modélisation de la révision qui est centré sur les deux principes essentiels suivants:

. .

cohérence:

l'ensemble

des croyances de l'agent doit

toujours être cohérent;

inertie: si une contradiction survient, il est nécessaire de restaurer la cohérence des croyances de l'agent en supprimant un minimum de croyances.

Dans le cadre de la logique propositionnelle, l'ensemble de croyances d'un agent ayant une capacité de déduction non limitée peut être considéré comme la fermeture déductive (i.e. l'ensemble des conséquences logiques de) d'un ensemble de formules. Dans ce cas, une croyance est représentée par une formule (à l'équivalence logique près). De manière équivalente, croyances et ensembles de croyances peuvent être représentés par des ensembles d'interprétations (au sens logique), i.e. les interprétations qui sont des modèles des formules ou des ensembles de formules considérés.

Les bases de l'approche Dans l'approche fondée sur la cohérence, une opération de révision est modélisée formellement par une application 0, qui à tout couple formé d'un ensemble de croyances K et d'une croyance m à intégrer, associe un ensemble de croyances noté K 0 m. Bien évidemment, toute application 0 ne peut être considérée comme une fonction de
18

La révision en intelligence artificielle: deux paradigmes

révision rationnelle. La démarche est axiomatique: Alchourron, Gardenfors et Makinson (1985) et Katsuno et Mendelzon (1991) proposent des ensembles de contraintes (ou postulats) que toute fonction de révision raisonnable (rationnelle) doit satisfaire. Nous adoptons ici la présentation de Katsuno et Mendelzon (1991) qui s'appuie sur des bases de croyances. Un ensemble de formules Best appelé base de croyances lorsque sa fermeture déductive

K = B* représente effectivement l'ensemble de croyances K considéré. La notion de base de croyances est ainsi plus générale que la notion d'ensemble de croyances dans la mesure où tout ensemble de croyances est une base de croyances, mais la réciproque n'est pas vraie. Bien évidemment, un même ensemble de croyances peut être représenté par plusieurs bases de croyances distinctes dans le cas général. Si le résultat de la révision de B par m est noté B 0 m, l'ensemble de croyances résultant de la révision de K = B * par fi est (B 0 m)*. Les postulats de rationalité présentés dans (Katsuno et Mendelzon, 1991) sont les sui vants :

. . . . .

B0m

~m (R 1) Si B u {m} est cohérent alors Born ==B u {m} (R2) Si m est cohérent alors Born est cohérent (R3)
Si BI ==B2 et ml ==m2 alors BI 0 ml ==B2 0 m2 (B 0 ml) u {m2} I=B 0 (ml /\ m2) (R4) (R5)

. Si (B 0 ml) u {m2} est cohérent alors B 0 (ml /\ m2) 1= (B 0 ml) u {m2}

(R6)

Les postulats (RI) ... (R6) sont appelés postulats AGM pour la révision. Ils visent à transcrire formellement les exigences de cohérence et d'inertie mentionnées plus haut (cf. Alchourron, Gardenfors et Makinson, 1985, pour de plus amples explications). Katsuno et Mendelzon (1991) proposent deux postulats (R?) et (R8) qui constituent une alternative moins restrictive que (R6) dans le sens où tout opérateur de révision 0 qui satisfait (R 1) ... (R6) satisfait aussi (R 1) ... 19

Pierre Marquis

(R5) (R7) (R8) mais la réciproque n'est pas vraie:

. .

Si B 0 ml I=m2 et B 0 m2 I=ml alors
B 0 ml == B 0 m2 (B 0 ml) u (B 0 m2)
1= B 0 (ml v m2)

(R7) (R8) la révision les

On appellera postulats KM pour postulats (RI) ... (R5) (R7) (R8). (R6)} et KM

Les deux ensembles de postulats AGM

= {(RI)

... (R5) (R7) (R8)} ne caractérisent pas

= {(R1)

...

chacun une fonction de révision unique mais des ensembles de fonctions de révision rationnelles. On appellera celles qui satisfont AGM des fonctions de révision AGM et, plus généralement, celles qui satisfont KM des fonctions de révision KM. Comme nous l'avons évoqué précédemment, révision et contraction sont des notions étroitement liées. En effet, à chaque opérateur de révision 0, on peut associer un opérateur de contraction - d'ensembles de croyances via ['identité de Harper (Harper, 1976) : K - m = (K 0 -wm) (\ K. Intuitivement, la croyance m est supprimée de K en révisant K avec la négation de m et en ne conservant dans l'ensemble de croyances résultant que les croyances qui appartiennent à K. Réciproquement, tout opérateur de contraction - d'ensembles de croyances peut être associé à un opérateur de réviK + m est l'expansion de K par m définie par K + m = K u {ml). Ainsi, réviser K avec m consiste à supprimer de K toute information qui contredit m, puis à ajouter m. Liés à cette correspondance entre les deux notions, Alchourron, Gardenfors et Makinson (1985) ont proposé des postulats de rationalité pour les fonctions de contraction d'ensembles de croyances. Ces postulats calquent au plus près les postulats (RI) ... (R6) donnés plus haut; en particulier, Alchourron, Gardenfors et Makinson (1985) montrent qu'à partir d'un opérateur de révision AGM, l'identité de Harper permet de dériver un opérateur de contraction rationnel (au sens AGM) et, réciproquement, à partir d'un opérateur de contraction
20
sion par ['identité de Levi (1977) : K 0 m

= (K - -wm)+ m (où

La révision en intelligence artificielle: deux paradigmes

AGM, l'identité de Levi permet de dériver un opérateur de révision AGM. Clairement, les postulats AGM et KM expriment seulement les propriétés qu'une fonction de révision rationnelle doit satisfaire mais ils ne donnent aucune indication directe sur la façon de construire une telle fonction (ce qui est pour le moins fâcheux dans la perspective de l'intelligence artificielle). En outre, AGM et KM ne portent que sur les liens logiques qui existent entre connaissances. De ce point de vue, toutes les connaissances sont sur un pied d'égalité. En particulier, dans l'approche fondée sur la cohérence, une connaissance est supprimée seulement si elle doit l'être pour restaurer la cohérence: dans la mesure où aucune notion de causalité n'est prise en compte, les faits dérivés survivent toujours à leur cause. Alchourron, Gardenfors et Makinson justifient ce choix par les résultats d'études conduites en Psychologie et montrant que, dans la très grande majorité des cas, l'être humain n'a aucune conscience de l'origine de ses croyances. Pour pallier les deux problèmes évoqués dans l'introduction (choix des croyances à supprimer pour restaurer la cohérence et traitement des faits dérivés) et caractériser les opérateurs de révision rationnels d'un point de vue constructiviste, plusieurs solutions existent. En effet, les informations extra-logiques nécessaires pour effectuer un choix judicieux entre plusieurs ensembles de croyances candidats (tous aussi raisonnables l'un que l'autre d'un point de vue purement logique) peuvent être représentées de différentes façons: relation de préférence entre bases de croyances (ou entre formules) ou entre modèles. Ces deux voies permettent de caractériser les opérateurs de révision AGM par des théorèmes de représentation.

Sous-bases préférées et enracinement épistémique Soit B une base de croyances. On note B J, ..,m l'ensemble des sous-ensembles K de B qui sont maximaux pour l'inclusion ensembliste et cohérents avec m. Les 21

Pierre Marquis

éléments K de B

~ -wm sont

appelés sous-bases maximales

cohérentes (implicitement, avec m) de B.
Choisir quelles croyances supprimer pour restaurer la cohérence lorsque m est ajouté revient à choisir une ou plusieurs sous-bases maximales cohérentes K de B* et considérer l'intersection de leurs fermetures déductives. Formellement, on peut définir une fonction S de sélection

qui à chaque élément K de B *

~ -wmassocie un booléen

vrai

oufaux suivant que l'élément considéré est retenu ou pas. Il est alors possible de définir l'ensemble de croyances révisé K 0 m = (B 0 m)* par l'intersection des sous-bases K ainsi sélectionnées:
(B 0 m)* = n (KE 8(B*J,-wm))(K U {m})*.

On parle alors de partial meet revision. Dans Ie cas où la fonction de sélection choisie est identiquement vraie, on parle de full meet revision. Dans le cas où cette fonction ne retient qu'un seul élément de B* t -wm, on parle de révision maxichoix. Ces deux cas particuliers ne sont pas intéressants en général car ils conduisent à des ensembles de croyances dégénérés (en effet, (B 0 m)* = {m} * dans le cas de la full meet revision et (B 0 m)* est complet, i.e. toute formule ou sa négation apparaît dans (B 0 m)* dans le cas de la révision maxichoix). Pour définir une fonction de sélection S, il peut être commode d'introduire une relation ~ entre sous-bases maximales cohérentes; intuitivement, KI S K2 représente l'information extra-logique «K2 est préférée à KI». Il est alors possible de définir une fonction de sélection S ne retenant que les sous-bases au moins aussi préférées que toutes les sous-bases maximales cohérentes de B* ~ -wm. Une telle fonction de sélection est dite relationnelle. Un cas particulièrement intéressant est obtenu lorsque ~ est, en outre, transitive; on dit alors que S est transitivement relationnelle. Cette façon de définir des opérateurs de révision permet de faire le lien entre les fonctions de révision rationnelles (celles qui satisfont les postulats AGM) et celles

22

La révision en intelligence artificielle: deux paradigmes

pour lesquelles il existe des algorithmes permettant (nonobstant les problèmes de complexité algorithmique) de mettre en œuvre la révision. En effet, Gardenfors (1988) prouve le théorème de représentation suivant: 0 est une fonction de révision AGM si et seulement si il existe une fonction de sélection S transitivement relationnelle telle que pour tout K = B* et tout m, on a : Kom = (B 0 m)* = n (KE 8(B*.tlm)) (l( U {m})*.

Illustrons maintenant ces différentes notions en considérant à nouveau l'exemple donné dans l'introduction. L'ensemble des croyances dont nous disposons peut être formellement représenté par la fermeture déductive K de l'ensemble des formules B suivant:
{il_pleut, il_pleut il_pleut jardin_mouillé, chaussée_mouillée}

==> ==>

où il_pleut, jardin_mouillé et chaussée_mouillée sont des symboles propositionnels représentant respectivement les propositions il pleut, mon jardin est mouillé et la chaussée est mouillée. La révision est provoquée par la prise en (qui est compte du fait m =def -chaussée_mouillée contradictoire avec K). Quatre fonctions de révision AGM

à quatre fonctions de 01' 02' 03' 04' associées sélection transitivement relationnelles, peuvent s'appliquer pour produire quatre ensembles de croyances distincts:
différentes

. . . .

K 01 m = {il_pleut, jardin_mouillé, -chaussée_mouillée} * ; K 02 m = {il_pleut, -jardin_mouillé, -chaussée_mouillée} * ; K 03 m = {-il_pleut, jardin_mouillé, -chaussée_mouillée} * ; K 04 m = {-il_pleut, -jardin_mouillé, -chaussée_mouillée}*.

23

Pierre Marquis

En effet, K est aussi la fermeture déductive de la base {il_pleut, jardin_mouillé, chaussée_mouillée} qui admet:
{il_pleut Ç:> chaussée_mouillée, jardin_mouillé Ç:> chaussée_mouillée}

comme sous-base maximale cohérente avec chaussée_mouillée. Ainsi, K 04 m est caractérisé par toute fonction de sélection associée à une relation transitive S entre sous-bases maximales cohérentes telle que:
{il_pleut Ç:> chaussée_mouillée,

jardin_mouillé

<=}

chaussée_mouillée}

domine (i.e. est préférée à) toute sous-base maximale cohérente. Une voie possible pour caractériser les sous-bases préférées consiste à utiliser la notion d'enracinement épistémique (Gardenfors, 1988). Intuitivement, les formules les plus enracinées épistémiquement doivent être préservées en priorité. L'enracinement épistémique sur un ensemble de croyances K est représenté mathématiquement par une relation entre formules qui dépend de K. Il exprime une information extra-logique sur les croyances de la base. Formellement, étant donné un ensemble de croyances K, on considère les relations SK sur les formules x, y, z qui vérifient les propriétés suivantes:

. . . . x SKy pour tout y
si x
1=

si X SK y et y SK z alors x SK Z

y alors x SK y

X SK (x /\ y) ou Y SK (x /\ y)

(EE 1) (EE2) (EE3) (EE4 ) (EE5)

si K est cohérent, x é K si et seulement si
si X ~K Y pour tout x alors y est valide.

.

24

La révision en intelligence

artificielle:

deux paradigmes

Ces postulats traduisent les différentes propriétés qu'une relation de préférence entre formules dans un cadre de révision doit satisfaire. Par exemple, le postulat de dominance (EE2) stipule que les formules les plus spécifiques (celles qui sont logiquement les plus faibles) doivent être préservées en priorité; en effet, si y est plus spécifique que x et si x ou y doit être supprimé pour restaurer la cohérence, mieux vaut supprimer x puisque supprimer y nécessite de supprimer x aussi. Gardenfors et Makinson (1988) montrent comment on

peut définir un ensemble de croyances K - m (où - est un
opérateur de contraction) à partir d'une relation ~K et, réciproquement, comment on peut définir une relation ~K d'enracinement épistémique à partir d'un ensemble de croyances K - m :

.

.

X ~K

Y si et seulement

si x E K - (x /\ y) ou (x /\ y) est

valide, (C~K) ; X E K - Y si et seulement si x E K et (y <K (y V x) ou y est valide), (C-) ;

où <K est la relation entre formules définie par x <K y si et seulement si x ~K y et non(y ~K x). L'intérêt de ces deux transformations réside dans le fait que la rationalité (au sens AGM) est préservée. Ainsi, Gardenfors et Makinson (1988) donnent les théorèmes de représentation suivant:

. .

si ~K satisfait (EEl)

... (EE5) alors la fonction

de

contraction définie par (C-) satisfait les postulats AGM de rationalité pour la contraction; si une fonction de contraction - est rationnelle au sens AGM alors la relation ~K définie par (C~K) satisfait (EEl) ... (EE5).

Comme on l'a vu précédemment, il est possible de définir un opérateur de révision AGM à partir d'un opérateur de contraction AGM grâce à l'identité de Levi. En 25

Pierre Marquis

conséquence, tout opérateur de révision AGM peut être caractérisé par une relation d'enracinement épistémique. Pour illustrer ces notions, considérons à nouveau l'exemple précédent. Les quatre ensembles de croyances donnés précédemment peuv~nt être dérivés sur la base d'enracinements épistémiques sur K, grâce à la caractérisation (C-). Par exemple, l'ensemble de croyances K 04 m peut être obtenu en accordant plus d'importance à la formule
(il_pleut =} chaussée_mouillée)

(resp. jardin_mouillé plutôt qu'à la formule

=}

chaussée_mouillée),

(il_pleut v chaussée_mouillée) (resp. jardin_mouillé v chaussée_mouillée). Formellement, on doit avoir:

(il_pleut v chaussée_mouillée) <K (il_pleut =} chaussée_mouillée) et Uardin_mouillé v chaussée_mouillée) <K Uardin_mouillé =} chaussée_mouillée) . Il est ainsi possible de produire l'ensemble de croyances qui doit résulter de la révision de K par m lorsque il pleut est la cause de la chaussée est mouillée et il pleut est la cause de le jardin est mouillé. Le lecteur aura toutefois noté que la notion de causalité n'est pas formellement représentée dans le cadre AGM.

Ordre sur les modèles
Une seconde voie permettant de caractériser les opérateurs de révision rationnels a été développée par Katsuno et Mendelzon (1991). Elle consiste à associer à toute base de croyances B une relation <p(B) = ~B sur 26

La révision en intelligence artificielle: deux paradigmes

l'ensemble W des interprétations I sur le langage propositionnel considéré. Soit M(B) = {I E W I I ~ B} l'ensemble des modèles de B (qui coïncide bien entendu avec M(B *) = M(K)). L'application f considérée doit être fidèle, i.e. :

. .

min(W, ~B) = M(B) pour tout B cohérent,
~BI

= ~B2 chaque

fois que BI ==B2.

Katsuno et Mendelzon (1991) prouvent les théorèmes de représentation suivants: un opérateur de révision 0 est AGM (resp. KM) si et seulement s'il existe une application

fidèle telle que chaque base de croyances B est associée à une relation de pré-ordre total (resp. partiel) <t>(B) ~B et =
<t>

M(B 0 m) = min(M(m), ~B)' Les modèles de B 0 m sont ainsi les modèles de m qui sont minimaux pour ~B (intuitivement, ceux qui correspondent à une modification minimale de B vue à l'équivalence logique près). Ainsi, K 04 m = (B 04 m)* peut être caractérisé par une relation d'ordre total ~B sur W telle que: {-il_pleut, -jardin_mouillé, -chaussée_mouillée} <K {-il_pleut, jardin_mouillé, -chaussée_mouillée} <K {il_pleut, -jardin_mouillé, -chaussée_mouillée} <K {il_pleut, jardin_mouillé, -chaussée_mouillée}. Le modèle {-il_pleut, -jardin_mouillé, -chaussée_mouillée} de m est ainsi préféré aux autres modèles possibles pour produire K 04 m.

3. L'approche fondationnelle L'approche fondationnelle de la révision a été initiée par Doyle (1979, 1992) et reprise par plusieurs chercheurs dont Nebel (1989, 1990, 1991). Dans l'approche fondationnelle, les croyances sont munies d'une structure extra-logique. Intuitivement, certaines connaissances sont justifiées par d'autres (par exemple, la chaussée est mouillée
27

Pierre

Marquis

est justifiée par il pleut), elles-mêmes justifiées par d'autres... L'existence de connaissances de base autojustifiées permet d'éviter la régression à l'infini. Lorsqu'une contradiction se produit suite à l'apport d'information, au moins une des connaissances de base doit être retirée de l'ensemble des connaissances de l'agent. Un tel retrait peut naturellement conduire à l'apparition de croyances non justifiées qui doivent être retirées également. Les bases de l'approche L'approche fondationnelle admet différentes présentations. Primitivement, elle a été décrite d'un point de vue opératoire: comment, en pratique, réaliser la révision de croyances? Comment supprimer les faits dérivés qui ne sont plus supportés par aucune justification? Divers types de systèmes de maintien de raisonnement (appelés originellement systèmes de maintien de vérité, bien que ce nom soit mal choisi) ont été introduits à cet usage. Citons seulement Doyle (1979), de Kleer (1986) et McDermott (1991). Dans les systèmes de maintien de vérité à base de justifications, les croyances sont organisées sous forme de réseau de dépendance de données, liant les propositions à leurs justifications. Dans certains systèmes, des justifications non monotones peuvent être prises en compte: une proposition peut être justifiée par la présence mais aussi par l'absence de certaines propositions dans l'ensemble des croyances de l'agent. Dans les systèmes de maintien de raisonnement à base d'hypothèses, à chaque croyance est associé l'ensemble des croyances de base (ou hypothèses) ayant permis de la dériver. Nous renvoyons le lecteur à Martins (1990) pour une bibliographie détaillée de tels systèmes. Afin de rendre possible une comparaison avec l'approche fondée sur la cohérence, nous préférerons ici présenter l'approche fondationnelle d'un point de vue théorique comme un cadre de révision de bases de croyances. Contrairement à l'approche fondée sur la 28

La révision en intelligence artificielle: deux paradigmes

cohérence, la forme syntaxique des croyances va jouer un rôle dans l'approche fondationnelle. En effet, seules les croyances de base de l'agent seront représentées. Ainsi, bien qu'elle soit utile pour donner une vue intuitive de l'approche fondationnelle et qu'elle soit pertinente pour les systèmes de maintien de raisonnement, la notion de justification ne joue logiquement aucun rôle dans le cadre de l'approche fondationnelle : le seul point clé dans cette approche est de discriminer les croyances de base de l'agent de ses croyances dérivées, i.e. celles qui peuvent être déduites des croyances de base (Nebel, 1991). Pour définir les opérateurs de révision fondationnels, nous utilisons la présentation de deI Val (1994). Contrairement à l'approche fondée sur la cohérence, cette présentation est directement constructive (elle adresse la question «comment construire un opérateur de révision fondationnel ?») et pas axiomatique (elle ne décrit pas ce qu'est un opérateur de révision fondationnel par les propriétés qu'il doit satisfaire). Dans cette présentation, on considère une application L qui, à toute base de croyances B, associe un ensemble de formules L(B) contenant les croyances de base associées L. L(B) est tel que:

. . .

L(B 1) = L(B2) chaque fois que BI ==B2 .

L(B) * = {B} * ; L(B) est un ensemble fini.

'

Cette application permet d'associer à toute base de croyances une présentation syntaxique de celle-ci de telle sorte qu'aucune information ne soit perdue et que deux bases équivalentes se voient associer la même présentation syntaxique. L'introduction de cette application permet de séparer l'ensemble des croyances de l'agent (interprétées à l'équivalence logique près, donc sans accorder d'importance à la syntaxe) de la forme syntaxique de ces croyances (qui, elle, est significative dans l'approche fondationnelle). Un opérateur de révision fondationnel 0 est une application qui, à un ensemble de croyances K = B* associe 29

Pierre Marquis

un ensemble de croyances K 0 m défini par: K 0m

=n

(1(

E L (B i *

....,

(K U {m}) *.

Ainsi, contrairement à l'approche fondée sur la cohérence dans laquelle les sous-bases maximales cohérentes K considérées sont certains sous-ensembles de B * parmi ceux qui sont cohérents avec m, dans l'approche
fondationnelle, les sous-bases maximales cohérentes K considérées sont les sous-ensembles de L(B) qui sont cohérents avec m. Considérons à nouveau l'exemple précédent. Soit la base: B

= {il_pleut,

jardin_mouillé,

chaussée_mouillée} l'ensemble des

dont la fermeture déductive caractérise croyances d'un agent rationnel. Soit: L(B)

= {il_pleut,
il_pleut ~ jardin_mouillé, il_pleut ~ chaussée_mouillée},
des croyances de base associées à B. I,(B) admet

l'ensemble
-chaussée

deux sous-bases
mouillée:

maximales

cohérentes

avec m

= def

{il_pleut, il_pleut ~ jardin_mouillé} et {il_pleut =} jardin_mouillé, il pleut =} chaussée_mouillée} .

A partir de la première de ces sous-bases complétée par m, il est possible d'inférer il_pleut et jardin_mouillé. A partir de la seconde, il est possible de conclure ""'il_pleut. En fin de compte, ni il_pleut ni jardin_mouillé ni leurs négations ne sont des conséquences logiques de l'ensemble de croyances résultant K 0 m. On voit apparaître sur cet exemple une difficulté

30

La révision en intelligence

artificielle:

deux paradigmes

inhérente à l'approche fondationnelle telle que nous l'avons définie: la révision ne peut pas être itérée simplement. En effet, l'approche n'impose aucune contrainte sur ce que doit être l'ensemble des croyances de base de la base révisée. Le choix le plus simple n'est assurément pas le bon: l'ensemble de croyances K 0 m est la fermeture déductive de la base de croyances B' réduite à une seule formule: V
(K

E (L(B)
1-

-.m» (K U {m}).

Si cette base B' est considérée comme contenant seulement des croyances de base (i.e. B' = L(B')) et si elle doit être à son tour révisée et qu'une contradiction émerge, toute l'information contenue dans B' devra être supprimée puisque la formule ci-dessus devra être rejetée. Différentes solutions à ce problème ont été proposées (cf Nebel, 1990). Sous-bases préférées et pertinence épistémique

Si l'on souhaite privilégier une ou plusieurs sous-bases de L(B), plusieurs voies sont encore possibles. Par exemple, il est possible d'utiliser une relation de préférence entre sous-bases (Nebel, 1990). Cela peut se traduire formellement de différentes façons, par exemple par l'introduction d'une fonction de sélection S comme au paragraphe 2.2. Une autre voie consiste à intégrer la sélection des sous-bases maximales cohérentes préférées directement dans la définition de L(B) .t -.m. Soit ~ une relation de pré-ordre
entre bases de croyances telle que ~ étend c : si KI c K2alors KI ~ K2. On note L(B) JJ, -.m l'ensemble des sous-ensembles K de L(B) maximaux pour ~ et cohérents avec m. Bien entendu, on a (L(B) .u. -.m) ç (L(B) -.m). Il suffit alors d'utiliser la définition:

.t

K 0 m

=n

(K E (L(B) jj, -.m»

(K U {m})

*

en lieu et place de la définition précédente, pour définir un
31

Pierre Marquis

opérateur de révision fondationnel o. On dit que 0 est l'opérateur de révision fondationnel induit par la relation ~. Clairement, cette nouvelle définition généralise la définition précédente (il suffit de choisir ~ = ç pour la retrouver comme un cas particulier). Grâce à une telle relation de préférence, il va être possible d'accorder plus d'importance à certaines sous-bases de L(B) qu'à d'autres. En particulier, sur l'exemple précédent, si l'on admet que:
{il_pleut, il_pleut ==> jardin_mouillé} < {il_pleut jardin_mouillé, il_pleut ==>chaussée_mouillée}, ==>

où KI < K2est défini par KI ~ K2 et non (KI ~ K2)' il va être possible de conclure -'il_pleut à partir de la seconde sousbase (celle qui est préférée) complétée par m. Notons ici qu'il ne sera pas possible de conclure -'jardin_mouillé à partir de la présentation syntaxique L(B) donnée ci-avant quelle que soit la relation de préférence choisie. En revanche, si l'on considère la présentation syntaxique:) : L(B)

= {il_pleut,
il pleut

jardin_mouillé ==> chaussée_mouillée}
et une relation de préférence ~ entre sous-bases de L(B) telle que:
{il_pleut, il_pleut ==> jardin_mouillé} < {il_pleut, jardin_mouillé => chaussée_mouillée} chaussée_mouillée}

==>

jardin_mouillé,

< {il pleut => jardin_mouillé,
,

jardin_mouillé

==>

il sera possible de conclure -'il_pleut et -,jardin_mouillé à partir de K 0 m. Une voie pour privilégier un ensemble de croyances candidat parmi plusieurs possibles consiste à définir une relation de préférence entre formules de L(B) comme au
32

La révision en intelligence artificielle: deux paradigmes

paragraphe 2.2. Toutefois, la notion d'enracinement épistémique ne convient pas au cadre de la révision de bases de croyances. En particulier, le postulat de dominance (EE2) n'est plus adapté: ce sont les croyances de base, i.e. les formules apparaissant dans L(B) qui doivent être préservées en priorité. Nebel introduit la notion de pertinence épistémique pour caractériser de tels pré-ordres entre formules (cf Nebel (1990) pour plus de détails). 4. Relation entre les approches L'approche fondationnelle et l'approche fondée sur la cohérence visent toutes deux à offrir un cadre pour la révision de bases de connaissances dans lequel priorité est donnée à l'information qui conduit à la révision: dans les deux approches, l'information m supportant la révision n'est jamais rejetée. Elle appartient même nécessairement à l'ensemble de croyances révisé K 0 m.
Ce en quoi elles diffèrent

Cependant, les deux approches diffèrent bel et bien; d'abord, leurs genèses sont différentes: l'approche fondée sur la cohérence s'inscrit dans un cadre essentiellement logique alors que l'approche fondationnelle a été développée à l'origine dans un cadre opérationnel. D'un point de vue plus central, les informations extra-logiques requises pour effectuer un choix parmi les différentes bases révisées candidates ne sont pas prises en compte de la même façon dans les deux approches: relations de préférence entre sousbases, formules, modèles sont utilisées dans l'approche fondée sur la cohérence, alors que c'est essentiellement la présentation syntaxique de la base (éventuellement complétée par une relation de préférence entre sous-bases ou formules) qui importe dans l'approche fondationnelle. Ainsi, dans l'approche fondationnelle, deux ensembles de croyances identiques peuvent être révisés différemment lorsque leurs croyances de base (caractérisées par les
33

Pierre Marquis

applications L) diffèrent (en d'autres termes, lorsque deux bases de croyances syntaxiquement différentes mais logiquement équivalentes sont prises en compte). Cela est exclu dans le cas de l'approche fondée sur la cohérence par le postulat de rationalité (R4) : deux bases de croyances logiquement équivalentes sont toujours révisées de la même façon. L'approche fondationnelle va, de ce fait, présenter des avantages et des inconvénients par rapport à l'approche fondée sur la cohérence. Sur le plan des avantages, l'approche fondationnelle ne s'applique pas à des agents idéaux, ayant une capacité de déduction illimitée, i.e. des agents ayant conscience de l'ensemble de leurs croyances, ce qui contraste avec l'approche fondée sur la cohérence dans laquelle des ensembles de croyances (déductivement fermés) sont considérés. De tels agents rationnels ayant des capacités d'inférence restreinte sont sans aucun doute plus proches des agents intelligents « réels », humains ou autres. Cette absence de contrainte sur le pouvoir de raisonnement des agents a une conséquence importante sur l'efficacité (du point de vue calculatoire) avec laquelle on va pouvoir mettre en œuvre l'approche fondationnelle sur un ordinateur dans certaines circonstances (Nebel, 1992 ; Eiter & Gottlob, 1992 ; Nebel, 1994). Comme nous l'avons évoqué dans l'introduction, cette possibilité de simulation « efficace» est d'une importance cruciale en intelligence artificielle. Le prix à payer est cependant non négligeable: en effet, le fait d'accorder une certaine importance à la syntaxe dans l'approche fondationnelle pose immédiatement le problème de la sémantique. La sémantique de la logique propositionnelle classique ne peut évidemment plus s'appliquer directement. Déterminer le sens exact donné à une base appelée à être révisée n'est plus chose triviale. De ce fait, la conception de la base de croyances est une tâche difficile: les croyances de base et les croyances dérivées doivent être séparées, au mépris de toute considération de concision et de compréhensibilité qui sont pourtant des éléments centraux dans la conception d'une base de

34