Initiation à l’Intelligence Artificielle
Philippe Beaune, Gauthier Picard, Laurent Vercouter
École Nationale Supérieure des Mines de Saint-Étienne
[Link]@[Link]
Pôle XXI 2010-2011
Initiation à l’Intelligence Artificielle 1 / 34
. Sommaire
1. Introduction
2. Logique des propositions
3. Logique des prédicats
4. Prolog
Initiation à l’Intelligence Artificielle 2 / 34
. Objectifs et déroulement
.
Objectifs de ce cours
.
▸ Avoir un aperçu (forcément partiel) de l’Intelligence Artificielle
▸ Être capable de découvrir d’autres champs de l’Intelligence Artificielle
.
.
Déroulement
.
▸ 1 cours de 1h30
▸ 3 séances de TP en Prolog
.
Initiation à l’Intelligence Artificielle 3 / 34
Le livre de référence
. Artificial Intelligence : A Modern Approach, Stuart Russell & Peter Norvig
1st edition
1995
2nd edition
2003
2006 3rd edition
2010
▸ [Link]
▸ Plein de ressources sur le site du livre
Initiation à l’Intelligence Artificielle 4 / 34
. Quelques autres ressources
▸ AFIA : [Link]
▸ Revue d’IA : [Link]
▸ AAAI : [Link]
▸ AI Magazine : [Link]
▸ ACM SIGART : [Link]
▸ Nils J. Nilsson : [Link]
▸ John McCarthy : [Link]
▸ Marvin Minsky : [Link]
▸ JAIR : [Link]
▸ IJCAI : [Link]
▸ AI Journal : [Link]
▸ ECCAI, ECAI : [Link]
▸ AI/Alife Howto : [Link]
▸ ETAI : [Link]
▸ …liste non exhaustive, bien évidemment
Initiation à l’Intelligence Artificielle 5 / 34
. Logique des propositions (1)
▸ On va s’intéresser à des énoncés soit vrais soit faux, et aux relations entre ces
énoncés, avec une présentation simplifiée
.
Syntaxe
.
▸ Vocabulaire
▸ Chaînes de caractères représentant les atomes
▸ Connecteurs : ∨, ∧, ⇒, ⇔, ¬, …
▸ Parenthésage : (, )
▸ Règles de construction des formules bien formées (fbf )
▸ Un atome est une fbf
▸ Si F est une fbf, alors (F) est une fbf
▸ Si G est une fbf, alors ¬G est une fbf
▸ Si F et G sont deux fbf, alors F ∨ G, F ∧ G, F ⇒ G, F ⇔ G et F ⇒ ¬G sont des
fbf
▸ (Règles de priorité entre connecteurs)
.
Initiation à l’Intelligence Artificielle 6 / 34
. Logique des propositions (2)
.
Composition
.
▸ La valeur de vérité d’une fbf dépend uniquement des connecteurs et de la
valeur de vérité de chaque atome
.
.
Tables de vérités
.
F G ¬F F∧G F∨G F⇒G F⇔G
faux faux vrai faux faux vrai vrai
faux vrai vrai faux vrai vrai faux
vrai faux faux faux vrai faux faux
vrai vrai faux vrai vrai vrai vrai
.
.
Interprétation
.
.Fonction I de {atomes} vers {vrai, faux}
Initiation à l’Intelligence Artificielle 7 / 34
. Logique des propositions (3)
.
Quelques formules
.
P⇒Q ≡ (¬P ∧ Q)
P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P) ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)
¬¬P ≡ P
▸ Loi de de Morgan :
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
▸ Commutativité, associativité, distributivité, …
▸ Contradiction : P ∧ ¬P ≡ FAUX
▸ Tiers-exclus : P ∨ ¬P ≡ VRAI
▸ Absorption :
P ∨ (P ∧ Q) ≡ P
P ∧ (P ∨ Q) ≡ P
.
Initiation à l’Intelligence Artificielle 8 / 34
. Logique des propositions (4)
.
Quelques règles d’inférence
.
α ⇒ β, α
Modus Ponens ou élimination de ⇒ :
β
α ∧ α ∧ . . . ∧ αn
Elimination du ∧ :
αi
α , α , . . . , αn
Introduction du ∧ :
α ∧ α ∧ . . . ∧ αn
αi
Introduction du ∨ :
α ∨ α ∨ . . . ∨ αn
¬¬α
Elimination de la double nég. : α
α ∧ β, ¬β
Résolution unitaire :
α
α ∨ β, ¬β ∨ γ ¬α ⇒ β, β ⇒ γ
Résolution : ou
. α∨γ ¬α ⇒ γ
Initiation à l’Intelligence Artificielle 9 / 34
. Logique des propositions (5)
.
Définitions
.
▸ Un modèle d’une fbf (resp. d’un ensemble F de fbf ) est une interprétation qui
rend vraie cette fbf (resp. chaque fbf de F)
▸ S’il existe un modèle m d’une fbf (resp. d’un ensemble de fbf ), on dit que la fbf
(resp. l’ensemble de fbf ) est satisfiable, sinon elle (resp. il) est inconsistant
▸ Si une fbf (resp. un ensemble de fbf ) est satisfiable pour tout modèle, on dit
qu’elle (resp. il) est valide.
▸ Une fbf A est fbf conséquence logique d’un ensemble F de fbf si tout modèle
de F est modèle de A, et on note F ⊧ A
▸ Exemples : {A , B} ⊧ A, {A , B} ⊧ A ∧ B, {A , A ⇒ B} ⊧ B
▸ Si A est valide, on note ⊧ A
.
. .
Théorème de déduction Réfutation
. .
. ⊧ B ssi ⊧ (A ⇒ B)
A . ⊧ B ssi(A ∧ ¬B) est inconsistant
A
Initiation à l’Intelligence Artificielle 10 / 34
. Logique des propositions (6)
.
Algorithmes d’inférence
.
▸ Soit KB un ensemble de fbf, F une fbf, et i un algorithme d’inférence :
▸ Si F est dérivée de KB par i alors on note : KB ⊢i F
▸ Si i dérive seulement des conséquences logiques alors i est dit sain :
▸ Si KB ⊢i F alors KB ⊧ F
▸ Si toute conséquence logique peut être dérivée par i, alors i est dit complet :
▸ Si KB ⊧ F alors KB ⊢i F
å Méthode avec tables de vérité ? Si n atomes alors n lignes !
.
Initiation à l’Intelligence Artificielle 11 / 34
. Logique des propositions (7)
.
Forme normale conjonctive
.
▸ Un littéral est un atome (A) ou la négation d’un atome (¬A)
▸ Une fbf est mise sous forme normale conjonctive (FNC) si elle est sous la
forme F ∧ F ∧ . . . ∧ Fn où chaque Fi est une disjonction de littéraux
▸ Les Fi sont des clauses
▸ La forme clausale est l’ensemble des clauses
▸ Toute fbf peut être mise sous forme normale conjonctive (et donc clausale) :
1. Éliminer ⇔ puis ⇒
2. Lois de de Morgan
3. Éliminer les doubles négations
4. Appliquer les règles de distributivité
.
Initiation à l’Intelligence Artificielle 12 / 34
. Logique des propositions (8)
.
Principe de réfutation
.
Pour montrer que F , F , . . . , Fn ⊧ C, il faut et il suffit de montrer que la formule de
réfutation
. F ∧ F ∧ . . . ∧ Fn ∧ ¬C est inconsistante
.
Règle de résolution
.
Soient C et C deux clauses d’une formule F, s’il existe un atome A tel que A ∈ C
et ¬A ∈ C alors la clause (C ∖ {A}) ∪ (C ∖ {¬A}), est dite résolvante de C et
C
. , et elle est conséquence logique de F
Initiation à l’Intelligence Artificielle 13 / 34
. Logique des propositions (9)
.
Méthode de résolution (Robinson, 1965)
.
▸ Pour montrer qu’une formule F est inconsistante, il faut et il suffit de produire
la clause vide par résolution à partir de l’ensemble des clauses issues de F
mise sous forme clausale
▸ D’où la méthode, pour montrer que KB ⊧ A :
1. Construire la formule de réfutation
2. La mettre sous forme clausale : F
3. Construire une résolvante (tant que c’est possible) et l’ajouter à F jusqu’à obtenir
la clause vide
4. Si la clause vide est obtenue alors KB ⊧ A sinon KB ⊭ A
.
Initiation à l’Intelligence Artificielle 14 / 34
. Logique des propositions (10)
.
Exemple sur le modus ponens
.
▸ Montrer que {A, A ⇒ B} ⊧ B
▸ Formule de réfutation : A ∧ (A ⇒ B) ∧ ¬B
▸ Forme clausale : {A, (¬A ∨ B), ¬B}
▸ 1e solution :
▸ résolvante de A et (¬A ∨ B) : B, puis
▸ résolvante de B et ¬B : ∅
▸ 2e solution :
▸ résolvante de (¬A ∧ B) et ¬B : ¬A, puis
▸ résolvante de A et ¬A : ∅
.
.
▸ Dans quel ordre prendre les clauses pour obtenir les résolvantes successives ?
▸ Plusieurs algo qui garantissent la complétude
▸ NP-complet sauf classe P pour certains cas dont les clauses de Horn
.
Initiation à l’Intelligence Artificielle 15 / 34
. Une énigme à résoudre
Vous êtes perdus sur une piste dans le désert. Vous arrivez à une bifurcation. Chacune
des deux pistes est gardée par un sphinx que vous pouvez interroger. Les pistes peuvent
soit conduire à une oasis, soit se perdre dans le désert profond (au mieux, elle
conduisent toutes à une oasis, au pire elles se perdent toutes les deux).
1. Le sphinx de droite vous répond : « Une au moins des deux pistes conduit à une
oasis. »
2. Le sphinx de gauche vous répond : « La piste de droite se perd dans le désert. »
3. Vous savez que les sphinx disent tous les deux la vérité, ou bien mentent tous les
deux.
tiré de Notes de cours de Jérôme Champavert :
[Link]
Initiation à l’Intelligence Artificielle 16 / 34
. Logique des prédicats (1)
.
Limitation de la logique des propositions
.
▸ La logique des propositions a un pouvoir d’expression limité
▸ Comment exprimer que si Sylvain est fils de Philippe, et Philippe fils de Jean,
alors Jean est grand-père de Sylvain, ainsi que de Marion, fille aussi de Philippe,
et que cela est vrai dans plein d’autres cas, sans avoir à énumérer tous les liens
de parentés pour toutes les familles ?
.
Initiation à l’Intelligence Artificielle 17 / 34
. Logique des prédicats (1)
.
Limitation de la logique des propositions
.
▸ La logique des propositions a un pouvoir d’expression limité
▸ Comment exprimer que si Sylvain est fils de Philippe, et Philippe fils de Jean,
alors Jean est grand-père de Sylvain, ainsi que de Marion, fille aussi de Philippe,
et que cela est vrai dans plein d’autres cas, sans avoir à énumérer tous les liens
de parentés pour toutes les familles ?
.
.
Introduction de prédicats et de variables
.
Fils(x, y) ∧ Fils(y, z) ⇔ Grand_pere(z, x)
∀x, Gentil(x) ∧ Beau(x) /* tt le monde est gentil et beau */
. x, Fatigue(x)
∃ /* quelqu’un est fatigué */
Initiation à l’Intelligence Artificielle 17 / 34
. Logique des prédicats (2)
.
Syntaxe
.
▸ Termes : constantes (majuscules : A), variables (minuscules : x), fonctions
(minuscules : f(A, X, f(g(e))))
▸ Formules atomiques
▸ prédicats dont les arguments sont des termes (majuscules :
P(x, t, f(u, g(s), R), Z))
▸ terme = terme
▸ Formules bien formées (fbf )
▸ Une formule atomique est une fbf
▸ Si F est une fbf, (F) et ¬F sont des fbf
▸ Si F et G sont des fbf : F ∧ G, F ∨ G, F ⇒ G et F ⇔ G sont des fbf
▸ Si F est une fbf et x une variable :
▸ ∀x . F est une fbf
▸ ∃x . F est une fbf
Initiation à l’Intelligence Artificielle 18 / 34
. Logique des prédicats (3)
.
Les quantificateurs
.
▸ L’ordre peut être important :
∀x.(∃[Link](x, y)) vs. ∃x.(∀[Link](x, y))
▸ Loi de de Morgan :
¬∀x.F ≡ ∃x.¬F
¬∃x.F ≡ ∀x.¬F
∀x.F ≡ ¬∃x.¬F
∃x.F ≡ ¬∀x.¬F
▸ Une variable est dite libre dans F si toutes ses occurrences dans F sont hors de
portée des quantificateurs, sinon elle est liée
▸ Une formule est fermée (ou close) si elle ne contient aucune variable libre,
sinon elle est ouverte
.
Initiation à l’Intelligence Artificielle 19 / 34
. Logique des prédicats (4)
.
Interprétation
.
On se donne :
▸ un domaine de valeurs pour les constantes
▸ une application qui donne une valeur à chaque variable
▸ une application qui associe à toute fonction d’arité n et à tout n-uplet de
termes une valeur dans le domaine de valeurs
▸ une application qui associe à tout prédicat d’arité n et à tout n-uplet de
termes une valeur dans {vrai,faux}
▸ ∀x.P est vrai ssi P est vrai pour toute interprétation de x
▸ ∃x.P est vrai ssi P est vrai pour au moins une interprétation de x
.
Initiation à l’Intelligence Artificielle 20 / 34
. Logique des prédicats (5)
.
Forme de skolem
.
▸ Une formule F est sous forme prenex ssi elle est sous la forme
Q x Q x . . . Qn xn .A où Qi est un quantificateur et A ne contient aucun
quantificateur
▸ Pour toute formule F il existe une formule F′ sous forme prenex telle que
F ≡ F′
▸ Soit F une formule sous forme prenex de la forme
∀x . . . ∀xi ∃xi+ Qi+ xi+ . . . Qn xn .A
et f un nouveau symbole d’une fonction i-aire, la formule F′
∀x . . . ∀xi Qi+ xi+ . . . Qn xn .A{xi+ /f(x , . . . , xi )}
est la skolémisation partielle de F et F est satisfiable ssi F′ l’est
▸ Si une formule prenex F a n quantificateurs ∃, la forme de skolem F′ de F est
obtenue par n applications de la skolémisation partielle et F est satisfiable ssi
F′ l’est.
.
Initiation à l’Intelligence Artificielle 21 / 34
. Logique des prédicats (6)
.
Mise sous forme clausale (principales étapes)
.
1. Mise sous FNC comme en logique des propositions
.2 Mise sous forme prenex
3. Skolémisation
4. Mise sous forme clausale : élimination des ∀
.
.
Substitution
.
Une substitution est application σ de l’ensemble des variables vers l’ensemble des
.termes. Par extension on note σ(F) la formule F dans laquelle on a appliqué σ
.
Unification
.
F et F sont unifiables s’il existe une substitution σ telle que σ(F ) = σ(F )
.σ est alors appelée unificateur de F et F
Initiation à l’Intelligence Artificielle 22 / 34
. Logique des prédicats (7)
.
Résolution
.
Comme en logique des propositions mais en passant par l’unification :
▸ Soient F et F deux clauses : elles sont résolvables ssi elles contiennent une
paire opposée de formules atomiques P(x , . . . , xn ) et ¬P(x′ , . . . , x′n ) et si
elles peuvent être unifiées par un unificateur σ
▸ La résolvante est alors σ(F ∖ {P}) ∪ σ(F ∖ {¬P})
▸ Exemple : F(x) ∧ G(Toto) et ¬F(y) ∧ G(z)
.
Initiation à l’Intelligence Artificielle 23 / 34
. Logique des prédicats (7)
.
Résolution
.
Comme en logique des propositions mais en passant par l’unification :
▸ Soient F et F deux clauses : elles sont résolvables ssi elles contiennent une
paire opposée de formules atomiques P(x , . . . , xn ) et ¬P(x′ , . . . , x′n ) et si
elles peuvent être unifiées par un unificateur σ
▸ La résolvante est alors σ(F ∖ {P}) ∪ σ(F ∖ {¬P})
▸ Exemple : F(x) ∧ G(Toto) et ¬F(y) ∧ G(z)
.
å La résolution est saine et complète (au sens de la réfutation)
Initiation à l’Intelligence Artificielle 23 / 34
. Logique des prédicats (8)
.
Décidabilité
.
▸ La logique des propositions est décidable (on peut montrer en un nombre fini
d’opérations qu’une formule est valide ou contradictoire)
▸ La logique des prédicats est indécidable (Gödel, 1931)
▸ La logique des prédicats est semi-décidable : on peut montrer en un nombre
fini d’opérations si une formule est valide mais pas si elle est contradictoire
▸ La logique des prédicats réduite aux clauses de Horn est décidable (cf. Prolog)
.
Initiation à l’Intelligence Artificielle 24 / 34
. Prolog (1)
.
Clauses de Horn
.
▸ Disjonction de littéraux dont un seul au plus est positif
▸ ex. : p(X) ⇐ q(a) ∧ r(Z) ∧ s(Z) ∧ t(toto)
▸ Clause avec exactement un littéral positif est dite clause définie
.
.
Constituants de Prolog
.
▸ Base de règles : ensemble de clauses définies non réduites à un littéral positif
▸ Base de faits : ensemble de littéraux positifs
▸ ex. : {p(truc), r(machin), s(X , Y)}
▸ Question : clause négative
▸ ex. : q(X , toto) ∧ w(truc) ?
Initiation à l’Intelligence Artificielle 25 / 34
. Prolog (2)
.
Moteur d’inférence
.
▸ Ordre 1 : à base de la logique des prédicats
▸ Chaînage arrière : raisonnement guidé par les buts
▸ Principe de résolution (par SLD-resolution) avec stratégie en profondeur
d’abord
▸ Régime par tentatives : backtrack si échec
▸ Non-monotone
▸ Négation par l’échec (SLDNF-resolution)
▸ not(p) réussit si p n’est pas démontrable
Initiation à l’Intelligence Artificielle 26 / 34
. Prolog (3)
.
SLD-resolution
.
▸ Chaque étape de résolution doit prendre une clause négative (initialement, la
question) et une clause définie (prise dans le programme)
▸ SLD-resolution (Linear resolution for Definite clauses with Selection function) :
▸ Prendre un littéral de la clause négative (lequel ?) et tenter une unification avec
le littéral positif d’une clause définie (unificateur le plus général)
▸ Si une telle unification est trouvée alors remplacer le littéral choisi de la clause
négative par les éventuels littéraux négatifs de la clause définie qui a réussi
l’unification (Linear)
▸ Si l’unification échoue, reporter cet échec à l’unification de niveau supérieur
▸ Si la clause négative est vide : succès !
.
Initiation à l’Intelligence Artificielle 27 / 34
. Prolog (4)
.
Stratégie de Prolog : profondeur d’abord
.
▸ Choix du 1er littéral de la clause négative
▸ Backtrack aux feuilles de l’arbre
▸ Choix des clauses définies dans l’ordre d’écriture du programme
▸ Conséquences :
▸ Une stratégie en profondeur est efficace (en largeur ce serait gourmand en taille
mémoire)
▸ Mais il y a un risque de boucle infinie (attention à l’ordre d’écriture des règles) :
donc Prolog n’est pas complet (même si la SLD-resolution est complète pour la
réfutation)
.
Initiation à l’Intelligence Artificielle 28 / 34
. Prolog (5)
.
Syntaxe
.
▸ Constantes : entiers, flottants, ou chaînes de caractères commençant par une
minuscule
▸ Variables : chaînes de caractères commençant par une majuscule
▸ Prédicats :
▸ Nom commençant par une minuscule
▸ Arguments pouvant être des constantes, des variables et des prédicats
▸ Listes :
[a,b,c] = [a | [b | c]] = [a,b |[c]]
▸ Faits :
toto(truc, machin).
▸ Règles :
titi(X) :- toto(X,machin),
bidule(foo).
.
Initiation à l’Intelligence Artificielle 29 / 34
. Prolog (6)
.
Exemple familial
.
homme(jean).
homme(pierre).
homme(luc).
femme(marie).
femme(anne).
femme(marion).
pere(Papa,Enfant) :- parent(Papa,Enfant), homme(Papa).
mere(X,Y) :- parent(X,Y), femme(X).
grand_pere(X,Y) :- pere(X,Z), parent(Z,Y).
grand_mere(X,Y) :- mere(X,Z), parent(Z,Y).
frere(X,Y) :- parent(Z,X), parent(Z,Y), X\=Y, homme(X).
oncle(O,N) :- frere(O,X), parent(X,N).
parent(jean,pierre).
parent(jean,marie).
parent(anne,marion).
parent(luc,jean).
parent(luc,anne).
:-
. oncle(X,Y) ?
Initiation à l’Intelligence Artificielle 30 / 34
. Prolog (7)
.
Un pas en avant
.
▸ Être une liste ou pas :
list(X) :- X=[Y].
ce qui peut se simplifier en :
list([Y]).
ce qui peut encore se simplifier en :
list([_]).
hé ! on oublie les listes vides, il faut ajouter :
list([]).
▸ Récursivité :
▸ Être élément ou ne pas être :
elem(X,[X|_]).
elem(X,[_|Y]) :- elem(X,Y).
▸ Être premier élément, être dernier élément,… à vous de jouer…
▸ Concaténation de 2 listes :
concat([],X,X).
concat([X|S],Y,[X|R]) :- concat(S,Y,R).
. Initiation à l’Intelligence Artificielle 31 / 34
. Prolog (8)
.
Divers
.
▸ Affectation :
X is 2+3
▸ Comparaisons :
▸ X = Y réussit s’il unifie les 2 termes ou s’ils sont identiques
▸ X == Y réussit si les 2 termes sont équivalents (sans unification)
▸ X =@= Y réussit si les 2 termes sont structurellement équivalents (sans
unification)
▸ …
.
Initiation à l’Intelligence Artificielle 32 / 34
. Prolog (9)
.
Toujours penser déclaratif, mais néanmoins...
.
▸ fail : échoue toujours
▸ true : réussit toujours
▸ ! (cut) : bloque le backtracking
not(X) :- X , ! , fail.
not(X).
… ne pas recourir trop souvent au cut !
.
.
Divers
.
▸ Certains Prolog vont plus loin, notamment CSP
▸ Compilation (WAM, 1983), standard ISO (1995), …
.
La suite en T.P. …
Initiation à l’Intelligence Artificielle 33 / 34
Prolog (10)
. Bibliographie
▸ The art of Prolog
L. Sterling & E. Shapiro,
1994 (VF de 1990 chez Masson)
▸ Logic, Programming and Prolog (2ed)
Ulf Nilsson and Jan Maluszynski,
2000
[Link]
Initiation à l’Intelligence Artificielle 34 / 34
