REPRESENTATION DES CONNAISSANCES & SYSTEMES EXPERTS

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, … d’une situation nouvelle.

La structure « modèle » (les frames et les scripts) a été développée en 1975 par Minsky au MIT. L’idée des frames est d’offrir un support permettant de regrouper l’ensemble des informations disponibles sur un objet. On parle de modèles, d’instances et d’hé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 d’objets, à 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 d’héritage permet d’attribuer aux structures qui descendent d’un prototype (sous-classes ou instances) les caractéristiques de leur ancêtre. Par exemple, si l’on définit le modèle siège comme un meuble fait pour s’asseoir et doté de pieds, le tabouret ou la chaise auront les mêmes caractéristiques, auxquelles on ajoutera seulement l’absence 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 l’objet modèle. A l’intérieur d’un champ (attribut), plusieurs éléments peuvent être décrits. Ces éléments, appelés facettes sont des données ou des comportements attachés à l’attribut :

- -

-

-

valeur : valeur de l’attribut ; 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 l’absence d’indications spécifiques ; si nécessaire (if-needed) : précise la conduite à tenir si la valeur n’est pas disponible et si l’on en a besoin. Ceci peut se présenter sous plusieurs formes :

a. un calcul ; b. un pointeur vers un élément susceptible de contenir l’information ; c. un appel d’une 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 d’une valeur d’un 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 lorsqu’une modification (adjonction ou suppression) est effectuée sur la valeur d’un 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 ″Don’t let him sing″

Aspects procéduraux

if-needed: if-added: if-removed: gestion d’inté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 s’agit d’algorithme basé sur les propriétés structurelles (rapide), il fait les inférences usuelles à travers l’héritage, les contraintes et les démons. Les facettes de contraintes assurent le maintien automatique de l’intégrité sémantique (type, cardinalité, …) à l’affectation d’une 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 d’annoncer … »  raisonnement dirigé par les données 

chaînage avant ;

L’héritage de structure correspond à la façon dont la structure se transmet à la création d’un frame « fils » (certains/tous les champs, certaines/toutes les facettes). Alors que l’héritage de valeur correspond à la façon dont les valeurs se transmettent de père à fils.

Attachement procédural

Il s’agit 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. L’utilisation des deux formalismes mène à la définition de systèmes hybrides. Il y a, ainsi, une perte d’uniformité et de simplicité mais un gain d’efficacité, 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 d’héritage.

- Forte rigidité de la structure, qui ne pourra s’accommoder de données non conformes au canevas prédéfini. Néanmoins, cette rigidité est tempérée par la richesse de l’outil, 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

D’abord : puis : puis : puis : puis :

script Entrer_au_Restaurant script Attirer_Attention_du_Maître_d’hô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_l’addition script Quitter_Restaurant

Conclusion

Il n’existe 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 d’inté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 à s’intéresser à la représentation des mécanismes de raisonnement. Ces efforts ont abouti à la création d’un 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 l’Intelligence 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 qu’on 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é l’idée fondamentale qu’il fallait séparer la masse des connaissances du domaine, de ses mécanismes d’interprétation.

Extraire des SE les mécanismes « universels » de raisonnement réutilisables d’un domaine à l’autre.

8

Wided Lejouad-Chaari

La méthodologie système-expert est justifiée pour des problèmes où l’on peut examiner exhaustivement toutes les solutions potentielles en un temps « raisonnable », en utilisant la puissance de calcul des ordinateurs.

2.2. Qu’est ce qu’un 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 d’un expert humain. Il ne s’agit pas seulement de représenter dans l’ordinateur une expertise humaine, il a fallu aussi développer des méthodes permettant des améliorations continuelles pendant la phase où l’expert humain dévoile ses méthodes et ses connaissances au cogniticien.

Le cogniticien est cet informaticien chargé d’aider à 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 d’interprétation de ces connaissances. Ce qui permet de les modifier plus aisément surtout qu’elles prennent une forme déclarative et elles sont représentées sans ordre prédéfini d’utilisation.

2.3. Rôles des systèmes experts

Dans bon nombre d’activités intellectuelles qualifiées, le savoir-faire des experts humains n’est pas suffisamment structuré pour que l’on dispose d’algorithmes représentatifs de ces activités. Dans ces domaines, le savoir-faire des spécialistes est représenté comme un ensemble d’unités ou REGLES, chacune étant appropriée pour une situation éventuelle. Historiquement, la notion de système expert est apparue à l’occasion de l’informatisation 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

L’architecture 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 d’un système expert

9

Wided Lejouad-Chaari

a. La base de faits : elle comprend des faits permanents du domaine (ex. l’Oï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 l’on appelle aussi des données. C’est 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 l’on a sur la véracité d’une prémisse ou la confiance accordée à une conclusion (il varie entre +1 et –1).

c. Le moteur d’infé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 d’une 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 d’inférences ne contiennent que des constantes (logique des propositions), plus compliqué lorsqu’elles contiennent des variables (logique des prédicats). Dans ce dernier cas, l’algorithme 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 qu’en logique des propositions, une règle n’est déclenchée qu’une fois au plus.

2.5. Principe de fonctionnement des moteurs d’inférences

Le moteur d’infé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 d’exécution.

PHASE D’EVALUATION

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

a. La sélection : elle détermine à partir d’un état BF de la base des faits et d’un é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 d’inférences compare la partie déclencheur de chacune des règles de R1 par rapport à l’ensemble 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 D’EXECUTION

Le moteur d’inférences commande la mise en œuvre des actions définies par les règles de l’ensemble R3 s’il est non vide.

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

Lorsque R3 est vide certains moteurs très simples s’arrêtent : on dit que ces moteurs ont un régime de contrôle irrévocable. D’autres moteurs reconsidèrent l’ensemble de conflits (R2) d’un cycle antérieur et examinent la possibilité de déclencher d’autres règles de R2.

Si aucun des déclenchements de règles réalisés depuis le précédent choix dans R2 n’est 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 lorsqu’il y a remplacement de déclenchements de règles par d’autres.

Lorsqu’un moteur revient sur une résolution de conflits antérieur, en remettant en cause des déclenchements de règles, on dit qu’il opère un retour-arrière ou backtracking.

Lorsqu’une 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 s’agit d’un 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 d’un sous-ensemble de règles résultant de l’application 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 qu’elles 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 l’intérêt des conclusions qu’elles apportent, en fonction d’un 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

L’attribution des priorités peut être faite selon plusieurs méthodes :

- par un algorithme directement bâti dans le moteur d’inférences (intrinsèque) et qui

calcule dynamiquement le meilleur ordre d’application 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 d’acquisition des connaissances.

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

Les moteurs d’inférences chargés du raisonnement et de l’interprétation des connaissances n’ont pas tous la même procédure de fonctionnement. Ils varient d’un système expert à un autre.

a. Modes fondamentaux d’invocation des règles

Chaînage-avant

Un moteur d’infé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 d’infé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 ; lorsqu’une 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 s’avè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, l’infé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 », d’autres sont considérés comme établis (les faits proprement dits). - Les conditions des règles peuvent porter simultanément sur des faits de l’une ou

l’autre sorte.

12

Wided Lejouad-Chaari

Exemple de fait établi : la température d’un malade. Exemple de fait à établir : « le malade a la jaunisse » hypothèse à justifier.

b. Modes d’inférences

Dans son principe, le mécanisme de base du chaînage-avant consiste à vérifier, d’une part de la présence d’un fait P dans la base des faits établis, et d’autre part, de la présence dans la base des règles d’une règle dont le déclencheur est P et le corps Q, pour décider qu’un fait Q sera mémorisé dans la base des faits établis.

Le chaînage-avant correspond étroitement au mode d’inférence valide connu en logique sous le nom de modus ponens qui peut être exprimé, d’un 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 s’appuie sur l’existence d’une 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 l’existence d’un fait établi P(a), pour introduire Q(a) dans la base des faits établis.

Il s’agit donc d’une combinaison du mode d’inférence modus ponens et du mode d’inférence appelé spécialisation universelle selon lequel : Si R(x) est vrai  x, alors R(a) est vrai. En l’occurrence, par spécialisation on peut affirmer que :

Si P(x) implique Q(x) est vrai  x, alors P(a) implique Q(a) est vrai d’où 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 l’introduction d’un problème P dès lors qu’il existe une règle de corps P et de déclencheur Q, et qu’il 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) lorsqu’il existe un problème Q(a).

Dès qu’un 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 d’inférence indiquant quand, comment utiliser une règle. Il existe des mécanismes utilisés par le moteur d’inférence expliquant l’utilisation d’une 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 d’invocation de règles on superpose toujours l’une ou l’autre des stratégies classiques de développement de la recherche dans les espaces d’états ou les espaces de sous-problèmes.

Représentation par espace d’états

Les règles sont considérées comme des opérateurs de changements d’états de la base des faits. L’espace des états correspondant à une application particulière est potentiellement défini par application de toutes les règles, depuis l’état initial qui est convenu être la base initiale.

L’espace des états est représenté comme un graphe orienté dont chaque sommet Ei figure un état , tandis que chaque arc EiEj symbolise l’application d’une règle transformant l’état Ei de la base des faits en l’état Ej. Un état-objectif (succès de la recherche) sera défini comme :

- une base de faits dans laquelle sera apparu un fait satisfaisant certaines

caractéristiques ;

- une base de faits dont auront disparu tous les faits à établir ; - une base de faits telle qu’aucune règle ne peut lui apporter de modification (arrêt

par saturation).

Représentation par espace de sous-problèmes

En cas de chaînage-arrière, on peut considérer les règles comme des opérateurs de décomposition de problèmes (les faits à établir) en sous-problèmes (d’autres faits à établir). L’espace des sous-problèmes peut être représenté par un graphe orienté de type ET-OU. Chaque sommet symbolise soit un problème Pi, soit une application ARj d’une règle.

…

Pi *

* ….

…

=ARp

AR1 =

P1,1 *

…

* P1,q

…

Décomposition du problème Pi par plusieurs applications de règles AR1…ARp.

Fig.3. Une partie de graphe ET-OU représentant un espace de sous-problèmes. L’application de règle AR1 décompose le problème Pi en sous-problèmes

P1,1 … P1,q.

Un état-objectif est atteint si la partie explorée de l’espace des sous-problèmes permet d’affirmer que le problème initial est résolu, au moyen de :

14

Wided Lejouad-Chaari

- un sommet-problème représentant un problème primitif est par définition considéré

comme résolu.

- un sommet-problème dont un fils (sommet-règle) au moins est étiqueté résolu sera

aussi résolu.

- un sommet-règle dont tous les fils (sommet-problèmes) sont étiquetés rés