Les systèmes experts

cours DEA IngénIA, 13 Octobre 1993

Phil. Reitz, LIRMM, département ARC

Plan

Pourquoi les Systèmes Experts
Préambule : IA et SE
L'IA en quelques mots
Le système GPS (Newell & Simon, 1956)
DENDRAL (Feigenbaum, 1965)
Premiers constats
Un premier cahier des charges d'un SE
Le système MYCIN (1974)
Structure générale d'un SE
Les faits
La représentation des connaissances
Les règles de production
Une stratégie de raisonnement : la marche avant
Une stratégie de raisonnement : la marche arrière
Une stratégie de raisonnement : la marche mixte
Résolution de l'ensemble de conflits
Méta-connaissance
Ordre 0 et ordre 1
La conception des SE aujourd'hui
Le langage PROLOG
PROLOG en un exemple
Les systèmes multi-experts
Construire une base de connaissance
Applications des SE
Conclusion
Bibliographie

Pourquoi les Systèmes Experts
Un constat navrant
Les experts d'un domaine ont pour caractéristiques :
	• d'être rares, donc peu disponibles
	• d'être compétents (si possible les meilleurs)
	• d'être souvent incapables d'expliquer leur démarche
	• d'être mortels

Les objectifs des SE
	• rendre une expertise accessible à tous
	• approcher au mieux la perfection
	• décortiquer 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) défauts de la nature humaine.

Les principales difficultés
	• comment programmer une machine pour en faire un expert
	• comment gérer les contradictions éventuelles entre différents experts
	• comment faire évoluer un tel système sans que ses compétences se dégradent (le paradoxe du trop-plein de connaissance)
Préambule : IA et SE
L'Intelligence Artificielle (IA)
Objectif : concevoir une machine dont le comportement est jugé intelligent
	Question : qu'est-ce qu'un comportement intelligent ?
		• démontrer un théorème ?
		• bien jouer aux échecs ?
		• lire un document puis répondre à des questions ?
		• exploiter son passé pour prévoir le futur ?
		• faire le ménage à la maison ?
	Question : qu'est-ce qu'être intelligent
		• simuler l'intelligence = être intelligent ?
		• une réponse : le test de Turing.

Le projet existe depuis les débuts de l'Informatique (~ 1940)
Les Systèmes Experts (SE)
L'un des rares succès industriels de l'Intelligence Artificielle
L'IA en quelques mots
Les disciplines de l'IA
Résolution de problèmes
Programmation automatique, apprentissage
Déduction, démonstration de théorèmes
Langages, formalismes de représentation des connaissances
Langage naturel
Reconnaissance de formes
Un domaine interdisciplinaire
Psychologie cognitive
Epistémologie
Neurobiologie
Sociologie

Les vrais débuts de l'Intelligence Artificielle
Le système GPS, en 1956 (résolution de problèmes)

Les premiers travaux contribuant à la naissance des SE
Le système DENDRAL, en 1965 (identification en chimie)

Le premier système expert digne de ce nom
Le système MYCIN, en 1974 (maladies du sang)
Le système GPS (Newell & Simon, 1956)
Objectif
Concevoir un système de résolution automatique de problèmes qui soit indépendant du problème à résoudre.
Contre-pied de la démarche classique
Démarche classique : programme = suite d'instructions
	Usager :
		• doit préciser les opérations à appliquer
		• doit indiquer dans quel ordre les appliquer
Démarche de GPS : la stratégie d'application des opérateurs est universelle
	Usager :
		• doit spécifier tous les opérateurs applicables
	GPS :
		• choisit l'opérateur selon le contexte
Principe
• une situation = état du résolveur à un instant donné
• un opérateur transforme une situation en une autre qui la rapproche d'une situation solution (degré de solution)
• GPS choisit l'opérateur qui minimise au mieux ce degré
Inconvénient
GPS peut ne pas aboutir à une solution, bien qu'il puisse en exister une (problème du minimum local, classique en optimisation)
Exemple
Parcours d'un labyrinthe
DENDRAL (Feigenbaum, 1965)
Objectif
Identifier une structure chimique à partir de résultats de mesures chimiques, physiques et spectrométriques.
Principe
Déduire des résultats de mesures toutes les informations possibles
Interroger l'usager si des informations sont manquantes
Faire une synthèse et conclure
Inconvénient
Programmé de manière classique
	Þ difficilement maintenable
Aucune possibilité d'explication
Premiers constats
• Le système travaille sur des données factuelles spécifiques d'un problème donné
• Le système applique des transformations dont la définition est indépendante du problème en cours de résolution, mais dépend du problème général à résoudre
• L'ordre d'application de ces transformations est dépendant du contexte, dont a priori non déterministe
• L'efficacité du système est liée à cet ordre d'application
Conclusion provisoire
• il faut séparer
	- les données d'un problème particulier
	- les opérations qui vont transformer ces données
• il faut éviter
	- de figer la stratégie de choix de l'opération à appliquer
	- d'avoir des opérations trop interdépendantes
Problèmes posés
Existe-t-il un système universel de codage répondant à ces exigences ? Þ représentation des connaissances
Quelles limitations sur le raisonnement sont induites par un tel système de représentation des connaissances ?
Un premier cahier des charges d'un SE
• Un système dans lequel la connaissance est facilement codée
	Þ Représentation de la connaissance
• Un système capable d'effectuer des inférences
	Þ Mécanismes de raisonnement (déduction, abduction)
• Un système facilement modifiable
	Þ Evolution de la connaissance
• Un système capable d'expliquer son raisonnement
	Þ Etre convaincu de la justesse des résultats
	Þ Essayer des alternatives, juste "pour voir"
Le système MYCIN (1974)
Objectif
Aide au diagnostic dans le domaine des maladies infectieuses, en particulier méningites et maladies du sang

Exemples de données factuelles
le site de la culture est le sang
le patient a été sérieusement brûlé (certitude 0.9)
Exemple d'opération ajoutant des informations
SI	le site de la culture est le sang
ET	l'identité de l'organisme n'est pas connue avec certitude
ET	la coloration de l'organisme est GRAM négatif
ET	la morphologie de l'organisme est bâtonnet
ET	le patient a été sérieusement brûlé
ALORS l'identité de l'organisme est Pseudomas (0.4)

Caractéristique intéressante
Les informations peuvent être incertaines
Structure générale d'un SE

SE de base = base de connaissance + moteur d'inférences

Base de connaissance = faits + règles + méta-règles + …
Moteur d'inférences : mécanisme de raisonnement, indépendant du domaine et du problème

Faits : mémoire à court terme, dépendant du problème
Règles : mémoire à long terme, indépendant du problème, dépendant du domaine
	Þ une règle manipule des faits
Méta-règles : mémoire à long terme, indépendant du problème, voire du domaine
	Þ une méta-règle manipule des règles
Les faits
Toute description d'une situation implique des entités liées par des relations
Un fait représente au moins une relation liant diverses entités
Représentation centrée sur les entités
Un homme en général :
	HOMME
		est-un MAMMIFERE
		mortel? (par défaut = oui)
Un philosophe en général :
	PHILOSOPHE
		est-un HOMME
		nationalité (par défaut = GREC)
Le philosophe J.P. Sartre :
	J.P.SARTRE
		est-un PHILOSOPHE
		nationalité FRANCAIS
Représentation centrée sur les relations
La relation est-un :
	est-un ( PHILOSOPHE, HOMME)
La relation nationalité :
	nationalité ( J.P.SARTRE, FRANCAIS )
La relation mortel? :
	est-un ( x, HOMME) ﬁ  mortel? ( x, oui )
La représentation des connaissances
Objectif de ce domaine de recherche
Question : comment représenter une connaissance afin :
	- qu'elle puisse être exploitée le plus efficacement possible
	- qu'elle occupe un espace mémoire le plus faible possible

Réponse : il n'y a pas de système de représentation miracle.
	Il y a des systèmes de représentation, chacun adapté à une forme d'exploitation

Les systèmes de représentation existants
Les réseaux sémantiques, les prototypes, les objets
	Þ proche de la pensée humaine (compréhension aisée)
La logique, les règles de production
	Þ proche des mécanismes de raisonnement
Les procédures
	Þ lié à notre conception actuelle des ordinateurs
Les règles de production
Définition
Une règle de production est composée
	• d'une partie prémisse (SI)
		= condition logique que doivent vérifier des faits
	• d'une partie condition (ALORS)
		= actions à opérer sur la base de faits
Les actions usuelles : ajouter, modifier, effacer des faits

Autres caractéristiques possibles d'une règle :
	- coefficients de certitude
	- contexte d'application (groupe de règles)
	- …
Exemple (tiré de MYCIN)
SI	le site de la culture est le sang
ET	l'identité de l'organisme n'est pas connue avec certitude
ET	la coloration de l'organisme est GRAM négatif
ET	la morphologie de l'organisme est bâtonnet
ET	le patient a été sérieusement brûlé
ALORS l'identité de l'organisme est Pseudomas (0.4)
Une stratégie de raisonnement :
la marche avant
Principe (démarche déductive)
entrée : une base de faits F, une base de règles R
sortie : la base de faits F transformée
algorithme :
	répéter
		S = ensemble des règles applicables de R
		si S ≠ Ø alors
			a = choix d'une règle de S
			application de la règle choisie a
			marquer la règle a
		finsi
	jusqu'à S = Ø

Une règle applicable est une règle :
	- non marquée
	- dont la prémisse est satisfaite
Un exemple
Base de faits : A C D F
Base de règles : 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
Une stratégie de raisonnement :
la marche arrière
Principe (démarche hypothético-déductive)
entrée : une base de faits F, une base de règles R, un ensemble P de faits à prouver
sortie : la base de faits transformée F
algorithme :
	tantque P ≠ Ø
		extraire (en l'effaçant) de P un fait f
		si le fait f est absent de F alors
			S = ensemble des règles concluant sur f
			si S ≠ Ø alors
				a = choix d'une règle de S
				prouver tous les faits en prémisse de a
				si a est applicable alors
					appliquer la règle a
				finsi
			finsi
		finsi
	fintant (attention au problème du bouclage, donc de non terminaison)
Un exemple
Base de faits : A C D F
Base de règles : 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
Faits à prouver : G F
Une stratégie de raisonnement :
la marche mixte
Principe
Fonctionner en marche arrière
Dès qu'un fait nouveau est connu, fonctionner en marche avant
Poursuivre la marche arrière
Un exemple
Base de faits : A C D F
Base de règles : 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
Résolution de l'ensemble de conflits
Résoudre l'ensemble de conflits = choisir une règle parmi celles applicables

Quelques stratégies courantes
prendre la première règle de l'ensemble
prendre la règle qui conclut sur le plus de faits
prendre la règle qui a le plus de conditions
essayer toutes les règles
prendre la règle qui travaille sur les faits les plus récents
prendre la règle ayant la prémisse de plus fort coefficient de certitude

En général,
la stratégie est prédéfinie une fois pour toute.

Le Nec Plus Ultra
considérer que sélectionner une règle parmi d'autres est un problème en soi, qui nécessite une expertise.
Autrement dit, utiliser un autre système expert pour opérer ce choix !
	Þ notion de méta-connaissance
Méta-connaissance
Niveau normal
Les faits sont liés au problème à résoudre
Une règle agit sur les faits

Niveau Méta
Les méta-faits sont des informations sur la résolution en cours :
	- fait en cours de preuve
	- règles potentiellement applicables
	- stratégie adoptée
Une méta-règle agit sur les méta-faits
	(donc indirectement sur les règles)

Niveau Méta-Méta …
Il est possible de construire un nombre quelconque de niveaux méta.
	Þ difficile à appréhender conceptuellement
Ordre 0 et ordre 1
Moteur d'inférences d'ordre 0
Le fonctionnement du moteur d'inférences peut s'expliquer à l'aide de la logique des propositions seule.
	- aucune notion de variable n'est autorisée
	- les seules actions autorisées sont l'ajout de faits
	- toute règle appliquée est éliminée
exemple
	si	l'animal est un mammifère
	et	l'animal possède un pelage rayé de noir et de blanc
	alors l'animal est un zèbre
Moteur d'inférences d'ordre 0+
Moteur d'ordre 0 autorisé à modifier des faits (par exemple un compteur que l'on incrémente).
Une règle appliquée n'est pas nécessairement effacée.
exemple
	si	la température est < 30°C
	et	la consigne est ≤ 50
	alors ajouter 2 à la consigne
Moteur d'inférences d'ordre 1
Le fonctionnement du moteur s'explique avec la logique des prédicats :
	- notion de variable et d'appariement (unification)
Une règle appliquée reste toujours possiblement applicable
exemple
	si	X est un homme
	alors X est mortel
La conception des SE aujourd'hui
Conception de A à Z (programmation du moteur, etc…)
de plus en plus rare…

Utilisation de générateurs de SE (moteurs d'inférences nus)
M1, OPS5, MP-LRO

Usage de langages de programmation pour l'IA
Langages fonctionnels : LISP, ML, CAML
Langages logiques : PROLOG
Le langage PROLOG
Moteur d'inférences d'ordre 1
Langage de programmation
Langage d'expression de requêtes à une base de données

Historique
1972, Univ. de Marseille
en 1985, adopté par les Japonais pour le projet "5ème génération"

Conclusion
Un langage idéal pour construire rapidement des prototypes de SE.
PROLOG en un exemple
Ecrire des faits
père(pierre, michel) .
père(michel, paul) .

Poser des questions (réduire des buts)
père(X, Y) ?
X = pierre Y = michel
X = michel Y = paul

père(michel, X) ?
X = paul

Ecrire des règles
grand-père(X, Z) :- père(X, Y), père(Y, Z) .

grand-père(X, paul) ?
X = pierre
Les systèmes multi-experts
Proposition naïve
Pour disposer d'un SE ayant plusieurs domaines d'expertise, il suffit :
	• d'un simple moteur d'inférences et d'indiquer dans les règles le domaine dont elles dépendent
	• de plusieurs SE, chacun expert dans un domaine, contrôlés par un SE qui supervise le tout et activera le bon SE

Ces solutions ont été essayées, sans grand succès

Des propositions étudiées dans les laboratoires
• Les tableaux noirs
	La base de faits est une mémoire partagée par divers experts (sources de connaissance)
	Chaque expert réagit dès qu'il y a une modification de la base qui le concerne
	Chaque expert n'agit que sur une partie de la base
		Þ systèmes multi-agents
			Þ vie artificielle 
Construire une base de connaissance
Collaboration cogniticien-expert
Interview de l'expert par le cogniticien
Codage par le cogniticien de la connaissance extraite
Confrontation du système avec l'expert

Apprentissage automatique
Donnée par l'expert d'une série de problèmes résolus
Induction par la machine d'une base de règles capable de retrouver les solutions proposées aux problèmes de l'expert
Confrontation du système avec l'expert

Les principales difficultés
Trouver une stratégie d'extraction de connaissance qui soit efficace et universelle
Vérifier la cohérence de la base de connaissance

Conclusion provisoire
L'expert est :
	- au début, enchanté : explicitation de sa connaissance (il apprend lui-même de l'analyse de son propre savoir ainsi mis à plat)
	- ensuite, inquiet : la compétence du SE semble réelle
	- enfin, rassuré : il existe toujours des problèmes que le SE ne sait pas résoudre, malgré les multiples révisions de la base de connaissance
Applications des SE
tous les domaines :
	Chimie (DENDRAL)
	Géologie (PROSPECTOR)
	Economie - Finances
	Droit
	Médecine (MYCIN)
	Diagnostic de pannes
	…

Conclusion
Prometteurs, mais n'ont pas encore vraiment convaincu les industriels
La raison essentielle : nous ne savons pas encore concevoir une machine capable d'acquérir une connaissance et l'exploiter à bon escient, quel que soit le domaine.
Comment augmenter l'efficacité du SE tout en le rendant modifiable à volonté
Produire une argumentation
explication, objection à une proposition de l'usager
Prendre en compte toute contestation-confirmation
Adapter le comportement du SE à son usager
Bibliographie
C. Bonnet : IA, promesses et réalités (InterEditions, 1984)
M.O. Cordier : Les SE (revue La Recherche, n°151, Jan 1984)
C. Ernst : Introduction aux SE de gestion (Eyrolles, 1985)
H. Farreny : les SE, principes et exemples (Cepadues, 1985)
J.L. Laurière : les SE (revue TSI, Vol 1, n°1 & 2, 1982)
…