*
Maurice Clerc, 1996
*
Maurice Clerc, 1996
Il y a juste un siècle que Lewis Carroll publiait à Londres son ouvrage "Symbolic Logic, Part 1; Elementary. En hommage à ce précurseur, je voudrais juste évoquer une autre manier de "jouer" la logique, plus adaptée à notre goût actuel pour les réseaux en tous genre.
INTRODUCTION
Des deux déclarations suivantes :
1. Quelques poulets sont des chats
2. Quelques chats parlent français
que peut-on conclure, à part le fait que leur auteur est citadin ... et anglophone? Faites le test, vous serez surpris de l'éventail des réponses, depuis le défaitisme complet ("Rien du tout"), jusqu'au sophisme optimiste ("Quelques poulets parlent français"). Voici un petit échantillon de celles usuellement considérées comme valides, dans le cas restrictif où le quantificateur "quelques" est précisé comme signifiant "au moins un et pas tous":
- quelques poulets ne sont pas des chats
- quelques chats sont des poulets
- la probabilité qu'un poulet parle français est non nulle
- je crois qu'il est possible qu'au moins un poulet parle français
-etc.
En tout cas peu de personnes sont capables de tirer toute la substantifique moëlle d'un exemple aussi simple : l'apprentissage de la logique est toujours d'actualité, ou plutôt des logiques, car depuis que, il y a exactement un siècle (1896), Lewis Carroll publiait sa "Logique symbolique", la situation s'est un peu compliquée : logique modale, temporelle, floue etc; sans oublier la logique quantique chère à Greg Bear [Bear G. 1990]. Je voudrais cependant tenter de montrer, en m'appuyant sur des exemples tirés d'une traduction commentée ultérieure [Carroll L. 1966] qu'il reste possible d'avoir une présentation à la fois ludique, mais néanmoins pas abusivement simplifiée, d'une logique allant un peu au-delà de la logique propositionnelle classique, ou même de la logique des prédicats.
L'idée est de reprendre certains des concepts utilisés dans des systèmes artificiels censés pouvoir raisonner pour l'homme. Le lecteur curieux pourra consulter Burattini, E.Tamburrini G. 1991 , Saffiotti A.,Umkehrer E. 1991, Sloman S. A. 1993 , Madigan D.Mosurski K. et al. 1994 , Weida R.,Litman D. 1994 , Giraud-Carrier C. G.,Martinez T. R. 1995 ; Larrosa J.,Cortés U. 1995 , Pearl J. 1995, Sun R. 1995, Clerc M. 1996] pour ne citer que quelques-uns des plus récents travaux.
En effet ces modèles ont été conçus pour être "enseignés" à des ordinateurs, particulièrement stupides, comme chacun sait, et ils sont donc complètement explicites, ne supposant jamais une quelconque connaissance autre que celle qui est donnée. Ce sont donc de bonnes sources d'inspiration pour élaborer une aide à l'apprentissage du raisonnement par l'homme, et je m'appuyerai ici essentiellement sur un autre article de Ron Sun, un peu plus ancien [Sun R. 1994] . Cependant nous traitons en général bien mieux que l'ordinateur les représentations graphiques (ou à la rigueur tabulaires) et les manipulations concrètes. Il n'y a donc pas de honte à profiter de ces atouts plutôt que de tenter en vain d'égaler la machine dans les calculs symboliques. C'est pourquoi je vous propose ici un jeu à base d'étiquettes annotées, de flèches , et de jetons.
REPRÉSENTATION ET RÈGLES DU JEU
L'imagerie adoptée est celle d'un réseau, avec des noeuds (les étiquettes) et des arcs (les flèches) les reliant. A un niveau d'abstraction moindre, on pourrait parler de lampes, et de connexions électriques , ou de joueurs pouvant voter les uns pour les autres, etc. Ma métaphore préférée est celle de maisons avec des chemins et souterrains à sens unique comportant des obstacles, les rez-de-chaussée abritant les "choses", et les caves les "non-choses". Mais ce serait un peu fastidieux à dessiner ici pour tous les exemples...
Chaque noeud porte un texte, qui, en pratique, désigne une chose, ou une classe de choses, ou un attribut, par exemple "chat", "parlant français". Toutes les négations sont mises sous la forme "non-<texte>", par exemple "non-parlant français". Disons tout de suite que j'ignore ici volontairement les problèmes d'existence, et d'indécidabilité, et que cette partition binaire est juste faite pour rester dans l'esprit carrollien. La tendance actuelle est plutôt d'avoir une partition moins tranchée (classes floues).
De même je ne tiendrai pas compte de l'effort à fournir pour trouver un résultat [Akman V.,Surav M. 1995] , à savoir que dans un "univers" un peu étendu, il faut bien s'arrêter un jour de propager les activations, c'est-à-dire limiter le nombre de pas de temps et/ou le nombre de noeuds dont on mémorise l'activation.
Arcs et noeuds sont valués par des jetons. Placé sur un arc, un jeton joue le double rôle d'un quantificateur et d'un filtre (cf. ci-dessous). Placé sur un noeud, c'est juste une mémorisation de résultat (en fait une représentation concrète simplifiée de la notion d'activation).
Il y a quatre types de jetons (cf Tableau 1), qui possèdent entre eux une relation d'ordre, du plus important "tous/tout" au moins important "aucun". On notera que par souci de simplification, le jeton de flèche noir, qui ne filtre rien, peut être omis.
| Jeton de flèche (importance décroissante) | Quantification, filtrage |
|---|---|
 |
tout, tous |
 |
certains voire tous |
 |
quelques et pas tous |
 |
aucun |
Par exemple, l'assertion "Quelques poulets sont des chats" sera représentée par
Le principe de base, une fois construit le réseau, en général à partir d'assertions sous forme textuelle, est de poser un jeton noir initial sur un noeud. L'attribution de jetons aux autres noeuds se fait alors via le processus de propagation. Une fois celui-ci terminé, on peut énoncer des interprétations linguistiques.
Règles de propagation, et raccourcis
Règle 1 (filtrage)
Tout jeton présent dans un noeud tente d'envoyer des copies de lui-même vers les autres noeuds, le long des flèches. Mais le jeton porté par la flèche "filtre" cette copie :
- un jeton de flèche noir (ou absent) laisse tout passer (le jeton aval est identique au jeton amont)
- un jeton de flèche blanc ne laisse rien passer (le jeton aval est blanc)
- un jeton amont blanc donne toujours un jeton aval blanc ("aucun" donne "aucun". Pas de génération spontanée!)
- un jeton flèche gris pâle transforme tout jeton amont non-blanc en un jeton aval gris pâle
- un jeton flèche gris foncé "diminue" d'un niveau les jetons qui lui sont supérieurs ou égaux (noir ou gris foncé), et laisse passer tel quel les autres (gris pâle ou blanc).
Exemples (les jetons numérotés sont ceux ajoutés pendant la propagation)
Règle 2 (cumul par maximisation)
Si, à un moment donné, un noeud comporte plusieurs jetons, on ne garde que le plus important (le plus foncé).
On notera que cette dernière règle implique que la "révision des croyances" ne peut être que monotone, ce qui garantit l'arrêt de la propagation au bout d'un nombre fini d'opérations.
Règle 3 (raccourcis/déductions)
À chaque instant (mais mieux vaut attendre la fin de la propagation), on peut créer des flèches depuis le noeud initial vers tous les noeuds ayant reçu un jeton. Sur chaque flèche, on pose une copie du jeton du noeud extrémité.
Traitons tout de suite quelques exemples.
LES POULETS-CHATS FRANCOPHONES
1. Quelques poulets sont des chats
2. Tous les chats parlent français
La Figure 1 montre les situations initiale et finale d'un propagation à partir du noeud "poulet". Les jetons sont numérotés selon leur ordre de dépose , une fois le réseau construit.
donne
Figure 1 -- Un syllogisme simple
LES ANIMAUX BAVARDS
1. Tous les chats parlent français
2. Quelques poulets parlent français
Figure 2 -- Quelques poulets sont-ils des chats ?
LES CHATS-POULETS
1. Quelques chats sont des poulets
2. Quelques poulets parlent français
Figure 3 -- Y-a-t-il des chats francophones ?
Mais, direz-vous, nous sommes loin de voir apparaître toutes les inférences évoquées en introduction. En effet, jusqu'ici nous n'avons pas utilisé d'items de type non-A. Pour ce faire, il faut poser au préalable deux règles supplémentaires.
Graphiquement, pour simplifier, les noeuds portant non-<texte> seront hachurés, et le libellé éventuellement absent, si le noeud <texte> est représenté juste à côté.
Règle 4 (tiers exclu étendu)
Pour toute flèche portant un jeton, on peut créer une flèche ayant les caractéristiques suivantes :
- elle joint le noeud origine de la première flèche au noeud contraire du noeud extrémité
.- elle porte le jeton contraire
Des expressions possibles sont :
"Si tout A est B, alors aucun A est non-B"
"Si au moins un A est B, alors tous les A ne sont pas non-B"
Ne pas oublier, par ailleurs, que B et non-B jouent des rôles symétriques.
Règle 5 (symétrie étendue)
Pour toute flèche portant un jeton blanc ou gris foncé, on peut créer une flèche ayant les caractéristiques suivantes :
- elle est en sens inverse de la flèche donnée
- elle porte le même jeton
Des expressions possibles sont :
"Si aucun A n'est B, alors aucun B n'est A"
"Si au moins un A est B, alors au moins un B est A"
À titre d'exercice, le lecteur pourra démontrer que "Si tous les A sont B, alors tous les non-B sont non-A"
La figure 5 donne un exemple d'application répétée de ces deux dernières règles. De "Aucun chat ne parle français" on déduit que "Tout francophone est non-chat", et "Aucun francophone n'est un chat", En pratique, on verra que pour réaliser une propagation, on peut ne s'intéresser qu'aux flèches portant des jetons "forts" (noir ou gris foncé).
donne
Figure 5 -- "Aucun chat ne parle français"
Voyons maintenant un exemple un peu plus compliqué. Dans un sorite, on se donne une suite d'assertions, les prémisses, et le but du jeu est de trouver la plus longue chaine déductive.
1. Tous les agents de police du secteur dînent avec notre cuisinière
2. Aucun homme aux cheveux longs ne peut être autre chose que poète
3. Amos Judd n'a jamais fait de séjour en prison
4. Les "cousins" de notre cuisinière aiment tous le gigot froid
5. Tous les poètes sont agent de police
6. Tous ceux qui dînent avec notre cuisinière sont ses "cousins"
7. Les hommes aux cheveux courts ont tous fait un séjour en prison
Figure 6 -- "Amos Judd aime le gigot froid"
Graphiquement (Figure 6), on voit tout de suite qu'il faut partir d'un noeud qui n'a pas d'arc entrant, donc "Amos Judd", et arriver à un noeud qui n'a pas d'arc sortant, donc "aimer le gigot froid". Ces deux noeuds constituent donc les rétinendes du sorite. Du moins si l'on peut effectivement trouver un cheminement. C'est le cas. En partant de "Amos Judd", on génère très facilement un chemin de jetons noirs. Les deux blocage apparents (au début, et au noeud "homme aux cheveux longs") sont aisément résolus par application de la règle 4.
En passant, on a une description du fameux "cousin" Amos Judd : cheveux longs, poète, agent de police du secteur , dinant avec notre cuisinière, et aimant le gigot froid ... Un bon point pour lui : il n'a jamais été en prison !
LES CINQ AMIS
Souvent, une asssertion se présente sous la forme "Si A et B, alors C". On peut encore "jouer" avec des jetons, en créant des noeuds "ET", avec sensiblement les règles de fonctionnement des schémas logiques électroniques :
Règle 6
La sortie d'un noeud ET est un jeton noir si et seulement si tous ses noeuds amonts portent un jeton noir.
Donnons un exemple.
Pour assurer la variété de leurs promenades, cinq amis ont convenu de faire des petis groupes selon les règles suivantes :
1. Si Amédée est avec sa femme - dans le même groupe - Barnabé avec la sienne, ainsi qu'Eusèbe , alors Casimir doit être avec Mme Désiré
2. Si Casimir et Désiré, ainsi que leurs femmes, se trouvent tous les quatre dans le même groupe, il ne faut pas qu'Eusèbe se trouve avec sa femme
Le problème consiste à prouver qu'il faut que chaque jour, il y ait au moins un couple (mari et femme) dont les deux membres sont dans des groupes différents
Chaque noeud du graphe représente un couple possible. Sous cette forme, la situation de la règle 2 peut se traduire par la conjonction des trois couples (Casimir, Mme Casimir), (Désiré, Mme Désiré) et (Casimir, Mme Désiré). (Rappellons que le graphique n'est qu'une aide : rien n'empêche de réfléchir aussi un peu !) . Le tracé lui-même est intuitivement assez évident.
Supposons, a contrario de ce que l'on cherche à prouver, que chaque couple mari et femme soit dans un même groupe. Sur le graphe, ceci revient à "activer" les noeuds (X, Mme X), en y posant un jeton noir. La propagation nous donne alors non-(Eusèbe, Mme Eusèbe), ce qui est en contradiction avec l'hypothèse. Celle-ci est donc fausse.
Figure 7 -- Les cinq amis. Impossible que tous les couples soient réunis.
Cet exemple est intéressant en ce qu'il fait référence à un ensemble vide, ce qui peut être interprété de différentes manières.
1. Aucun de mes élèves n'est vaniteux
2. Aucun de mes élèves n'est intelligent
3. Seul un élève intelligent peut résoudre ce problème
4. Tous les élèves intelligents sont choristes
5. Quelques-uns de mes élèves ne sont pas choristes
Le graphe est facile à construire (Figure 8), seule l'assertion 3 nécessitant un petit moment de réflexion (reformulation : "tout élève qui résoud ce problème est intelligent")
Figure 8 -- Les cancres. Et en plus certains chantent faux !
C'est volontairement que la figure ne contient pas de jetons de propagation, car à la réflexion, si j'ose dire, je laisse à votre sagacité le soin de répondre, par exemple, aux questions suivantes :
i) Un élève vaniteux est-il gourmand ?
ii) Un des élèves est-il capable de résoudre ce problème ?
iii) Un élève non intelligent peut-il ne pas être un choriste ?
Bon courage !
ANNEXE
Réponses au dernier exemple :
i) sans réponse. Un jeton noir placé sur "vaniteux" ne se propage pas. (à noter que Lewis Carroll répond "non"). En fait, il n'y a pas d'élève vaniteux ...
ii) non. Un jeton noir posé sur "élève" se propage jusqu'au noeud non-"résoud le problème" (par création des liens élève => non-intelligent => non-résoud_le_problème)
iii) oui. Il faut reformuler la question "Un élève peut-il être non-intelligent ET non-choriste". Un jeton noir sur "élève" va bien, en effet , activer ces deux autres noeuds.
Quelles logiques ?
On peut se demander quelles relations la logique propagative et cumulative illustrée ici entretient avec d'autres logiques. En fait, dans le papier déjà cité [R. Sun 1994], Ron Sun montre que son système FEL (Fuzzy Evidential Logic) est capable de simuler la théorie causale de Shoham [Shoham Y. 1990] ,(ou plus exactement une restriction atemporelle et monotone) et, partant, la logique propositionnelle de Horn. Le jeu graphique présenté est, au fond, très proche de FEL, et une démonstration analogue peut s'appliquer, mutatis mutandis (en fait, elle revient à faire des vérifications au cas par cas sur un certain nombre de formules de base de la Théorie Causale).
Ou, plus intuitivement, il suffit de remarquer que en donnant les valeurs 1 aux jetons noirs et gris, -1 aux blancs, et en considérant que les noeuds ET se déclenchent (propagent une valeur 1) dès que la somme des entrées est égale à leur nombre, on retrouve en effet le fonctionnement de FEL.
RÉFÉRENCES
* La photographie de Lewis Carroll provient du site de l'Université de l'Illinois
Un autre site intéressant ici
Akman V. , Surav M. (1995). Contexts, Oracles, and Relevance.
Bear G. (1990). La reine des anges. Paris, France, Robert Laffont.
Burattini E. ,Tamburrini G. (1991). A pseudo-neuronal system for hypothesis selection. LA.FOR.IA Institut Blaise Pascal.
Carroll L. (1966). Logique sans peine. Paris, Hermann.
Clerc M. (1996). "Déduction en Représentation Floue Hiérarchique. Un exemple." InCognito (3): 2-4.
Giraud-Carrier C. G. ,Martinez T. R. (1995). "An integrated framework for learning and reasoning." Journal of Artificial Intelligence Research 3: 147-185.
Larrosa J. ,Cortés U. (1995). "A Framework for Abductive Rule Formation." Ai Communications 8(2): 91-100.
Madigan D., Mosurski K., et al. (1994). Explanation in Belief Networks. USA, University of Washington.
Pearl J. (1995). "Causal diagrams for experimental research." Biometrika 82(2): 669-709.
Saffiotti A. ,Umkehrer E. (1991). PULCINELLA: A General Tool for Propagating Uncertainty in Valuation Networks. 7th Conf. on Uncertainty in AI, Los Angeles, CA, 323-331
Shoham Y. (1990). "Non-monotonic reasoning and causation." Cognitive Science : 213-252.
Sloman S. A. (1993). "Feature-based induction." Cognitive psychology 25(2): 231-280.
Sun R. (1994). "A neural network model of causality." IEEE transactions on neural networks 5(4): 604-611.
Sun R. (1995). "A new approach toward modeling causality in commonsense reasoning." International journal of intelligent systems 10(6): 581-616.
Weida R. ,Litman D. (1994). Subsumption and Recognition of Heterogeneous Constraint Networks. Conference on Artificial Intelligence for Application (CAIA-94),