LessystmesexpertscoursDEAIngnIA,13Octobre1993 Phil.Reitz,LIRMM,dpartementARC

Plan

PourquoilesSystmesExperts.........................................................2 Prambule............................................................................................3 L'IAenquelquesmots.......................................................................4 LesystmeGPS(Newell&Simon,1956)........................................5 DENDRAL(Feigenbaum,1965).......................................................6 Premiersconstats................................................................................7 Unpremiercahierdeschargesd'unSE...........................................8 LesystmeMYCIN(1974).................................................................9 Structuregnraled'unSE..............................................................10 Lesfaits..............................................................................................11 Lesrglesdeproduction.................................................................12 Unestratgiederaisonnement:.....................................................13 Unestratgiederaisonnement:.....................................................14 Unestratgiederaisonnement:.....................................................15 Rsolutiondel'ensembledeconflits..............................................16 Mtaconnaissance...........................................................................17 Ordre0etordre1.............................................................................18 LaconceptiondesSEaujourd'hui..................................................19 LelangagePROLOG........................................................................20 PROLOGenunexemple.................................................................21 Lessystmesmultiexperts.............................................................22 Construireunebasedeconnaissance............................................23 ApplicationsdesSE..........................................................................24 Conclusion.........................................................................................25 Bibliographie.....................................................................................261 / 27

Un navrant

Pourquoi les Systmes Prambule : IA et Experts SE

constat

Les experts d'un domaine ont pour caractristiques : d'tre rares, donc peu disponibles d'tre comptents (si possible les meilleurs) d'tre souvent incapables d'expliquer leur dmarche d'tre mortels Les objectifs des SE rendre une expertise accessible tous approcher au mieux la perfection dcortiquer le raisonnement expert pour expliquer rendre une connaissance experte insensible au temps En un mot, simuler le comportement d'un expert humain sans avoir les petits (et grands) dfauts de la nature humaine. Les principales difficults comment programmer une machine pour en faire un expert comment grer les contradictions ventuelles entre diffrents experts comment faire voluer un tel systme sans que ses comptences se dgradent (le paradoxe du trop-plein de connaissance) L'Intelligence Artificielle (IA) Objectif : concevoir une machine dont le comportement est2 / 27

jug

L'IA en quelques mots

intelligent Question

:

qu'est-ce qu'un comportement intelligent ? dmontrer un thorme ? bien jouer aux checs ? lire un document puis rpondre des questions ? exploiter son pass pour prvoir le futur ? faire le mnage la maison ? Question : qu'est-ce qu'tre intelligent simuler l'intelligence = tre intelligent ? Le projet existe depuis les dbuts de l'Informatique (~ 1940) Les Systmes Experts (SE) L'un des rares succs industriels de l'Intelligence Artificielle Les disciplines de l'IA Rsolution de problmes Programmation automatique, apprentissage Dduction, dmonstration de thormes Langages, formalismes de reprsentation des connaissances Langage naturel Reconnaissance de formes Un domaine interdisciplinaire Psychologie cognitive Epistmologie Neurobiologie Sociologie3 / 27

Le systme GPS (Newell & Simon, 1956)Les vrais dbuts de l'Intelligence Artificielle Le systme GPS, en 1956 (rsolution de problmes) Les premiers travaux contribuant la naissance des SE Le systme DENDRAL, en 1965 (identification en chimie) Le premier systme expert digne de ce nom Le systme MYCIN, en 1974 (maladies du sang) Objectif Concevoir un systme de rsolution automatique de problmes qui soit indpendant du problme rsoudre. Contre-pied de la dmarche classique Dmarche classique : programme = suite d'instructions Usager : doit prciser les oprations appliquer doit indiquer dans quel ordre les appliquer Dmarche de GPS : la stratgie d'application des oprateurs est universelle Usager : doit spcifier tous les oprateurs applicables GPS : choisit l'oprateur selon le contexte4 / 27

Principe

DENDRAL (Feigenbaum, Premiers constats 1965)

une situation = tat du rsolveur un instant donn un oprateur transforme une situation en une autre qui la rapproche d'une situation solution (degr de solution) GPS choisit l'oprateur qui minimise au mieux ce degr Inconvnient GPS peut ne pas aboutir une solution, bien qu'il puisse en exister une (problme du minimum local, classique en optimisation) Exemple Parcours d'un labyrinthe Objectif identifier une structure chimique partir de rsultats de mesures chimiques, physiques et spectromtriques. Principe Dduire des rsultats de mesures toutes les informations possibles Interroger l'usager si des informations sont manquantes Faire une synthse et conclure Inconvnient Programm de manire classique difficilement maintenable Aucune possibilit d'explication Le systme travaille sur des donnes factuelles spcifiques5 / 27

Un premier cahier des charges d'un SE

d'un

problme donn Le systme applique des transformations dont la dfinition est indpendante du problme en cours de rsolution, mais dpend du problme gnral rsoudre L'ordre d'application de ces transformations est dpendant du contexte, dont a priori non dterministe L'efficacit du systme est lie cet ordre d'application Conclusion provisoire il faut sparer - les donnes d'un problme particulier - les oprations qui vont transformer ces donnes il faut viter - de figer la stratgie de choix de l'opration appliquer - d'avoir des oprations trop interdpendantes Problmes poss Existe-t-il un systme universel de codage rpondant ces exigences ? reprsentation des connaissances Quelles limitations sur le raisonnement sont induites par un tel systme de reprsentation des connaissances ? Un systme dans lequel la connaissance est facilement code Reprsentation de la connaissance Un systme capable d'effectuer des infrences Mcanismes de raisonnement (dduction, abduction) Un systme facilement modifiable6 / 27

Le systme MYCIN (1974) Evolution de la connaissance Un systme capable d'expliquer son raisonnement Etre convaincu de la justesse des rsultats Essayer des alternatives, juste "pour voir" Objectif Aide au diagnostic dans le domaine des maladies infectueuses, en particulier mningites et maladies du sang Exemples de donnes factuelles le site de la culture est le sang le patient a t srieusement brl (certitude 0.9) Exemple d'opration ajoutant des informations SI le site de la culture est le sang ET l'identit de l'organisme n'est pas connu avec certitude ET la coloration de l'organisme est GRAM ngatif ET la morphologie de l'organisme est batonnet ET le patient a t srieusement brl ALORS l'identit de l'organisme est Pseudomas (0.4) Caractristique intressante Les informations peuvent tre incertaines

7 / 27

Structure gnrale d'un Les faits SEExpert Cogniticien Basedefaits Basedergles Mtargles Basede connaissance Moteur d'apprentissage SE de base = base de connaissance + moteur d'infrences Base de connaissance = faits + rgles + mta-rgles + Moteur d'infrences : mcanisme de raisonnement, indpendant du domaine et du problme Faits : mmoire court terme, dpendant du problme Rgles : mmoire long terme, indpendant du problme, dpendant du domaine une rgle manipule des faits Mta-rgles : mmoire long terme, indpendant du problme, voire du domaine une mta-rgle manipule des rgles Toute description d'une situation implique des entits lis8 / 27

Moteur d'infrences

Usager

Module d'acquisition

Module d'explication

La reprsentation des connaissancesrelations

par des

Un fait reprsente au moins une relation liant diverses entits Reprsentation centre sur les entits Un homme en gnral :HOMME estunMAMMIFERE mortel?(pardfaut=oui)

Un philosophe en gnral :PHILOSOPHE estunHOMME nationalit(pardfaut=GREC)

Le philosophe J.P. Sartre :J.P.SARTRE estunPHILOSOPHE nationalitFRANCAIS

Reprsentation centre sur les relations La relation est-un :estun(PHILOSOPHE,HOMME)

La relation nationalit :nationalit(J.P.SARTRE,FRANCAIS)

La relation mortel? :estun(x,HOMME)mortel?(x,oui)

Objectif de ce domaine de recherche Question : comment reprsenter une connaissance afin : - qu'elle puisse tre exploite le plus efficacement possible - qu'elle occupe un espace mmoire le plus faible9 / 27

possible

Les rgles de production

Rponse : il n'y a pas de systme de reprsentation miracle. Il y a des systmes de reprsentation, chacun adapt une forme d'exploitation Les systmes de reprsentation existants Les rseaux smantiques, les prototypes, les objets proche de la pense humaine (comprhension aise) La logique, les rgles de production proche des mcanismes de raisonnement Les procdures li notre conception actuelle des ordinateurs Dfinition Une rgle de production est compose d'une partie prmisse (SI) = condition logique que doivent vrifier des faits d'une partie condition (ALORS) = actions oprer sur la base de faits Les actions usuelles : ajouter, modifier, effacer des faits Autres caractristiques possibles d'une rgle : - coefficients de certitude - contexte d'application (groupe de rgles) - Exemple (tir de MYCIN)10 / 27

SI le site de la culture est le sang ET l'identit de l'organisme n'est pas connu avec certitude ET la coloration de l'organisme est GRAM ngatif ET la morphologie de l'organisme est batonnet ET le patient a t srieusement brl ALORS l'identit de l'organisme est Pseudomas (0.4) Principe (dmarche dductive) entre : une base de faits F, une base de rgles R sortie : la base de faits F transforme algorithme :rpter S = ensemble des rgles applicables de R si S alors a = choix d'une rgle de S application de la rgle choisie a marquer la rgle a finsi jusqu' S =

Une stratgie de raisonnement : la marche avant

Une rgle applicable est une rgle : - non marque - dont la prmisse est satisfaite Un exemple Base de faits : A C D F Base de rgles : R1 R2 R3 R411 / 27

C

Une stratgie de raisonnement : la marche arrire

R1 : si E alors B R2 : si A

D alors E R3 : si A B F alors G R4 : si C D alors F Principe (dmarche hypothtico-dductive) entre : une base de faits F, une base de rgles R, un ensemble P de faits prouver sortie : la base de faits transforme F algorithme :tantque P extraire (en l'effaant) de P un fait f si le fait f est absent de F alors S = ensemble des rgles concluant sur f si S alors a = choix d'une rgle de S prouver tous les faits en prmisse de a si a est applicable alors appliquer la rgle a finsi finsi finsi fintantterminaison) (attention au problme du bouclage, donc de non

Un exemple Base de faits : A C D F Base de rgles : R1 R2 R3 R4 R1 : si E C alors B12 / 27

R2 D

Rsolutionstratgie de de Une de l'ensemble raisonnement : conflits la marche mixte

: si A alors E

R3 : si A B F alors G R4 : si C D alors F Faits prouver : G F Principe Fonctionner en marche arrire Ds qu'un fait nouveau est connu, fonctionner en marche avant Poursuivre la marche arrire Un exemple Base de faits : A C D F Base de rgles : R1 R2 R3 R4 R1 : si E C alors B R2 : si A D alors E R3 : si A B F alors G R4 : si C D alors F Fait prouver : G Rsoudre l'ensemble de conflits = choisir une rgle parmi celles applicables

Quelques stratgies courantes prendre la premire rgle de l'ensemble prendre la rgle qui conclut sur le plus de faits prendre la rgle qui a le plus de conditions13 / 27

Mta-connaissanceessayer toutes les rgles prendre la rgle qui travaille sur les faits les plus rcents prendre la rgle ayant la prmisse de plus fort coefficient de certitude En gnral, la stratgie est prdfinie une fois pour toute. Le Nec Plus Ultra considrer que slectionner une rgle parmi d'autres est un problme en soi, qui ncessite une expertise. Autrement dit, utiliser un autre systme expert pour oprer ce choix ! notion de mta-connaissance Niveau normal Les faits sont lis au problme rsoudre Une rgle agit sur les faits Niveau Mta Les mta-faits sont des informations sur la rsolution en cours : - fait en cours de preuve - rgles potentiellement applicables - stratgie adopte Une mta-rgle agit sur les mta-faits (donc indirectement sur les rgles)14 / 27

Ordre 0 et ordre 1Niveau Mta-Mta Il est possible de construire un nombre quelconque de niveaux mta. difficile apprhender conceptuellement Moteur d'infrences d'ordre 0 Le fonctionnement du moteur d'infrences peut s'expliquer l'aide de la logique des propositions seule. - aucune notion de variable n'est autorise - les seules actions autorises sont l'ajout et l'effacement de faits - toute rgle applique est limine exemplesi l'animalestunmammifre et l'animalpossdeunpelageraydenoiretdeblanc alorsl'animalestunzbre

Moteur d'infrences d'ordre 0+ Moteur d'ordre 0 autoris modifier des faits (par exemple un compteur que l'on incrmente). Une rgle applique n'est pas ncessairement efface. exemplesi latempratureest