REPRESENTATION DES CONNAISSANCES & SYSTEMES EXPERTS

Les repr sentations proc durales sont utilis es dans le d veloppement des strat gies de

r solution des conflits dans les syst mes experts, ainsi que dans les attachements proc duraux

du langage des Frames (les objets structur s).

1.3. Repr sentation objets des connaissances

Lorganisation des objets en classes constitue une part vitale de la repr sentation des

connaissances. Les classes servent organiser et simplifier la base de connaissances

travers lh ritage. Si lon dit que toutes les instances de la cat gorie Nourriture sont

comestibles et quon affirme que Fruits est une sous-classe de Nourriture et que Pomme est

une sous-classe de Fruits, alors on peut inf rer que toutes les pommes sont comestibles. On

dit que les pommes individuelles h ritent de la propri t de comestibilit parce quelles

appartiennent la classe Nourriture. Les relations de sous-classe organisent les classes en

une taxonomie.

1.3.1. R seaux s mantiques

Les r seaux s mantiques pr sentent une structure de graphe dans laquelle les nSuds sont des

concepts et les arcs sont les liens entre ces concepts. Un concept peut correspondre une

classe, une sous-classe, une instance, une situation ou une action. Les liens entre les concepts

peuvent tre binaires ou n-aires. Dans le dernier cas, il sagit darcs dencadrement d crivant

une action ou une situation donn e.

Les liens entre les concepts sont exprim s par des relations s mantiques propres la

connaissance exprimer. Il existe trois types pr d finis de relations entre concepts : est-un

(isa), sorte-de (ako), partie-de (part-of). Le lien est-un exprime une relation instance/classe, le

lien sorte-de exprime une relation classe/sous-classe et le lien partie-de exprime des relations

entre objets.

Lh ritage et la composition de relations constituent les notions de base du principe

dinf rence dans les r seaux s mantiques. Une requ te nest autre quun fragment dun

r seau s mantique qui sera mis en concordance avec le r seau s mantique global pour

identifier linconnu.

1.3.2. D pendances conceptuelles

La d pendance conceptuelle a t d velopp e par R. Schank partir de 1969 sur la base de

ses travaux sur la compr hension du langage naturel. Elle cherche offrir un cadre de

description de la r alit . Schank propose de d crire les significations partir de 11 actions

primitives :

3

Wided Lejouad-Chaari

a. Actes physiques :

• PROPEL : appliquer une force un objet physique ;
• MOVE : d placer une partie dun corps ;
• &

b. Actes caract ris s par le changement d tat qui en r sulte :

• PTRANS : changer lemplacement dun objet physique ;
• &

On d signe le processus de cr ation dun repr sentant dune classe par le terme

dinstanciation, lobjet cr est une instance. Ainsi, la visite de notre ami Jean son p re est

une instance dun changement demplacement PTRANS, soit un nSud particulier PTRANS_1

cr partir dun nSud g n rique PTRANS.

Laction PTRANS_1 a n cessairement : un acteur (qui effectue le transport), un objet

(transport ), un point de d part, un point darriv e et une date.

Personne

INST

INST

PTRANS

LIEU

Nom

Acteur

INST

A

Situ

Nom

&

Personne_1

PTRANS_1

Lieu_1

Personne_2

&

Objet

Date

&

DE

&

P re de

Jean rend visite son p re

Fig.1. Exemple de Repr sentation par D pendance Conceptuelle

1.3.3. Frames, Prototypes, Scripts

Les Frames sont des r seaux de relations s mantiques complexes statiques, tir s de r alit s

psychologiques du raisonnement humain

Le raisonnement humain se r f re des prototypes d j en m moire et

les compare aux objets, v nements, & dune situation nouvelle.

La structure mod le (les frames et les scripts) a t d velopp e en 1975 par Minsky au

MIT. Lid e des frames est doffrir un support permettant de regrouper lensemble des

informations disponibles sur un objet. On parle de mod les, dinstances et dh ritage.

Les traits principaux sont les suivants :

4

Wided Lejouad-Chaari

1. La structure de la base sert d crire des objets g n riques, des mod les dobjets,

partir desquels on d rivera (par instanciation) les objets particuliers. Par exemple, un

frame d crira une chaise, et une instance de ce frame g n rique sera la chaise de

Paul.

2. Une autre cat gorie de filiation peut tre tablie entre les mod les, permettant de

rattacher un mod le g n rique donn un super-mod le, plus g n ral. Par exemple,

le frame chaise peut tre rattach un frame plus g n ral meuble.

3. Un m canisme dh ritage permet dattribuer aux structures qui descendent dun

prototype (sous-classes ou instances) les caract ristiques de leur anc tre. Par

exemple, si lon d finit le mod le si ge comme un meuble fait pour sasseoir et dot

de pieds, le tabouret ou la chaise auront les m mes caract ristiques, auxquelles on

ajoutera seulement labsence de dossier pour le tabouret et sa pr sence pour la

chaise.

Le frame constitue un cadre dans lequel sont rassembl es les caract ristiques de lobjet

mod le. A lint rieur dun champ (attribut), plusieurs l ments peuvent tre d crits. Ces

l ments, appel s facettes sont des donn es ou des comportements attach s lattribut :

-

-

-

-

valeur : valeur de lattribut ;

doit tre (require) : sp cifie un domaine de d finition (nombre entier, cha ne de

caract res, (0, 1, 2), &) ;

par d faut (default) : indique la valeur qui devra tre admise en labsence

dindications sp cifiques ;

si n cessaire (if-needed) : pr cise la conduite tenir si la valeur nest pas disponible

et si lon en a besoin. Ceci peut se pr senter sous plusieurs formes :

a. un calcul ;

b. un pointeur vers un l ment susceptible de contenir linformation ;

c. un appel dune proc dure (attachement proc dural).

Exemples :

Frame

Voiture

Attributs

sorte-de Vehicule

marque

Facettes

domaine (Peugeot, Renault, Citro n)

defaut Renault

Frame Chaise

sorte_de :

nombre_de_pieds : doit tre entier

Meuble

style_du_dossier :

nombre_de_bras :

par d faut 4

doit tre Droit, Rembourr

doit tre 0, 1 ou 2

Frame Chaise_de_Paul

sorte_de :

nombre_de_pieds : 4

style_du_dossier : Rembourr

nombre_de_bras : 0

Chaise

5

Wided Lejouad-Chaari

Les attributs sorte-de et est-un d crivent la hi rarchie des Frames. Dans une description de

Frame, on peut d crire aussi des propri t s (taille, ge, couleur), des propri t s structurelles

(partie-de), des relations entre objets (pr s, loin) et des r les (p re, ami).

Les facettes expriment des valeurs par d faut, des contraintes (description des valeurs

admises) et des d mons utilis s la lecture ou modification dune valeur dun attribut. Ainsi,

les d mons sont des proc dures lanc es automatiquement quand certains v nements se

produisent. Les facettes if added , if removed d crivent les actions entreprendre lorsquune

modification (adjonction ou suppression) est effectu e sur la valeur dun champ.

Exemple de facette d faut en FRL

Meeting

Day

$DEFAULT (ToDay)

Exemple de facette de contraintes en KEE

Unit Attendant

Memberslot : Profession

Value.Class : (INTERSECTION MEN (UNION DOCTORS Lawyers))

Cardinality : [1 2]

Exemple de facette contenant des valeurs complexes en KEE

Unit John Member.of Attendant

Ownslot : Hobby

Value.Class : (Art)

Cardinality : [0 2]

Value (Singer, Painter)

Comment 3Dont let him sing3

Aspects proc duraux

if-needed:

if-added:

if-removed: gestion dint grit ;

gestion des buts;

propagation de valeurs;

Exemple en FRL :

Activity

AKO

WHO $REQUIRE

$VALUE

Thing

(AKO Person)

$IF-NEEDED (Ask)

WHEN $REQUIRE

(AKO Interval)

$IF-ADDED (AddToCalendar)

Raisonnement automatique

Il sagit dalgorithme bas sur les propri t s structurelles (rapide), il fait les inf rences

usuelles travers lh ritage, les contraintes et les d mons. Les facettes de contraintes assurent

le maintien automatique de lint grit s mantique (type, cardinalit , &) laffectation dune

nouvelle valeur. Le raisonnement avec les d mons peut tre vu comme suit :

6

Wided Lejouad-Chaari

-

-

if-needed : quelle est la valeur de ? raisonnement dirig par les buts

cha nage arri re ;

if-added : on vient dannoncer & raisonnement dirig par les donn es

cha nage avant ;

Lh ritage de structure correspond la fa on dont la structure se transmet la cr ation dun

frame fils (certains/tous les champs, certaines/toutes les facettes). Alors que lh ritage de

valeur correspond la fa on dont les valeurs se transmettent de p re fils.

Attachement proc dural

Il sagit de liens d finissant le comportement des objets la r ception de messages. Une

primitive de transmission de message, active les objets (ex. construction send en Le_Lisp).

Frames et r gles

Les Frames ne sont pas contradictoires avec les r gles. Lutilisation des deux formalismes

m ne la d finition de syst mes hybrides. Il y a, ainsi, une perte duniformit et de simplicit

mais un gain defficacit , de flexibilit et de naturel .

Avantages et limites des Frames :

• Clart et coh rence du canevas tabli pour stocker les informations dont la structure

reproduira une architecture famili re au sp cialiste utilisateur.

• D finition concise gr ce la sp cialisation.
• Economie de stockage obtenue par le m canisme dh ritage.

• Forte rigidit de la structure, qui ne pourra saccommoder de donn es non conformes

au canevas pr d fini. N anmoins, cette rigidit est temp r e par la richesse de loutil,

qui permet de faire face de nombreux besoins de repr sentation.

• Faible volutivit des structures une fois d finies : structure complexe et volume de

donn es important (bien r fl chir avant de constituer la structure).

Scripts

La notion de scripts (sc nario) a t introduite, sur le mod le des frames, par Schank et

Abelson (1977) pour d crire, non plus des objets, mais des sc nes de la vie courante.

Exemple :

Script Manger_au_Restaurant

El ments : (Restaurant, Argent, Nourriture, Menu, Tables, Chaises)

R les : (Personnes_Affam es, Serveurs, Chefs)

Point_de_vue : Personnes_Affam es

Moment : (Heures_Ouverture du Restaurant)

Lieu : (Emplacement du Restaurant)

7

Wided Lejouad-Chaari

Sc nario

Dabord :

puis :

puis :

puis :

puis :

script Entrer_au_Restaurant

script Attirer_Attention_du_Ma tre_dh tel

script Prendre_Place_ _Table

script Passer_Commande

script Manger

sauf_si (Longue_Attente)

alors script Sortie_en_col re

puis :

puis :

enfin :

si (Qualit _Nourriture > Convenable)

alors script F liciter_le_Chef

script Payer_laddition

script Quitter_Restaurant

Conclusion

Il nexiste pas de formalisme de repr sentation de connaissances universel. De plus en plus de

travail est fait par les langages : Langages Objet sur Lisp ou Prolog, &

2. Introduction aux syst mes experts

2.1. Bref historique

La recherche sur les Syst mes Experts (SE) est apparue un moment o il y avait une baisse

dint r t de la part des chercheurs pour la repr sentation de m canismes universels

incapables de r soudre des probl mes particuliers (le compromis entre g n ralit et

efficacit ). Edward Feigenbaum commen a au d but des ann es soixante sint resser la

repr sentation des m canismes de raisonnement. Ces efforts ont abouti la cr ation dun

projet Dendral en 1971.

Apr s des progr s consid rables apport s par la recherche sur les m canismes de

raisonnement dans des domaines particuliers, comme la m decine avec Mycin (1976) et la

g ologie avec Prospector (1979), il y eut un nouvel engouement pour d velopper des outils

g n raux de repr sentation des connaissances dans les diff rents domaines particuliers ; la

recherche sur les syst mes experts a pu tre ainsi nouveau consid r e comme faisant

pleinement partie de lIntelligence Artificielle (IA). Entre-temps la recherche sur les

d monstrations de th or mes et la r solution de probl mes (Newell et Simon 1972) avaient

beaucoup progress , fournissant les bases th oriques de la m thodologie des Syst mes Base

de Connaissances (SBC).

Le programme Dendral poss dait une immense quantit de connaissances sp cialis es en

chimie, la moindre am lioration quon lui apportait tait fort co teuse apr s des ann es de

d veloppement : les connaissances propres au domaine taient int gr es aux m canismes de

raisonnement. Petit petit a merg lid e fondamentale quil fallait s parer la masse des

connaissances du domaine, de ses m canismes dinterpr tation.

Extraire des SE les m canismes universels de raisonnement

r utilisables dun domaine lautre.

8

Wided Lejouad-Chaari

La m thodologie syst me-expert est justifi e pour des probl mes o lon peut examiner

exhaustivement toutes les solutions potentielles en un temps raisonnable , en utilisant la

puissance de calcul des ordinateurs.

2.2. Quest ce quun syst me expert ?

Un syst me expert est un programme poss dant une grande masse de connaissances dans un

domaine sp cialis , ces connaissances provenant g n ralement dun expert humain. Il ne

sagit pas seulement de repr senter dans lordinateur une expertise humaine, il a fallu aussi

d velopper des m thodes permettant des am liorations continuelles pendant la phase o

lexpert humain d voile ses m thodes et ses connaissances au cogniticien.

Le cogniticien est cet informaticien charg daider

la production des connaissances puis leur formalisation et leur implantation.

L volution des travaux dans le domaine ont conduit repr senter s par ment les

connaissances des m canismes logiques dinterpr tation de ces connaissances. Ce qui permet

de les modifier plus ais ment surtout quelles prennent une forme d clarative et elles sont

repr sent es sans ordre pr d fini dutilisation.

2.3. R les des syst mes experts

Dans bon nombre dactivit s intellectuelles qualifi es, le savoir-faire des experts humains

nest pas suffisamment structur pour que lon dispose dalgorithmes repr sentatifs de ces

activit s. Dans ces domaines, le savoir-faire des sp cialistes est repr sent comme un

ensemble dunit s ou REGLES, chacune tant appropri e pour une situation ventuelle.

Historiquement, la notion de syst me expert est apparue loccasion de linformatisation de

t ches intellectuelles normalement assur es par des experts tels que m decins, g ologues,

ing nieurs, etc.

2.4. Anatomie des syst mes experts

Larchitecture de base des syst mes experts est repr sent e par le sch ma suivant :

DONNEES

Base de

connaissances

Interpr teur

Faits

SOLUTION

Fig.2. Composants dun syst me expert

9

Wided Lejouad-Chaari

a. La base de faits : elle comprend des faits permanents du domaine (ex. lO dium est

un champignon) et des faits propres un probl me r soudre (ex. le plant de

tomate tudi a des t ches jaunes sur les feuilles), que lon appelle aussi des

donn es. Cest la m moire de travail du syst me expert.

b. La base de connaissances : elle est constitu e de r gles de production qui

permettent g n ralement de tirer des conclusions qui ajoutent de nouveaux faits

dans la base de faits, partir de ceux d j connus. Une r gle comporte une partie

gauche exprimant des conditions et une partie droite contenant des conclusions. Un

coefficient de vraisemblance peut tre d fini, il exprime la croyance que lon a sur

la v racit dune pr misse ou la confiance accord e une conclusion (il varie entre

+1 et 1).

c. Le moteur dinf rences : il exploite la base de connaissances en fonction du

contenu de la base de faits afin de mener un raisonnement sur le probl me pos . Il

comprend un algorithme de filtrage (pattern-matching) qui v rifie si la pr misse

dune r gle est v rifi e dans la base de faits. Une pr misse est un ensemble de

clauses logiques reli es par des ET et/ou des OU logiques.

Le filtrage est simple r aliser si les r gles dinf rences ne contiennent que des

constantes (logique des propositions), plus compliqu lorsquelles contiennent des

variables (logique des pr dicats). Dans ce dernier cas, lalgorithme est appel

unificateur.

En logique des pr dicats, une r gle donn e peut tre d clench e

pour diff rentes instanciations des variables (plusieurs fois), alors quen logique des

propositions, une r gle nest d clench e quune fois au plus.

2.5. Principe de fonctionnement des moteurs dinf rences

Le moteur dinf rences fonctionne selon un cycle de base. Une r gle peut tre repr sent e

comme suit :

REGLE = <DECLENCHEUR> + <CORPS>

Le moteur encha ne des cycles de travail comportant chacun deux phases : une phase

d valuation et une phase dex cution.

PHASE DEVALUATION

Elle comprend 3 tapes : la s lection, le filtrage et la r solution de conflits.

a. La s lection : elle d termine partir dun tat BF de la base des faits et dun tat BR

de la base des r gles, un sous-ensemble F de BF et un ensemble R1 de BR qui, a

priori, m ritent d tre compar s lors de l tape de filtrage.

b. Le filtrage : le moteur dinf rences compare la partie d clencheur de chacune des

r gles de R1 par rapport lensemble F de faits. Un sous-ensemble R2 de R1

10

Wided Lejouad-Chaari

rassemble alors les r gles jug es compatibles avec F (celles dont les conditions de

d clenchement ont t jug es satisfaites). R2 est appel ensemble de conflits.

c. La r solution de conflits : le moteur d termine les r gles, soit un sous-ensemble R3

de R2, qui doivent tre effectivement d clench es.

PHASE DEXECUTION

Le moteur dinf rences commande la mise en Suvre des actions d finies par les r gles de

lensemble R3 sil est non vide.

2.6. R gimes irr vocables ou par tentatives (retours-arri re)

Lorsque R3 est vide certains moteurs tr s simples sarr tent : on dit que ces moteurs ont un

r gime de contr le irr vocable. Dautres moteurs reconsid rent lensemble de conflits (R2)

dun cycle ant rieur et examinent la possibilit de d clencher dautres r gles de R2.

Si aucun des d clenchements de r gles r alis s depuis le pr c dent choix dans R2 nest remis

en cause, c- -d si les effets de ces r gles ne sont pas annul s, on dit encore que ces moteurs

fonctionnent selon un r gime de contr le irr vocable.

On parle de r gime de contr le par tentatives lorsquil y a remplacement de d clenchements

de r gles par dautres.

Lorsquun moteur revient sur une r solution de conflits ant rieur,

en remettant en cause des d clenchements de r gles, on dit quil op re un retour-arri re ou

backtracking.

Lorsquune impasse est rencontr e au cycle n, un retour-arri re est r alis au cycle n+1 par

retour au contexte du cycle n-1. Il sagit dun retour-arri re chronologique.

2.7. Strat gies de r solution de conflits

Il existe de nombreuses strat gies de r solution de conflits. La mani re la plus couramment

utilis e, lorsque plusieurs r gles sont a priori applicables dans une situation donn e, consiste

les d clencher suivant certaines priorit s :

• d clenchement s lectif dun sous-ensemble de r gles r sultant de lapplication de

m ta-r gles ;

• d clenchement prioritaire des r gles dont la partie pr misse est la plus d taill e. La

raison en est quelles engendrent des conclusions plus pr cises ;

• d clenchement prioritaire des r gles utilisant les informations les plus r cemment

acquises ou d duites ;

• d clenchement prioritaire des r gles amenant le plus grand nombre de conclusions ;

-

classement des r gles en fonction de lint r t des conclusions quelles apportent, en

fonction dun ordre dans la liste des buts ;

• d clenchement ordonn par plausibilit d croissante des conclusions dans le cas o

elles ont un poids associ ;

11

Wided Lejouad-Chaari

Lattribution des priorit s peut tre faite selon plusieurs m thodes :

• par un algorithme directement b ti dans le moteur dinf rences (intrins que) et qui

calcule dynamiquement le meilleur ordre dapplication de ces r gles ;

• par des m tar gles qui s lectionnent les r gles par leur contenu et les ordonnent en

fonction de crit res pouvant d pendre du probl me traiter. Cette m thode est

parfois utilis e conjointement la premi re ;

• par une tape de compilation des r gles effectu e au moment de leur saisie par le

module dacquisition des connaissances.

2.8. Diff renciations entre syst mes experts selon les aptitudes du moteur

Les moteurs dinf rences charg s du raisonnement et de linterpr tation des connaissances

nont pas tous la m me proc dure de fonctionnement. Ils varient dun syst me expert un

autre.

a. Modes fondamentaux dinvocation des r gles

Cha nage-avant

Un moteur dinf rences fonctionne en cha nage-avant (des donn es vers les buts) lorsque

les faits de la base de faits, sur lesquels portent les d clencheurs des r gles, repr sentent

des informations dont la valeur de v rit est d j tablie.

Cha nage-arri re

Un moteur dinf rences fonctionne en cha nage-arri re (des buts vers les donn es)

lorsque :

-

-

-

-

certains faits de la base des faits sont consid r s comme tant tablir ou valuer,

on les appelle souvent probl mes (en suspens, r soudre) ou hypoth ses (

v rifier) ou buts ( atteindre) ;

les d clencheurs des r gles se r f rent uniquement aux probl mes en suspens ;

lorsquune r gle est d clench e, de nouveaux probl mes, d finis par le corps de la

r gle, peuvent tre introduits dans la base des faits, titre de nouveaux probl mes en

suspens ;

les probl mes auxquels se r f re le d clencheur sont consid r s r solus lorsque les

probl mes introduits par le d clenchement de la r gle , soit sav rent tre des

probl mes d clar s a priori comme primitifs (consid r s comme r solus), soit

ont t r solus au pr alable. Ainsi, linf rence d crite par la r gle est effectivement

ex cut e.

Cha nage mixte (bidirectionnel)

Certains syst mes fonctionnent en cha nage mixte :

• une partie des faits de la base des faits est consid r e comme tant tablir (ce sont

les probl mes , dautres sont consid r s comme tablis (les faits proprement dits).

• Les conditions des r gles peuvent porter simultan ment sur des faits de lune ou

lautre sorte.

12

Wided Lejouad-Chaari

Exemple de fait tabli : la temp rature dun malade.

Exemple de fait tablir : le malade a la jaunisse hypoth se justifier.

b. Modes dinf rences

Dans son principe, le m canisme de base du cha nage-avant consiste v rifier, dune part

de la pr sence dun fait P dans la base des faits tablis, et dautre part, de la pr sence dans

la base des r gles dune r gle dont le d clencheur est P et le corps Q, pour d cider quun

fait Q sera m moris dans la base des faits tablis.

Le cha nage-avant correspond troitement au mode dinf rence valide connu en logique

sous le nom de modus ponens qui peut tre exprim , dun point de vue pratique, par :

Si P implique Q est vrai, et si P est vrai, alors Q est vrai .

Cependant,

la plupart des syst mes experts autorisent des variables quantifi es

universellement dans les r gles. Dans ce cas le m canisme de base du cha nage-avant

sappuie sur lexistence dune r gle dont le d clencheur est de la forme P(x) et le corps de

la forme Q(x), o x est une variable, et sur lexistence dun fait tabli P(a), pour introduire

Q(a) dans la base des faits tablis.

Il sagit donc dune combinaison du mode dinf rence modus ponens et du mode

dinf rence appel sp cialisation universelle selon lequel : Si R(x) est vrai " x, alors R(a)

est vrai . En loccurrence, par sp cialisation on peut affirmer que :

Si P(x) implique Q(x) est vrai " x, alors P(a) implique Q(a) est vrai

do on conclut par modus ponens, puisque P(a) est vrai, que Q(a) est vrai.

Le m canisme de base du cha nage-arri re permet lintroduction dun probl me P d s lors

quil existe une r gle de corps P et de d clencheur Q, et quil existe un probl me Q. Les

syst mes admettant des variables dans les r gles utilisent la sp cialisation universelle pour

invoquer une r gle dont le d clencheur est de la forme Q(x) lorsquil existe un probl me

Q(a).

D s quun probl me P, ant rieurement introduit par cha nage-arri re via une r gle R (dont

P est le corps et Q le d clencheur), est reconnu r solu on peut appliquer la sp cialisation et

le modus ponens partir de la r gle R pour conclure que Q est r solu, une information qui

pourra son tour tre propag e par sp cialisation et modus ponens partir de la r gle qui a

introduit Q, etc.). Pour utiliser les r gles, il faut mettre une logique dinf rence indiquant

quand, comment utiliser une r gle. Il existe des m canismes utilis s par le moteur

dinf rence expliquant lutilisation dune r gle, savoir les th or mes de d duction :

Modus ponens

Modus tollens

Fait P

R gle P Q

---------

Q

Conclusion

Fait Q

R gle P Q

---------

P

Conclusion

13

Wided Lejouad-Chaari

c. Strat gies de d veloppement de la recherche

Aux modes dinvocation de r gles on superpose toujours lune ou lautre des strat gies

classiques de d veloppement de la recherche dans les espaces d tats ou les espaces de

sous-probl mes.

Repr sentation...