Chapitre 1

Introduction

Module: Représentation des connaissances et

raisonnement 1
Chargée de module: Dr. Makhlouf A.
2 Problématique

 En intelligence artificielle, les systèmes physiques ou virtuels évoluant de

manière autonome doivent être pourvus de capacités de représentation de
leur environnement et de raisonnement. L’axe thématique « Représentation
des connaissances et raisonnements » se consacre à l’étude (l’identification,
la modélisation, la représentation et l’implémentation) des différents types
d’informations (connaissances, croyances, préférences, actions, etc.) et de
raisonnements nécessaires au développement de tels systèmes.
 Des langages logiques (propositionnels, modaux, pondérés, etc.) et des
modèles graphiques (réseaux bayésiens, systèmes d’argumentation abstraits,
réseaux conceptuels, etc.) sont utilisés pour représenter les différentes
informations (qualitatives ou numériques) disponibles.
3 Introduction

 La représentation des connaissances se situe au cœur

de la problématique des sciences cognitives en
général, et de l'intelligence artificielle en particulier. Elle
fait parfois appel à des théories développées
antérieurement mais qu'elle utilise sous un angle
particulier, parfois elle crée de nouveaux outils,
conceptuels.
4 Introduction à l'Intelligence Artificielle(IA)

 Le projet de l'Intelligence Artificielle (IA) est de construire

des artefacts intelligents.
Intelligence : percevoir, raisonner, communiquer et
agir.
Construire : aspect ingénierie => un agent perçoit,
raisonne, communique et agit.
Artefact : machine inorganique manipulant des
symboles.
 Evaluation : Test de Turing ?
5 Test de Turing

 Repose sur le jeu de l'imitation.

 Suggère l'ensemble de composants de l'IA :
connaissance, raisonnement, apprentissage et
compréhension du langage.
 Prix Loebner ([Link]
[Link]).
6 Définitions de l'IA
7 Démarche cognitive

 Tentative de compréhension du fonctionnement de

l'esprit humain.
 Utilisation de modèles informatiques et de techniques
expérimentales de la psychologie.
 Approche difficile à mettre en œuvre :
 Difficile à transcrire dans des programmes
informatiques.
 Problème de performance.
8 Démarche pragmatique
 Exploitation de la logique mathématique : notation et règles de
dérivation.
 Les problèmes et les connaissances doivent être traduits en une
description formelle.
 Le système exploite des mécanismes abstraits de raisonnement
pour dériver une solution.
 Limites :
 Tous les comportements intelligents ne sont pas logiques.
 Problèmes liés aux ressources dans des cas concrets et
pratiques (temps, capacité mémoire et calcul).
9 Problématique :Algorithme & heuristique

 Tout problème pour lequel aucune solution

algorithmique n'est connue relève à priori de
l'intelligence artificielle.
 Algorithme : codé dans un certain langage de
programmation pour fournir un programme, consiste en
une description exhaustive de la séquence d'opération
à mener pour résoudre un problème.
 Heuristique : méthode de résolution qui emprunte des
voies non déterministes, et dont le succès n'est pas
garanti mais qui, lorsqu'elle marche , permet souvent
une grande économie de temps de calcul (ex : les jeux).
10 Domaines

 Aide à la prise de décisions.

 Reconnaissance et synthèse de la parole, d'images.
 Reconnaissance de l'écriture
 Traitement du langage naturel
 Apprentissage
 Robotique
 Jeux (othello, backgammon, échecs, etc..).
 Aide à la programmation
11 Un exemple avec les jeux

 Les échecs :
 Arbre du jeu : 10128 nœuds.
 Deeper Blue (IBM) bat Kasparov en 1997.
 Deeper Blue : 200 millions de positions calculées par
seconde.
 Deeper blue : jusqu'à 8 coups à l'avance.
 Othello : 1060 nœuds.
 Les dames : 1032 nœuds.
12 Les origines

 1943 : Articles de McCullough et Pitts (réseaux de

neurones) et Wiener, Rosenblueth et Bigelow
(rétroaction) sont les fondements de la cybernétique.
 1956 : Conférences de Darmouth college : le terme IA
est proposé par MacCarthy (créateur du LISP).
13 1ère période : années 50-60

 Logic Theorist (Newell, Shaw, Simon 1956) :

démonstration de théorèmes de la logique des
propositions.
 En 58, Prédiction de Newell et Simon : "Avant 1968,un
programme sera champion d'échecs et démontrera
un important théorème mathématique."
 General Problem Solver (GPS Newell, Simon - 1961) imite
les méthodes humaines pour la résolution de problèmes.
 Le robot Shakey (SRI) raisonne et agit physiquement.
 Approche essentiellement combinatoire.
14 1ère période : années 50-60

 Eliza (Weizenbaum) : A computer program for the study

of natural language communication between man and
machine. Communications of the ACM, 9.1:36-45.
 STUDENT (Bobrow 1967) résolution de problèmes
algébriques.
 Réseaux de neurones (Rosenblatt -1962).
 Algorithmes génétiques (Friedberg -1958).
15 2ème période : années 60-70

 Un constat sur les travaux de la 1ère période :

 Pas de "sens commun" (ELIZA).
 Apprentissage des réseaux de neurones est limité (Minsky,
Papert 1969).
 Il faut gérer les connaissances
 Systèmes experts
 Cadres
 Représentation des connaissances (KR) basé sur la logique.
 Apprentissage est un problème clé.
 Approche combinatoire + heuristique
16 2ème période : années 60-70

 Les systèmes experts

 DENDRAL (Feigenbaum) réalise l'analyse
automatique de spectres de masse pour déterminer
la structure moléculaire du corps chimique étudié.
 MYCIN (Shortliffe) diagnostique les maladies
infectieuses du sang et propose un traitement
adapté.
17 3ème période : les années 80

 IA approchée par l'industrie

 Systèmes experts : Digital Equipment (Xcon),
Intellicorp
 Lisp machines: LMI, Symbolics
 Robotique
 Reconnaissance des formes et de la parole
 Retour de réseaux de neurones.
18 Période actuelle

 IA devient plus technique et mathématique (moins

philosophique)
 Preuves formelles et empirisme (contre intuition).
 Les agents
 Un glue entre des champs de l'IA
 Gestion de l'information
 Pour aider les utilisateurs humains
 Data mining
19 Langages utilisés

 Langages applicatifs :
 Fonctionnels : LISP (MacCarthy en 1960) et les les
autres (Caml, Miranda, Haskell, etc.).
 Logique : PROLOG (Colmerauer 1972) et les autres
(OPS5, CLISP, etc.).
 Langages objets
 Smalltalk, Java, C++, Python, etc..
20 Exemple

Un fermier sur une rive veut passer sur l'autre rive d'une
rivière avec un renard, une oie et un sac de grains . Son
bateau ne peut contenir que 2 entité s .
Contraintes : s'il laisse le canard seul avec le renard, ce
dernier va manger l'oie. S'il laisse l'oie avec le sac de
grains! Plus de grains .
Résoudre le problème du passage d'une rive à l'autre .
21 Exemple
 Pour avoir une bonne perception du problème, on doit s’efforcer
de trouver une représentation simple et complète. On commence
par identifier les objets pertinents : le fermier, le renard, l’oie et le
sac de grains ainsi que la rivière et la barque.
 Par ailleurs, on note qu’à chaque instant il est important de
connaître la position de chaque objet. À un instant donné, la
situation peut être décrite par la position du fermier et de chacun
de ses biens. On parlera alors d’un état.
 En étudiant les mouvements des divers objets, on note que le
parcours du fermier comprend des étapes consistant chacune, à
partir d’une rive, à embarquer seul ou avec un de ses biens et
ramer jusqu’à l’autre rive.
22 Exemple
On ne considérera qu’une partie de tous les états possibles.
Par exemple, l’état < fermier, renard / oie, grain > n’a pas à
être considéré puisque l’oie ne doit pas être laissée seule
avec le grain. Le changement d’un état à un autre sera
représenté par une flèche orientée reliant le premier au
second. Le problème peut être complètement représenté
au moyen du graphe suivant :
23 Exemple
24 Exemple

La recherche d’une solution devient alors très facile. Il est même

possible de trouver plusieurs solutions. Par exemple :
 1, 2, 3, 4, 5, 8, 9, 10
 1, 2, 3, 6, 7, 8, 9, 10 ·
 1, 2, 3, 4, 5, 4, 3, 6, 7, 8, 9, 10.
Idéalement, une bonne représentation est celle qui permet une
résolution presque immédiate du problème. Elle doit donc être
transparente, concise, complète et doit permettre un accès rapide à
l’information, selon une démarche procédurale.
25 Exemple

Une représentation doit comprendre Dans le problème du fermier, la

quatre parties fondamentales : · représentation comprenait :
 lexicale : Quels sont les symboles  au niveau lexical : les nœuds et les
autorisés pour représenter objets et flèches pour représenter le
relations ? problème ;
 structurelle : Quelles sont les  au niveau structurel : une flèche
contraintes d’arrangement de ces reliait deux nœuds ; ·
symboles ?
 au niveau procédural : des
 procédurale : Comment créer et mécanismes mentaux permettent
modifier l’information ? de dessiner le graphe en fonction
de la perception du problème ainsi
 sémantique : Comment associer un que de l’interprétation qui serait
sens aux descriptions formelles ? faite de la représentation
symbolique.
 au niveau sémantique : un nœud était
associé à chaque couple de listes
d’objets et une flèche à chaque
changement d’état ;
26 Information, Donnée, Connaissance
 Donnée (data)
 Elément fondamental servant de base à un raisonnement, à une
recherche. (ex : _ _ _)
 Information (information)
 Elément de connaissance susceptible d'être codé pour être
conservé, traité ou communiqué.
 Représentation conventionnelle d'un information sous une forme
convenant à son traitement par ordinateur. (ex: SOS)
 Connaissance (Knowledge)
 Ce que l'on a appris par l'étude ou la pratique. (ex : En cas
d'alerte, ...).
 la connaissance inclut la généralisation et l'abstraction d'un grand
volume de données [Wiederhold, 1986].
27 Connaissances et agents

 Raisonnement intelligent n'est rien sans connaissances

(expertise)
 Nécessité d'une représentation des connaissances
 Nécessité de développement des algorithmes /
heuristiques pour le traitement de ces représentations
28 Connaissance et raisonnement

 Connaissance
≠ de donnée et information. Nouvelles connaissances
peuvent être créées depuis des connaissances à
l'aide de raisonnements.
 Raisonnement
Penser de manière cohérente et logique.
Inférence logique
Le processus de création de connaissances implicites
depuis des connaissances explicites.
29 Représentation des connaissances
 C’est le transfert des connaissances d’un expert vers une machine -
-> Psychologie cognitive

 Changement de media
 Changement de forme de représentation

 C’est aussi une tâche de modélisation linguistique : puissance

expressive, applicable pour le raisonnement, efficace.
30 Représentation des connaissances

 Knowledge Representation : KR.

 Représentation : une relation entre 2 domaines :
 Le domaine à représenter (ex: le nombre 7, le
concept de femme), le domaine représenté est bien
souvent plus concret et accessible que le premier
domaine (les symboles "7" ou "VII", le symbole "O+").
 KR ="the field of study concerned with using formal
symbols to represent a collection of propositions
believed by some agent."
31 Différents types de connaissances

 Connaissance procédurale : Représente comment un problème est

résolu. Indique comment réaliser une tâche.
 Connaissance déclarative : Décrit ce qui est connu du problème ;
des énoncés décrivant les objets et concepts.
 Méta-connaissance : Décrit la connaissance sur la connaissance, par
exemple, quelle connaissance est adaptée à un moment donné
pour résoudre une tâche donnée. À relier à l’efficacité.
 Connaissance heuristique : Connaissance empirique acquise par un
expert au fil de son expérience passée. Sert à guider le raisonnement.
Appelée aussi connaissance de surface (vs. profonde).
 Connaissance structurée : Décrit un modèle mental de l ’expert sous
forme de structures : concepts, sous-concepts, objets, etc.
32 Apport de la logique

 On peut utiliser la logique dans le contexte de la KR mais

certaines approches réfutent l'utilisation de logiques.
 "According to one view, logic is the study of entailment
relations languages, truth conditions, and rules of
inference". [R. Brachman, H. Lesvesque].
33 2 approches

 Symbolique : il existe une correspondance entre les

éléments du modèle et la représentation symbolique.
L'algorithme manipulant ces connaissances exploite
directement cette correspondance.
 Approche inspirée concepts biologiques : les
correspondances entre les deux modèles (réel et
représenté), autres que les entrées et sorties, sont très
difficiles à mettre en évidence. Le processus de
résolution n'exploite donc aucune correspondance et
les méthodes les plus utilisées sont les statistiques et les
probabilités. Autres exemples : les réseaux de neurones
et les algorithmes génétiques.
34 Approche symbolique

 2 classes :
Une approche basée sur les règles dans laquelle on
retrouve les sous-ensembles de la programmation
logique et les systèmes experts.
Une approche basée sur le concept d'objet dans
laquelle on retrouve les sous-ensembles des réseaux
sémantiques, les cadres, les scripts, les logiques de
descriptions, les graphes conceptuels, les espaces
conceptuels et les systèmes hybrides.
35 Base de connaissances (KB)

 Une description (simplifiée, abstraite) d'un domaine.

 Une structure symbolique avec des règles formelles de
manipulation de ces symboles.
 Nécessité d'un lien avec le domaine référent
(interprétation)
 Contient des données intensionnelles et extensionnelles.
36 Représentation des connaissances

 Comment représenter et utiliser l'information dans des

modèles informatiques
 Deux domaines principaux :
 Conception de formats pour décrire l'information
Des langages généraux (logique des prédicats).
 Encodage de la connaissance
Identifier et décrire des vocabulaires (ontologies).
37 Solution simple

 On programme la connaissance nécessaire dans le

système. Par exemple en Lisp ou Prolog.
 Cette approche possède des défauts :
 Le système est basé sur les connaissances du
développeurs.
 impossible d'implémenter des modules pour
l'explication des comportements "intelligents".
38 Un système de KR

La connaissance n'est pas programmée dans le système

mais elle est explicitement et déclarativement représentée
dans le système, en utilisant un langage formel : une
formalisme de représentation des connaissances.
39 Opérations de base d'un KB

 Tell
 Ajouter une entrée dans le KB
 Fonctionnalités liées
Ajouter des entrées dérivées
Tester la cohérence de l'ensemble
 Untell
 Supprimer une entrée de la KB
 Fonctionnalités liées
Supprimer les entrées dérivées
40 Opérations de base d'un KB

 Ask Questionner la KB
 Pour savoir si une entrée est une conséquence
logique de la KB
 Pour obtenir des résultats respectant la satisfaction
de contraintes
41 KR et Base de données

 Base de données : connaissances concrètes

 Pas de disjonctions, ni de quantificateurs (sauf dans
le schéma)
 KR : connaissances abstraites
 Expressivité
 Raisonnement
 Base de données déductives est un juste milieu