La logique contextuelle

1. Introduction

La logique contextuelle Lc est un formalisme logique de la famille de dicto . Proposée par Arnaud Kohler [Koh95], elle présente une sémantique non monotone pour modéliser et exploiter, en respectant les règles de production syntaxique de la logique propositionnelle, des informations incomplètes, incohérentes ou modales dans le cadre général de la révision des croyances.

Le terme a aussi été employé par Nicolas Gauvrit pour nommer un modèle de logique locale permettant d'élucider certains paradoxes de la logique naturelle [Gau01], et par Yvon Gauthier pour proposer une analogie avec les logiques internes [Gau91].

2. Présentation par un exemple

Ce paragraphe propose de découvrir la logique contextuelle au travers d'un exemple.

2.1 Quelques principes généraux

La révision des croyances fait l'objet d'une littérature particulièrement riche. Quelques problèmes reviennent invariablement :

2.2 La question : les oiseaux volent-ils ?

Mettons-nous dans le cadre de la syntaxe de la logique propositionnelle, et considérons E un ensemble contenant les connaissances suivantes :

1 → ( Oiseau → Voler )
2 → ( Oiseau → Herbivore )
3 → ( Oie → Oiseau )
4 → ( Autruche → Oiseau )
5 → ( Vautour → Oiseau )

La première formule, par exemple, se lit : Le signe 1 exprime que les oiseaux volent. Appelons un ensemble comme {1,2,3} un contexte, et une formule produite par un contexte une croyance. Par exemple, la croyance Les oies volent est produite par le contexte {1,3}.

Si on suppose que le contexte {1,2,3,4,5} est vrai, alors on déduit que les oies, les autruches et les vautours sont des oiseaux herbivores qui volent. Ce n'est pas tout à fait vrai. Notamment, les autruches ne volent pas. Modélisons cette nouvelle information :

1 → ( Oiseau → Voler )
2 → ( Oiseau → Herbivore )
3 → ( Oie → Oiseau )
4 → ( Autruche → Oiseau )
5 → ( Vautour → Oiseau )
6 → ( Autruche → ¬ Voler )

Le contexte {1,4,6} produit la croyance que les autruches volent et ne volent pas - donc, selon les règles syntaxiques de la logique propositionnelle, qu'elles n'existent pas. Faisons toutefois l'hypothèse qu'elles existent. Dans ce cas :

L'incohérence relevée sur {1,4,6} provient de 1 : en fait, tous les oiseaux ne volent pas. Pour modéliser cette nouvelle information, exprimons simplement le fait que 1 est parfois vrai et parfois faux :

1 → ( Oiseau → Voler )
2 → ( Oiseau → Herbivore )
3 → ( Oie → Oiseau )
4 → ( Autruche → Oiseau )
5 → ( Vautour → Oiseau )
6 → ( Autruche → ¬ Voler )
1' → ( 1 )
2' → ( ¬ 1 )

1' et 2' expriment une méta connaissance (dans le sens d'une connaissance sur la connaissance) sur 1 et, indirectement, sur 4 et 6. Elles suggérent l'existence de 2 contextes d'interprétations, distinguant lorsque 1 est vrai et lorsque 1 est faux. Faisons à nouveau l'hypothèse que les autruches existent :

Chacun de ces contextes produit des croyances :

Le cumul des croyances issues séparément de chacun des 2 contextes forment un tout cohérent, et donne toutes les information qu'il est possible de produire de cet ensemble de connaissances. Par contre, l'ensemble des croyances issues de la conjonction des 2 contextes serait incohérent avec l'hypothèse.

Nous venons d'illustrer au travers de ce petit exemple le mécanisme de raisonnement de la logique contextuelle. Mais avant de synthétiser, introduisons une dernière information pour mieux nous approprier son comportement. Les vautours ne sont pas des herbivores, ce sont des carnivores - donc 2 est parfois vrai et parfois faux. Appliquons :

1 → ( Oiseau → Voler )
2 → ( Oiseau → Herbivore )
3 → ( Oie → Oiseau )
4 → ( Autruche → Oiseau )
5 → ( Vautour → Oiseau )
6 → ( Autruche → ¬ Voler )
7 → ( Vautour → Carnivore )
8 → ( Vautour → ¬ Herbivore )
1' → ( 1 )
2' → ( ¬ 1 )
3' → ( 2 )
4' → ( ¬ 2 )
La base de connaissances contient maintenant 4 méta connaissances : 1', 2', 3' et 4'. Et la combinatoire propose 4 contextes d'interprétation :

L'exploitation sans outil de ces contextes est fastidieuse, mais elle permet de vérifier que l'ensemble des croyances produites à partir de chaque contexte pris séparément forme un tout cohérent et complet (compte tenu évidemment des connaissances disponibles) - et qu'il ne faut pas tenir compte des croyances produites des conjonctions des contextes crédibles. Pour s'en convaincre, il suffit de tester le mécanisme sur l'hypothèse que les vautours existent ou que les autruches existent par exemples.

2.3 Retour sur les principes généraux

Le mécanisme présenté propose bien une solution aux différents problèmes soulevés par la révision des croyances :

L'exemple introduit le terme hypothèse. Nous ne nous attarderons pas dans ce document sur cette notion, parce qu'elle ne relève pas d'une question de formalisme : il aurait en effet était possible d'intégrer directement dans la base l'information que les autruches existent. Mais il aurait alors fallu la compléter, en indiquant que les oies et les vautours existent, que les oies ne sont ni des vautours ni des autruches, etc.. Cela aurait rendu l'exemple complètement illisible sans valeur ajoutée à son objectif initial, qui est d'illustrer le mécanisme de raisonnement de Lc.

En synthèse, 2 principes semblent ressortir de cet exemple :

En fait, le premier principe induit le second. En effet, le fait que la somme c1c2 des croyances issues de 2 contextes différents n'est pas l'ensemble des croyances issues du contexte c1c2 est aussi une conséquence de l'approche de dicto : c1c2 est une formule du langage, et il ne faut pas raisonner sur les formules. Cette remarque, et ces impacts dans le formalisme de Lc, est l'apport de ce document aux réflexions présentées par Arnaud Kohler dans [Koh95].

Le mécanisme étant illustré, il convient maintenant de lui construire un cadre formel.

3. La logique contextuelle

3.1. Le principe fondateur : l'approche de dicto

Les formalismes logiques peuvent être regroupés en deux familles, d'une part la conception de re, pour laquelle Les prédicats se rapportent à la nature de la chose dont on parle, et d'autre part la conception de dicto, pour laquelle Les prédicats déterminent la nature du dictum, de la proposition qui est dite.

En conception de re, un état de chose et son expression sont supposés liés, dans le langage, par une relation d'équivalence. L'approche de dicto propose une interprétation différente. Selon elle, un tableau peint peut être décrit par un ensemble de phrases, mais il n'y a pas d'équivalence entre le tableau et l'ensemble des formules du langage qui le représente : quand bien même la description serait idéalement complète et parfaite, elle n'est pas le tableau initial.

L'approche de dicto suppose donc que le tableau, d'une part, et les formules qui le représentent, d'autre part, doivent être distingués dans le langage. Pour formaliser ce postulat, la logique contextuelle propose une relation entre la syntaxe (les combinaisons des symboles utilisées pour modéliser le langage) et la sémantique (l'interprétation que le formalisme propose de ces combinaisons) :

Soit L un langage muni de la règle d'interprétation sémantique ⊨L. Soit c un état, et f la formule qui décrit c dans L. Alors :

Selon cet énoncé, l'agent ne mémorise ni l'état c ni sa modélisation f : il mémorise la connaissance qu'il a de modéliser c par f. Cette approche rejoint L. Wittgenstein, qui affirme [Wit] : Nous ne devons pas dire : Le signe complexe aRb dit que a se trouve dans la relation R avec b, mais : Que a se trouve dans une certaine relation R avec b dit que aRb.

3.2. Le langage

Le langage de Lc est celui de la logique propositionnelle Lp. Les connecteurs de négation, de disjonction, de conjonction, d'implication, et d'équivalence, sont notés respectivement ¬, ∨, ∧, → et ↔. Lc utilise les symboles classiques de parenthèses.

L'ensemble infini dénombrable des propositions atomiques p est noté PLc. Il est décomposé en une infinité d'ensembles infinis dénombrables disjoints de propositions atomiques, notés PLci, pour i un nombre entier. i est appelé le rang de p dans Lc. p est noté pi.

Par convention, PLc0 est considéré comme étant l'ensemble des propositions atomiques de PLp.

3.3. La syntaxe

La syntaxe de Lc est celle de la logique propositionnelle Lp. La règle d'inférence valide de Lc est celle de Lp, notée ⊢Lp.

Une formule contextuelle est une formule de la forme pi+1f i telle que :

L'ensemble des formules contextuelles, noté WLc, forme l'ensemble des formules biens formées de Lc.

Lc propose des définitions formelles pour les termes connaissance, contexte, hypothèse et croyance :

On déduit facilement :

3.4. La sémantique

La sémantique de Lc étend la sémantique de Lp en définissant une fonction de méta interprétation des croyances. Soient :

Une croyance c est dite :

La sémantique de Lc profite des propriétés de Lp pour garantir son adéquation et sa complétude.

3.5. Les contextes crédibles

La sémantique de Lc ne propose pas de solution pour déterminer, parmi l'ensemble des contextes possibles, ceux qu'il faut retenir comme contextes de référence. Cette omission est volontaire. Lc postule en effet que ce choix, déterminant, ne dépend pas du langage formel, mais est complètement lié au raisonnement qu'on souhaite modéliser.

La définition retenue pour présenter l'exemple au paragraphe précédent exploite l'idée que les propositions de rang i expriment une méta connaissance sur les contextes de rang inférieurs. Un contexte crédible privilégie donc les propositions du plus haut rang i, puis les propositions du rang i-1, etc., jusqu'au rang 1 (un contexte ne contenant pas de proposition atomique de rang 0). Il se construit de la manière suivante :

Soit i le plus haut des rangs dans l'ensemble des connaissances :

Notons que cette définition est constructive, et que les différents contextes peuvent être construits indépendamment les uns des autres. Cette remarque est utile pour optimiser des algorithmes de production de preuve, en cherchant à construire uniquement le contexte crédible répondant à la question posée.

3. Application à l'Intelligence Artificielle

L'expression Intelligence Artificielle, ou IA, ne bénéficie pas d'une définition unanimement acceptée. Elle varie notamment selon le but recherché : modéliser un raisonnement humain ou modéliser un raisonnement idéal. Lc propose une sémantique des croyances. Elle se situe donc dans le premier cas, intégrant la modélisation des doutes et des erreurs.

3.1. La révision des croyances

L'exemple présenté dans les paragraphes précédents apporte quelques instructions :

Un avantage important de Lc est de rester dans les règles de production syntaxique de Lp. Cela lui permet de bénéficier de ses algorithmes.

Ceux-çi ont toutefois une charge des calculs et des temps de réponses non négligeables. Les progrès des technologies réalisés depuis plusieurs décennies repoussent sans cesse le seuil des possibles, mais sans préjuger définitivement de la non existence d'une limite. Les sciences cognitives proposent des solutions à cette difficulté.

3.2. Les modèles cognitifs

Les recherches autour des modèles cognitifs ont conduit à l'émergence de différents concepts (les définitions ci-dessous sont très succinctes, et font toujours l'objet de discussions) :

Les modèles cognitifs distinguent donc une MLT (contenant l'ensemble des connaissances) d'une MCT (contenant un sous-ensemble "actif" de la MLT. Dans le cadre de l'IA, cette distinction peut être utilisée pour répondre au problème posé par la charge de calcul rencontré par les formalismes logiques en limitant la charge de calcul à un nombre fini de formules.

Pour gérer la définition du périmètre de la MCT, 3 principes reviennent le plus souvent :

Pour être complet, on peut indiquer les travaux de J. Pitrat. Ils laissent à penser que les croyances d'un humain excèdent rarement plus de quatre niveaux de méta-connaissances, supposant l'existence d'un seuil d'incapacité sémantique. En logique contextuelle, cela pourrait se traduire par un rang maximum sur les propositions atomiques.

3.3. Le modèle cognitif contextuel

Sur ces principes, le modèle cognitif contextuel propose :

  1. le RS est le lieu où est mémorisé l'ensemble des fonctions procédurales,
  2. la MLT contient l'ensemble des formules contextuelles. Elles sont indexées par le RS sur chacune des propositions atomiques qui la composent suivant leur chronologie d'apparition dans la MCT,
  3. la MT contient toutes les formules susceptibles d'être produites par résolution sur la MCT,
  4. la MCT contient un ensemble fini de formules de la MLT. Elle a une taille limitée. Lorsqu'il intègre une formule dans la MCT, le RS efface en fonction des seuils d'incapacité la formule la plus ancienne, et met à jour la MT, la MLT et ses index. La MCT évolue en réaction à une stimulation :
    1. si arrivée d'une connaissance, sous la forme d'une formule cf : le RS vérifie dans la MLT s'il existe une ancienne connaissance c'f en tenant compte des seuils d'incapacité. Il intègre la connaissance (nouvelle ou ancienne) dans la MCT,
    2. si interrogation, sous la forme d'un ensemble de propositions atomiques : le but est alors de trouver une croyance contenant ces propositions pour produire une interprétation sémantique :
      1. si une réponse se trouve déjà dans la MT, le système la produit. Le RS efface de la MCT les formules qui ont participé à la réponse, et les réintègre,
      2. sinon, le RS recherche dans les index de la MLT, en respectant les seuils d'incapacités, des formules construites sur au moins deux des propositions contenues dans l'interrogation :
        1. s'il n'en trouve pas, il produit une réponse d'échec et attend une nouvelle stimulation.
        2. s'il en trouve, il les intègre à la MCT. Il reprend ensuite à l'étape (4.2.1) après avoir ajouté dans l'interrogation les propositions des formules qu'il vient d'extraire de la MLT.

3.4. Remarques et application

Sur (1), recherche d'une ancienne connaissance : le but est double, ne pas saturer la MLT d'une part, et bénéficier de l'indexation sur le contexte de l'ancienne connaissance d'autre part. L'existence des seuils techniques peut conduire à la création en double d'une croyance, ce qui suppose l'existence d'un mécanisme de nettoyage de la MLT.

Sur (2), indexation des propositions : ainsi, une connaissance a → ( bc) est triplement indexée sur a, b et c. Le RS pourra donc y accéder de trois manières différentes. Et suivant les valeurs des seuils d'incapacités, elle pourra être inaccessible par l'index a mais accessible par l'index b par exemple.

Sur (4.2.1), effacement et réintégration des formules dans la MCT : le but de l'opération est de mettre à jour les différentes indexations.

Sur (4.2.2), recherche sur au moins deux propositions : deux est un choix arbitraire, qui peut être modifié.

Sur (4.2.2.1), constat d'échec : le RS indique qu'il n'a pas trouvé de relation entre les propositions qui formaient l'interrogation.

Sur (4.2.2.2), enrichissement de l'interrogation : il permet au RS d'élargir si besoin sa recherche dans la MLT aux propositions en corrélation avec la question posée.

Sur (4.2.2.2), risque de bouclage infini : un seuil technique peut être défini pour échapper à ce risque.

Ce modèle est simple à implémenter. Les seuils techniques permettent de maîtriser les temps de calcul. Son objectif est d'essayer de simuler des comportements "humains", incluant les erreurs, les oublis, des réponses différentes entre 2 instants, etc.. Les réponses produites dépendent en effet fortement des seuils d'incapacités appliqués et de l'historique du système.

L'ambition du modèle cognitif contextuel est de pouvoir reproduire un comportement comme : De quelle couleur est ce mur ? "Blanc". Que boivent les vaches ? "Du lait". La connaissance Une vache boit de l'eau, incluse dans la MLT, n'est pas automatiquement remontée par le RS dans la MCT... Ce n'est pas la réponse attendue d'un agent absolument rationnel. Mais c'est, bien souvent, la réponse que fournit une intelligence humaine.

4. Relation avec d'autres formalismes non classiques

Un langage L est dit classique si, et seulement si, il vérifie la propriété suivante : quels que soient F1 et F2 des ensembles de formules bien formées de L, et f une formule bien formée de L, l'interprétation sémantique de f dans F1 est égale à l'interprétation sémantique de f dans {F1,F2}. C'est le cas par exemple de la logique propositionnelle.

Soit f une formule bien formée de WLp. Pour Lc, WLp = WLc0. La relation entre un ensemble F de formules propositionnelles et un ensemble E de formules contextuelles est donnée par :

cPLc1 tel que : FLp f si et seulement si {E,c} ⊨Lp f

Cette traduction exprime le fait que la logique propositionnelle ne modélise qu'un contexte à la fois.

Les formalismes monotones peuvent modéliser les raisonnement strictement rigoureux (comme les raisonnements mathématiques par exemple), mais pas les raisonnements dits de sens commun : ceux-ci s'appuient à un chaque instant sur des informations incomplètes, voir même éventuellement fausses ou incohérentes, que l'arrivée d'une nouvelle information F2 peut complètement remettre en question.

Les formalismes non classiques sont apparus pour tenter de résoudre cette difficulté. Ils induisent une nouvelle propriété : L est dit non monotone si, et seulement si, il existe F1 et F2 des ensembles de formules bien formées de L, et f une formule bien formée de L tels que l'interprétation sémantique de f dans F1 est différente de l'interprétation sémantique de f dans {F1,F2}.

La logique contextuelle a la particularité suivante :

Des comparaisons avec d'autres formalismes non monotones sont présentés succintement ci-dessous.

4.1. La circonscription

Proposée par J. Mc Carthy, l'idée de la circonscription est de traduire une règle avec exception(s) par une expression de la forme :

(a ∧ ¬anormal) → b

Son sens intuitif est : Si a est vraie, et qu'on n'est pas dans un cas anormal, alors b est vraie. Elle est, classiquement, accompagnée par une (des) formule(s) qui détermine(nt) ce qui relève de l'anormalité, de la forme :

canormal

pour Si c est vraie, alors on est dans un cas anormal. La proposition de J. Mc Carthy est de calculer l'extension qui minimise le nombre d'anormalités, c'est à dire qui contient "le moins de" littéraux positifs anormaux.

Dans Lc, ces énoncés peuvent se traduire par les formules contextuelles suivantes :

p1→(ab) pour p1PLc1
p2→(c→¬p1) pour p2PLc2

Les extensions au sens de Mc Carthy sont les croyances de WLc0 produites par les contextes possibles maximaux qui contiennent tous les p2. La minimalité du nombre d'anormalités est portée par la maximisation du nombre de p1.

Il est difficile d'établir dans quelle mesure cette traduction est adéquate et complète, la proposition anormal disparaissant du langage.

4.2. La théorie des défauts

Proposée par R. Reiter, une théorie avec défauts T = (F , D) est composée d'un ensemble FWLp, et d'un ensemble D de règles de défauts, qui ont comme forme :

(a : b / c) pour a,b,cWLp

Le sens intuitif de cette expression est : Si a est vraie, et si b n'est pas contradictoire avec ce qui est vraie, alors c est vraie. Le but est, à partir d'une théorie avec défauts, de générer une extension comprenant, en plus de l'ensemble initial F, de nouvelles informations obtenues par l'application des règles de défauts.

Au sens de R. Reiter, E est une extension de T si, et seulement si, E = ⋃iN Ei, tel que :

E0 = F
Ei+1 = Th ( Ei ) ⋃ c tel que (a : b / c) ∈ D et aEi et ¬bE

où Th ( Ei ) désigne l'ensemble des théorèmes déduits de façon monotone (c'est à dire par les lois d'inférences classiques) à partir de Ei.

Dans Lc, soit p01PLc1 tel que p01F. Pour chaque règle de défauts (a : b / c), il existe un couple (p1PLc1 , p2PLc2) tel que :

p1 → (ac)
p2 → ((¬a ∨ ¬b ∨ ¬c) → ¬p1)

Les extensions au sens de R. Reiter sont les croyances de WLc0 produites par les contextes possibles maximaux qui contiennent p01 et tous les p2.

Cette traduction est complète mais non adéquate : elle ajoute la formule ac à certaines extensions de Reiter qui ne la contiennent pas. Pour y parvenir, il faut retirer cette formule des extensions qui ne vérifient pas ¬a ou c.

4.3. Les logiques modales

Le langage des logiques modales Lm est celui de la logique propositionnelle, étendu à au moins un connecteur monadique, classiquement noté ◻. L'ensemble des formules bien formées de Lm est noté WLm.

Lorsqu'il y a plusieurs connecteurs modaux, on parle de formalisme multi-modal. Le rapprochement avec Lc présenté ci-dessous est limité au périmètre des logiques mono-modales dites aléthiques, pour lesquelles ◻ caractérise une notion de vraisemblance : ◻a exprime que a est nécessaire (et donc son dual ¬◻¬a, noté ◇a, que a est possible) par exemple.

La sémantique de Kripke est considérée comme la sémantique la plus complète et la plus satisfaisante pour les logiques modales. Un P-modèle de Kripke est un triplet (W , I , R) tel que :

I respecte les règles suivantes :

Ainsi, dans une approche aléthique, une formule est nécessairement vraie dans un monde si, et seulement si, tous les mondes auxquels ce dernier accède contiennent cette formule.

Soit F un ensemble de formules modales. Sa traduction en un ensemble E de formules contextuelles peut être :

L'objectif de cette traduction est d'exprimer chaque monde possible de Kripke comme un contexte possible dans Lc. Les écarts entre les rangs des contextes modélisent la relation d'accessibilité entre les mondes.

Cette traduction est adéquate mais non complète : les formules possibles ne sont identifiables que si leur négation est aussi possible. Dans le cas contraire, elles sont confondues avec les formules nécessaires, ce qui ne permet pas de capturer complètement la relation d'accessibilité.

5. Bibliographie