Intelligence Artificielle

Année universitaire 2018/2019

Pr. Jaouad Boumhidi

 Plan du cours

Introduction à l'Intelligence Artificielle

Chap 1: Représentation des connaissances et inférence en logique
des propositions et des prédicats
Chap 2: Représentation des connaissances et inférence en logique
floue
Chap 3: Introduction à la théorie d’Apprentissage:
 Arbre de décosion
 Réseau de neuronnes,
 SVM
Définir l'Intelligence Artificielle ?

IA: Science qui étudie des agents intelligents (Programme

intelligent+ Architecture matériel) :
Agents intelligents: Quatre types de définitions:
 1) Système qui pense comme les humains (cognitive)
 2) Système qui agit comme les humains (Système passant le test
de Turing)
 3) Système qui pense rationnellement (Logicisme: pensée
logique)
 4) Système qui agit rationnellement

Rationalité: consiste à faire l’action appropriée, cela dépend

essentiellement de la mesure de performance qui définit le critère de
succès.
Le test de turing: Un testeur humain doit identifier s'il dialogue
avec un humain ou une machine : la machine réussit le test si elle
n'est pas identifiée en tant que telle.
 Agent intelligent
(Programme + Architecture)
Définition d’agent:
Entité considéré comme percevant(perception) son environnement par
des capteurs (sensors)et agit rationnellement sur cet environnement
par des effecteurs(actuators).
Agents interagissant avec l’environnement
<Percepts, Fonction Agent, Programme Agent et Action(Décision)>

 Percepts: Entrées perceptives d’un agent à un instant

donnée.

 Actions: Action à un instant donnée, (qui dépend de la

séquence de percepts prise jusqu’à ce moment).
 Fonction Agent:
Fonction mathématique décrivant le comportement d’un agent et qui fait
lier une action à chaque séquence de percepts.
Un agent est complètement déterminé par la fonction d'agent
qui étant donnée une séquence de perception renvoie une action.

 Programme Agent:
Implémentation de la fonction Agent qui s’exécute sur l’architecture
Agent
Chap. 1 Représentation des connaissances en Logique des
propositions et des prédicats

Plan:
 Logique des propositions
 Logique des prédicats
 Moteurs d’inférences à base de règles
 Application en Prolog
• Deux aspects dans une représentation des
connaissances:

–La syntaxe: définit les énoncées valides

–La sémantique: Définit les règles de détermination de la vérité

d’un énoncé (Manière par laquelle l’agent atteint son but)
 Logique des propositions(LP)
La logique des propositions est un langage formel
constitué d’une syntaxe et d’une sémantique
Syntaxe:
Proposition?
C’est une expression (énoncé) qui prend ses valeurs(de vérité)
dans l’ensemble {Vrai, Faux}
Exemples:
Mohammed est le père de Ali
Les droites D1 et D2 sont parallèles.
 Syntaxe de LP

SYMBOLES PROPOSITIONNELS : (p, q, r,….) :

Pour représenter et manipuler une proposition on utilise des
symboles propositionnels dont la valeur peut être vraie ou faux.
Nous utilisons des lettres en minuscules pour chaque symbole
(p, q, r,….)
Exemple:
p=Driss est le père de Rachid
CONNECTEURS:
 Syntaxe de LP

 Une énoncée tel que p→q est une implication,

P: sa permisse ou antécédent
Q: sa conclusion ou conséquence
 Syntaxe de LP
ENONCÉ ATOMIQUE
C’est une proposition élémentaire, constitué d’un seul symbole
propositionnel ne contenant pas de connecteurs logique.
Exemples
p: représente la proposition : «Driss est père de Ali»

LITTÉRAUX (ATOME OU SA NÉGATION)

Un littéral positif est un atome

Un littéral négatif est la négation d’un atome

Exemples

Littéraux positifs : p, q

Littéraux négatifs: ¬p, ¬q

 Syntaxe de LP

ENONCÉE COMPLEXE (FORMULE):

Construite à partir de symboles propositionnel et de
connecteurs
Exemple: ( P  Q )  R

Si Rachid est malade, il ne sort pas P  Q

AMBIGUÏTÉ SYNTAXIQUE :
Pour assurer l’absence d’ambiguïté syntaxique, toute énoncée
complexe doit être encadré par des parenthèses
Exemple:
On peut utiliser les règles de priorité (par ordre décroissant)
des connecteurs:
¬, ^,V, ,
 Syntaxe de LP

Mais la priorité ne résout pas les ambigüités des énoncées tel

que:
abc
Qui peut se lire: (a  b)  c ou encore a (b  c) qui ne
signifie pas la même chose

Cepedant,
a^b^c
Qui peut se lire: (a ^ b) ^ c ou encore a ^ (b ^ c) est autorisée
 Sémantique de LP

SÉMANTIQUE
Elle définit les règles de détermination de la valeur de vérité d’une Formule(énoncé
quelconque) dans un modèle quelconque (c.à.d un énoncé est il vrai ou faux).

BASE DE CONNAISSANCES (KNOWLEDGE BASE):

C’est l’ensemble des énoncés (supposées tous vrais) à utiliser pour réaliser
l’inférence(pour vérifier si un certain énoncé est vrai)

 MODÈLES ASSOCIÉ À UNE KB (KNOWLEDGE BASE).

Considérant par exemple les énoncées de KB qui utilisent les symboles p ,q et r.
un modèle possible est m1= {p=faux , q=faux, r= vraie }
 Avec 3 symboles il existe 23 modèles possibles.

Le calcul de la valeur de vérité d’un énoncé est réalisé selon la table de vérité suivante :
 Sémantique de LP

Exemple: Dans le modèle m1= {p=faux , q=faux, r= vraie }

Quel est la valeur de vérité de: (p v q) ^ (¬ r)
 Sémantique de LP

BASE DE CONNAISSANCE (KB)

C’est l’ensemble des énoncés (supposées tous vrais) à
utiliser pour réaliser l’inférence(pour vérifier si un certain
énoncé est vrai)
Cette base est représentée aussi par la conjonction de ces
énoncés.
En effet : si la KB se compose des énoncés E1, ……,EN on
peut les considérer comme un seule énoncée :
E1^ E2 ^…….. ^EN on affirme que tous les énoncés
individuels sont vrais.
 Sémantique de LP

INFÉRENCE : (DÉCIDER LA BONNE CONSÉQUENCE)

 Le but est de décider si la conjonction de la KB a pour
conséquence Une énoncée α : KB ╞ α
Cela signifie que : Si KB vrai alors α ? Vraie (ie α est –elle
conséquence ?)
L’opérateur ╞ est dit de conséquence.
 Sémantique de LP

Algorithme d’inférence par énumération de modèles

Cet algorithme permet de :

 Enumérer les modèles

 Et vérifier si α est vraie dans tous les modèles pour lequel KB
est vrai.
 Sémantique de LP

ENUMÉRATION DE MODÈLES :
Revient à affecter des Vrai et Faux pour tout symbole propositionnel.

 Soit par exemple KB est :

R1 ¬ P (vraie)
R2 P→Q (vraie)

On a: 2 symboles P et Q
Il existe 22=4 modèles possibles.
m1 = {P=V, Q=V}
m2= {P=V, Q=F}
m3= {P=F, Q=V}
m4= {P=F, Q=F}

Quel sont les modèles pour lequel R1 ^R2 est vrai (c.à.d) R1 vrai et R2 vrai.
 Sémantique de LP

DRESSER LA TABLE DE VÉRITÉ :

Les modèles pour lesquels KB est vraie sont :

m3 = {P=F, Q=V}
m4 = {P=F, Q=F}
Si on veut par exemple décider si pour KB= { R1 et R2 }
α =Q est elle conséquence (Q est elle vraie)
On remarque : α n’est pas toujours vrai dans m3 et m4 alors α = Q n’est pas
conséquence. Cependant, l’énoncée α = (¬ P)^ (¬ P)
c’est toujours vraie dans m3 et m4 alors α est conséquence de KB
càd KB╞ α
 Exercice1
Soit la base de connaissance suivante:
KB={
E1: p ^ q
E2: ¬pq
}
Vérifier si les énoncée suivant sont vrai?
((¬ p) v (¬ q)) p
(p v q) ^ (¬ p)
 Exercice2
Soit la base de connaissance suivante:
KB={
E1: p ^ q
E2: ¬pr
E3:(q v r)p
}
Vérifier si les énoncée suivant sont vrai?
((¬ p) v (¬ q)) r
(p v q) ^ (¬ r)
REPRÉSENTATION DE CONNAISSANCES EN LOGIQUE DES
PRÉDICATS DU PREMIER ORDRE

La logique des propositions ne permet pas de formaliser des

énoncés généraux: comme suit:
x est père de y et x est père de z alors y et z sont frères (ou x,
y et z sont des variables).

Ceci est réalisé par la logique des prédicats qui est

indépendante des noms propres sous forme:
( x, y, z ) ( père ( x, y )  père( x, z ))  frère( y, z )

Où père et frère sont maintenant des prédicats (relations

entre les différents objets)
 PRÉDICAT :
P : D1  D2  .......  Dn  vrai, faux
( x1 , x 2 ,................, x n )  P( x1 , x 2 ,...x n )
Exemple: père(X,Y)
 Le prédicat P appliqué à un certains objet constants C1 , C2 ,
……Cn : P(C1 ,C2 ,…Cn) devient une proposition.
Exemple : Père (Ali ,Youssef)

Ensemble de départ de dim 1:

Soit: Ali est un homme: peut être représenté par: H(Ali)
X est un homme: H(X) ou Homme(X)
 REMARQUES:

Un prédicat peut être appliqué à des variables et /ou des

constantes
 Le nombre de paramètres d’un prédicat est appellé: ‘arité’
 Un prédicat d’arité 0 est une proposition.
 Les connecteurs de la LProposition (,, , , )
sont aussi ceux de LPrédicats
 Les quantificateurs () , () : sont les éléments de L
Prédicats
SYMBOLES ET INTERPRÉTATIONS :

Quatre types de symboles :

 Les symboles de constants (Ali, Mohammed,….)
 Les symboles de variables (X, Y,…)
 Les symboles de prédicats : représentent les relations(liens)
entre les objets ( décrit les propriétés des objets)
Exemples: frère, père , mère….

 Les symboles de fonctions (chaque objet est caractérisé par

un ensemble de fonctions
Exemple: voiture(x)
ATOME : Prédicat appliqué à des termes: p(t1 ,
……,tm )
FORMULE BIEN FORMÉE (F.B.F)
C’est une expression formé d’atomes auquel sont appliqués les
connecteurs(et/ou quantificateurs):
,, , , , (), ()

Exemple:

F  (( (x) P ( x) )  (( y )Q( y )))  ((x) R( x))

Tous les philosophes sont assis F  (x) ( P ( x)  A( x))

Quelques philosophes sont assis F  ( x) ( P( x)  A( x))

 Objectif:

Formule bien Forme normal de Forme standard de

formé Prenexe Skolem

Forme Clausale

Représentation en
Prolog
 FORME NORMALE DE PRENEXE :

Une f.b.f nommée F est normal de Prenexe ssi :

F  (Q1 x1 )(Q2 x 2 )....(Qn x n ) M

Où Qi i=1,2 sont des quantificateurs ou 

M est une formule sans quantificateurs

Exemple : F  (x)( y ) ( z )( f ( x, y )  Q( y, z ))

Remarque : Toute f.b.f admet une forme normale de Prenexe

EQUIVALENCES DE BASE UTILISÉES POUR ATTEINDRE LA
FORME CLAUSALE:

((x) p( x))  (x)p( x)

((x) p ( x))  (x)p ( x)
 Soit M et N deux f.b.f sans quantificateurs
((x) M )  ((x) N )  (x)( M  N )
((x) M )  ((x) N )  (x)( M  N )
((x) M )  ((x) N )  (x)( M  N ) 
((x)( M  N )  ((x) M )  (x) N )
Soient Q1 et Q2 deux quantificateurs qcq
((Q1 x) M ( x))  ((Q2 y ) N ( y ))  (Q1 x)(Q2 y )( M ( x)  N ( y ))
((Q1 x) M ( x))  ((Q2 y ) N ( y ))  (Q1 x)(Q2 y )( M ( x)  N ( y ))
 Forme standard de Skolem (la
Skolemisation)
Consiste à supprimer les quantificateurs existentiel (  )
 Soit F une f.b.f, Pour mettre F sous forme standard de SKolem
on réalise les étapes suivantes :
 Mettre F sous forme normale de Prenexe:
F=(Q1X1 )(Q2 X2 )……(QN XN)M
Pour tous quantifieurs: Q  
i

 S’il n’y a aucune  à gauche de Qi alors :

Supprimer (Qi xi) et remplacer xi dans M par une constante non
déjà existante.
EXEMPLE : F  ( y ) ( x) P( x)  Q( y )
 ( x) P( x)  Q(a)
 Si Qj , Qj+1 ,……., Qe sont des quantificateurs  à gauche de
Qi ,alors :
Supprimer (Qi xi ) et remplacer xi dans M par une fonction f de
xj , xj+1,… xe : (f(xj , xj+1,… xe )
Exemple : F  ( x) ( y ) P( x)  Q( y )
 ( x) P( x)  Q( f ( x))

 Les constantes et fonctions introduits dans M sont appellées

fonctions de Skolem.
 Exemple 2

Peut être écrite sous forme skolem suivante:

Remarque : une f.b.f peut avoir plusieurs formes

de Skolem différents
 FORME CLAUSALE OU ENSEMBLE DE
CLAUSES :
Pour obtenir une Clause d’une f.b.f, , il suffit de la mettre sous
forme standard de Skolem
( x1 )( x2) …..( xn) F1
F1: est dite une clause
Une forme clausale est une conjonction de clauses Noté aussi:

Ou:
{ F1, F2 ,……, Fk }
C’est ce qu’on appelle en prolog la base des faits
En logique des prédicats: la base de connaissances est constituée
d’une base de faits= ensemble de clauses + base de règles
(utilisée pour déduire un but)

Sémantique de la logique des prédicats:

Utilisation des moteurs d’inférences (chainage avant et arrière)
pour la déduction d’un but.
MOTEUR D’INFÉRENCE :
 LES MI À CHAINAGE AVANT (FORWARD CHAINING )

Détermine le résultat ou (But) à partir de (BDF : base de fait)+

(la base de règles)

Exemple :
Soit BDF= {A, B, C, D}
Et soit la règle A, C→G
On obtient une nouvelle BDF= {A, B ,C, D ,G}
 TYPES D’EXPLORATION

Exploration en profondeur d’abord et l’exploration en largeur

d’abord (Aveugle)

Résultats d’exploration eu profondeur d’abord A, B, E, F, C, D….

Par contre l’exploration en largeur d’abord → A B C D E F
 EXEMPLE : M.I À CHAINAGE AVANT EN
PROFONDEUR D’ABORD :
Soit la base de connaissance suivant BDF= {A, D, E,G}
Et soit la base de règles suivante :
BDR= {
R1 : A,B,C → H
R2: A, U, C → F
R3: E, G, B → S
R4: D, G → C
R5: A, E → B
R6: U, S, T → F
R7: G, H → R
R8: D, E → T
R9: R, S, H → F
R10: A, U → B
}
  Le problème est d’établir le fait F
 Le problème du MI peut être schématisé par l’ordre suivant qui
illustre l’exploration en profondeur d’abord de l’arbre de
recherche
Racine de l’arbre

A partir de cette base , on peut aboutir directement , Selon

R4 → C
R5 → B
R8 → T
LA RÈGLE R4 EST EXPLORÉ (ELLE NE SERA PLUS APPLIQUÉE)

…
 Moteur d’inférence à chainage arrière-en
profondeur d’abord-
Correspond ou chemin inverse effectué par MI à chainage avant,
on commence du fait à établir et regarde les autres faits qui le
produit (se sont les nouveaux problèmes à résoudre)
 Exercice
Soit la base des faits suivante :
Et la base de règles suivante :

Déduire le fait H en utilisant les moteurs d’inférence

chainage avant et chainage arrière par exploration en
profondeur d’abord.
 Langage Prolog
 Un langage de programmation logique (déclarative)
 Comporte: un compilateur et une bibliothèque
  Si Prolog démarre normalement, vous verrez apparaître ce
qui suit:

Le symbole ?- est appelé l’invite de commande (ou encore prompt). Elle indique
que Prolog attend une requête
 Exemple:

On met toujours un point en fin de requête.

Le mot true imprimé ensuite par Prolog indique que la
commande a réussi, du point de vue logique.
Constitution d’un Programme Prolog
 Programme Prolog=Base de connaissance={faits+Règles}

 Les faits: se sont des clauses supposées toujours vrais

 Les règles: sont des relations qui permettent d’établir de
nouveau faits.
Exemple: si on est le père du père de quelqu’un alors on est
son grand-père se traduit par :
pere(X,Z) ˆ pere(Z,Y) grandpere(X,Y) se traduit en prolog
par:
grandpere(X,Y):-pere(X,Z),pere(Z,Y).
grandpere(X,Y):-pere(X,Z),pere(Z,Y).
Est interprété comme:
∀X ∀Y ∀Z pere(X,Z)ˆ pere(Z,Y) grandpere(X,Y)
Conventions de SWI-PROLOG

 Il existe plusieurs éditeur/débuggeur PROLOG. Nous utiliserons ici SWI-PROLOG.

 Tous les faits et règles doivent se terminer par un « . ».

 Les variables utilisées dans les faits ou les règles commencent toujours par une majuscule
ou « _ »
Exemple : X Genre _nombre _

 A l’inverse, tout le reste commence par une minuscule

 Il ne faut pas mettre d’espace entre le prédicat et la parenthèse ouvrante qui l’accompagne
 Pas d’accent dans le programme

 Les commentaires sont mis entre « /* » et « */ » ou commencent par « % » et se

terminent sur la même ligne.
Exemple de programmation d’une base de
connaissance

 Soit le prédicat nommé famille :

 famille(enfant, sexe, pere).
 Considérant une table dont les attributs sont le nom de
l’enfant, son sexe et le nom de son père.
Considérant la table des faits suivants:
Table des faits (ou base de faits)
 famille(mohammed, h, driss).
 famille(sanae, f, ahmed).
 famille(nagib, h, rachid).
 famille(rajae, f, said).
 famille(mourad, h,driss).
 famille(jamal, h, ismail).
 famille(meriem, f, ahmed).
 famille(jaouad, h,samir).
 famille(driss, h,jaber).
 famille(ahmed, h,jaber).
 Lancer SWI-PROLOG
 Si Prolog démarre normalement, vous verrez apparaître ce
qui suit:

Le symbole ?- est appelé l’invite de commande (ou encore prompt). Elle indique
que Prolog attend une requête
 Créer un nouveau fichier (File/new…
 Puis saisir la base des faits précédente
 Et enregistrer le fichier sous l’extention .pl
 Fermer votre fichier
Remarque :
 On peut travailler sans règles (comme une base de
donnée) pour la recherche ou la vérification de la
présence d’une donnée).
 Avec les règles on déduit d’autres faits vrais, C’est ce
qui fait la puissance d’un langage comme PROLOG par
rapport à SQL où toutes les données de la base doivent
être explicitement énoncées.
Revenir à swi prolog puis Compiler votre fichier:
(File/consulter….)

répondre aux questions suivantes:

1) Vérifier la présence ou non d’une donnée dans la table (sans
utiliser les règles)
 Najib, homme et son père est rachid
 Rajae femme et son père est ahmed
 Quelle sont les femmes qui figurent comme enfants
 Quelle sont les enfants de driss
 Le système répond par true s'il trouve une façon de prouver
le nouveau fait a partir des faits et des relations donnes dans
le programme.

 L'utilisation de _ dans le fait signifie que sa valeur ne nous

importe pas
 Ajouter maintenant les règles suivantes:
 /***************** Les regles ********************/
 /*R1*/ pere(X,Y):-famille(Y,_,X).
 /*R2*/ frere(X,Y):-famille(X,_,Z),famille(Y,_,Z).
 /*R3*/ oncle(X,Y):-pere(Z,Y),frere(X,Z).
répondre aux questions suivantes:
 Mohammed et mourad sont ils des frères
 Ahmed est il oncle de mourad
 Ahmed est il oncle de najib
 Exercice
Soit la base de connaissance suivante (faits+règles):
/***************** Les faits*******************/
/*Arguemnts du predicat ‘gestion’ :
gestion(etudiant, sexe, annee_bac, moy)*/
gestion (mohammed, h, 2008, 12).
gestion (sanae, f, 2009, 10.5).
gestion (nagib, h, 2007, 13).
gestion (rajae, f, 2009, 12.5).
gestion (mourad, h, 2008, 11).
gestion (ahmed, h, 2009, 10).
gestion (meriem, f, 2010, 14).
gestion (rachid, h, 2009, 11).
/***************** Les règles *******************/
/*R1*/ mention(X,Y):- gestion (X,_,_,Y),Y>=12.
Vérifier qu’un étudiant figure ou non dans la table
Afficher la liste de tous les étudiants (leurs noms)
Afficher les noms des étudiants ayant la moyenne supérieure à
10
Afficher les noms des étudiants ayant la moyenne entre 12 et 14
Afficher les noms des étudiants ayant la moyenne supérieure à
13 ou inférieure à 11
Afficher uniquement les noms des étudiants ayant une mention
Afficher les noms et les moyens des étudiants ayant une
Unification et affectation.
Le symbole « = » en PROLOG signifie l'unification et pas
l'affectation.
Pour affecter une valeur numérique à une variable, en évaluant
mathématiquement le résultat, il faut utiliser « is »
Exemple:
?- M=1+1, N is 1+1.
M = 1+1
N=2;
write(),
Il existe quelques actions prédéfinies comme write(), qui est
applicable à une constante, une variable ou une chaîne de
caractères entre guillemets simples, nl (passage à la ligne)
Exemple:
?- write('bonjour'),nl,write('bonsoir').
bonjour
bonsoir
true.
?- X is 2,write(X).
2
X = 2.
En PROLOG, on ne définit pas de fonction ou de
procédures mais des prédicats
 calculer la somme de deux nombres ?
somme(X,Y,S) :- S is X+Y.
Requête:
?- somme(2,4,X).
X = 6.

 connaître le plus grand parmi 2 nombres ? parmi 3 ?

max2(X,Y,X) :- X>=Y.
max2(X,Y,Y) :- X<Y.
max3(X,Y,Z,M) :- max2(X,Y,N),max2(N,Z,M).
 Récursivité
 En PROLOG, il n'y a pas d'autres moyens de faire des
boucles que d'utiliser la récursivité:

 Exemple:
Afficher N fois 'bonjour'. (Ou : ecrit(N) est vrai si le
message 'bonjour' est écrit N fois.):
ecrit(N) :- N>0, write('bonjour'), nl, N1 is N-1,ecrit(N1).
Requête:
?- ecrit(4).
Récursivité
Afficher les nombres de 1 à N.
/* de N à 1 */
decroissant(0).
decroissant(N) :- N>0, write(N), nl, N1 is N-1,
decroissant(N1).
/* de 1 à N */
croissant(0).
croissant(N) :- N>0, N1 is N-1, croissant(N1), write(N), nl.
un nombre est pair?
 pair(0).
 pair(X) :- X>0, X2 is X-2, pair(X2).
 somme des N premiers entiers. (Ou : som(N,X) est vrai si X est la
somme des entiers de 1 à N.):
som(0,0). som(N,X) :- N>0, N1 is N-1, som(N1,X1), X is
N+X1.

factorielle d'un nombre. (Ou : fact(N,X) est vrai si X vaut N!.)

fact(0,1). fact(N,X) :- N>0, N1 is N-1, fact(N1,X1), X is
N*X1.
fibo(N,X) est vrai si X est la valeur de la suite de Fibonacci au
rang N.
fibo(1,1). fibo(2,1). fibo(N,X) :- N>2, U is N-1, V is N-2,
fibo(U,U1), fibo(V,V1), X is U1+V1.