Licence Informatique

Module Théories et Modèles pour l'Informatique II


Option Programmation logique en Prolog 

Philippe Collard

 


Atelier 4 : Application aux Systèmes Experts


Composants de base

Base de connaissance :

Les connaissances sont propres au domaine d’expertise

Règles de production (si prémisse alors conclusion)

Moteur d’inférences :

Le mécanisme d’exploitation est indépendant du domaine


Moteur d’inférences

Le cycle de base :

1.     Phase de restriction

Eliminer les connaissances trivialement inutilisables

2.     Phase de filtrage

Déterminer l’ensemble de résolution de conflits (i.e les connaissances potentiellement utilisables)

3.     Phase de résolution de conflit

Sélectionner la ou les connaissances qui seront effectivement exploitées lors de la phase d’exécution

Par exemple, toutes les connaissances, la première, choix aléatoire, coût, intérêt, …

4.     exécution

 

 

Caractéristiques d’un moteur d’inférences :

Mode d’invocation des règles

·        Chaînage avant : sélection d’une règle selon sa prémisse

1.     phase de restriction : les faits établis

2.     phase de filtrage : les règles dont la prémisse est vérifiée

3.     recherche indépendante de l’objectif

·        Chaînage arrière : sélection d’une règle selon ses conclusions

1.     phase de restriction : les faits à établir

2.     phase de filtrage : les règles dont la conclusion contient des faits à  établir

3.     recherche dirigée par le but

 

Régime

·        irrévocable : les choix réalisés en phase de résolution de conflit ne sont jamais remis en cause

·        par tentatives : on considère plusieurs éléments dans l’ensemble de conflit

 

Moteur d’inférences interactif

Interroger l’utilisateur pour obtenir des connaissances immédiatement exploitables par le moteur

 

Capacités d’explications

·        Objectif : renforcer la crédibilité du système

·        Expliquer :

pourquoi le moteur pose telle question

comment le moteur a pu obtenir telle réponse

 


1.   Prolog : un moteur d’inférences !


Mode d’invocation des règles : ?

Régime : ?

Interactif : ?

Capacités d’explications : ?

 

Un premier exemple :

 

Base de connaissance symbolique :

Base des faits initiaux :

a,c,d,e,g,h,k

Base de règles :

1. si k et w et m alors i

2. si i et w et j alors q

3. si f et h alors b

4. si a et b alors q

5. si c et h alors r

6. si r et j et m alors s

7. si g alors f

8.  si w et n et o et p alors q

 

Par exemple, si on demande d’établir le fait q, les règles 2, 4 et 8 forment l’ensemble de conflit. On choisira par exemple la première ; cela aura pour effet de substituer à q dans la liste des faits à établir les faits i, w et j

Implémentation de la base de connaissance et du moteur d’inférences en Prolog

:- unknown(trace,fail).

%------------------------

% BASE DES FAITS ETABLIS

%------------------------

a.

c.

d.

e.

g.

h.

k.

%-----------------------

% BASE DES REGLES

%-----------------------

i :- k,w,m.

%----------------

q :- i,w,j.

q :- a,b.

q :- w,n,o,p.

%----------------

b :- f,h.

%----------------

r :- c,h.

%----------------

s :- r,j,m.

%----------------

f :- g.

%----------------------

% MOTEUR D’INFERENCES

%-----------------------

expertiser(L) :- si(effacer(L),ecrire_succes(L),ecrire_echec(L)).

%---------------------

effacer([]).

effacer([But|AutresButs]) :- But, effacer(AutresButs).

%---------------------

ecrire_succes(L) :- print_conjonction(L,succes).

ecrire_echec(L)  :- print_conjonction(L,echec).

%---------------------

print_conjonction([T],Etat) :- ! , write('le fait ')

     , write(T)

     , si(Etat=succes, write(' est etabli'), write(' n''est pas etabli')), nl.

print_conjonction(L,Etat) :- write('la conjonction de faits ')

     , print_conjonction(L)

     , si(Etat=succes, write(' est etablie'), write(' n''est pas etablie')), nl.

%----------------------

print_conjonction([]).

print_conjonction([T])  :- !,write(T).

print_conjonction([T|Q]):- write(T),write(' et '),print_conjonction(Q).

%----------------------

si(C,A,_):- C,!,A.

si(_,_,S) :- S.

 

Exemples d’exécution

?- expertiser([q]).

le fait q est etabli

?- expertiser([i]).

le fait i n'est pas etabli

?- expertiser([q,a,i]).

la conjonction de faits q et a et i n'est pas etablie

?- expertiser([q,a,h]).

la conjonction de faits q et a et h est etablie


2. Redéfinir un moteur d’inférences « au dessus » de Prolog


Mode d’invocation des règles : chaînage arrière

Régime : par tentatives

Capacités d’explications : oui (répondre au « comment »)

Interactif : non


Question 2.1

Dans une première étape, nous allons (simplement) redéfinir Prolog « au dessus » de Prolog. Pour ce faire nous allons utiliser le prédicat rule/2 en mode in,out.  Ce prédicat met en relation la tête et le corps d’une règle. Par exemple on pourra obtenir toutes les règles de la procédure q/0

?- rule(q, Corps).

Corps = [i , w , j] ;

Corps = [a , b] ;

Corps = [w , n , o , p] ;

No

Redéfinir la procédure effacer/1 de telle façon que le comportement globale du système expert ne soit pas modifié

effacer([]).

effacer([But|AutresButs]) :-  ? .

 

Question 2.2

Nous pouvons maintenant ajouter des capacités d’explication : le moteur devra justifier ses réponses en fournissant une « explication » de son raisonnement. Plus précisément, suite à un succès, le moteur devra fournir la trace des inférences. Par exemple on aura la session suivante :

?- expertiser([q]).

Le fait q est etabli

q ?

      a est un fait etabli

      b ?

            f ?

                  g est un fait etabli

            h est un fait etabli

 La trace des inférences est une liste définie comme suit :

·        Si on efface un fait f, la trace est [f]

·        Si on efface une règle tete :- b1,b2,…,bn la trace est la liste [tete,trace_b1,trace_b2,…, trace_bn]trace_bi est la trace des inférences relatives à l’effacement du but bi

·        Si on efface une conjonction de buts, la trace est la liste des traces relatives à l’effacement de chaque but

 Par exemple :

·        la trace résultant de l’effacement de a est [[a]]

·        la trace résultant de l’effacement de q est [[q, [a], [b, [f, [g]], [h]]]]

 

Compléter le programme suivant dans lequel on a ajouté un second argument au prédicat effacer pour implémenter la trace des inférences

expertiser(L) :- si(effacer(L, Trace), ecrire_succes(L, Trace), ecrire_echec(L)).

%--------------------------------------------

effacer([] , ???).

effacer([But|AutresButs], ???) :- ???.

%--------------------------------------------

ecrire_succes(L, Trace) :-

     print_conjonction(L,succes),

     afficher_trace(Trace).

%----------------------------------------------

afficher_trace(T) :- afficher_trace(T,0).

%----------------------------------------------

afficher_trace([],_):-!.

afficher_trace([C],Ident) :- atom(C),!,

     tab(Ident), write(C),write(' est un fait etabli'),nl.

afficher_trace([C,X|Y],Ident):- atom(C),!,

     tab(Ident), write(C), write(' ?'), nl,

     NewIdent is Ident+4,

     afficher_trace(X, NewIdent),

     afficher_trace(Y,NewIdent).

afficher_trace([X|Y], Ident) :-

     afficher_trace(X, Ident),

     afficher_trace(Y, Ident).

 

Question 2.3

Modifier la procédure effacer pour éviter d’inférer (en appliquant des règles) plusieurs fois le même fait

Voici quelques exemples de session :

?- expertiser([f])

le fait f est etabli

f ?

g est un fait etabli

 

?- expertiser([f])

le fait f est etabli

f est un fait etabli

 

effacer([But|AutresButs],[[But|TraceSousButs]|TraceAutresButs]) :-

     rule(But,SousButs), effacer(SousButs,TraceSousButs),

% si (But a ete infére en utilisant une regle) alors ajouter But dans la base des faits établis

     si(?????????),

     effacer(AutresButs,TraceAutresButs).

 

Dans cette question la base de connaissance est gérée dynamiquement ; vous devez donc ajouter les directives suivantes au début du fichier source prolog

:- unknown(trace, fail).

:- dynamic b/0,f/0,i/0,j/0,n/0,o/0,p/0,q/0,r/0,s/0,w/0.

 


3. Moteur d’inférences interactif : où comment questionner pour inférer …


Mode d’invocation des règles : chaînage arrière

Régime : par tentatives

Capacités d’explications : oui (répondre au « comment »)

Interactif : oui


Vous allez ajouter au moteur des capacités d’interactions avec l’utilisateur. Plus précisément, dans le cas où le moteur échoue dans l’effacement d’un but, il n’existe plus alors de clause utilisable, le système devra interroger l’utilisateur pour savoir s’il considère que le but à effacer est un fait ; dans l’affirmative, on ajoutera ce fait dans la base des faits établis et on poursuivra les inférences.

Cette capacité d’interaction introduit une nouvelle catégorie de faits : les faits négatifs ; c’est à dire ceux qui ont été infirmés par l’utilisateur. Un fait sera donc soit  :

·        positif, c’est à dire initialement établi, ou bien établi par l’utilisateur (suite à une question concernant ce fait)

·        négatif, infirmé par l’utilisateur (suite à une question concernant ce fait)

·        indéterminé, on ne connaît pas sa valeur de vérité (considéré comme faux par Prolog en vertu de l’hypothèse du « monde clos »)

Il suffit de représenter dans la base de connaissance uniquement les faits positifs et les faits négatifs.

·         Les faits positifs seront représentés directement par un fait Prolog. Par exemple, si l’utilisateur répond positivement à la question  le fait f est-il établi? on ajoutera dynamiquement le fait f en utilisant l’instruction asserta(f)

·         Les faits négatifs seront représentés par un fait Prolog. Par exemple, si l’utilisateur répond par la négative à la question le fait f est-il établi? on ajoutera dynamiquement le fait negatif(f) en utilisant l’instruction asserta(negatif(f))

On veillera à garantir la monotonie (un fait ne peut pas changer de valeur de vérité) et la cohérence (un fait ne peut pas avoir deux valeurs de vérité). Par conséquent, on interrogera l’utilisateur sur la véracité d’un fait uniquement si ce fait n’est pas négatif et s’il ne peut pas être effacé par le moteur, soit qu’il n’existe pas de clauses dont la tête s’unifient avec lui, soit que de telles clauses existent mais ne permettent pas de l’effacer.

Question 3.1

Développer un moteur d’inférences interactif en complétant la version précédente (question 2)

effacer([],[]).

% La liste des buts n'est pas vide

effacer([But|_], _) :- ???, !, ???.

% La liste des buts n'est pas vide et But n'est pas un fait negatif

effacer([But|AutresButs], ???) :- ???, ! , ???.

% La liste des buts n'est pas vide et

% But n'est pas un fait negatif et

% But n'a pas pu etre effacé par Prolog

effacer([But|AutresButs] , ???) :-

    write('le fait '), write(But), write(' est-il etabli ? (o./n.):'), nl, read(R),

    si(R='o' , ?????? ).

 

Voici quelques exemples de session :

?- expertiser([i]).

le fait w est-il etabli ? (o./n.):

|: o.

le fait m est-il etabli ? (o./n.):

|: o.

le fait i est etabli

i ?

    k est un fait etabli

    w est un fait etabli

    m est un fait etabli

 

?- expertiser([i]).

le fait w est-il etabli ? (o./n.):

|: o.

le fait m est-il etabli ? (o./n.):

|: n.

le fait i est-il etabli ? (o./n.):

|: n.

le fait i n'est pas etabli

 

Question 3.2

Adapter le moteur pour que l’utilisateur ait la possibilité de « passer » une question. Dans ce cas, le système abandonne la voie qu’il est en train d’explorer, comme si la réponse était négative. Aucune information n’est mémorisée concernant la véracité du fait ; le système pourra donc reposer ultérieurement la même question

 

effacer([],[]).

% La liste des buts n'est pas vide

effacer([But|_], _) :- ??? , !, ??? .

% La liste des buts n'est pas vide et But n'est pas un fait negatif

effacer([But|AutresButs], ??? ) :- ??? , !, ???.

% La liste des buts n'est pas vide et

% But n'est pas un fait negatif et

% But n'a pas pu etre effacé par Prolog

effacer([But|AutresButs], ??? ) :-

     write('le fait '), write(But), write(' est-il etabli ? (o./n./p.):'), nl, read(R),

     si(R='o', ??? , si(R='p', ???, ??? )).

 

Question 3.3

Compléter la procédure effacer pour que le système puisse expliquer pourquoi il pose une question.

Si on utilise une règle t :- b1,…,bi,…,bn. dans le but d’effacer la tête t, la « liste pourquoi » commune à tous les sous-buts bi est la liste [t|q] ou q est la « liste pourquoi » relative à la tête t de la règle.

Pour implémenter la « liste pourquoi » commune à tous les buts de la liste figurant en premier argument du prédicat effacer, il suffit d’ajouter un troisième argument à ce prédicat. Ainsi, on aura une procédure effacer/3 qui met en relation

·         Une liste de buts à effacer,

·         Une liste qui permet d’expliquer comment le système expert a pu effacer tous ces buts,

·         Une liste qui permet d’expliquer pourquoi le système tente d’effacer ces buts.

 

Voici un exemple de session :

?- expertiser([q]).

Je pose cette question pour etablir i puis q

le fait w est-il etabli ? (o./n./p.):

|: o.

Je pose cette question pour etablir i puis q

le fait m est-il etabli ? (o./n./p.):

|: o.

Je pose cette question pour etablir q

le fait j est-il etabli ? (o./n./p.):

|: o.

le fait q est etabli

q ?

    i ?

        k est un fait etabli

        w est un fait etabli

        m est un fait etabli

    w est un fait etabli

    j est un fait etabli

 

 

 


4.  Un expert qui attribue des coefficients de confiance


Mode d’invocation des règles : chaînage arrière

Régime : par tentatives

Capacités d’explications : oui (répondre au « comment »)

Interactif : non

Coefficient de confiance : oui


On suppose dans cette partie que l’expert attribue à chaque règle de la base de connaissance un coefficient de confiance qui mesure la fiabilité de la règle.

 

On propose d’implémenter une règle tete:-corps affecté d’un coefficient de confiance c par une règle Prolog de la forme tete:‑[c|corps]. Par exemple la règle q :- a,b.

affectée du coefficient de confiance 7 sera représentée par la règle q :- [7,a,b].

On pourra par exemple avoir la base de connaissance suivante :

% base des faits etablis

a.

c.

d.

e.

g.

h.

k.

% base des regles

i :- [6,k,w,m].

%----------------

q :- [5,i,w,j].

q :- [7,a,b].

q :- [2,w,n,o,p].

%----------------

b :- [6,f,h].

%----------------

r :- [5,c,h].

%----------------

s :- [9,r,j,m].

%----------------

f :- [6,g].

 

On suppose que le coefficient de confiance est un nombre entier positif.

 

Question 4.1

 

Modifier la procédure effacer/2 développée dans la question 2 pour inférer dans un paquet de clauses (i.e une procédure)  uniquement la règle la plus fiable (celle qui possède le plus grand coefficient de confiance) . On pourra utiliser les prédicats prédéfinis clause/2 et setof/3.

?- clause(a,X).

X = true ;

 

?- clause(q,X).

X = [5, i, w, j] ;

X = [7, a, b] ;

X = [2, w, n, o, p] ;

 

?- setof(X,clause,L).

X = _G158

L = [true] ;

 

?- setof(X,clause(q,X),L).

X = _G158

L = [[2, w, n, o, p], [5, i, w, j], [7, a, b]] ;

 

 

Question 4.2

 

Modifier la procédure effacer/2 développée dans la question précédente pour incrémenter le coefficient de confiance d’une règle dont on vient d’effacer le corps.

?- clause(q,L).

L = [8, i, w, j] ;

L = [7, a, b] ;

L = [2, w, n, o, p] ;

 

?- assert(:-(q,[3,m,n])).

Yes

 

?- clause(q,L).

L = [8, i, w, j] ;

L = [7, a, b] ;

L = [2, w, n, o, p] ;

L = [3, m, n] ;

 

Question 4.3

 

Modifier la procédure effacer/2 développée dans la question précédente pour décrémenter le coefficient de confiance d’une règle dont l’effacement du corps vient d’échouer

 

Correction question 4

 

effacer([],[]).

 

effacer([But|AutresButs],[[But|TraceSousButs]|TraceAutresButs]) :-

     setof(X,clause(But,X),ListeDesCorps),  % pour declencher uniquement la regle la plus fiable

     si(ListeDesCorps=[true],SousButs=[],last([Coef|SousButs],ListeDesCorps)),  % pour declencher uniquement la regle la plus fiable

     effacer(SousButs,TraceSousButs),!,

     si(SousButs=[], true, maj_coef_regle(inc, But, [Coef |SousButs])),

     effacer(AutresButs,TraceAutresButs).

    

effacer([But|_],_) :- % dans la regle precedente on a echouer dans l'effacement de  : effacer(SousButs,TraceSousButs)

     setof(X,clause(But,X),ListeDesCorps),  % pour declencher uniquement la regle la plus fiable

     si(ListeDesCorps=[true],SousButs=[],last([Coef|SousButs],ListeDesCorps)),

     si(SousButs=[],true , maj_coef_regle(dec, But, [Coef |SousButs])),

     fail.

    

%---------------------

maj_coef_regle(M,Tete,[OldCoef|Corps]) :- %la clause est donc une regle

      si(M=inc, NewCoef is OldCoef+1, NewCoef is OldCoef-1),

      retract(:-(Tete,[OldCoef|Corps])),

      assert( :-(Tete,[NewCoef|Corps])).


Annexe


 

clause(?Head, ?Body)

Succeeds when Head can be unified with a clause head and Body with the corresponding clause body. Gives alternative clauses on backtracking. For facts Body is unified with the atom true. Normally clause/2 is used to find clause definitions for a predicate, but it can also be used to find clause heads for some body template.

 

setof(+Var, +Goal, -Set)

Equivalent to bagof/3, but sorts the result using sort/2 to get a sorted list of alternatives without duplicates.

 

last(?Elem, ?List)

Succeeds if Elem unifies with the last element of List. If List is a proper list last/2 is deterministic. If List has an unbound tail, backtracking will cause List to grow.

 

assert(+Term)

Assert a fact or clause in the database. Term is asserted as the last fact or clause of the corresponding predicate.

 

Number is +Expr

Succeeds when Number has successfully been unified with the number Expr evaluates to. If Expr evaluates to a float that can be represented using an integer (i.e, the value is integer and within the range that can be described by Prolog's integer representation), Expr is unified with the integer value.