*
Maurice Clerc, 1996
*
Maurice Clerc, 1996
Il y a juste un siècle que Lewis Carroll publiait à Londres sonouvrage "Symbolic Logic, Part 1; Elementary. En hommage à ceprécurseur, je voudrais juste évoquer une autre manier de"jouer" la logique, plus adaptée à notre goût actuel pourles 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 ... etanglophone? Faites le test, vous serez surpris de l'éventail desréponses, depuis le défaitisme complet ("Rien du tout"), jusqu'ausophisme optimiste ("Quelques poulets parlent français"). Voici un petitéchantillon de celles usuellement considérées commevalides, dans le cas restrictif où le quantificateur "quelques" estpré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 substantifiquemoëlle d'un exemple aussi simple : l'apprentissage de la logique esttoujours d'actualité, ou plutôt des logiques, car depuisque, il y a exactement un siècle (1896), Lewis Carroll publiait sa"Logique symbolique", la situation s'est un peu compliquée : logiquemodale, temporelle, floue etc; sans oublier la logique quantique chèreà Greg Bear [BearG. 1990].Je voudrais cependant tenter de montrer, en m'appuyant sur des exemplestirés d'une traduction commentée ultérieure [CarrollL. 1966]qu'il reste possible d'avoir une présentation à la fois ludique,mais néanmoins pas abusivement simplifiée, d'une logique allantun peu au-delà de la logique propositionnelle classique, ou mêmede la logique des prédicats.
L'idée est de reprendre certains des concepts utilisés dans dessystèmes artificiels censés pouvoir raisonner pourl'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, nesupposant jamais une quelconque connaissance autre que celle qui estdonnée. Ce sont donc de bonnes sources d'inspiration pourélaborer une aide à l'apprentissage du raisonnement parl'homme, et je m'appuyerai ici essentiellement sur un autre article de RonSun, un peu plus ancien[SunR. 1994]. Cependant nous traitons en général bien mieux que l'ordinateurles représentations graphiques (ou à la rigueur tabulaires) etles manipulations concrètes. Il n'y a donc pas de honte àprofiter de ces atouts plutôt que de tenter en vain d'égaler lamachine dans les calculs symboliques. C'est pourquoi je vous propose ici un jeuà base d'étiquettes annotées, de flèches , et dejetons.
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 niveaud'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 deschemins et souterrains à sens unique comportant des obstacles, lesrez-de-chaussée abritant les "choses", et les caves les "non-choses".Mais ce serait un peu fastidieux à dessiner ici pour tous lesexemples...
Chaque noeud porte un texte, qui, en pratique, désigne une chose, ouune classe de choses, ou un attribut, par exemple "chat", "parlantfrançais". Toutes les négations sont mises sous la forme"non-<texte>", par exemple "non-parlant français". Disons tout desuite que j'ignore ici volontairement les problèmes d'existence, etd'indécidabilité, et que cette partition binaire est juste faitepour rester dans l'esprit carrollien. La tendance actuelle est plutôtd'avoir une partition moins tranchée (classes floues).
De même je ne tiendrai pas compte de l'effort à fournirpour trouver un résultat [AkmanV.,Surav M. 1995] , à savoir que dans un "univers" un peu étendu, il faut biens'arrêter un jour de propager les activations, c'est-à-direlimiter le nombre de pas de temps et/ou le nombre de noeuds dont onmémorise l'activation.
Arcs et noeuds sont valués par des jetons. Placé sur un arc, unjeton 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 derésultat (en fait une représentation concrètesimplifiée de la notion d'activation).
Il y a quatre types de jetons (cf Tableau 1), qui possèdent entre euxune 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, quine 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, engénéral à partir d'assertions sous forme textuelle, est deposer un jeton noir initial sur un noeud. L'attribution de jetons aux autresnoeuds se fait alors via le processus de propagation. Une fois celui-citerminé, on peut énoncer des interprétationslinguistiques.
Règles de propagation, et raccourcis
Règle 1 (filtrage)
Tout jeton présent dans un noeud tente d'envoyer des copies delui-même vers les autres noeuds, le long des flèches. Mais lejeton porté par la flèche "filtre" cette copie :
- un jeton de flèche noir (ou absent) laisse tout passer (lejeton aval est identique au jeton amont)
- un jeton de flèche blanc ne laisse rien passer (le jeton avalest 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-blancen un jeton aval gris pâle
- un jeton flèche gris foncé "diminue" d'un niveau les jetons quilui sont supérieurs ou égaux (noir ou gris foncé), etlaisse passer tel quel les autres (gris pâle ou blanc).
Exemples (les jetons numérotés sont ceux ajoutés pendantla propagation)
Règle 2 (cumul par maximisation)
Si, à un moment donné, un noeud comporte plusieurs jetons, on negarde 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 quigarantit l'arrêt de la propagation au bout d'un nombre finid'opérations.
Règle 3 (raccourcis/déductions)
À chaque instant (mais mieux vaut attendre la fin de la propagation), onpeut créer des flèches depuis le noeud initial vers tous lesnoeuds ayant reçu un jeton. Sur chaque flèche, on pose une copiedu 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 leurordre 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 lesinférences évoquées en introduction. En effet, jusqu'icinous n'avons pas utilisé d'items de type non-A. Pour ce faire, il fautposer au préalable deux règles supplémentaires.
Graphiquement, pour simplifier, les noeuds portant non-<texte> seronthachuré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 uneflèche ayant les caractéristiques suivantes :
- elle joint le noeud origine de la première flèche au noeudcontraire 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ôlessymétriques.
Règle 5 (symétrie étendue)
Pour toute flèche portant un jeton blanc ou gris foncé, on peutcré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 lesA sont B, alors tous les non-B sont non-A"
La figure 5 donne un exemple d'application répétée de cesdeux dernières règles. De "Aucun chat ne parle français"on déduit que "Tout francophone est non-chat", et "Aucun francophonen'est un chat", En pratique, on verra que pour réaliser unepropagation, on peut ne s'intéresser qu'aux flèches portant desjetons "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, onse donne une suite d'assertions, les prémisses, et le but du jeu est detrouver la plus longue chaine déductive.
1. Tous les agents de police du secteur dînent avec notrecuisinière
2. Aucun homme aux cheveux longs ne peut être autre chose quepoè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 noeudqui n'a pas d'arc entrant, donc "Amos Judd", et arriver à un noeud quin'a pas d'arc sortant, donc "aimer le gigot froid". Ces deux noeuds constituentdonc les rétinendes du sorite. Du moins si l'on peut effectivementtrouver un cheminement. C'est le cas. En partant de "Amos Judd", ongénère très facilement un chemin de jetons noirs. Les deuxblocage apparents (au début, et au noeud "homme aux cheveux longs") sontaisé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 notrecuisinière, et aimant le gigot froid ... Un bon point pour lui : il n'ajamais é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", avecsensiblement 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 noeudsamonts portent un jeton noir.
Donnons un exemple.
Pour assurer la variété de leurs promenades, cinq amis ontconvenu 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 tousles quatre dans le même groupe, il ne faut pas qu'Eusèbe setrouve avec sa femme
Le problème consiste à prouver qu'il faut que chaque jour, il yait au moins un couple (mari et femme) dont les deux membres sont dans desgroupes 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 troiscouples (Casimir, Mme Casimir), (Désiré, MmeDésiré) et (Casimir, Mme Désiré). (Rappellons quele graphique n'est qu'une aide : rien n'empêche deréfléchir aussi un peu !) . Le tracé lui-même estintuitivement assez évident.
Supposons, a contrario de ce que l'on cherche à prouver, que chaquecouple mari et femme soit dans un même groupe. Sur le graphe, cecirevient à "activer" les noeuds (X, Mme X), en y posant un jeton noir.La propagation nous donne alors non-(Eusèbe, Mme Eusèbe), ce quiest en contradiction avec l'hypothèse. Celle-ci est donc fausse.
Figure 7 -- Les cinq amis. Impossible que tous les couples soientréunis.
Cet exemple est intéressant en ce qu'il fait référenceà un ensemble vide, ce qui peut être interprété dediffé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 ceproblè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 3né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 à votresagacité le soin de répondre, par exemple, aux questionssuivantes :
i) Un élève vaniteux est-il gourmand ?
ii) Un des élèves est-il capable de résoudre ceproblème ?
iii) Un élève non intelligent peut-il ne pas être unchoriste ?
Bon courage !
ANNEXE
Réponses au dernier exemple :
i) sans réponse. Un jeton noir placé sur "vaniteux" ne se propagepas. (à noter que Lewis Carroll répond "non"). En fait, il n'y apas d'élève vaniteux ...
ii) non. Un jeton noir posé sur "élève" se propagejusqu'au noeud non-"résoud le problème" (par création desliens é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 cumulativeillustrée ici entretient avec d'autres logiques. En fait, dans le papierdé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] ,(ouplus exactement une restriction atemporelle et monotone) et, partant, lalogique propositionnelle de Horn. Le jeu graphique présenté est,au fond, très proche de FEL, et une démonstration analogue peuts'appliquer, mutatis mutandis (en fait, elle revient à faire desvérifications au cas par cas sur un certain nombre de formules de basede la Théorie Causale).
Ou, plus intuitivement, il suffit de remarquer que en donnant les valeurs 1 auxjetons noirs et gris, -1 aux blancs, et en considérant que les noeudsET se déclenchent (propagent une valeur 1) dès que la somme desentrées est égale à leur nombre, on retrouve en effet lefonctionnement 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 hypothesisselection. LA.FOR.IA Institut Blaise Pascal.
Carroll L. (1966). Logique sans peine. Paris, Hermann.
Clerc M. (1996). "Déduction en Représentation FloueHiérarchique. Un exemple." InCognito (3): 2-4.
Giraud-Carrier C. G. ,Martinez T. R. (1995). "An integrated framework forlearning and reasoning." Journal of Artificial Intelligence Research3: 147-185.
Larrosa J. ,Cortés U. (1995). "A Framework for Abductive RuleFormation." 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." Biometrika82(2): 669-709.
Saffiotti A. ,Umkehrer E. (1991). PULCINELLA: A General Tool forPropagating Uncertainty in Valuation Networks. 7th Conf. on Uncertainty in AI, Los Angeles, CA, 323-331
Shoham Y. (1990). "Non-monotonic reasoning and causation." CognitiveScience : 213-252.
Sloman S. A. (1993). "Feature-based induction." Cognitive psychology25(2): 231-280.
Sun R. (1994). "A neural network model of causality." IEEE transactions onneural networks 5(4): 604-611.
Sun R. (1995). "A new approach toward modeling causality in commonsensereasoning." 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),