Systèmes Experts
Examen Exercises
Exercices à faire et à Projet
Systèmes Experts rendre pendant le TD
Projet: développement
Richard Moot 33%
et programmation d’un
[Link]@[Link] mini système expert
50%
en Prolog
17%
Examen
Définition
“un logiciel intelligent qui utilise des
connaissances et des inférences logiques
pour résoudre des problèmes qui sont
suffisamment difficiles pour nécessiter une
expertise humaine important pour trouver
une solution” (Feigenbaum 1982)
Systèmes Experts
Dans quelles situations peut-on utiliser des
un système expert est un logiciel qui sait systèmes experts?
donner des recommandations — pour une
domaine et une application bien défini — au
même niveau d’un expert humain de ce
domaine.
Systèmes Experts Systèmes Experts
Quand on peut Quand on peut
résoudre le problème résoudre le problème
par un appel par un appel
téléphonique à un téléphonique à un
expert en moins que expert en moins que
15 minutes 15 minutes
En plus de détail
Les besoins justifient le coût de
développement; le problème ne peut pas être
résolu avec l’informatique traditionnel
Le problème est bien structuré et ne dépend Systèmes Experts
pas (trop) de bon sens “common sense” Exemples
Il y a des experts qui sont disponibles et qui
savent bien s’exprimer sur le sujet
La taille du problème se prête bien à un
système expert.
Exemples - Exemples -
Diagnose Surveillance
dans le domaine médical, mais détection de fraudes avec
aussi en informatique cartes de crédit et téléphones,
aide au surveillance continu des
patients
Exemples -
Exemples - Planning/
Surveillance Scheduling
détection de fraudes avec gestion de personnel, machines,
cartes de crédit et téléphones, ressources
aide au surveillance continu des
patients
Exemples -
Finance Systèmes Experts
aide a l’affectation du crédit
immobilier ou du crédit à une Architecture
entreprise, calcul des risques
pour assurances, prédiction des
marchés
Système Expert Système Expert
Architecture de Base de
Architecture de Base de
systèmes experts connaissances systèmes experts connaissances
Système d’Inférences Généralement, ce sont des Système d’Inférences
A partir d’entretiens avec des règles du type:
Logiques si on affecte du personnel pour Logiques
experts, on extrait un base de
données avec des connaissances Expertise Faits la garde de nuit et si c’est la Expertise Faits
spécifiques à ce domaine. soirée d’une fête nationale
Utilisateur alors assure la présence d’un Utilisateur
médecin en plus que pour une
nuit normale
Système Expert Système Expert
Architecture de Base de
Architecture de Base de
systèmes experts connaissances systèmes experts connaissances
Généralement, ce sont des Système d’Inférences Généralement, ce sont des Système d’Inférences
règles du type: règles du type:
si plusieurs retraits de plus de Logiques si p et q alors r Logiques
100 euros chacun sont fait et si Expertise Faits (avec probabilité X) Expertise Faits
ces retrait sont fait dans des
différents pays alors une Utilisateur C’est à dire des formules Utilisateur
utilisation frauduleuse est très logiques éventuellement avec
probable (probabilité 0.9) des probabilités
Système Expert Système Expert
Architecture de Base de
Architecture de Base de
systèmes experts connaissances systèmes experts connaissances
Le système d’inférences Système d’Inférences L’avantage ce façon d’organiser Système d’Inférences
logiques établit une conclusion un système expert est qu’on a
grâce à l’information fourni par Logiques besoin de changer que la base Logiques
l’utilisateur et au base des Expertise Faits de connaissances pour obtenir Expertise Faits
connaissances. un système expert dans un
Utilisateur autre domaine Utilisateur
Système Expert Système Expert
Architecture de Base de
Architecture de Base de
systèmes experts connaissances systèmes experts connaissances
L’interaction avec l’utilisateur Système d’Inférences Idéalement, l’utilisateur peut Système d’Inférences
prend typiquement le forme demander le système expert
d’une dialogue, où le système Logiques d’expliquer son raisonnement: Logiques
expert pose des questions pour Expertise Faits pourquoi pose-t-il cette Expertise Faits
aider à trouver la bonne question? comment est-il arrivé
solution Utilisateur à cette conclusion? Utilisateur
Architecture des
Logique des Propositions
systèmes experts
La base de données des connaissances ainsi
que le système d’inférence sont fondés sur la
logique et l’inférence logique,
Alors, on a besoin de commencer par une Littéralement au
petite introduction en logique et déduction coeur des ordinateurs
automatique,
On finira par voir comment ces principes
donnent un langage de programmation:
PROLOG, PROgrammation en LOGique.
Logique des Propositions Logique des Propositions
Classique Classique — Syntaxe
On coupe le monde en petit morceaux, des
phrases simples comme “il fait beau” ou “le
soleil gravite autour de la terre” qui sont soit
1. Une proposition atomique est une proposition,
vrai (indiqué par la valeur 1) soit faux
(indiqué par la valeur 0). [Link] X est une proposition (pas nécessairement
atomique) alors ¬X — “non X” ou “la négation
Comme abstraction, on remplace ces phrases
de X” — est une proposition,
par des lettres p,q,r,… qu’on appelle des
propositions atomiques ou des formulas
atomiques.
Logique des Propositions Logique des Propositions
Classique — Syntaxe Classique — Syntaxe
[Link] X et Y sont des propositions alors,
3.a. (X!Y) “X et Y”
3.b. (X"Y) “X ou Y” [Link] d’autre n’est une proposition.
3.c. (X!Y) “si X alors Y”
3.d. (X Y) “X si et seulement si Y”
sont aussi des propositions
Logique des Propositions Logique des Propositions
Classique — Syntaxe Classique — Syntaxe
Une formule correspond naturellement à un
arbre, par exemple le formule (p!¬q)!r
Grâce a cette définition on peut démontrer que
correspond à l’arbre:
(p!¬q) !
est une proposition mais aussi que ! r
(p!qr)
p ¬
n’est pas une proposition.
Logique des Propositions Logique des Propositions
Classique — Syntaxe Classique — Modélisation
On appelle les noeuds dans cet arbre les sous- On assume d’avoir une méthode pour vérifier si
formules de ce formule. Alors p, q, r, ¬q, p!¬q une proposition atomique est vrai ou faux.
et (p!¬q)!r même sont tous de sous-formules
de (p!¬q)!r. ! !
! r ! r
p ¬ p ¬
q q
Logique des Propositions Interprétation des
Classique — Modélisation Propositions Complexes
p “le feu est vert”
q “il y un piéton en train de traverser”
r “j’avance au vitesse maximale” L’interprétation d’un formule complexe
! dépend que de l’interprétation de ses sous-
formules directs.
! r
Alors, étant donné une interprétation pour les
p ¬ prépositions atomiques, on peut trouver
X!Y X Y
¬X X
0 0 0
0 1 0 0 1
0 1 0
1 0
1 1 1
¬: négation logique !: “et” logique
X"Y X Y X"Y X Y
0 0 0 0 0 0
1 0 1 1 0 1
1 1 0 1 1 0
1 1 1 1 1 1
": “ou” logique
Remarque
le “ou” logique est inclusif, aux menus “dessert ou fromage” et “vin ou café”
ne veulent pas dire “aux moins un des deux”, mais plutôt “exactement un”
X!Y X Y X!Y X Y
1 0 0 1 0 0
1 0 1 1 0 1
0 1 0 0 1 0
1 1 1 1 1 1
!: implication logique
L’implication logique est peut-être le connecteur le plus difficile à
comprendre. Aucun causalité entre X et Y ne peut être déduit! X!Y est
faux que quand X est vrai et Y est faux et vrai dans tous les autres cas.
Logique des Propositions
X Y X Y
Classique — Modélisation
1 0 0 p “le feu est vert” vrai
q “il y un piéton en train de traverser” vrai
0 0 1
r “j’avance à la vitesse maximale” faux
0 1 0 !
! r
1 1 1
p ¬
: “équivalence” logique q
Logique des Propositions Logique des Propositions
Classique — Modélisation Classique — Modélisation
p “le feu est vert” vrai p “le feu est vert” vrai
q “il y un piéton en train de traverser” vrai q “il y un piéton en train de traverser” vrai
r “j’avance à la vitesse maximale” faux r “j’avance à la vitesse maximale” faux
! !
! r ! r
1 ¬ 1 ¬
q 1
Logique des Propositions Logique des Propositions
Classique — Modélisation Classique — Modélisation
p “le feu est vert” vrai p “le feu est vert” vrai
q “il y un piéton en train de traverser” vrai q “il y un piéton en train de traverser” vrai
r “j’avance à la vitesse maximale” faux r “j’avance à la vitesse maximale” faux
! !
! 0 ! 0
1 ¬ 1 0
Logique des Propositions Logique des Propositions
Classique — Modélisation Classique — Modélisation
p “le feu est vert” vrai p “le feu est vert” vrai
q “il y un piéton en train de traverser” vrai q “il y un piéton en train de traverser” vrai
r “j’avance à la vitesse maximale” faux r “j’avance à la vitesse maximale” faux
! 1
0 0 Alors, (p!¬q)!r est vrai
Vérifier tout les valeurs Vérifier tout les valeurs
de vérité de vérité
Des fois on s’intéresse à savoir pour quels
valeurs de vérité des formules atomiques un
formule complexe est vrai ou faux, Par contre, décider si un formule est valide,
un tautologie ou une contradiction est
S’il se trouve qu’un formule X n’est jamais difficile.
vrai, on parle d’une contradiction
Car, pour a formules atomiques, il y a 2a
Sinon on le formule X est valide,
combinaisons à vérifier.
De plus, s’il se trouve X est toujours vrai, on
parle d’un tautologie
Algorithme: Algorithme:
comment construire un table de comment construire un table de
vérité pour un formule vérité pour un formule
1. On fait un table avec:
[Link] pour chaque formule X dont on a
1 ligne pour chaque combinaison de valeurs
énuméré tout les possibilité de valeurs de ses
de vérité pour les formules atomique
sous-formules direct, on remplit la colonne
1 colonne pour chaque sous-formule de la qui correspond a X grâce à la définition du
formule. table de vérité pour ce connecteur.
[Link] remplit les lignes et les colonnes [Link] jusqu’au moment où on a rempli
correspondant aux formules atomique en tous les champs du table.
énumérant toutes les possibilités.
tautologie tautologie
p!p p p!p p
0 0
Il nous reste à remplir la
L’exemple le plus 1 colonne p!p. 1 1
simple possible: un
On vérifie la table de vérité
proposition atomique, X!Y X Y
pour X!Y. Pour p!p on a
p, et une implication. juste deux cas.
1 0 0
p peut être soit faux X = 1 et Y = 1, qui donne 1
1 0 1
(0) soit vrai (1).
X = 0 et Y = 0, qui donne 1
0 1 0
1 1 1
tautologie tautologie
p!p p p!p p
Il nous reste à remplir la
1 0 colonne p!p. 1 0
Il nous reste à remplir la
colonne p!p. 1 1 On vérifie la table de vérité 1 1
pour X!Y. Pour p!p on a
On vérifie la table de vérité juste deux cas.
pour X!Y. Pour p!p on a X!Y X Y X!Y X Y
juste deux cas.
1 0 0 X = 1 et Y = 1, qui donne 1 1 0 0
X = 1 et Y = 1, qui donne 1
1 0 1 X = 0 et Y = 0, qui donne 1 1 0 1
X = 0 et Y = 0, qui donne 1
0 1 0 Alors on est terminé et p!p 0 1 0
est un tautologie
1 1 1 1 1 1
tautologie tautologie
Encore une exemple,
La formule dont on
cette fois avec ¬X X
sait les possibilités de
négation et
ses sous-formules est 0 1
disjonction: p"¬p
¬p (car on vient de
traiter p) 1 0
On commence comme
avant, énumérant les
p"¬p ¬p p Grâce au table de p"¬p ¬p p
possibilités pour p et
vérité pour la
en faisant un colonne 0 négation on remplit la 1 0
pour chaque sous-
colonne ¬p
formule: p, ¬p et p"¬p 1 0 1
tautologie
p"¬p ¬p p
X"Y X Y
Maintenant on sait les
valeur de vérité pour 0 0 0
les deux sous-
1 0 1 1 1 0
formules de p"¬p: p
et ¬p 1 1 0
En utilisant la table
1 1 1
1 0 1
on trouve 1"0 = 1 et
0"1 = 1 p"¬p ¬p p
Alors p"¬p est un 1 1 0
tautologie 1 0 1 tautologie
p!¬p ¬p p p!¬p ¬p p
0 1 0
1 0 1
contradiction contradiction
(p!¬q)!r p!¬q ¬q p q r
p!¬p ¬p p 0 0 0
0 0 1
0 1 0
0 1 0 0 1 1
1 0 0
1 0 1
0 0 1 1 1 0
1 1 1
contradiction Exemple: (p!¬q)!r
(p!¬q)!r p!¬q ¬q p q r (p!¬q)!r p!¬q ¬q p q r
0 0 0 1 0 0 0
0 0 1 1 0 0 1
0 1 0 0 0 1 0
0 1 1 0 0 1 1
1 0 0 1 1 0 0
1 0 1 1 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
Exemple: (p!¬q)!r Exemple: (p!¬q)!r
(p!¬q)!r p!¬q ¬q p q r (p!¬q)!r p!¬q ¬q p q r
1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 1
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 1
1 1 0 0 1 1 0 0
1 1 0 1 1 1 0 1
0 1 1 0 0 1 1 0
0 1 1 1 0 1 1 1
Exemple: (p!¬q)!r Exemple: (p!¬q)!r
(p!¬q)!r p!¬q ¬q p q r (p!¬q)!r p!¬q ¬q p q r
0 1 0 0 0 0 1 0 0 0
0 1 0 0 1 0 1 0 0 1
0 0 0 1 0 0 0 0 1 0
0 0 0 1 1 0 0 0 1 1
1 1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 0 1
0 0 1 1 0 0 0 1 1 0
0 0 1 1 1 0 0 1 1 1
Exemple: (p!¬q)!r Exemple: (p!¬q)!r
(p!¬q)!r p!¬q ¬q p q r (p!¬q)!r p!¬q ¬q p q r
0 1 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 0 1 0 0 1
0 0 0 1 0 1 0 0 0 1 0
0 0 0 1 1 1 0 0 0 1 1
1 1 1 0 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1 0 1
0 0 1 1 0 1 0 0 1 1 0
0 0 1 1 1 1 0 0 1 1 1
Exemple: (p!¬q)!r Exemple: (p!¬q)!r
(p!¬q)!r p!¬q ¬q p q r
Logique des Propositions
1 0 1 0 0 0 Classique — Modélisation
1 0 1 0 0 1
p “le feu est vert”
1 0 0 0 1 0
q “il y un piéton en train de traverser”
1 0 0 0 1 1
r “j’avance au vitesse maximale”
0 1 1 1 0 0
!
1 1 1 1 0 1
1 0 0 1 1 0 ! r
1 0 0 1 1 1
p ¬
Exemple: (p!¬q)!r q
Logique des Propositions r!(p!¬q) p!¬q ¬q p q r
Classique — Modélisation 0 0 0
0 0 1
p “le feu est vert”
0 1 0
q “il y un piéton en train de traverser”
0 1 1
r “j’avance au vitesse maximale”
1 0 0
!
1 0 1
r ! 1 1 0
1 1 1
p ¬
q
Exemple: r!(p!¬q)
r!(p!¬q) p!¬q ¬q p q r r!(p!¬q) p!¬q ¬q p q r
0 1 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 0 1 0 0 1
0 0 0 1 0 1 0 0 0 1 0
0 0 0 1 1 1 0 0 0 1 1
1 1 1 0 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1 0 1
0 0 1 1 0 1 0 0 1 1 0
0 0 1 1 1 1 0 0 1 1 1
Exemple: r!(p!¬q) Exemple: r!(p!¬q)
r!(p!¬q)
1
p!¬q
0
¬q
1
p
0
q
0
r
0
Interprétation
0 0 1 0 0 1
1 0 0 0 1 0 Alors, on vient de déduire que la proposition
0 0 0 0 1 1 r!(p!¬q) est faux si et seulement si
1 1 1 1 0 0
r est vrai et p est faux “le conducteur
1 1 1 1 0 1
avance en vitesse mais le feux n’est pas
1 0 0 1 1 0
vert” (s’il y a un piéton ou pas)
0 0 0 1 1 1
r et q sont vrais: “le conducteur avance en
vitesse quand il y a un piéton” (si le feu
Exemple: r!(p!¬q) est rouge ou vert
Conclusion Algorithme de Quine
Quand on veut modéliser le monde en les constants T,#
logique, c’est facile de se tromper!
substitution des formules
C’est un des raisons pour faire la validation:
faire des tests (à la main ou par ordinateur) équivalences
pour vérifier que nos formules correspondent
bien aux intuitions et intentions de l’expert. l’algorithme
Algorithme de Quine Algorithme de Quine
Les constants T et #
Lemme: Substitution
Soit
X un formule,
T, “vrai”, est un constante qui a toujours la Y un des sous-formules de X,
valeur de vérité 1 Z unles formule telT,#
constants que Y Z,
alors quand on remplace toutes les occurrences
#, “faux”, est un constante qui a toujours la substitution des formules
de Y dans X par Z, dénoté par X[Y := Z], X est
valeur de vérité 0
équivalent à X[Y := Z], c’est à dire
X X[Y := Z]
Algorithme de Quine Algorithme de Quine
Equivalences Equivalences
Définitions de ! et Définitions de ! et
(X!Y)$(¬X"Y) (X!Y)$(¬X"Y)
(X Y)$((X!Y)!(Y!X)) (X Y)$((X!Y)!(Y!X))$((¬X"Y)!(¬Y"X))
Algorithme de Quine Algorithme de Quine
Equivalences Equivalences
Commutativité de ! et " Associativité de ! et "
(X!Y)$(Y!X) ((X!Y)!Z)$(X!(Y!Z))
(X"Y)$(Y"X) ((X"Y)"Z)$(X"(Y"Z))
Algorithme de Quine Algorithme de Quine
Equivalences Equivalences
Distributivité de ! et " Règles de De Morgan
¬T$#
¬#$T
((X!Y)"Z)$((X"Z)!(Y"Z))
¬¬X$X
((X"Y)!Z)$((X!Z)"(Y!Z))
¬(X!Y)$(¬X"¬Y)
¬(X"Y)$(¬X!¬Y)
Algorithme de Quine Algorithme de Quine
Equivalences Equivalences
Simplifications de Quine Simplifications de Quine
(T!X) $ X (T"X) $ T
(X!T) $ T (X"T) $ T
(#!X) $ T (#"X) $ X
(X!#) $ ¬X (X"#) $ X
Algorithme de Quine
Algorithme de Quine
Equivalences L’algorithme
Simplifications de Quine
1. Initialiser par l’arbre simple qui contient que la formule a vérifier
(T!X) $ X comme feuille (et racine).
(X!T) $ X 2. Applique les simplifications, ajoutant une feuille pour chaque
simplification. Continue jusqu’au moment qu’aucune simplification ne
peut être fait.
(#!X) $ #
3. Trouve un feuille qui contient un formule atomique, disons X avec
sous-formule atomique p. Ajout deux feuilles X[p := T] et X[p :=#].
(X!#) $ #
Continue avec 2.
Exemple de l’algorithme Exemple de l’algorithme
de Quine de Quine
r!(p!¬q) r=1 r!(p!¬q) r=0
T!(p!¬q) #!(p!¬q)
Exemple de l’algorithme Exemple de l’algorithme
de Quine de Quine
r=1 r!(p!¬q) r=0 r=1 r!(p!¬q) r=0
T!(p!¬q) #!(p!¬q) T!(p!¬q) #!(p!¬q)
# (p!¬q) #
Exemple de l’algorithme Exemple de l’algorithme
de Quine de Quine
r=1 r!(p!¬q) r=0 r=1 r!(p!¬q) r=0
T!(p!¬q) #!(p!¬q) T!(p!¬q) #!(p!¬q)
p=1 (p!¬q) p=0 # p=1 (p!¬q) p=0 #
(T!¬q) (#!¬q) (T!¬q) (#!¬q)
#
Exemple de l’algorithme Exemple de l’algorithme
de Quine de Quine
r=1 r!(p!¬q) r=0 r=1 r!(p!¬q) r=0
T!(p!¬q) #!(p!¬q) T!(p!¬q) #!(p!¬q)
p=1 (p!¬q) p=0 # p=1 (p!¬q) p=0 #
(T!¬q) (#!¬q) (T!¬q) (#!¬q)
¬q # q=1 ¬q q=0 #
¬T ¬#
Exemple de l’algorithme
de Quine
r=1 r!(p!¬q) r=0
T!(p!¬q) #!(p!¬q)
p=1 (p!¬q) p=0 #
(T!¬q) (#!¬q)
q=1 ¬q q=0 #
¬T ¬#
# T