République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université de Jijel
Faculté des Sciences Exactes et Informatique
Département d’Informatique

MII IA SYSTEMES INTELLIGENTS

Support de cours élaboré par Dr. Saloua CHETTIBI Maître de

Conférences B en Informatique | 2019/2020
 Avant-propos
Le présent support de cours est le fruit de cinq ans d’expérience dans l’enseignement
de la matière intitulée « Systèmes Intelligents » aux étudiants en master II
spécialité « Intelligence Artificielle».
« Développer un système intelligent » est évidemment la question principale en IA. Mais
que désigne-t-on par système intelligent ? Les bonnes réponses sont multiples : « c’est
un système qui raisonne, qui supporte l’incertitude, qui est doté de la faculté
d’apprentissage1 … la réponse peut être aussi : c’est un système qui peut traiter un
langage naturel».
En effet, l’intelligence est multi-facette. C’est pourquoi les chapitres dans ce support
de cours semblent à première vue un peu hétérogènes. Les thématiques suivantes
sont abordées : la conception des agents intelligents, les ontologies, les logiques non
classiques, à savoir : les logiques de description, la logique floue, les logiques
modales et temporelles. Une introduction au Traitement Automatique du Langage
Naturel (TALN) est également prévue.
L’objectif pédagogique ultime de la matière SI est de faire découvrir aux étudiants
comment ces différentes thématiques sont en fait étroitement liées :
 Un système intelligent peut être mono-agent ou multi-agent (SMA).
 Un agent intelligent peut mener un raisonnement approximatif via un
système d’inférence floue.
 Le comportement désiré d’un agent peut être spécifié/vérifié grâce aux
logiques temporelles.
 Les différents agents dans un SMA peuvent communiquer via un vocabulaire
défini par le biais d’une ontologie.
 Une ontologie est un modèle de représentation de connaissance souvent
formalisé en logique de description.
 Une ontologie peut être construite à l’aide des outils du TALN.
 La représentation de la sémantique d’un langage naturel s’appuie sur les
différents formalismes de représentation des connaissances y compris les
ontologies.
 …etc.
La matière est très intéressante et n’a pour prérequis que la connaissance des
logiques des propositions et des prédicats. Le contenu de ce document est toujours
en évolution : toute remarque susceptible d’améliorer sa qualité est la bienvenue.

L’auteur, Novembre 2019.

1
La partie de l’apprentissage est volontairement omise puisque elle fait l’objet d’un autre
module dans le cursus IA.

Page | i
 Table des Matières

CHAPITRE 1 : Agents Intelligents

1.1 Introduction ...................................................................................................................................................................................................1
1.2 Concept d’Agent en IA .......................................................................................................................................................................2
1.3 Caractéristiques d’un agent intelligent ..................................................................................................................................2
1.4 Structure des agents intelligents ..................................................................................................................................................4
1.5 Environnement de la tâche et ses propriétés ...................................................................................................................6
1.6 Modèle abstrait des agents ...........................................................................................................................................................8
1.7 Architectures concrètes des agents ...........................................................................................................................................10
1.7.1 Agent basé sur la logique ...........................................................................................................................................10
1.7.2 Architecture à subsomption ......................................................................................................................................12
1.7.3 Architecture BDI (Belief, Desire, Intention) ...............................................................................................14
[Link] Description informelle du modèle ................................................................................................14
[Link] Spécification formelle d'un agent BDI .......................................................................................15
1.7.4 Architectures hybrides .................................................................................................................................................16
1.8 Conclusion ......................................................................................................................................................................................................18
Références du chapitre ..................................................................................................................................................................................19

CHAPITRE 2 : Connaissance et Ontologie

2.1 Introduction ...................................................................................................................................................................................................20
2.2 Niveau de connaissance ......................................................................................................................................................................21
2.3 Ontologies .......................................................................................................................................................................................................22
2.3.1 Origine du terme Ontologie ......................................................................................................................................22
2.3.2 Définition de l’Ontologie en Informatique...................................................................................................22
[Link] Une Ontologie est un « Vocabulaire très riche »...............................................................23
[Link] Ontologie Versus Base de connaissance .................................................................................23
2.4 Cycle de Vie des ontologies ............................................................................................................................................................24
2.5 Phase de Conceptualisation............................................................................................................................................................24
2.6 Logiques de Description ..................................................................................................................................................................26
2.6.1 Syntaxe et Sémantique des LDs .............................................................................................................................28
2.6.2 Propriétés ..................................................................................................................................................................................29
2.6.3 Problèmes d’inférences..................................................................................................................................................29
[Link] Réduction au non satisfiabilité .........................................................................................................29
[Link] Algorithme de Tableaux Sémantiques pour la logique ALC..............................30
2.7 Phase d’opérationnalisation – Langage OWL ..................................................................................................................32
2.8 Conclusion .....................................................................................................................................................................................................34
TD 1. Conceptualisation d’une première Ontologie ...........................................................................................................36
TD 2. Formalisation de notre Ontologie en LD SHOIN(D) ...........................................................................................40
TD 3. Opérationnalisation de l’ontologie avec PROTéGé ..............................................................................................40
TD 4. Exercices Supplémentaires ........................................................................................................................................................46
Références du chapitre ..................................................................................................................................................................................49

CHAPITRE 3 : Systèmes d’Inférence Floue

3.1 Introduction ...................................................................................................................................................................................................50
3.2 Logique Floue ..............................................................................................................................................................................................51
3.2.1 Concept d’ensemble flou .............................................................................................................................................51

Page | ii
 3.2.2 Degré d’appartenance Vs Probabilité ...............................................................................................................51
3.2.3 Opérations sur les ensembles flous.....................................................................................................................52
3.2.4 Types des fonctions d’appartenance .................................................................................................................53
3.3 Raisonnement approximatif ...........................................................................................................................................................54
3.3.1 Variable linguistique .......................................................................................................................................................54
3.3.2 Proposition floue.................................................................................................................................................................55
3.3.3 Opérations de la logique floue ................................................................................................................................55
3.4 Système d’inférence floue de type MAMDANI .............................................................................................................56
3.5 Modèle de Sugeno ....................................................................................................................................................................................59
3.6 Contrôle flou d’une machine à laver........................................................................................................................................60
3.7 Contrôleur flou pour la navigation d’un robot mobile de type voiture .................................................62
3.8 Conclusion .....................................................................................................................................................................................................64
Travaux Pratiques .............................................................................................................................................................................................65
Références du chapitre ..................................................................................................................................................................................66

CHAPITRE 4 : Logiques Modales

4.1 Introduction ...................................................................................................................................................................................................67
4.2 Logique modale propositionnelle ..............................................................................................................................................68
4.2.1 Syntaxe de la logique modale propositionnelle ..........................................................................................69
4.2.2 Mondes possibles et structure de Kripke..........................................................................................................69
[Link] Sémantique des mondes possibles ..........................................................................................................70
[Link] Propriétés algébriques des relations d’accessibilité ...................................................................70
4.3 Axiomes de la logique modale ......................................................................................................................................................71
4.4 Systèmes de la logique modale .....................................................................................................................................................71
4.5 Raisonnement sur les connaissances dans un système multi-agent .............................................................74
4.6 Logique dynamique et Logique déontique ........................................................................................................................74
4.7 Logiques temporelles.............................................................................................................................................................................74
4.7.1 Logique LTL............................................................................................................................................................................75
[Link] Syntaxe de la logique LTL....................................................................................................................75
[Link] Sémantique de la logique LTL..........................................................................................................75
4.7.2 Logique CTL ...........................................................................................................................................................................76
[Link] Syntaxe de la logique CTL ...................................................................................................................76
[Link] Sémantique de la logique CTL .........................................................................................................76
4.7.3 Vérification de modèle (ou Model Checking) ...........................................................................................77
4.8 Conclusion .....................................................................................................................................................................................................79
Recueil d’exercices ............................................................................................................................................................................................80
Références du chapitre ..................................................................................................................................................................................84

CHAPITRE 5 : Introduction au Traitement Automatique du Langage Naturel

5.1 Introduction ...................................................................................................................................................................................................85
5.2 Niveaux d’analyse linguistique dans une application du TALN ...................................................................86
5.3 Modèles et Algorithmes ......................................................................................................................................................................87
5.4 Quelques notions préliminaires en TALN ..........................................................................................................................88
5.4.1 N-grammes ..............................................................................................................................................................................88
5.4.2 Corpus..........................................................................................................................................................................................88
5.4.3 Thésaurus ..................................................................................................................................................................................88
5.5 Programmation logique avec Prolog .......................................................................................................................................89
5.5.1 Rappel des notions de la logique des prédicats utilisées en PL .................................................89
5.5.2 Langage Prolog ....................................................................................................................................................................90

Page | iii
5.6 Chaines de Markov .................................................................................................................................................................................93
5.6.1 Modèles de Markov Cachés .....................................................................................................................................93
5.6.2 Algorithme de Viterbi ....................................................................................................................................................94
5.7 Traitement phonétique .........................................................................................................................................................................95
5.8 Traitement morphologique ..............................................................................................................................................................96
5.8.1 Automates à état fini .....................................................................................................................................................97
5.8.2 Etiquetage morphosyntaxique avec l’algorithme de Viterbi .....................................................98
5.9 Analyse syntaxique .................................................................................................................................................................................100
5.9.1 Grammaires formelles .................................................................................................................................................100
5.9.2 Grammaires à clauses définies en Prolog ...................................................................................................102
5.10 Sémantique Lexicale...........................................................................................................................................................................104
5.10.1 Décomposition en primitives sémantiques ...............................................................................................104
5.10.2 Polysémie et ambiguïté .............................................................................................................................................105
5.10.3 Similarité entre mots d’après thésaurus ......................................................................................................105
5.11 Conclusion ..................................................................................................................................................................................................107
Travail Pratique...................................................................................................................................................................................................108
Références du chapitre ..................................................................................................................................................................................110

ANNEXE : Sujets des Examens

Examen 2015/2016 ...........................................................................................................................................................................................112
Examen 2016/2017 ...........................................................................................................................................................................................114
Examen 2017/2018 ...........................................................................................................................................................................................116

Page | iv
 Liste des Figures

Figure 1.1 schéma d’un agent standard ........................................................................................................................................2

Figure 1.2 La distinction cognitif/réactif ......................................................................................................................................4
Figure 1.3 Représentation schématique d’un agent réflexe simple........................................................................5
Figure 1.4 Représentation schématique d’un agent basé sur un modèle ..........................................................5
Figure 1.5 Représentation schématique d’un agent basé sur les Buts .................................................................6
Figure 1.6 Représentation schématique d’un agent basé sur l’utilité...................................................................6
Figure 1.7 Schéma associé au modèle abstrait construit..................................................................................................9
Figure 1.8 l’environnement simplifié du robot aspirateur ............................................................................................11
Figure 1.9 Système de contrôle à découpage vertical ........................................................................................................12
Figure 1.10 Flux de données/contrôle dans les trois architectures en couches...........................................16
Figure 1.11 Model d’un agent INTERRAP ..................................................................................................................................17
Figure 1.12 Situations de conflit entre deux robots Interrap ..................................................................... 18

Figure 2.1 Les niveaux de description de comportement selon Newell ............................................................21

Figure 2.2 Description du processus de classification au niveau cognitif ........................................................22
Figure 2.3 Cycle de vie d’une ontologie.........................................................................................................................................24
Figure 2.4 Les langages OWL .................................................................................................................................................................32
Figure 2.5 Hiérarchie de classe sous Protégé ............................................................................................................................41
Figure 2.6 Hiérarchie des relations binaires et des attributs sous Protégé ......................................................41
Figure 2.7 Définition du concept Medecin_S dans Protégé ..........................................................................................42

Figure 3.1 Union de deux ensembles flous avec l’opérateur Max ..........................................................................52
Figure 3.2 Intersection de deux ensembles flous avec l’opérateur Min .............................................................52
Figure 3.3 Ensembles flous de la variable linguistique Température ..................................................................54
Figure 3.4 Les différents modules d’un SIF de type MAMDANI ...........................................................................56
Figure 3.5 Méthodes de défuzzification.........................................................................................................................................57
Figure 3.6 Exemple d’un SIF de type MAMDANI ................................................................................ 58
Figure 3.7 Les ensembles flous pour l’entrée (a) Saleté (b) poids ............................................................................61
Figure 3.8 La sortie quantité détergent ...........................................................................................................................................61
Figure 3.9 Le robot voiture RobuCar utilisé dans les expérimentations ...........................................................62

Figure 4.1 Le carré modal...........................................................................................................................................................................68

Figure 4.2 Systèmes de la logique modale ...................................................................................................................................72

Figure 5.1 Processus général du TALN..........................................................................................................................................86

Figure 5.2 Représentation du modèle de Markov par un Treillis ...........................................................................93
Figure 5.3 Un signal de la parole correspondant à “this is”.........................................................................................95
Figure 5.4 Triangles sémiotiques pour fauteuil, tabouret et chaise .......................................................................104
Figure 5.5 Analyse sémique du mot canard...............................................................................................................................105

Page | v
 Liste des Tableaux

Tableau 1.1 Exemples d’agents et de leurs spécifications PEAS..............................................................................7

Tableau 1.2 Exemples d’environnements de tâche avec leurs propriétés .......................................................8

Tableau 2.1 Logiques de description ..............................................................................................................................................26

Tableau 2.2 Correspondance entre la syntaxe OWL et la syntaxe LD (partie 1)........................................33
Tableau 2.3 Correspondance entre la syntaxe OWL et la syntaxe LD (partie 2)........................................34

Tableau 3.1 Fonctions d’appartenance usuelles ..................................................................................................................53

Tableau 3.2 Opérations de la logique floue................................................................................................................................55

Tableau 4.1 Interprétations des opérateurs modaux .........................................................................................................68

Tableau 4.2 Interprétations de la relation d’accessibilité ..............................................................................................69
Tableau 4.3 Interprétations de la relation d’accessibilité et des opérateurs modaux
en logique Temporelle...................................................................................................................................................................................74
Tableau 4.4 Signification des opérateurs de la logique LTL........................................................................................75

Page | vi
 CHAPITRE 1
Agents Intelligents

1.1 Introduction
L’Intelligence Artificielle (IA) peut être définie comme l’étude de la conception
d’agents intelligents [1], c’est-à-dire des systèmes qui montrent un comportement
rationnel. Un système est dit rationnel s’il fonctionne correctement compte tenu de ce
qu’il sait. Cette approche de l’IA est au cœur de ce premier chapitre centré sur le
thème de la conception des agents intelligents.
Ce cours récapitule les caractéristiques d’un agent intelligent et met surtout
l’accent sur le compromis « réactivité/proactivité ». La conception d’un agent
intelligent passe d’abord par la spécification de son environnement de tâche et
ensuite par le choix d’une architecture convenable (réactive, délibérative ou hybride).
Mais avant d’aborder le comment ? (i.e. les architectures concrètes), les étudiants
doivent comprendre de quoi s’agit-il ? En réponse à cette question, le modèle abstrait
des agents est développé.
Il faut souligner que les exemples utilisés dans le chapitre portent en général sur
des robots mobiles. La robotique mobile étant un domaine d’application typique
pour les agents intelligents.

Page | 1
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

1.2 Concept d’Agent en IA

Le mot Agent a pour origine le terme latin « agere » qui signifie « faire ».
Simplement, un Agent peut être vu comme une « une entité qui agit ». Cette entité
peut être physique ou virtuelle [2]: une entité physique est quelque chose qui agit
dans le monde réel (robot, avion, voiture). En revanche, un composant logiciel, un
module informatique sont des entités virtuelles car elles n’existent pas
physiquement.
Une définition plus élaborée de ce qui est un agent est la suivante [1]: « Un agent
est tout ce qui peut être vu comme percevant son environnement au travers de
capteurs et agissant sur cet environnement au travers d'effecteurs». Un agent
générique ou standard peut être schématisé comme dans la figure ci-dessous.

Figure 1.1 Schéma d’un agent standard [1].

Sujet de Débat
Peut-on considérer un système expert (de genre MYCIN) comme Agent ?
Un tel système n'interagit pas directement avec un environnement:
 il reçoit ses informations non pas via des capteurs mais par l'intermédiaire d'un
utilisateur agissant comme intermédiaire.
 il n'agit pas sur un environnement mais donne des commentaires ou des conseils
à un tiers.
La réponse doit être alors NON [3].
NB. Mycin est un système Expert (développé dans les années 1970) servant au
diagnostic des maladies infectieuses.

1.3 Caractéristiques d’un agent intelligent

Il est très difficile de donner une définition finale pour « l’Intelligence » et c’est
également le cas si on cherche à définir ce qui est « un agent intelligent ». Selon
Frékon et Kazar [4], un agent est dit intelligent s’il est : intentionnel, cognitif,
rationnel et adaptatif.
 L’agent intentionnel possède des buts et des plans explicites lui permettant
d’accomplir ses buts [2].

Page | 2
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

 L’agent cognitif est un agent qui mène des raisonnements afin de choisir ses
actions [4]. Il est doté d’une représentation interne de son environnement avec un
mécanisme d’inférence.
 L’agent rationnel est celui qui choisit toujours l’action appropriée. Plus
formellement, un agent rationnel choisit l’action qui maximise l’espérance d’une
mesure de performance [1].
 L'agent adaptatif est un agent capable de moduler son comportement selon l'état
de l’environnement [4]. Autrement, c’est un agent doté de la faculté
d’apprentissage qui lui permet de compenser ses connaissances a priori
incomplètes voire erronées [1].
Autres propriétés désirables des agents intelligents [3]:
 Autonomie: l'agent est plus ou moins indépendant de l'utilisateur et des autres
agents.
 Sociabilité: capacité d’interagir avec d’autres agents ou même avec des humains
en utilisant un ACL (Agent Communication Language).
 Réactivité: capacité de répondre rapidement aux changements dans
l’environnement.
 Proactivité: capacité de prendre l’initiative c’est-à-dire prévoir les évènements
futurs et donc d’anticiper en planifiant les actions à accomplir.
Un agent est qualifié de flexible s’il vérifie les trois dernières propriétés.

Sujet de débat
Réactivité Vs Proactivité avec un exemple adapté de la référence [2] :
Imaginons un robot qui veut franchir une porte et que celle-ci se ferme à clef. S’il
s’agit d’un agent proactif, il pourra construire (d’une certaine manière) un plan
« ouvrir Porte» :
Aller jusqu’à l’endroit où se trouve la clef
Prendre la clef
Aller jusqu’à la porte
Ouvrir la porte avec la clef
S’il s’agit d’un agent réactif, on peut construire les règles de fonctionnement
suivantes :
Si je suis devant la porte et que j’ai une clef Alors l’ouvrir
Si je suis devant la porte et sans clef Alors essayer de l’ouvrir
Si la porte ne s’ouvre pas et que je n’ai pas la clef Alors aller chercher la clef
Si je cherche une clef et qu’il y a une clef devant moi Alors prendre la clef et aller
vers la porte
Comparons les deux agents :
Proactif Réactif
Le plan est construit par l’agent lui- Les règles sont données explicitement par le
même. concepteur.
Point fort : Optimisation (moins de Point fort : Souplesse (si la porte est ouverte,
déplacements si la porte est fermée) l’agent ouvre directement sans aller chercher
la clef)

Page | 3
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Bien que la distinction entre réactivité et proactivité soit utile dans un premier
temps, mais il ne faut pas comprendre qu’il s’agit d’une opposition catégorique. Bien
au contraire, l’enjeu actuel est de réaliser des agents qui mêlent des capacités
cognitives et réactives [2].

Figure 1.2 La distinction cognitif/réactif (Axe pratique d’évaluation de la capacité

des agents à accomplir individuellement des tâches complexes et à planifier leurs
actions) [2].

1.4 Structure des agents intelligents

La structure d’un agent intelligent peut être décrite comme suit [1] :
Agent = Architecture + Programme
Le programme agent implémente la fonction associant aux perceptions des
actions (la boite noire dans la Figure 1.1). L’architecture quant à elle désigne un
équipement informatique doté d’effecteurs et de capteurs physiques. Elle transmet
au programme les perceptions issues des capteurs, exécute le programme et
achemine les actions choisies aux effecteurs. Nous nous intéressons dans ce qui suit à
la conception des programmes agents.
Selon le fonctionnement du programme agent, on distingue les quatre types
d’agents suivants [1]:
a) Agent réflexe simple
Il sélectionne des actions en fonction de la perception courante et ignore le
reste de l’historique des perceptions. Le comportement d’un agent réactif est
régi par un ensemble de règles de la forme « Si situation(s) ou condition(s)
Alors action ».
Exemple : le thermostat d’un chauffage est muni d’un capteur pour détecter
la température ambiante. Selon si la température est actuellement trop basse
ou bonne, une action est choisie : « allumer chauffage » ou « éteindre
chauffage».
b) Agent réflexe fondé sur des modèles
Ce type d’agent doit maintenir des informations concernant : i) la manière
dont le monde évolue indépendamment de l’agent et ii) la façon dont les
actions de l’agent affectent le monde. La perception courante est combinée
avec l’ancien état interne pour mettre à jour l’état courant en se basant sur le
modèle interne.

Page | 4
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Figure 1.3 Représentation schématique d’un agent réflexe simple [1]

Figure 1.4 Représentation schématique d’un agent basé sur un modèle [1].

c) Agent fondé sur les buts

Dans la sélection de ses actions, ce type d’agent est guidé non seulement par
l’état actuel de l’environnement mais également par son but final.
d) Agent fondé sur l’utilité
Il est possible d’atteindre ses buts en suivant différentes séquences d’actions,
mais quelle est la meilleure séquence : la plus sûre, la moins coûteuse, la plus
rapide, etc. ? L’agent doit choisir les actions susceptibles de maximiser sa
fonction d’utilité.

Page | 5
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Figure 1.5 Représentation schématique d’un agent basé sur les Buts [1].

Figure 1.6 Représentation schématique d’un agent basé sur l’utilité [1].

1.5 Environnement de la tâche et ses propriétés

L'environnement est l'univers dans lequel l'agent évolue et effectue ses tâches.
L'environnement de la tâche est défini par la combinaison : mesure de performance,
environnement, effecteurs et capteurs (PEAS en anglais de : Performance Environment
Actuators Sensors).
Avant de construire un agent intelligent, on doit spécifier son PEAS. Dans le
Tableau 1.1 se trouvent des exemples d’agents avec leurs spécifications PEAS.
On distingue différents types d'environnements, en l’occurrence [1]:
 Entièrement observable (Vs partiellement observable): si l’agent peut avoir une
information précise, complète et à jour concernant l’état de l’environnement
alors l’environnement est entièrement observable. (à l’inverse : données bruités,
incomplètes ou imprécises…..)

Page | 6
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

 Mono-agent (Vs multi-agent : concurrentiel ou coopératif).

 Déterministe (Vs stochastique) : si l’état suivant de l’environnement est
complètement déterminé par l’état actuel et par l’action exécutée alors
l’environnement est déterministe, il est stochastique sinon.
 Séquentiel (Vs épisodique): dans les environnements séquentiels, la décision
courante est susceptible d’affecter les décisions futures. (In contrario, chaque
épisode est indépendant).
 Statique (Vs dynamique): l'état de l’environnement ne change pas au cours de
la prise de décision. Soulignons que le monde physique est un environnement
hautement dynamique.
 Discret (Vs continu) : s’il existe un nombre fini d’actions et de perceptions
alors l’environnement est discret.

Le Tableau 1.2 récapitule les propriétés de plusieurs environnements familiers.

Tableau 1.1 Exemples d’agents et de leurs spécifications PEAS [1].

Page | 7
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Tableau 1.2 : Exemples d’environnements de tâche avec leurs propriétés [1].

1.6 Modèle abstrait des agents

Le modèle abstrait des agents présenté ci-après est pris de la référence [3].
Commençons par la modélisation de l’agent générique déjà vu dans la section 1.2,
pour ce faire considérons:
𝑺 = {𝒔𝟏, 𝒔𝟐, … } : L’ensemble des états de l'environnement.
𝑨 = {𝒂𝟏, 𝒂𝟐, … } : L'ensemble des actions potentielles.
Alors l'agent peut être vu comme une fonction qui associe à une séquence d'états
(historique ou expérience) une action :
Action : S* → A
Le comportement non déterministe d'un environnement peut être décrit par
une fonction :
𝑬𝒏𝒗 : 𝑺 𝒙 𝑨 → ℘(𝑺).
Si l'environnement est déterministe alors Env devient :
𝑬𝒏𝒗 : 𝑺 𝒙 𝑨 → 𝑺
L'historique de l’interaction de l'agent avec son environnement, considérée
continue, est vu comme une séquence h infinie (𝑆0 é𝑡𝑎𝑛𝑡 𝑙 ′ é𝑡𝑎𝑡 𝑖𝑛𝑖𝑡𝑖𝑎𝑙):
𝒂𝟎 𝒂𝟏 𝒂𝒖−𝟏 𝒂𝒖
𝒉: 𝑺𝟎 → 𝑺𝟏 → 𝑺𝟐 … → 𝑺𝒖 → …
Un agent purement réactif ne tient pas compte de son expérience passée dans
la prise de décision : il réagit simplement à l'état courant du système. Dans ce cas, la
fonction action devient :
Action : S → A

Page | 8
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Exemple (Un modèle abstrait du thermostat)

Notation utilisée :
s1 (Température - OK) a1 (Allumer chauffage)
s2 (Basse Température) a2 (Eteindre chauffage)
𝑆 = { 𝑠1, 𝑠2}
𝐴 = { 𝑎1, 𝑎2}
La fonction Action est alors définie comme suit :
a2 si s = s1
Action (s) = {
a1 si s = s2
Nous raffinons maintenant la définition de la fonction Action en créant la fonction
see :
𝑺𝒆𝒆 : 𝑺 → 𝑷
Cette fonction a pour rôle d’associer à un état de l'environnement des perceptions
(P). Alors la fonction Action devient :
Action : P* → A
NB. Pour deux états différents de l’environnement, la fonction See peut associer la
même perception.
Exemple (Implémentation de la fonction See [3])
 Pour un robot mobile : une caméra vidéo, un capteur infra rouge, …etc.
 Pour un agent logiciel : par exemple des commandes linux comme : ls qui
renvoie la liste des répertoires ou fichiers se trouvant dans le répertoire
courant et ps qui renvoie la liste des processus en cours d’exécution.

Certains agents maintiennent un état interne mémorisant leurs historiques. On

définit alors I l'ensemble de tous les états internes. See ne va pas changer mais
Action devient :
Action : I → A
Dans ce cas, on aura besoin d'une nouvelle fonction qui met à jour l’état interne
en fonction de la nouvelle perception:
Next : I x P → I

Figure 1.7 Schéma associé au modèle abstrait construit [3].

Page | 9
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

En résumé :
 l'agent se trouve dans un état interne 𝒊𝒕 ;
 l’agent observe l'état courant de l'environnement 𝑺𝒕
 il génère une perception 𝑆𝑒𝑒(𝑺𝒕 )
 l'état interne est mis à jour par Next et devient Next(𝒊𝒕 , 𝑺𝒆𝒆(𝑺𝒕 ))
 Enfin, l’action choisie est : Action (Next(𝒊𝒕 , 𝑺𝒆𝒆(𝑺𝒕 )))

1.7 Architectures concrètes des agents

Dans la section précédente, nous n'avons pas déterminé à quoi ressemble
l'état interne de l’agent ni comment la fonction action est implémentée. En effet, les
principales architectures concrètes des agents [3] répondant à toutes ces questions
sont décrites dans les sous-sections suivantes.

1.7.1 Agent basé sur la logique

L'approche traditionnelle de l'IA symbolique suggère que le comportement
intelligent peut être généré par un système si ce dernier est doté d'une représentation
symbolique de l’environnement et de celle du comportement envisagé avec une
manipulation syntaxique de ces représentations. Dans notre contexte: les
représentations symboliques sont faites à l'aide de formules logiques et la
manipulation syntaxique correspond à une déduction logique (ou à une preuve de
théorème).
Au fait, l'état interne d'un agent basé sur la logique correspond à une base de
formules logiques notée ∆ (i.e. base de connaissance ou base des faits de l’agent). Soit
𝐿 l’ensemble de toutes les formules logiques et soit 𝐷 = ℘(𝐿) l’ensemble de toutes
les bases de connaissance possibles. Alors :
 La fonction See reste inchangée.
 La fonction Next devient : Next :D x P → D
 Pour la fonction Action : D → A, on donne le pseudo code suivant [3] :
1. Fonction action (∆: 𝐷): 𝐴
2. Début
3. Pour chaque 𝑎 ∈ 𝐴 faire
4. Si ∆⊢𝜌 𝑓𝑎𝑖𝑟𝑒 (𝑎) alors
5. Retourner a
6. Fin-si
7. Fin-pour
8. Pour chaque 𝑎 ∈ 𝐴 faire
9. Si ¬(∆⊢𝜌 ¬𝑓𝑎𝑖𝑟𝑒 (𝑎)) alors
10. Retourner a
11. Fin-si
12. Fin-pour
13. Renvoyer null
14. Fin fonction action

 L'état du système sous forme de formules logiques est passé à la fonction qui
doit renvoyer une action (Ligne1).

Page | 10
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

 L’agent cherche une action qui peut être dérivée avec les règles de
déduction 𝝆. Si une action est trouvée alors elle est renvoyée en sortie (Ligne
5).
 Si aucune action n’est trouvée, l’agent cherche au moins une action qui ne soit
pas explicitement interdite c’est à dire pour laquelle on ne peut pas dériver
¬ 𝑓𝑎𝑖𝑟𝑒 (𝑎) (Ligne 10).
 Si les tests précédents échouent, alors l’action Null (rien faire) est retournée
(Ligne 13).
Exemple [3]
Considérons l’exemple classique d’un robot aspirateur dont l’objectif est de
nettoyer une pièce (représentée par une grille 3x3). Initialement, l'agent est dans la
position (0,0) en face du nord. Seulement les déplacements illustrés sur la figure sont
autorisés (autrement dit : la trajectoire du robot est prédéfinie):

Figure 1.8 L’environnement simplifié du robot aspirateur.

Nous considérons que l’aspirateur est doté d’un capteur approprié pour la
détection de la saleté. Ce capteur permet l’acquisition de l’état de l’environnement.
On suppose l’existence d’une certaine fonction See permettant la transformation des
états aux perceptions suivantes: 𝑃 = {𝑆, 𝑋, 𝑌, 𝐷}
Tel que : S désigne Saleté, D désigne direction, (X,Y) représente la position de
l’aspirateur.
L’ensemble des actions potentielles est : 𝐴 = {𝐴𝑣𝑎𝑛𝑐𝑒𝑟, 𝑁𝑒𝑡𝑡𝑜𝑦𝑒𝑟, 𝑇𝑜𝑢𝑟𝑛𝑒𝑟}.
Remarque : Le raffinement de l’action Tourner (à gauche ou à droite ?) est laissé aux
étudiants.
En outre, définissons les prédicats du domaine :
𝑳(𝒙, 𝒚) : l'agent se trouve dans la localisation (x,y)
𝑺(𝒙, 𝒚) : présence de la Saleté dans la position (x,y)
𝑭(𝒅) : l’agent est en face de la direction d (Nord, Est, Ouest ou Sud).
L’aspirateur se trouve dans l’état initial (ce que l’agent connait sur son
environnement) :
∆0 = {𝐿(0,0), ¬𝑆(0,0), 𝐹(𝑁𝑜𝑟𝑑)}
Les règles de déduction qui régissent le fonctionnement de l'agent aspirateur sont les
suivantes:
𝑳(𝒙, 𝒚) ∧ 𝑺(𝒙, 𝒚) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑵𝒆𝒕𝒕𝒐𝒚𝒆𝒓)

Page | 11
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Cette règle est prioritaire aux règles de navigation suivantes:

𝑳(𝟎, 𝟎) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟎, 𝟎) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟎, 𝟏) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟎, 𝟏) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟎, 𝟐) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟎, 𝟐) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑻𝒐𝒖𝒓𝒏𝒆𝒓)
𝑳(𝟎, 𝟐) ∧ 𝑭(𝑬𝒔𝒕) ∧ ¬𝑺(𝟎, 𝟐) ⊢ 𝒇𝒂𝒊𝒓𝒆(𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟏, 𝟐) ∧ 𝑭(𝑬𝒔𝒕) ∧ ¬𝑺(𝟏, 𝟐) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑻𝒐𝒖𝒓𝒏𝒆𝒓)
𝑳(𝟏, 𝟐) ∧ 𝑭(𝑺) ∧ ¬𝑺(𝟏, 𝟐) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟏, 𝟏) ∧ 𝑭(𝑺) ∧ ¬𝑺(𝟏, 𝟏) ⊢ 𝒇𝒂𝒊𝒓𝒆(𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟏, 𝟎) ∧ 𝑭(𝑺) ∧ ¬𝑺(𝟏, 𝟎) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑻𝒐𝒖𝒓𝒏𝒆𝒓)
𝑳(𝟏, 𝟎) ∧ 𝑭(𝑬𝒔𝒕) ∧ ¬𝑺(𝟏, 𝟎) ⊢ 𝒇𝒂𝒊𝒓𝒆(𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟐, 𝟎) ∧ 𝑭(𝑬𝒔𝒕) ∧ ¬𝑺(𝟐, 𝟎) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑻𝒐𝒖𝒓𝒏𝒆𝒓)
𝑳(𝟐, 𝟎) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟐, 𝟎) ⊢ 𝒇𝒂𝒊𝒓𝒆 (𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟐, 𝟏) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟐, 𝟏) ⊢ 𝒇𝒂𝒊𝒓𝒆(𝑨𝒗𝒂𝒏𝒄𝒆𝒓)
𝑳(𝟐, 𝟐) ∧ 𝑭(𝑵) ∧ ¬𝑺(𝟐, 𝟐) ⊢ ⋯ (Arrêter ou recommencer ?)
Avantages/Inconvénients
L'approche basée sur la logique présente l'avantage d'un fondement
théorique solide. Cependant, la complexité des preuves des théorèmes limite
l'application de cette approche dans des environnements à forte contraintes
temporelles [4]. En outre, cette approche reste inappropriée quand il s’agit des agents
ayant des ressources de calcul, de stockage et/ou d’énergie limitées.
Enfin, il faut noter que l’implémentation de la fonction See effectuant le
passage de l’état de l’environnement vers des perceptions représentées via des
formules logiques n’est pas une tâche évidente.

1.7.2 Architecture à subsomption

Les architectures de l’IA classique utilisent un découpage vertical de type
« détecter- planifier-agir » [5] :

Figure 1.9 Système de contrôle à découpage vertical [5]

Les grandeurs physiques mesurées par les capteurs doivent être reformulées en des
informations symboliques exploitables par la couche planification. Cette dernière
maintient une représentation symbolique du monde. Les actions décidées sont

Page | 12
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

passées enfin au module responsable de l’exécution qui est directement connecté au

Effecteurs.
En opposition à cette vision, Rodney Brooks (le père de la robotique), a
développé dans les années 80 l’architecture à subsomption en utilisant un découpage
horizontal de type « Perception – Action ». A savoir, la subsomption désigne une
relation hiérarchique.
Brooks soutient la thèse suivante : « Le monde est son propre meilleur modèle ». Il
n’est pas nécessaire alors d’utiliser une représentation interne symbolique du monde.
Cette architecture de type réactive repose sur l’idée suivante : « Le comportement
intelligent est produit de l’interaction de l'agent avec son environnement et émerge de
l'interaction de plusieurs comportements plus simples » [3]. L’article « Elephants don’t Play
Chess » [6] décrit les robots développés par Brooks et ses collègues au sein du
laboratoire IA au MIT en utilisant l’architecture à subsomption (Robot Allen, Toto,
Herbert, Tom and Jerry, ….etc.)
Une architecture à subsomption comporte plusieurs modules (dits modules
de compétence), chaque module étant responsable de la réalisation d'une tâche
particulière et il est implémenté sous forme de règles : situation → action. Les
modules sont organisés sous forme hiérarchique.
Modèle formel correspondant [3]
 La fonction See a toujours le même rôle sauf que l'entrée des capteurs est
supposée très peu transformée.
 Une règle de comportement est une paire (𝑐, 𝑎) où 𝒄 ⊆ 𝑃 (P est l’ensemble des
perceptions) appelé condition et a est une action.
 Une règle de comportement (𝑐, 𝑎) est activée dans un état s SSI 𝑠𝑒𝑒(𝑠) ∈ 𝑐.
 Notons par 𝑅 l’ensemble de toutes les règles de comportement de l’agent ; On
définit une relation d’inhibition, ≺ ⊆ 𝑅𝑋𝑅 , qui est une relation d’ordre totale (i.e.
relation binaire Transitive, Réflexive et Antisymétrique). On écrit a ≺ 𝑏 et on lit a plus
prioritaire que b.
Le pseudocode de la fonction Action est comme suit:
1. Fonction action(𝑝: 𝑃): 𝐴
2. Var 𝑅è𝑔𝑙𝑒𝑠𝑎𝑐𝑡𝑖𝑣é𝑒𝑠 : ℘(𝑅)
3. Début
4. 𝑅è𝑔𝑙𝑒𝑠𝑎𝑐𝑡𝑖𝑣é𝑒𝑠 ← {(𝑐, 𝑎)|(𝑐, 𝑎) ∈ 𝑅 𝑒𝑡 𝑝 ∈ 𝑐}
5. Pour chaque (𝑐, 𝑎) ∈ 𝑅è𝑔𝑙𝑒𝑠𝑎𝑐𝑡𝑖𝑣é𝑒𝑠 faire
6. Si ¬(∃ (𝑐 ′ , 𝑎′ ) ∈ 𝑅è𝑔𝑙𝑒𝑠𝑎𝑐𝑡𝑖𝑣é𝑒𝑠 𝑡𝑒𝑙 𝑞𝑢𝑒 (𝑐 ′ , 𝑎′ ) ≺ (𝑐, 𝑎)) Alors
7. Retourner a
8. Fin-si
9. Fin-pour
10. Renvoyer null
11. Fin fonction action
Cette fonction détermine tout d’abord l'ensemble des règles de
comportements activées. Ensuite, pour chaque règle activée chercher s'il existe une
qui soit plus prioritaire. Si aucune n’est trouvée alors a est renvoyée. Si aucune règle
n'est activée alors renvoyer Null.

Page | 13
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Exemple [3]
Imaginons que l’architecture à subsomption est utilisée dans le contrôle d’un
robot mobile qui doit faire l’exploration d’une planète à la recherche d’une matière X
d’intérêt.
On peut proposer les règles de fonctionnement suivantes pour ce robot:
(R1) Si obstacle détecté alors changer de direction
(R2) Si porter échantillon et se trouver dans la station mère alors déposer échantillon
(R3) Si porter échantillon alors se diriger vers la station
(R4) Si détection de X alors prélever un échantillon
(R5) Si vrai alors explorer aléatoirement (toujours activée)
Avec l’ordre de priorité suivant: 𝑅1 ≺ 𝑅2 ≺ 𝑅3 ≺ 𝑅4 ≺ 𝑅5
Avantages/Inconvénients
Par sa simplicité, l’architecture à subsomption est bien adaptée à la résolution
de problèmes simples en temps réel (comme la navigation réactive d’un robot
mobile). L’insertion de nouveaux comportements se fait facilement sans avoir à
réécrire ceux déjà existants [5].
Néanmoins, en tant qu’architecture réactive, il sera impossible de doter
l’agent de la faculté de raisonnement ou d’apprentissage (aucun état interne n’est
maintenu et aussi aucune fonction d’utilité n’est définie). En outre, il n’existe pas une
méthodologie commune pour la construction des agents selon cette architecture : ce
n’est que par expérimentation qu’on vérifie la validité de notre conceptualisation [7].

1.7.3 Architecture BDI (Belief, Desire, Intention)

Cette architecture a été proposée par Michael Bartman en 1987, elle se base
sur la compréhension du raisonnement pratique: processus de décider, étape par
étape, quelle action exécuter pour aboutir à un objectif [3]. Dans ce processus, il faut
d’abord fixer les buts à atteindre (délibération) c'est-à-dire se demander quoi faire ?
Puis déterminer comment faire pour les atteindre ? (articulation moyens/fins) [4].

[Link] Description informelle du modèle

Le modèle BDI est basé sur trois attitudes mentales, à savoir: les croyances, les
désirs et les intentions.
Croyances : correspondent à la représentation de l'agent de l'état de son
environnement. Les croyances ne sont pas forcément vraies.
Exemple: un étudiant croit qu'il y aura des cours Dimanche prochain ; Alors
que c'est un jour férié par exemple.
Désirs : correspondent aux options disponibles à l'agent, les différents désirs peuvent
être en conflit.
Exemple : l'étudient peut assister le TD demain à 8h mais il peut aussi aller
voir son médecin à 8h.
Intentions : réfèrent à l'engagement de l’agent à la réalisation des désirs mais aussi
au plan lui permettant de les achever. Dans le modèle BDI, le raisonnement est

Page | 14
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

restreint à la réalisation des intentions. Bien sûr toute option en conflit avec les
intentions de l’agent doit être systématiquement annulée.
Exemple : l'étudiant décide d'assister au TD demain à 8H. Maintenant
l'étudiant doit raisonner sur comment arriver à l'heure. Le matin à 7:50 H
l'étudiant rencontre un collègue qui lui propose d'aller réviser en salle de
lecture : cette proposition est directement refusée !
En résumé : étant données des croyances sur l’environnement, l’agent peut avoir
plusieurs désirs mais celles choisies (engagements) deviennent les intentions de
l’agent ; les intentions déterminent les actions à exécuter (le plan).
Toutefois, un agent doit reconsidérer ou réviser ses intentions afin de
supprimer celles déjà réalisées, celles devenues impossibles ou celles dont la
motivation n’est plus présente. Certes, cette opération est coûteuse en termes des
ressources computationnelles.
Un dilemme se pose ici : d’une part, un agent doit reconsidérer ses intentions
(pour les raisons déjà mentionnées), d’autre part, un agent qui reconsidère
constamment ses intentions ne consacre pas suffisamment de temps dans leurs
réalisations et risque de ne les jamais accomplir. Il faut alors trouver un compromis :
déterminer la fréquence de reconsidération des intentions selon la dynamique de
l’environnement.

[Link] Spécification formelle d'un agent BDI

L’état d’un agent BDI, à tout moment, est défini par le triplet (B,D,I) tel que: 𝑩 ⊆
𝑩𝒆𝒍, 𝑫 ⊆ 𝑫𝒆𝒔, 𝑰 ⊆ 𝑰𝒏𝒕 , et :
 Bel: l’ensemble de toutes les croyances possibles sur l’état de
l’environnement.
 Des : l’ensemble de tous les désirs possibles de l’agent.
 Int : l’ensemble de toutes les Intentions possibles de l’agent.
Le comportement d'un agent BDI est alors défini par [3] :
 La fonction de révision de ses croyances qui calcule ses nouvelles
croyances à partir des croyances courantes et de nouvelles perceptions de
son environnement :
𝒃𝒓𝒇: ℘(𝑩𝒆𝒍) × 𝑷 → ℘(𝑩𝒆𝒍)
 Une fonction options de génération de ses options qui représentent ses
désirs ou choix possibles conformément à ses intentions ; basée sur les
croyances qu’il a de son environnement et sur ses intentions :
𝒐𝒑𝒕𝒊𝒐𝒏𝒔: ℘(𝑩𝒆𝒍) × ℘(𝑰𝒏𝒕) → ℘(𝑫𝒆𝒔)
 Fonction filtre : met à jour les intentions de l’agent (par exemple faire
exclure des intentions irréalisables, garder celles non encore réalisées,
exploiter de nouvelles opportunités …)
𝒇𝒊𝒍𝒕𝒆𝒓: ℘(𝑩𝒆𝒍) × ℘(𝑫𝒆𝒔) × ℘(𝑰𝒏𝒕) → ℘(𝑰𝒏𝒕)
Notons que filtrer(B,D,I) est inclus dans I union D : les nouvelles intentions sont soit
les anciennes intentions ou de nouvelles options adoptées.

Page | 15
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

 Fonction exécuter : retrourne une action exécutable

𝒆𝒙𝒆𝒄𝒖𝒕𝒆: ℘(𝑰𝒏𝒕) → 𝑨
Le pseudo-code de la fonction action de l’agent BDI correspond à ce qui suit:
1. Fonction action (p :P) : A
2. Début
3. 𝐵 ← 𝑏𝑟𝑓(𝐵, 𝑝)
4. 𝐷 ← 𝑜𝑝𝑡𝑖𝑜𝑛𝑠 (𝐵, 𝐼)
5. 𝐼 ← 𝑓𝑖𝑙𝑡𝑒𝑟(𝐵, 𝐷, 𝐼)
6. Retourner 𝑒𝑥𝑒𝑐𝑢𝑡𝑒 (𝐼)
7. Fin
Enfin, le model BDI est très intuitif avec une décomposition fonctionnelle
claire. Ce modèle a été implémenté avec succès notamment dans le système PRS
(Procedural Reasoning System) et son successeur dMars (distributed Multi-Agent
Reasonning System).

1.7.4 Architectures hybrides

Un agent réactif a l’avantage d’une réponse à temps du moment qu’il
fonctionne avec des règles simples de type : stimulus – action. Un tel agent ne
maintient aucune représentation de son environnement. Inversement, un agent
proactif ou délibératif maintient une représentation symbolique de son
environnement, manipule cette représentation afin de générer un comportement plus
ou moins sophistiqué. L’inconvénient d’un agent qui raisonne est qu’il est inadapté
aux environnements dynamiques.
Dans un problème issu du monde réel (environnement hautement
dynamique), on a besoin de la réactivité pour s’adapter aux changements survenant
dans l’environnement et de la délibération afin de réaliser des tâches plus ou moins
complexes. C’est cette constatation qui est derrière la proposition des architectures
hybrides qui combinent comportement réactif et proactif au sein d'un même agent.
Selon la propagation du flux données/contrôle, on distingue des architectures
verticales ou horizontales comme le montre la figure ci-dessous.

Figure 1.10 Flux de données/contrôle dans les trois architectures en couches [3].

Page | 16
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Dans une architecture horizontale, chaque couche propose une action et on

aura alors besoin de sélectionner une seule. Dans une architecture verticale, un seul
niveau se charge de la prise de décision. Si la couche inférieure est incapable de
décider alors le contrôle est passé à la couche supérieure et ainsi de suite.
NB. Quand il y a deux passes : on parle d’activation Bottom-up et d’exécution Top-
down.
Prenons comme exemple l'architecture Interrap de Jörg Müller (Integration of
Reactive Behavior and Rational Planning = Intégration du comportement réactif et
planification rationnelle) [8] qui génère comportement réactif, proactif et social. Il s’agit
d’une architecture verticale à deux passes [4]. Cette architecture a été simulée et
testée pour un problème de transport de marchandises par des robots mobiles (il
s’agit d’un SMA coopératif).

Figure 1.11 Model d’un agent INTERRAP [8]

Sur la figure 1.11 (BC pour base de connaissances) :
 BC-Monde (World Model) représente les croyances sur l'environnement.
 BC-Planification (Patterns of Behaviour & Local Plans) correspond à une
bibliothèque de plans.
 BC-Sociale (Cooperation knowledge) représente les croyances de l'agent sur les
autres agents du système et notamment sur leurs capacités de lui aider à
atteindre ses buts.
Les buts d'un agent InteRRaP sont divisés en trois catégories:
 Réactions (assurées par BBC): ce sont des buts simples à accomplir en
fonction des perceptions sur l'environnement.
 Buts locaux (assurés par PBC) : ce sont des buts que l'agent peut accomplir
lui-même.
 Buts coopératifs (assurés par CC) : ce sont les buts qui peuvent être accomplis
uniquement par une coopération avec d'autres agents dans le système.

Page | 17
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Exemple

Figure 1.12 Situations de conflit entre deux robots Interrap [8].

Pour la première scène (à gauche), les deux robots peuvent faire des simples
mouvements pour éviter la collision (reculer, tourner, etc.). Donc, le problème est
réglé au niveau de la couche responsable du comportement réactif. Pour la deuxième
scène (à droite), le robot a1 ne peut pas déposer sa charge puisque le robot a2 (qui
vient de déposer la sienne) le bloque. Une solution intelligente (avec un minimum de
déplacements pour les deux agents) consiste à déléguer le dépôt de la charge de a1 à
a2. La négociation d’un tel plan conjoint est assurée par la couche responsable du
comportement social.

1.8 Conclusion
Ce chapitre donne une vue d’ensemble sur la conception des agents
intelligents. En parallèle, l’attention des étudiants est orientée vers le domaine
pluridisciplinaire de la robotique mobile. Les connaissances théoriques exposées
dans ce chapitre peuvent être renforcées, par exemple, par l’apprentissage du
langage de programmation des systèmes multi-agent: «AgentSpeak» [9].
Dans le chapitre suivant, nous nous intéressons à la représentation des
connaissances via les ontologies. Nous parlerons, entre autres, sur leur apport à la
communication dans les systèmes multi-agent.

Page | 18
 Systèmes Intelligents

Chapitre 1: Agents Intelligents

Références du chapitre

[1] S. Russell and P. Norvig, Intelligence artificielle. Paris: Pearson Education, 2010.
[2] J. Ferber, Les systèmes multi-agents. Vers une intelligence collective. Paris :
InterEditions, 1995.
[3] G. Weiss, Multiagent systems: a modern approach to distributed artificial
intelligence. Cambridge, Mass. [u.a.]: MIT Press, 2006.
[4] L. Frécon and O. Kazar, Manuel d'intelligence artificielle. Lausanne: Presses
polytechniques et universitaires romandes, 2009.
[5] P. Arnaud, Des moutons et des robots. Lausanne: Presses polytechniques et
universitaires romandes, 2000.
[6] R. Brooks, Elephants don't play chess, Robotics and Autonomous Systems, vol.
6, no. 1-2, pp. 3-15, 1990.
[7] M. Luck, R. Ashri and M. D'Inverno, Agent-based software development. Boston:
Artech House, 2004.
[8] J.P. Müller and P. Markus, The agent architecture InteRRaP : concept and
application. Rapport de recherche, DFKI Saarbrücken (Allemagne), 1993.
[9] J. Hübner and M. Wooldridge, Programming Multi-Agent Systems in
AgentSpeak using Jason. John Wiley & Sons, 2008.

Page | 19
 CHAPITRE 2
Connaissance et Ontologie

2.1 Introduction
L’un des problèmes fondamentaux en Intelligence Artificielle est la
représentation symbolique des connaissances : sous forme de formules logiques (cas
d’un système formel) ou de règles de production (cas d’un système expert), etc. Le niveau
symbolique a été considéré pour longtemps comme le niveau adéquat pour la
modélisation de l’activité mentale [1]. Insatisfait de cette vision, Allen Newell [2]
propose d’ajouter un niveau d’abstraction dit « niveau de connaissance » au-dessus
du « niveau symbolique ». À ce niveau doit être définie la connaissance
indépendamment de sa représentation symbolique.
Le premier objectif de ce chapitre, intitulé « Connaissance et Ontologie », est de
montrer l’apport des ontologies au domaine de la représentation de connaissance.
Initialement, est d’une manière très simplifiée, on peut dire qu’une ontologie est le
support de tout type de connaissance : classes d’objets, propriétés et relations entre
objets mais aussi faits, règles et contraintes. A savoir, la conceptualisation d’une
ontologie doit être spécifiée au niveau cognitif. Mais, le présent cours va au-delà de
la phase de conceptualisation : nous abordons également la formalisation des
ontologies en logique de description et leur encodage en langage OWL (Ontologie
Web Language).

Page | 20
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

2.2 Niveau de connaissance

Une connaissance ne contient pas dans sa forme ce qui fait d’elle une
connaissance [1]. Par forme, on désigne la représentation de la connaissance sur
ordinateur en termes de structures de données avec les opérations de manipulation
et les procédures d’accès. Les connaissances se rapportent plutôt au contenu
conceptuel des structures de données [3].
D’après Newell, la description d’un processus de résolution de problèmes en
termes de connaissances nécessite l’introduction d’un nouveau niveau de description
indépendant de toute représentation informatique : le niveau cognitif (Knowledge
Level). Newell a proposé de continuer le parallèle entre le comportement de
l’homme et celui de la machine comme l’illustre la figure ci-dessous.

Connaissances Niveau cognitif

Représentations Niveau Symbolique

Gènes, neurones Niveau électronique

(
Sujet humain Artefact

Figure 2.1 Les niveaux de description de comportement selon Newell [1]

Le niveau physique de l’artefact correspond à tout ce qui est diode, transistor,
circuit électronique, etc. Le niveau symbolique quant à lui inclut tout ce qui est
langage de programmation.
Le niveau cognitif doit permettre de décrire les intentions et les justifications
rationnelles du comportement d’un système. A ce niveau, la connaissance prend la
forme de buts à atteindre, de savoir sur le monde et d’actions sur l’environnement.
Ces trois éléments interagissent selon le principe de rationalité. Ce principe consiste
à choisir, en fonction du savoir sur le monde, les actions susceptibles de conduire aux
buts visés [1].
Exemple
Donner une spécification au niveau cognitif du processus de classification.
Pour répondre à cette question, il faut identifier les connaissances nécessaires
au traitement du problème de classification séparément de toute implémentation
opérationnelle [1] :
 But : dans un problème de classification, l’objectif est d’identifier la classe
d’appartenance d’un objet.
 Savoir : observations enregistrées sur l’objet en question ainsi que les classes
avec leurs caractéristiques.
 Actions : re-description des observations en termes des caractéristiques,
comparaisons, un éventuel affinement de la classification obtenue.

Page | 21
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Caractéristiques Comparer Classes

Redécrire Affiner

Observations Classes

(
Figure 2.2 Description du processus de classification au niveau cognitif [1].
Pour plus d’éclaircissement, considérons un problème très simplifié:
classification d’une maison dans une des deux classes : «bonne maison» et « maison
moins bonne». Une bonne maison possède trois caractéristiques : elle est grande, avec
jardin et bien située. Une maison est moins bonne si une des caractéristiques
précédentes n’est pas vérifiée.
Etant donnée une maison, on a les observations suivantes : superficie (X),
avec jardin ou non (Y) et distance par rapport au centre-ville (Z).
Re-description (S1 et S2 sont des seuils):
Si X ≥ S1 alors grande
Si Z ≤ S2 alors bien située (puisque proche du centre-ville)
Dans l’affinement, on peut proposer une nouvelle classe de maisons : celles qui ne
vérifient aucune des caractéristiques d’une bonne maison.

2.3 Ontologies
Une donnée s'élabore à partir d'observation elle est simple et brute et n'a pas
d'utilité immédiate (par exemple 40). Cependant, l’information est une donnée
explicite et signifiante (par exemple: 40°C : maintenant on comprend qu’il s’agit d’une
Température). La connaissance est une information contextualisée à laquelle on peut
attribuer une valeur de vérité [4] (par exemple: le malade de la chambre 3 du service
pédiatrie a une température de 40°C).
L’ontologie est un support de connaissance utilisé par la communauté IA depuis les
années 80. Mais que désigne-t-on par Ontologie ? Et d’où vient ce terme ?

2.3.1 Origine du terme Ontologie

Les philosophes depuis Aristote se sont intéressés à ce qui existe et comment
le décrire mais aussi comment le placer parmi ce qui existe déjà. L’Ontologie, en
philosophie, est une branche de la Métaphysique qui s’intéresse à l’existence. En
effet, ce terme est construit à partir des racines grecques ontos qui veut dire ce qui
existe, l’être ou l’existant, et logos qui veut dire étude : d’où l’interprétation « étude de
l’être et par extension de l’existence ».

2.3.2 Définition de l’ontologie en Informatique

Les chercheurs en IA ont adopté les ontologies comme modèle computationnel
qui permet un certain raisonnement automatique. Pour certains chercheurs, les
ontologies computationnelles présentent une sorte de philosophie appliquée. La

Page | 22
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

définition de l’ontologie la plus répandue, en informatique, est celle donnée par

Gruber [5] : « Une ontologie est une spécification explicite et formelle d’une
conceptualisation partagée ».
 Spécification explicite : les concepts, propriétés, relations, contraintes et les
axiomes d'un domaine de connaissance sont définis d’une manière claire et
précise.
 Formelle: interprétable par une machine ce qui permet de mener des
raisonnements et déduire des nouvelles connaissances.
 Conceptualisation : modèle abstrait d'un phénomène dans le monde.
 Partagée : il s’agit de connaissances communes (sens & vocabulaire). Une
ontologie est le produit d’un consensus au sein d’une communauté.
Les ontologies sont utilisées comme référentiels de communication entre humains et
entre agents artificiels. Elles réduisent les types de conflits suivants:
 Conflit conceptuel : un même terme est interprété différemment.
Par exemple : les chercheurs en IA n'ont pas une vision commune sur ce qui est
l’intelligence. Chacun l’interprète d’un certain point de vue.
 Conflit terminologique : on est d'accord pour le sens d’un concept mais pas
pour le nom donné au concept.
Par exemple : doit-on utiliser Taxonomie ou Taxinomie pour désigner une
classification?
Pour mieux comprendre ce qui est une ontologie, nous positionnons cette
dernière par rapport à des notions très proches, à savoir: « Vocabulaire » et « Base de
connaissance ».

[Link] Une Ontologie est un « Vocabulaire très riche »

Selon leurs consistances, on distingue différents types de vocabulaires:
 Vocabulaire contrôlé: il s’agit d’une liste de termes liés à un domaine
d’intérêt.
 Taxonomie: liste de termes avec une relation de subsomption entre les
termes.
 Thésaurus: organisation hiérarchique de termes liés entre eux par des
relations de “synonymie” et de “terme associé".
 Ontologie : vocabulaire plus consistant, il peut être vu comme un réseau
(différents types de relations) de concepts (au fait, un concept est plus qu’un simple
terme).

[Link] Ontologie versus Base de connaissance

L’ontologie capture et représente la connaissance d’un domaine sans se
rattacher à une application particulière (dans ce cas, on parle d’ontologie de domaine).
Elle reflète une compréhension commune du domaine et elle est de ce fait
réutilisable. En revanche, une base de connaissance est construite dans l’esprit de
résolution d’un problème lié à un domaine donné. De ce fait, elle doit contenir de la
connaissance opérationnelle et seulement la partie de la connaissance conceptuelle
nécessaire à la résolution du problème posé [6].

Page | 23
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

De ce point de vue, les ontologies peuvent être utilisées comme un méta-

modèle pour la construction des systèmes à base de connaissance.

2.4 Cycle de vie des ontologies

Le cycle de vie d’une ontologie, inspiré du génie logiciel, peut être
schématisé comme dans la figure ci-dessous :

Figure 2.3 Cycle de vie d’une ontologie.

 Spécification: description de la portée de l'ontologie, ses utilisateurs ainsi que le
niveau de formalisation souhaité.
 Acquisition des connaissances: identifier les termes de l'ontologie et leur
définition et cela via l’analyse d'un corpus documentaire et/ou par interview des
spécialistes/experts.
 Conceptualisation: l'ingénieur de connaissance identifie les concepts, les
relations, les axiomes,… etc.
 Intégration: recherche d'ontologies existantes qui peuvent être réutilisées.
 Formalisation: formaliser le modèle conceptuel obtenu (dans notre cours, en
logique de description).
 Opérationnalisation: codage de l’ontologie dans un langage opérationnel (dans
notre cours, en langage OWL).
 Évaluation: vérifier et valider l'ontologie (de point de vue cohérence, complétude, etc.)
Remarque : Bien sûr ce processus n'est pas linéaire on peut réviser notre ontologie
voire même mettre à jour nos besoins.

2.5 Phase de Conceptualisation

Une alternative possible dans la Phase de conceptualisation consiste à suivre les
étapes de la méthode METHONTOLOGY [7] considérée parmi les méthodes les
plus complètes pour la construction d’une ontologie :
1. Construire un glossaire de termes.

Page | 24
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

2. Construire les arbres de classification des concepts (les hiérarchies).

3. Tracer le diagramme des relations binaires entre concepts.
4. Pour chaque arbre de classification construire :
1. une table de concepts
2. une table de relations binaires
3. une table des attributs
4. une table des axiomes
5. une table des instances
6. une table des assertions
Remarque
Les axiomes expriment la sémantique du domaine. Ils déterminent comment les
relations/concepts peuvent être utilisés d’une manière opérationnelle (aller au-delà
de la terminologie). Exemples d’axiomes dans une ontologie:
 Propriétés algébriques d’une relation (symétrie, réflexivité, transitivité)
 La subsomption entre concepts et/ou relation
 Les cardinalités d’une relation
 L’incompatibilité entre concepts (i.e. la disjonction)
Exemple (Il s’agit d’une initiation à la conceptualisation, voir le TD pour approfondir)
« Un robot mobile est un agent intelligent. un agent intelligent est capable d’exécuter une
tâche d’une manière autonome, il est capable de percevoir l’état de son environnement et de se
déplacer dans celui-ci ; un robot mobile possède une architecture … une architecture de
robotique peut être réactive, proactive ou hybride…iRobot Roomba 620 est un robot
aspirateur il a les caractéristiques suivantes 1: Diamètre du robot (cm) : 34, Poids du robot
(kg) : 3,6, Puissance (W) : 33, Capacité du réservoir (l) : 0,[Link] qu’un certain client
(c1) utilise son nouvel aspirateur iRobot Roomba 620 (a1) pour nettoyer sa maison (m1) »

A partir de ce texte, on peut dégager :

1. Les concepts : robot mobile, agent intelligent, environnement, architecture de
robotique, robot aspirateur…
2. Deux hiérarchies (y compris les relations de subsomption est-un):
H1 : Agent intelligent
–Robot mobile
– Robot aspirateur
– iRobot Roomba 620
H2: Architecture de robotique
– Architecture réactive
– Architecture proactive
– Architecture hybride
3. Les relations binaires: posséder, se déplacer dans, nettoyer, …
4. Les attributs du concept robot aspirateur : diamètre, poids, puissance, capacité du
réservoir,…
5. Les instances: a1, c1, m1,…
6. Les assertions : « a1 (nettoyer) m1 », « a1 (se déplacer dans) m1 »,…

1 [Link]

Page | 25
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

2.6 Logiques de Description

Plus récemment, les langages de représentation des ontologies à base des
logiques de description sont devenus très populaires. Ces langages sont apparus
notamment dans le contexte du Web sémantique [8]. Les logiques de description
sont des fragments suffisamment expressifs de la logique des prédicats2 et qui sont
souvent décidables.

2.6.1 Syntaxe et Sémantique des LDs

La sémantique d’une LD est donnée au moyen d’un domaine
d’interprétation I qui est un ensemble non vide d’individus et d’une fonction
d'interprétation I qui fait correspondre à un concept un sous-ensemble de I et à un
rôle un sous-ensemble de I X I . Le tableau ci-dessous récapitule la Syntaxe et la
sémantique des Logiques de Description [9].

Logique Constructeur Syntaxe Sémantique

𝑨𝓛 Concept atomique A 𝐴𝐼 ⊆ ∆𝐼
Rôle atomique R 𝑅𝐼 ⊆ ∆𝐼 × ∆𝐼
Concept le plus générale T ∆𝐼
Concept le plus spécifique ⊥ ∅
Négation atomique ¬𝐴 ∆𝐼 \𝐴𝐼
Conjonction 𝐶 ∩𝐷 𝐶 𝐼 ∩ 𝐷𝐼
Quantification universelle ∀𝑅. 𝐶 {𝑎 ∈ ∆𝐼 |∀𝑏(𝑎, 𝑏) ∈ 𝑅𝐼 → 𝑏 ∈ 𝐶 𝐼 }
Quantification existentielle ∃𝑅. 𝑇 {𝑎 ∈ ∆𝐼 |∃𝑏(𝑎, 𝑏) ∈ 𝑅𝐼 }
non qualifiée
U Disjonction ou union de 𝐶 ∪𝐷 𝐶 𝐼 ⋃𝐷𝐼
deux concepts
ℇ Quantification existentielle ∃𝑅. 𝐶 {𝑎 ∈ ∆𝐼 |∃𝑏(𝑎, 𝑏) ∈ 𝑅𝐼 ⋀𝑏 ∈ 𝐶 𝐼 }

ℵ Restriction de nombre ≤ 𝑛𝑅 {𝑎 ∈ ∆𝐼 | |{𝑏|(𝑎, 𝑏) ∈ 𝑅𝐼 }| ≥ 𝑛}

≥ 𝑛𝑅 {𝑎 ∈ ∆𝐼 | |{𝑏|(𝑎, 𝑏) ∈ 𝑅𝐼 }| ≤ 𝑛}
= 𝑛𝑅 {𝑎 ∈ ∆𝐼 | |{𝑏|(𝑎, 𝑏) ∈ 𝑅𝐼 }| = 𝑛}
F Rôle fonctionnel ≤ 1𝑅 {𝑎 ∈ ∆𝐼 | |{𝑏|(𝑎, 𝑏) ∈ 𝑅𝐼 }| ≤ 1}
C Négation de concepts ¬𝐶 ∆𝐼 \𝐶 𝐼
arbitraire
Q Restriction de nombre ≤ 𝑛𝑅. 𝐶 {𝑎 ∈ ∆𝐼 | |{𝑏 ∈ ∆𝐼 |(𝑎, 𝑏) ∈ 𝑅𝐼 ⋀𝑏 ∈ 𝐶 𝐼 }| ≤ 𝑛}
qualifiée ≥ 𝑛𝑅. 𝐶 {𝑎 ∈ ∆𝐼 | |{𝑏 ∈ ∆𝐼 |(𝑎, 𝑏) ∈ 𝑅𝐼 ⋀𝑏 ∈ 𝐶 𝐼 }| ≥ 𝑛}
= 𝑛𝑅. 𝐶 {𝑎 ∈ ∆𝐼 | |{𝑏 ∈ ∆𝐼 |(𝑎, 𝑏) ∈ 𝑅𝐼 ⋀𝑏 ∈ 𝐶 𝐼 }| = 𝑛}
S Clôture transitive de rôle 𝑅+ ⋃𝑖≥1(𝑅𝐼 )𝑖

H Rôle hiérarchique 𝑅⊆𝑆 𝑅𝑖 ⊆ 𝑆 𝑖

I Rôle inverse 𝑅 − {(𝑏, 𝑎) ∈ ∆𝐼 × ∆𝐼 |(𝑎, 𝑏) ∈ 𝑅𝐼 }
O Description des concepts {𝑎1 } ∪ … {𝑎𝑛 } {𝑎1 𝐼 } ∪. . .∪ {𝑎𝑛 𝐼 }
par énumération d'individus
nommés

Tableau 2.1 Logiques de description.

2
La logique des prédicats est semi-décidable.

Page | 26
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

En augmentant la logique de base 𝑨𝓛 avec les différents constructeurs on obtient

une famille de logiques de description, en l’occurrence :
 ALℇ N c’est la logique AL à laquelle sont ajoutées la quantification existentielle et
la restriction de nombre non qualifiée.
 Logique ALC est équivalente à ALUℇ puisque grâce à la négation non atomique
on peut définir U et ℇ :
¬(C ∩ D) ≡ ¬C ∪ ¬D
¬∀R. C ≡ ∃R. ¬C
 La logique ALC augmentée par les constructeurs H et S donne la logique SH.
 SH étendue avec I et F donne la logique SHIF (base du langage OWL-Lite).
 SHIF est clairement la logique SH + I + F.
 SHOIN est la logique SH + O+ I + N (qui est à la base du langage OWL-DL).
Remarques
¬(≥ n R) ≡ ≤ (n − 1)R
¬(≤ n R) ≡ ≥ (n + 1)R
¬¬ 𝐶 ≡ 𝐶
Une base de connaissance 𝚺 écrite en LD contient deux composantes [9]:
 T (TBox) : représente la terminologie d’un domaine sous forme de définitions de
concepts et de rôles. T est un ensemble fini d’axiomes terminologiques :
Axiome Lecture
𝑪 ≡ 𝑫 Le Concept C est par définition égal au concept D (on utilise la
même syntaxe pour définir l’équivalence entre rôles)
𝑪 ⊆ 𝑫 Le Concept C est par définition subsumé par le concept D (on
utilise la même syntaxe pour exprimer la subsomption entre rôles)
 A (ABox) : contient les assertions sur les individus du domaine considéré en
utilisant les termes de l’ontologie. A est un ensemble fini d’assertions:
Assertion Lecture
𝑪 (𝒂) a est un individu du concept C
R (𝒃, 𝒄) Les individus b et c sont liés par R
Exemple (Syntaxe)
Considérons les deux concepts atomiques Personne et Féminin et le rôle atomique
aEnfant. On peut alors définir les concepts suivants:
o Homme : Personne ⊓¬Féminin
o Personnes avec au moins un enfant : Personne⊓∃aEnfant
o Personnes dont tous les enfants sont des garçons : Personne⊓∀aEnfant. ¬Féminin

Exemple inspiré de la référence [10] (Sémantique)

Soit la base de connaissance qui contient les axiomes suivants :
𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑒𝑢𝑟 ⊆ 𝑀𝑒𝑚𝑏𝑟𝑒𝐹𝑎𝑐𝑢𝑙𝑡é
𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑒𝑢𝑟(𝐴𝑙𝑖)
𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒_à(𝐴𝑙𝑖, 𝑢𝑛𝑖𝑣𝐽𝑖𝑗𝑒𝑙)
L’interprétation suivante est-elle un modèle pour cette BC ?
𝑰 = {𝑎, 𝑏, 𝑐}
(𝐴𝑙𝑖)𝐼 = 𝑎
(𝑢𝑛𝑖𝑣𝐽𝑖𝑗𝑒𝑙)𝐼 = 𝑏

Page | 27
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

(𝑃𝑟𝑜𝑓𝑒𝑠𝑠𝑒𝑢𝑟)𝐼 = {𝑐}
(𝑀𝑒𝑚𝑏𝑟𝑒𝐹𝑎𝑐𝑢𝑙𝑡é)𝐼 = {𝑎, 𝑐}
(𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒_à)𝐼 = {(𝑐, 𝑏)}
Réponse : Non, pour les raisons suivantes :
 (Ali)I n’est pas inclut dans (Professeur)I cependant d’après la BC Ali est un
professeur.
 D’après la BC ((Ali)I , (univJijel)I ) doit appartenir à (Enseigne_à)I alors que ce
n’est pas le cas.

2.6.2 Propriétés [9]

 Satisfiabilité (consistance): Un concept C est satisfaisable, pour une interprétation
I, SSI CI ≠ ф.
Exemple le concept 𝐻𝑜𝑚𝑚𝑒 ∩ ¬𝐻𝑜𝑚𝑚𝑒 est insatisifable.
 Subsomption: Un concept C est subsumé par un concept D, pour une
interprétation I, si et seulement si 𝐶 𝐼 ⊆ 𝐷𝐼
Exemple 𝑃è𝑟𝑒 ⊆ 𝐻𝑜𝑚𝑚𝑒
 Equivalence : Un concept C est équivalent à un concept D, pour une
interprétation I, si et seulement si CI = DI
 Incompatibilité ou disjonction: Deux concepts C et D sont incompatibles, pour
une interprétation I, si et seulement si CI ∩ DI = ф
Exemple : GrandPère ∩ GrandeMère⊆⊥
Exemple (Exercice Résolu du sujet d’examen 2015/2016)
Imaginons qu’on dispose de deux ontologies décrivant : « les Enseignants, les
Chercheurs ainsi que les Documents rédigés par ces derniers» :
 La première ontologie est construite selon le point de vue « tâche
pédagogique» (utilisée par exemple au sein du département) ; Voici son
ABOX complète (Tous les individus sont mentionnés)
ABOX de la première ontologie
Enseignant (Omar) Enseignant (Ali) Enseignant (Sonia)
Enseignant (Lila) Enseignant (Dina)
Enseignant Vacataire () Chargé de cours (Ali) Chargé de TD (Lila)
Chargé de TP (Omar) Chargé de TP (Sonia) Chargé de TP (Dina)
Support de cours (doc3) Support de cours (doc4)
 La deuxième ontologie est construite selon le point de vue « grade
scientifique» (utilisée par exemple au sein du laboratoire de recherche) ; Voici
son ABOX complète:

ABOX de la deuxième ontologie

Maitre-assistant classe A (Omar) Maitre-assistant classe A (Sonia)
Maitre de conférences (Lila) Professeur (Ali)
Enseignant-chercheur (Omar) Enseignant-chercheur (Ali)
Enseignant-chercheur (Sonia) Enseignant-chercheur (Lila)
Article de recherche (doc1) Article de recherche (doc2)

Page | 28
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

On veut fusionner les deux ontologies. Exprimer en LD la TBOX de

l’ontologie fusionnée (résultante) tout en donnant les justifications formelles
adéquates.
Réponse : Clairement, le passage à la TBOX de l’ontologie fusionnée se fera à base
des interprétations des concepts données dans les ABOX :
TBOX en LD Justification formelle
Chargé de cours ≡professeur Un concept C est équivalent à un concept D si et
Chargé de TD ≡Maitre de conf… seulement si CI = DI
Enseignant-chercheur ⊑Enseignant Un concept C est subsumé par un concept D si et
MAA⊑ Chargé de TP… seulement si 𝐶 𝐼 ⊆ 𝐷𝐼
Support de cours ⊑ 𝑻 Ne sont subsumés par aucun concept défini dans
Article de recherche ⊑ 𝑻 les deux ontologies
Enseignant ⊑ 𝑻 ….
Enseignant Vacataire ⊑ ⊥ Un concept est non satisfiable alors il est subsumé
par ⊥ ; Sachant qu’un concept C est satisfaisable
pour une interprétation I SSI CI ≠ ф.

2.6.3 Problèmes d’inférences

Etant donnée une BC en LD, les problèmes d’inférence que nous souhaitons
résoudre sont les suivants [10] (on parle de concepts ou de classes indifféremment):
1) Satisfiabilité de la BC dans l’ensemble (possède-t-elle au moins un modèle ?)
2) Satisfiabilité de classes.
3) Inclusion de classes.
4) Equivalence de classes.
5) Disjonction de classes.
6) Appartenance d’un individu à une classe.
7) Recherche de tous les individus connus d’une classe.
Notons bien que les problèmes de 2 à 7 se réduisent au problème 1 qui peut être
résolu en utilisant l’algorithme des Tableaux Sémantiques. Cet algorithme est basé
sur l’idée de preuve par réfutation : c’est-à-dire afin de prouver qu’une formule est
satisfiable on montre que sa négation est une contradiction.

[Link] Réduction au non satisfiabilité

Soit K une base de connaissance en LD, la réduction au non satisfiabilité se fait
ainsi [10] :
 Non satisfiabilité d’une classe
(𝐾 ⊨ 𝐶 ⊆ ⊥) SSI 𝐾 ∪ {𝐶 (𝑎)} est non satisfiable tel que a est un nouvel individu
(ne figure pas déjà dans K).
 Subsomption
(𝐾 ⊨ 𝐶 ⊆ 𝐷) SSI 𝐾 ∪ {(𝐶 ∩ ¬𝐷)(𝑎)} est non satisfiable tel que a est un nouvel
individu (ne figure pas déjà dans K).
Soulignons que 𝐶 ⊆ 𝐷 ≡ ¬𝐶 ∪ 𝐷
 Equivalence de classes
(𝐾 ⊨ 𝐶 ≡ 𝐷) SSI 𝐾 ⊨ 𝐶 ⊆ 𝐷 et 𝐾 ⊨ 𝐷 ⊆ 𝐶

Page | 29
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

 Disjonction de classes
(𝐾 ⊨ 𝐶 ∩ 𝐷 ⊆ ⊥) SSI 𝐾 ∪ {(𝐶 ∩ 𝐷)(𝑎)} est non satisfiable tel que a est un
nouvel individu.
 Appartenance d’un individu à une classe
(𝐾 ⊨ C (a)) SSI 𝐾 ∪ {¬𝐶 (𝑎)} est non satisfiable.
 Recherche de tous les individus connus d’une classe
Il faut vérifier pour tous les individus a, si 𝐾 ⊨ 𝐶 (𝒂).

[Link] Algorithme des Tableaux Sémantiques pour la logique ALC

Avant d’appliquer l’algorithme, il faut réécrire la BC en utilisant seulement
les symboles de l’union et de l’intersection. Ensuite, il faut transformer la BC à son
équivalent en NNF (Negation Normal Form) comme suit [10]:

𝑁𝑁𝐹(𝐶 ) = 𝐶 𝑠𝑖 𝐶 𝑒𝑠𝑡 𝑢𝑛 𝑐𝑜𝑛𝑐𝑒𝑝𝑡 𝑎𝑡𝑜𝑚𝑖𝑞𝑢𝑒

𝑁𝑁𝐹(¬𝐶 ) = ¬𝐶 𝑠𝑖 𝐶 𝑒𝑠𝑡 𝑢𝑛 𝑐𝑜𝑛𝑐𝑒𝑝𝑡 𝑎𝑡𝑜𝑚𝑖𝑞𝑢𝑒
𝑁𝑁𝐹(¬¬𝐶 ) = 𝑁𝑁𝐹(𝐶)
𝑁𝑁𝐹(𝐶 ∪ 𝐷) = 𝑁𝑁𝐹(𝐶) ∪ 𝑁𝑁𝐹(𝐷)
𝑁𝑁𝐹(𝐶 ∩ 𝐷) = 𝑁𝑁𝐹(𝐶) ∩ 𝑁𝑁𝐹(𝐷)
𝑁𝑁𝐹(¬(𝐶 ∪ 𝐷)) = 𝑁𝑁𝐹(¬𝐶) ∩ 𝑁𝑁𝐹(¬𝐷)
𝑁𝑁𝐹(¬(𝐶 ∩ 𝐷)) = 𝑁𝑁𝐹(¬𝐶) ∪ 𝑁𝑁𝐹(¬𝐷)
𝑁𝑁𝐹(∀𝑅. 𝐶 ) = ∀𝑅. 𝑁𝑁𝐹(𝐶)
𝑁𝑁𝐹(∃𝑅. 𝐶 ) = ∃𝑅. 𝑁𝑁𝐹(𝐶)
𝑁𝑁𝐹(¬∀𝑅. 𝐶 ) = ∃𝑅. 𝑁𝑁𝐹(¬𝐶)
𝑁𝑁𝐹(¬∃𝑅. 𝐶 ) = ∀𝑅. 𝑁𝑁𝐹(¬𝐶)

Algorithme [11]

Soit 𝐾 = (𝑇, 𝐴) et A est consistante.

1 S  {A}.
2 S’il y a une règle à appliquer Aller vers l’étape 3.
Sinon K est consistante ; Exit.
3 Appliquer la règle sur S.
4 Supprimer tous les A’ contenant C(a) et ¬𝐶(𝑎).
5 Si 𝑆 = ∅ alors K est inconsistante ; Exit.
Sinon aller à l’étape 2.

Règles d’extension [11]

Soit A’∈ S :
Règle d’instanciation
Condition :
𝐶∈𝑇
Action :
Ajouter C(a) à A’ tel que : a est un individu connu (mentionné dans A’)
∩ −Règle
Condition :

Page | 30
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

(𝐶 ∩ 𝐷) (a) ∈ 𝐀′ et que 𝐶(𝑎) et 𝐷(𝑎) n’appartiennent pas à la fois à 𝐀′

Action :
Supprimer A’ et ajouter A’∪{C (a), 𝐷(a)} à S
∪ − Règle
Condition :
(C∪ 𝐷) (a) ∈ 𝐀′ et que ni 𝐶(𝑎) ∈ 𝐀′ ni 𝐷(𝑎) ∈ 𝐀′
Action :
Supprimer A’ de S ensuite ajouter A’∪{C(a)} et A′ ∪{D(a)} à S.
∃ −Règle
Condition :
∃ 𝑅. 𝐶 (𝑎) ∈ 𝐴′ mais qu’il n’existe pas un individu z tel que: 𝐶 (𝑧) ∈ 𝐴′ et
𝑅(𝑎, 𝑧) ∈ 𝐴′
Action :
Supprimer A’ est ajouter A’∪{C(z), 𝑅(𝑎, 𝑧)}
∀ −Règle
Condition :
∀ 𝑅. 𝐶 (𝑎) ∈ 𝐴′ et 𝑅(𝑎, 𝑦) ∈ 𝐴′ mais que 𝐶 (𝑦) ∉ 𝐴′
Action :
Supprimer A’ est ajouter A’∪{C(y)}

Exemple
Considérons :
 Les concepts atomiques : 𝑃, 𝐸, 𝑀, 𝑅
 𝐾 = (𝑇, 𝐴) tel que 𝑻 = {𝑷 ⊑ (𝑬 ∩ 𝑴) ∪ (𝑬 ⊓ ¬𝑹)}
 A= ∅
Question : Peut-on inférer à partir de K que 𝑃 ⊑ 𝐸 ?
Pour répondre à cette question on doit démontrer que : 𝑲 ∪ {(𝑷 ∩ ¬𝑬)(𝒂)} ⊨ ⊥

Initialisation
S {{(𝑃 ∩ ¬𝐸 )(𝑎)}}
(∩ −Règle)
S {{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝐸(𝑎 )}}
(Règle d’instanciation)
S {{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝐸(𝑎 ), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a)}}
(∪ − Règle )
S { {(𝑃 ∩ ¬𝐸 )(𝑎 ), 𝑷(𝒂 ), ¬𝐸(𝑎 ), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a), ¬𝐏(a)} ,
{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝐸(𝑎), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a), (𝐸 ∩ 𝑀)(a)} ,
{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝐸(𝑎), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a), (𝐸 ⊓ ¬𝑅)(a)}}
(∩ −Règle )
S {{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝑬(𝒂), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a), (𝐸 ∩ 𝑀)(a),
E(a),M(a)} ,{(𝑃 ∩ ¬𝐸 )(𝑎), 𝑃 (𝑎 ), ¬𝑬(𝒂), (¬P ∪ (𝐸 ∩ 𝑀) ∪ (𝐸 ⊓ ¬𝑅))(a), (𝐸 ⊓
¬𝑅)(a),E(a), ¬𝑅 (a)} }
S∅
Conclusion
S=∅ Alors K est Inconsistante et donc K ⊨ 𝑷 ⊑ 𝑬 (par réfutation)

Page | 31
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

2.7 Phase d’opérationnalisation – Langage OWL

Selon la consistance de l’ontologie, on doit choisir le dialecte OWL adéquat en
termes d’expressivité. En effet, OWL contient trois sous-langages: OWL Lite, OWL –
DL et OWL Full.

Figure 2.4 Les langages OWL.

Cependant, il y a un compromis entre décidabilité (calculabilité des inférences en un
temps fini) et expressivité [10]:

Langage Expressivité Décidable

OWL-Lite Limitée Oui
OWL-DL Très bonne Oui
OWL-Full Elevée Non

Citons quelques particularités/limitations de ces langages [10] :

 OWL-Lite est basé sur la logique SHIF(D) (D vient de Datatype) : il ne permet
alors que la définition des rôles fonctionnelles (seulement les cardinalité 0 et
1 sont permises).
 OWL-Lite ne permet pas l’énumération : il interdit alors l’usage du
constructeur owl :oneOf.
 OWL-DL est basé sur la logique SHOIN (D). Dans cette logique, les attributs
sont considérés comme des rôles (l’ensemble d’arrivée n’est rien autre que le
type de l’attribut).
 OWL-Full n’est pas basé sur la logique de description.
 OWL-DL et OWL-Full utilisent les mêmes constructeurs mais OWL-DL
impose certaines contraintes sur leurs utilisations. Par exemple, dans OWL-
DL :
o Les classes, les rôles et les individus doivent être disjoints (mais dans
OWL-Full par exemple une classe peut être en même temps un individu.)
o Les constructeurs : inverseOf, SymmetricProperty et TransitiveProperty ne
peuvent être appliqués sur les DataTypeProperty puisque
DataTypeProperty est disjoint d’ObjectProperty. Cela reste faisable en
langage OWL-Full.

Les tableaux suivants introduisent la syntaxe OWL avec son équivalent en Logique
de Description :

Page | 32
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Tableau 2.2 Correspondance entre la syntaxe OWL et la syntaxe LD (partie 1) [12].

Page | 33
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Tableau 2.3 Correspondance entre la syntaxe OWL et la syntaxe LD (partie 2) [12].

2.8 Conclusion
A l’issue de ce chapitre, l’étudiant est initié à l’ingénierie ontologique qui est
une discipline à part entière. L’intérêt d’une ontologie réside dans le fait qu’elle est
partagée (produit d’un consensus) et formelle (compréhensible par la machine).
Néanmoins, la construction d’une ontologie reste une tâche longue et fastidieuse.
Actuellement, l’ingénierie ontologique bénéficie des avancements en matière de
traitement automatique de langage naturel (voir le chapitre 5 pour une introduction).
Des outils qui aident à la construction automatique d’ontologies à partir de
ressources textuelles existent déjà : Text2Onto3 et SPRAT4 sont des exemples.
La connaissance dont on dispose sur le monde est généralement incertaine. Il
est important de pouvoir représenter/raisonner sur des connaissances incertaines. Le
chapitre suivant porte sur le raisonnement approximatif via des systèmes d’inférence
floue. Pour celui qui a pensé intuitivement à une ontologie-floue: oui cela existe.
Pour plus d’approfondissement, la référence [13] constitue un bon point de départ.

3
[Link]
4
[Link]

Page | 34
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Volet des Travaux Dirigés

Page | 35
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

TD 1. Conceptualisation d’une première Ontologie

La première phase dans le cycle de vie d'une ontologie est la
conceptualisation. Dans ce TD, nous construisons le modèle conceptuel d’une
ontologie très simple5 en partant du glossaire des termes candidats suivant:
Terme Description (informelle)
Personne Un être humain.
Habite Une personne habite une ville
Enseignant Une personne exerçant le métier d’enseignement à l’université

Est Chargé Un enseignant est chargé d’un module ou plusieurs

Médecin Une personne qui est docteur en médecine travaillant à l’hôpital :
spécialiste ou généraliste
Soigne Un médecin soigne un ou plusieurs malades
Etudiant Personne engagé dans un cursus d'enseignement supérieur.
Patient Une personne qui a été hospitalisée.
Ville Un milieu urbain où se concentre une forte population humaine (plus de
20 000 habitants) et localisée dans un Pays.
Module Matière d’enseignement.
Publication une publication peut être un livre ou un article de recherche.
Ecrit Une personne peut écrire un livre et les enseignants-chercheurs peuvent
écrire des articles de recherche.
…. …
On peut ajouter : Lieu de travail, Livre, Article de recherche, Hôpital, Université,
Pays, travaille à…etc.
Nous allons suivre les étapes de la méthode METHONTOLOGY déjà vu au
cours.

Etape 1 (Hiérarchies de concepts)

5
Cette ontologie est construite pour des fins pédagogiques, d’où l’absence de la phase d’acquisition
des connaissances

Page | 36
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Etape 2 (Diagramme de relations binaires)

Etape 3 (Dictionnaire de Concepts)

Concept Attribut Synonyme
Personne Nom de famille, Prénom Humain
Date de naissance
Module Intitulé
Enseignant Grade
Enseignant_Chercheur
Médecin Docteur en Médecine
Médecin_G
Médecin_S Spécialité
Lieu de Travail Nom, Secteur
Hôpital
Université
Etudiant Numéro d’inscription
Patient Date d’hospitalisation Malade
Ville Nom, Surface
Pays Nom, Code_ISO
Publication Titre
Nombre page
Livre
Article de recherche

Page | 37
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Etape 4 (Table des relations binaires)

Relation Concept Concept Card Card Relation
source cible Cible Source inverse
Habite Personne Ville 1..1 200000..n Habité_par
LocaliséeDans Ville Pays 1..1 1..n Contient
Ecrit Personne Publication 0..n 1..n Ecrit_Par
estChargé Enseignant Module 1..3 1..1 Enseigné_par
Enseigne_à Enseignant Université 1..1 1..n aPourEnseignant
Travaille_à Médecin Hôpital 1..1 1..n aPourMédecin
Soigne Médecin Patient 1..n 1..n SoignéPar
Fréquente Etudiant Université 1..1 1..n Fréquenté_par
Inscrit Etudiant module 1..n 1..n Etudié_par
… … …. … … ….
Etape 5 (Table des attributs)
Attribut Type Cardinalité Domaine de valeurs
Nom de famille String 1..1
Prénom String 1..2
date de naissance Date 1..1
Intitulé String 1..1
Grade String 1..1 MAB ,MAA, MCA,MCB,Prof
Nom String 1..1
Secteur String 1..1 Santé, EnseignementSup
Numéro d’inscription String 1..1
Date d’hospitalisation Date 1..n
Surface Integer 1..1
Code String 1..1
Titre String 1..1
Nombre page Integer 1..1
Etape 6 (Liste des axiomes)
Axiome en langage naturelle Concepts Relations
Une personne est soit un étudiant, Personne Est-un
un enseignant un médecin ou un patient Etudiant
Medecin
Enseignant
Patient
Un médecin est soit un médecin Medecin Est-un
spécialiste ou généraliste MedecinS
MedecinG
Un lieu de travail est soit un hôpital ou Lieu de travail Est-un
une université université
Une publication est soit un livre ou un Publi Est-un
article de recherche Livre
Article
Un livre est écrit par au moins une Livre écritPar
personne Personne
Un article de recherche est écrit par au Article de recherche écritPar
moins un enseignant-chercheur Enseignant-chercheur
Un module est enseigné par un et un seul Module enseignéPar
enseignant Enseignant

Page | 38
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Un étudiant est inscrit dans au moins un Etudiant Inscrit

module et fréquente une université Université fréquente
Module
Une personne habite une et une seule Personne Habite
ville Ville
Une ville est localisée dans un seul pays Ville localiséDans
Pays
…. … ….
Etape 8 (Table des instances)
Nom de concept Nom instance Attribut valeur
Patient P_1 Nom de famille f
Prénom Lila
date de naissance 11-07-2005
date hospitalisation 11-10-2015
MedecinG MG_1 Nom de famille ff
Prénom Ali
date de naissance 15-05-1960
Hôpital H_1 Nom 𝑀𝑑𝑆𝑒𝑑𝑖𝑘𝐵𝑒𝑛𝑌𝑎ℎ𝑖𝑎
Secteur Santé
Ville V_1 Nom Jijel
Surface 2577 Km2
Pays Pa_1 Nom Algérie
CodeISO DZ

Etape 8 (Table des assertions)

Nom de relation Instance source Instance Cible
Soigne MG_1 P_1
Habite MG_1 V_1
P_1 V_1
TravailleA MG_1 H_1
LocaliséDans V_1 Pa_1

Page | 39
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

TD2. Formalisation de notre Ontologie en LD SHOIN(D)

Construction de la TBOX
𝑆𝑒𝑐𝑡𝑒𝑢𝑟 ≡ {𝑆𝑎𝑛𝑡é} ∪ {𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒𝑚𝑒𝑛𝑡𝑆𝑢𝑝}
𝐺𝑟𝑎𝑑𝑒 ≡ {𝑀𝐴𝐵} ∪ {𝑀𝐴𝐴} ∪ {𝑀𝐶𝐵} ∪ {𝑀𝐶𝐴} ∪ {𝑃𝑟𝑜𝑓}
𝐿𝑖𝑒𝑢𝑇𝑟𝑎𝑣𝑎𝑖𝑙 ≡ (𝐻ô𝑝𝑖𝑡𝑎𝑙 ∪ 𝑈𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡é) ⊓= 1 Nom. String ⊓ = 1 Secteur
𝐻ô𝑝𝑖𝑡𝑎𝑙 ⊑ 𝐿𝑖𝑒𝑢_𝑇𝑟𝑎𝑣𝑎𝑖𝑙
𝑈𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡é ⊑ 𝐿𝑖𝑒𝑢𝑇𝑟𝑎𝑣𝑎𝑖𝑙
𝐻ô𝑝𝑖𝑡𝑎𝑙 ⊓ Université ⊑ ⊥
𝑀𝑜𝑑𝑢𝑙𝑒 ≡ 𝑇 ⊓ ∃ EtudiéPar . Etudiant ⊓= 1 EnseignéPar . 𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡
⊓= 1 Intitulé. String
𝑃𝑎𝑦𝑠 ⊓ Ville ⊑ ⊥
𝑀é𝑑𝑒𝑐𝑖𝑛 ≡ (𝑀é𝑑𝑒𝑐𝑖𝑛𝐺 ∪ 𝑀é𝑑𝑒𝑐𝑖𝑛𝑆) ⊓ ∃ Soigne. Patient ⊓ ∃ TravailleA. Hopital
𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒 ≡ (𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡 ∪ 𝐸𝑡𝑢𝑑𝑖𝑎𝑛𝑡 ∪ 𝑀é𝑑𝑒𝑐𝑖𝑛 ∪ 𝑃𝑎𝑡𝑖𝑒𝑛𝑡) ⊓ ≥ 0 Ecrit. Livre ⊓
= 1 Habite. Ville ⊓= 1 Nom. String ⊓= 1 dateNaissance. Date ⊓
≥ 1 Prénom. String ⊓≤ 2 Prénom. String
(… On fait de même pour tous les concepts)
𝐸𝑐𝑟𝑖𝑡 ≡ (𝐸𝑐𝑟𝑖𝑡𝑃𝑎𝑟)−
𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒 ≡ (𝐸𝑛𝑠𝑒𝑖𝑔𝑛é𝑃𝑎𝑟)−
(… On fait de même pour tous les rôles /rôles inverses)

Construction de l’ABOX
𝐻ô𝑝𝑖𝑡𝑎𝑙 (𝐻_1)
𝑃𝑎𝑡𝑖𝑒𝑛𝑡 (𝑃_1)
𝑀é𝑑𝑒𝑐𝑖𝑛𝐺(𝑀𝐺_1)
(… On fait de même pour tous les individus ou instances)
𝑆𝑜𝑖𝑔𝑛𝑒(𝑀𝐺_1, 𝑃_1)
𝑆𝑜𝑖𝑔𝑛é𝑃𝑎𝑟(𝑃_1, 𝑀𝐺_1)
…
𝑁𝑜𝑚 (𝐻_1, 𝑀𝑑𝑆𝑒𝑑𝑖𝑘𝐵𝑒𝑛𝑌𝑎ℎ𝑖𝑎)
𝑆𝑒𝑐𝑡𝑒𝑢𝑟(𝐻_1, 𝑆𝑎𝑛𝑡é)
(… On fait de même pour toutes les assertions)

TD 3. Opérationnalisation de l’ontologie avec PROTéGé

Le codage de l’ontologie dans un langage opérationnel (OWL dans notre

contexte) se fait pratiquement à l’aide d’un éditeur d’ontologie. En effet, PROTéGé
est le logiciel le plus utilisé. Il est téléchargeable à l’adresse ci-dessous :
[Link]

Remarque: Une Séance de TP doit être prévue pour éditer l’ontologie avec
PROTEGE.

Page | 40
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Figure 2.5 Hiérarchie de classe sous Protégé.

Figure 2.6 Hiérarchie des relations binaires et des attributs sous Protégé.

Page | 41
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Figure 2.7 Définition du concept Medecin_S dans Protégé

Dans ce TD, le code OWL généré automatiquement par l’outil PROTEGE est
décortiqué.
Un document OWL est un document RDF avec l’élément racine rdf:RDF :

<rdf:RDF
xmlns ="[Link]
xmlns:rdf ="[Link]
xmlns:xsd ="[Link]
xmlns:rdfs="[Link]
xmlns:owl ="[Link]
L’élément owl : Ontology donne des informations sur l’ontologie :
<owl:Ontology
rdf:about="[Link]
<rdfs:comment rdf:datatype="[Link]
Ontologie pour TD version : Mai 2016
</rdfs:comment>
</owl:Ontology>

[Les rôles : Object Properties and Data Properties]

<owl:DatatypeProperty rdf:about="Date_Hos">
<rdfs:domain rdf:resource="Patient"/>
<rdfs:range rdf:resource="&xsd;dateTime"/>
</owl:DatatypeProperty>

Page | 42
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

<owl:DatatypeProperty rdf:about="Code_ISO">
<rdfs:domain rdf:resource="Pays"/>
<rdfs:range rdf:resource="&xsd;string"/>
</owl:DatatypeProperty>
<owl:DatatypeProperty rdf:about="Secteur">
<rdfs:domain rdf:resource="Lieu_Travail"/>
<rdfs:range>
<rdfs:Datatype>
<owl:oneOf>
<rdf:Description>
<rdf:type rdf:resource="&rdf;List"/>
<rdf:first>Enseignement_Sup</rdf:first>
<rdf:rest>
<rdf:Description>
<rdf:type rdf:resource="&rdf;List"/>
<rdf:first>Sante</rdf:first>
<rdf:rest rdf:resource="&rdf;nil"/>
</rdf:Description></rdf:rest></rdf:Description>
</owl:oneOf>
</rdfs:Datatype>
</rdfs:range></owl:DatatypeProperty>
<owl:DatatypeProperty rdf:about="Nom">
<rdfs:range rdf:resource="&xsd;string"/>
<rdfs:domain>
<owl:Class>
<owl:unionOf rdf:parseType="Collection">
<rdf:Description rdf:about="Lieu_Travail"/>
<rdf:Description rdf:about="Pays"/>
<rdf:Description rdf:about="Ville"/>
</owl:unionOf>
</owl:Class>
</rdfs:domain>
</owl:DatatypeProperty>
<owl:ObjectProperty rdf:about="estCharge">
<rdfs:domain rdf:resource="Enseignant"/>
<rdfs:range rdf:resource="Module"/>
<inverseOf rdf:resource="Enseigne_Par"/>
</owl :ObjectProperty>
<owl: ObjectProperty rdf:about="Enseigne_Par">
<rdf:type rdf:resource="&owl;InverseFunctionalProperty"/>
</owl: ObjectProperty>

Question : Ajouter la relation a pour collègue à l’ontologie.

Réponse
<owl:ObjectProperty rdf:about="aPourCollegue">
<rdfs:domain rdf:resource="Personne"/>

Page | 43
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

<rdfs:range rdf:resource="Personne"/>
<rdf:type rdf:resource="&owl;TransitiveProperty" />
<rdf:type rdf:resource="&owl;SymmetricProperty" />
</owl:ObjectProperty>

[Les Concepts : Classes]

<owl:Class rdf:about="Medecin_G">
<rdfs:subClassOf rdf:resource="Medecin"/>
<owl:disjointWith rdf:resource="Medecin_S"/>
</owl:Class>
<owl:Class rdf:about="Etudiant">
<owl:equivalentClass>
<owl:Class>
<owl:intersectionOf rdf:parseType="Collection">
<rdf:Description rdf:about="Personne"/>
<owl:Restriction>
<owl:onProperty rdf:resource="Inscrit"/>
<owl:onClass rdf:resource="Module"/>
<owl:minQualifiedCardinality rdf:datatype="&xsd;nonNegativeInteger"> 1
</owl:minQualifiedCardinality>
</owl:Restriction>
<owl:Restriction>
<owl:onProperty rdf:resource="Frequente"/>
<owl: onClass rdf:resource="&exemple;Universite"/>
<qualifiedCardinality rdf:datatype="&xsd;nonNegativeInteger"> 1
</qualifiedCardinality>
</owl:Restriction>
<owl:Restriction>
<owl:onProperty rdf:resource="Num_Insc"/>
<qualifiedCardinality rdf:datatype="&xsd;nonNegativeInteger"> 1
</qualifiedCardinality>
<owl:onDataRange rdf:resource="&xsd;string"/>
</owl:Restriction>
</owl:intersectionOf>
</owl:Class>
</owl:equivalentClass>
</owl:Class>

Question. Définir le concept Ville en OWL.

Réponse
<owl:Class rdf:about=”Ville">
<owl:equivalentClass>
<owl:Class>
<owl:intersectionOf rdf:parseType="Collection">
<rdf:Description rdf:about="&owl;Thing"/>
<owl :Restriction>

Page | 44
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

<owl :onProperty rdf:resource="Habite_par"/>

<owl :onClass rdf:resource="Personne"/>
<owl :minQualifiedCardinality
rdf:datatype="&xsd;nonNegativeInteger">200000 </owl:
minQualifiedCardinality>
</owl : Restriction>
<owl : Restriction>
<owl: onProperty rdf:resource="Localisee_Dans"/>
<owl: onClass rdf:resource="Pays"/>
<owl: qualifiedCardinality
rdf:datatype="&xsd;nonNegativeInteger">1</qualifiedCardinality>
</owl:Restriction>
<owl: Restriction>
<onProperty rdf:resource="Nom"/>
<qualifiedCardinality
rdf:datatype="&xsd;nonNegativeInteger">1</qualifiedCardinality>
<owl:onDataRange rdf:resource="&xsd;string"/>
</owl:Restriction>
<owl:Restriction>
<owl:onProperty rdf:resource="&exemple;Surface"/>
<owl:qualifiedCardinality
rdf:datatype="&xsd;nonNegativeInteger">1</qualifiedCardinality>
<owl:onDataRange rdf:resource="&xsd;positiveInteger"/>
</owl:Restriction>
</owl:intersectionOf>
</owl:Class>
</owl:equivalentClass>
</owl:Class>

[Les instances/assertions : Individuals]

<owl:NamedIndividual rdf:about="Pa_1">
<Nom rdf:datatype="&xsd;string">Algerie</Nom>
<Code_ISO rdf:datatype="&xsd;string">DZ</Code_ISO>
</owl:NamedIndividual>
<owl:NamedIndividual rdf:about="MG1">
<Date_Naissance rdf:datatype="&xsd;dateTime">15-05-1960</Date_Naissance>
<Prenom rdf:datatype="&xsd;string">Ali</Prenom>
<Nom_F rdf:datatype="&xsd;string">ff</Nom_F>
<Travaille_a rdf:resource="H1"/>
<Soigne rdf:resource="P1"/>
<Habite rdf:resource="V1"/>
</owl:NamedIndividual>

Page | 45
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

TD4. Logiques de Description [14]

Exercice 1
1) Pour une interprétation I est un rôle R, combien de paires d’éléments peut-on avoir
dans 𝑅𝐼 ?
2) Pour un élément 𝑒 ∈ ∆𝐼 , peut-on avoir (𝑒, 𝑒) ∈ 𝑅𝐼 ?
3) Pour deux éléments 𝑒, 𝑓 ∈ ∆𝐼 , peut-on avoir {(𝑒, 𝑓), (𝑓, 𝑒)} ⊆ 𝑅𝐼 ?
4) Soit la TBOX
{𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡 ⊆ 𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒,
𝐶𝑜𝑢𝑟𝑠𝑀𝑎𝑠𝑡𝑒𝑟 ⊑ ¬𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒,
𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡 ⊑ ∃𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒. 𝐶𝑜𝑢𝑟𝑠,
∃𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒. 𝐶𝑜𝑢𝑟𝑠 ⊑ 𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒}
Vérifier si l’interprétation suivante est un modèle pour cette TBOX:
∆𝐼 = {𝑚, 𝑐6, 𝑐7, 𝑒𝑡}
𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡𝐼 = {𝑚}
𝐶𝑜𝑢𝑟𝑠 𝐼 = {𝑐6, 𝑐7, 𝑒𝑡}
𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒 𝐼 = {𝑚, 𝑒𝑡}
𝐶𝑜𝑢𝑟𝑠𝑀𝑎𝑠𝑡𝑒𝑟 𝐼 = {𝑐7}
𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒 𝐼 = {(𝑚, 𝑐6), (𝑚, 𝑐7), (𝑒𝑡, 𝑒𝑡)}
Refaire la question précédente si on ajoute à la TBOX les axiomes:
{𝐶𝑜𝑢𝑟𝑠 ⊑ ¬𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒, ∃𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒. 𝐶𝑜𝑢𝑟𝑠 ⊑ 𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡}
Exercice 2
Utiliser les concepts atomiques : Personne, Heureux, Animal, Chat, Vieux, Poisson et le
rôle atomique Possède pour définir en logique ALC :
 Personne heureuse
 Personne heureuse qui possède un animal
 Personne qui possède seulement des chats
 Personne Malheureuse qui possède un vieux chat
 Personne qui possède seulement des chats ou des poissons.
Exercice 3
1) Les Concepts suivants sont-ils satisfiables?
A ∪ ¬A
A ⊓ ∃R. B ⊓ ∀S. ¬B
A ⊓ ∃R. B ⊓ ∀R. ¬B
A ⊓ ∃R. (B ∩ C) ⊓ ∀R. ¬B
2) Lequel des énoncés suivants est vrai ?
B est subsumé parA ∪ ¬A
A ⊓ ∃R. B est subsumé par A ⊓ ∃R. T
A ⊓ ∃R. (B ∪ C) est subsumé par A ⊓ ∃R. B
A ⊓ ∃R. B est subsumé par A ⊓ ∀R. B
A ⊓ ∃R. A ⊓ ∀R. B est subsumé par A ⊓ ∃R. B

Page | 46
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Exercice 4
Exprimer en langage naturelle les axiomes LD suivants :
Conducteur ⊓ ∃Controle. Voiture ⊑ Majeur
Vélo ⊑ (= 2 Contient. Roue)
Voiture ⊑ (= 1 Controle− . Humain)
Tr(Contient)
Donner l’équivalent en logique des prédicats des axiomes LD suivants :
Humain ⊑ ¬Voiture
∃Controle. Voiture (Bob)
Conducteur ≡ Humain ⊓ ∃Controle. Véhicule
Vélo ≡ Véhicule ∩ ∃Contient. Roue ∩ ∃conduitePar. Humain
Exercice 5
Étant donné le fragment de code OWL suivant, donner son équivalent en LD.
1. <owl:Class rdf:about="Livre">
2. <rdfs:subClassOf rdf:resource="Publication"/>
3. <owl:disjointWith rdf:resource="Magazine"/>
4. </owl:Class>
5. <owl:Class rdf:about="Magazine">
6. <rdfs:subClassOf rdf:resource="Publication"/>
7. </owl:Class>
8. <owl:Class rdf:about="Publication">
9. <owl:equivalentClass>
10. <owl:Class>
11. <owl:unionOf rdf:parseType="Collection">
12. <rdf:Description rdf:about="Livre"/>
13. <rdf:Description rdf:about="Magazine"/>
14. </owl:unionOf>
15. </owl:Class>
16. </owl:equivalentClass>
17. </owl:Class>
18. <owl:NamedIndividual rdf:about="Per_11">
19. <rdf:type rdf:resource="Personne"/>
20. </owl:NamedIndividual>

Page | 47
 Systèmes Intelligents

Chapitre 2 : Connaissance et Ontologie

Références du chapitre

[1] G. Caplat, Modélisation cognitive et résolution de problèmes ;PPUR presses

polytechniques, 2002.
[2] A. Newell, The knowledge level, Artificial Intelligence, vol. 18, no. 1, pp. 87-127,
1982.
[3] M. Madeleine V. Pietri, L'ingénierie de la connaissance: la nouvelle épistémologie
appliquée, Volume 696, Presses Univ. Franche-Comté, 2000.
[4] P. Serrafero, Cycle de vie, maturité et dynamique de la connaissance : des
informations aux cognitions de l’entreprise Apprenante , Revue annuelle U.E. des
Arts et Métiers sur le Knowledge Mangement, Edition Dunod, 2000.
[5] T.R. Gruber, A Translation Approach to Portable Ontology Specifications.
Knowledge Acquisition: Vol.5, n.2, pp. 199–220, 1993.
[6] M. Hadzic, Ontology-based multi-agent systems, Springer, 2014.
[7] M. Fernandez-Lopez, A. Gomez-Pérez, N. Juristo, METHONTOLOGY: From
Ontological Art Towards Ontological Engineering. Spring Symposium on
Ontological Engineering of AAAI. Stanford University, California, pp 33–40,
1997.
[8] A. Gomez-Perez, M. Fernandez-Lopez and O. Corcho, Ontological engineering.
London: Springer-Verlag, 2010.
[9] F. Baader, D. Calvanese, D. McGuinness, D. Nardi and P. Patel-Schneider,
The description logic handbook. Cambridge: Cambridge University Press, 2010.
[10] P. Hitzler, M. Krötzsch and S. Rudolph, Foundations of semantic web
technologies. Boca Raton, Fla: CRC, 2010.
[11] G. Groner and M. Thimm, Semantic Web : Description logics, notes de cours,
Institute for Web Science and Technologies, University of Koblenz-Landau,
2013.
[12] I. Horrocks, OWL: A Description Logic Based Ontology Language, In: van Beek P.
(eds) Principles and Practice of Constraint Programming. Lecture Notes in
Computer Science, vol. 3709. Springer, Berlin, Heidelberg, 2005.
[13] F. Bobillo and U. Straccia, Fuzzy ontology representation using OWL 2,
International Journal of Approximate Reasoning, vol. 52, no. 7, pp. 1073-1094,
2011.
[14] F. Baader, I. Horrocks, C. Lutz and U. Sattler : A Basic Description Logic. In An
Introduction to Description Logic, pp. 10-49. Cambridge: Cambridge University
Press, 2017.

Page | 48
 CHAPITRE 3
Systèmes d’Inférence Floue

3.1 Introduction
L’être humain est capable d’utiliser des connaissances incertaines ou imprécises
afin de produire de nouvelles connaissances. La logique floue est un outil de
l’intelligence artificielle qui permet à la machine d’imiter cette faculté de
raisonnement approximatif. Cependant, il ne faut pas comprendre que « la logique
floue est floue ». Bien au contraire : « la logique floue est une logique précise de
l’imprécision et du raisonnement approximatif» [1].
La logique floue est basée sur les sous-ensemble-flous : un concept introduit la
première fois en 1965 par Lotfi Zadeh [2]. Dans ce chapitre, nous expliquons
succinctement les éléments de la logique floue permettant la construction d’un
système d’inférence floue (SIF). Particulièrement, nous abordons les SIFs de type
MAMDANI et TSK qui sont les plus cités dans la littérature mais aussi qui ont
prouvé leur performance dans l’industrie.
Enfin, des exemples portant sur l’utilisation des SIFs dans l’implémentation de
différents systèmes intelligents sont présentés. L’objectif étant de faire le lien avec les
connaissances déjà acquises, par les étudiants, sur la thématique de conception des
agents intelligents.

Page | 50
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

3.2 Logique Floue

Les connaissances issues du monde réel sont typiquement imparfaites. Par
imperfection, nous entendons l’incertitude (par rapport à la validité) et l’imprécision
(difficulté dans l’expression claire) des connaissances. L’être humain reste néanmoins
capable d’exploiter des perceptions vagues et de prendre par la suite une décision
adéquate à la situation rencontrée.
La logique floue permet une modélisation mathématique rigoureuse de
l’imprécision/incertitude comme l’illustre les sous-sections suivantes.

3.2.1 Concept d’ensemble flou1

Etant donné un univers de discours U (domaine de variation des variables), les
frontières d’un ensemble classique sont strictement définies. Un objet est soit
membre d’un ensemble ou non. Formellement, un ensemble classique peut être noté
par A = {x ∈ U|P(x)} où les éléments x de A vérifient la propriété P. La fonction
d’appartenance à A est définie comme suit : μA (x): U ⟶ {0,1}.
Prenons l’exemple [3] de l’ensemble des personnes adultes A classifiées selon
la propriété Age: A = {x ∈ U|Age(x) ≥ 18}. Clairement, les personnes âgées de 5 ans
ne sont pas des éléments de A contrairement à celles âgées de 45 ans. Un problème
se pose quant à la classification des personnes âgées par exemple de « 17 ans et 9
mois » qui, selon la définition de l’ensemble A, ne sont pas des adultes. Il sera
cependant plus juste de dire que «les personnes de 17 ans et 9 mois sont presque des
adultes». Il est possible d’établir une telle description grâce au concept d’ensemble
flou qui permet d’indiquer le degré d’appartenance d’un élément à un ensemble.
On dit que le passage de l’appartenance à la non-appartenance dans un
ensemble flou se fait progressivement.
Définition de la fonction d’appartenance d’un ensemble flou
Soit U l’univers de discours. Un ensemble flou A de U est caractérisé par une
fonction d’appartenance μA (x) qui associe à chaque point dans U un nombre réel
dans l’intervalle [0,1] où la valeur de μA (x) représente le degré d’appartenance de x
à A: μA (x): U ⟶ [0,1].
Remarque
Un ensemble flou A est vide SSI sa fonction d’appartenance est identiquement nulle
sur U. Plus formellement : ∀ x ∈ U: μA (x) = 0.

3.2.2 Degré d’appartenance Vs Probabilité

Afin d’illustrer la différence entre degré d’appartenance et probabilité, nous
utilisons l’exemple suivant pris de la référence [4] :
Supposons que l’univers de discours soit l’ensemble de tous les liquides. Soit
L l’ensemble flou des liquides potables. Imaginons que vous êtes dans un désert sans
rien à boire...vous tombez sur deux bouteilles:
 Bouteille A avec l’indication : degré d’appartenance de A à L = 0.9.
 Bouteille B avec l’indication : probabilité que B appartienne à L=0.9.

1
Ou sous-ensemble floue (les deux termes sont permis)

Page | 51
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Quelle bouteille allez-vous choisir ? La réponse doit être A puisque :
 Pour B : il y a une chance de 10% que le liquide soit dangereux.
 Pour A : le liquide est très proche d’un liquide pur (mais pas à 100%
évidement).
3.2.3 Opérations sur les ensembles flous
Les définitions suivantes sont compilées à partir des références [3,4] :
Deux ensembles flous A et B sont égaux, et on écrit 𝐴 = 𝐵, SSI :
∀ x ∈ U: μA (x) = μB (x)
Un ensemble flou A est inclus dans B, et on écrit A ⊆ B SSI :
∀ x ∈ U μA (x) ≤ μB (x)
Informellement : si pour n’importe quel élément x , x appartient moins à A qu’à B.
L’union de deux ensembles flous A et B est caractérisée par la fonction
d’appartenance suivante :
μA⋃B (x) = Max[μA (x), μB (x)]
Intuitivement, un élément ne peut appartenir à l’union de deux ensembles flous plus
fortement qu’il n’appartient à chacun d’eux.
L’intersection de deux ensembles flous A et B est caractérisée par la fonction
d’appartenance suivante :
μA∩B (x) = Min[μA (x), μB (x)]
Au fait, un élément ne peut appartenir à l’intersection de deux ensembles flous
moins fortement qu’il n’appartient à chacun d’eux.

Figure 3.1 Union de deux ensembles flous avec l’opérateur Max [4].

Figure 3.2 Intersection de deux ensembles flous avec l’opérateur Min [4].
Le complément d’un ensemble flou A est noté A ̅ et sa fonction d’appartenance est
définie comme suit : ∀ x ∈ U ∶ μA̅ (x) = 1 − μA (x).
Remarque
La propriété de la non contradiction n’est pas satisfaite pour les ensembles flous
(𝐴̅ ∩ 𝐴 ≠ ∅) et non plus la propriété du tiers exclu (𝐴̅ ∪ 𝐴 ≠ 𝑈) .

Page | 52
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

3.2.4 Types des fonctions d’appartenance

Une fonction d’appartenance peut prendre différentes formes comme le
montre le tableau suivant :
Fonction d’appartenance Représentation graphique Définition
Γ −fonction Γ: U ⟶ [0,1]
0 x<𝛼
x−α
Γ(x; α, β) = {β − α α≤x≤β
1 x>β

L −fonction L: U ⟶ [0,1]
1 x<𝛼
x−β
L(x; α, β) = { α≤x≤β
α−β
0 x>β

Λ −fonction Λ: U ⟶ [0,1]
ou fonction Triangulaire 0 x<𝛼
x−α
α≤x≤β
β−α
Λ(x; α, β, γ) = x − γ
β≤x<𝛾
β−γ
{ 0 x≥𝛾
Π −fonction Π: U ⟶ [0,1]
ou fonction Trapézoïdal 0 x<𝛼
x−α
α≤x<𝛽
β−α
Π(x; α, β, γ, δ) = 1 β≤x< 𝛾
x−δ
γ≤x<𝛿
γ−δ
{ 0 x≥δ
S −fonction croissante S: U ⟶ [0,1]
ou fonction sigmoïdal S(x; α, β, γ)
croissante 0 x<𝛼
x−α 2
2( ) α≤x≤β
γ−α
=
x−α 2
1 −2( ) β≤x≤γ
γ−α
{ 1 x>γ
S −fonction décroissante S: U ⟶ [0,1]
ou fonction sigmoïdal S(x; α, β, γ)
décroissante 1 x<𝛼
x−α 2
1 −2( ) α≤x≤β
γ−α
=
x−α 2
2( ) β≤x≤γ
γ−α
{ 0 x>γ
Fonction gaussienne G: U ⟶ [0,1]
(𝛾 − 𝑥)2
G(x; γ, σ) = exp(− )
2𝜎 2
Où 𝜎 est l’écart type

Tableau 3.1 Fonctions d’appartenance usuelles [3].

Page | 53
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Remarque : Vu leur simplicité, Γ −fonction, 𝐿 −fonction et Λ − fonction restent les
formes les plus utilisées dans la pratique.

3.3 Raisonnement approximatif

Dans cette partie, nous introduisons les concepts de la logique floue
nécessaires pour la mise en œuvre d’un raisonnement approximatif par le biais d’un
Système d’Inférence Floue (SIF).

3.3.1 Variable linguistique

Une variable linguistique 𝑢 est généralement identifiée par un ensemble de
termes 𝑇(𝑢) couvrant son univers de discours 𝑈.
Exemple
Considérons la variable linguistique 𝑇𝑒𝑚𝑝é𝑟𝑎𝑡𝑢𝑟𝑒 et l’univers de discours 𝑈 =
[0,40].
𝑇(𝑇𝑒𝑚𝑝é𝑟𝑎𝑡𝑢𝑟𝑒 ) = {𝐹𝑎𝑖𝑏𝑙𝑒, 𝑀𝑜𝑦𝑒𝑛𝑛𝑒, 𝐸𝑙𝑒𝑣é𝑒}.
A Chaque terme est associé un ensemble flou :
 F : température inférieure à 15°C
 M : température proche de 20°C
 E : température au-delà de 25°C
Les fonctions d’appartenance associées aux ensembles flous F, M, E sont
graphiquement présentées dans la figure ci-dessous.

Figure 3.3 Ensembles flous de la variable linguistique Température [3].

Question 1: auxquels ensembles flous appartiennent 17°C et 23°C et avec quel degré
d’appartenance ?

 Clairement 17°C est membre des ensembles flous F et M et 23°C est membre
des ensembles flous M et E.
 Pour calculer les degrés d’appartenance, nous utilisons les définitions qui
conviennent (selon la forme : triangulaire, trapèze, etc.) du tableau 3.1.
1 x < 15 0 x < 15
x − 18 x − 15
μF (x) = { 15 ≤ x ≤ 18 15 ≤ x ≤ 20
15 − 18 μM (x) = 20 − 15
0 x > 18 x − 25
20 ≤ x < 25
20 − 25
{ 0 x ≥ 25

Page | 54
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

0 x < 22
x − 22
μE (x) = { 22 ≤ x ≤ 25
25 − 22
1 x > 25

Il ne reste qu’à faire l’application numérique selon la valeur de x.

Ce type de calcul correspond à une Fuzzification (dans le sens : passage d’une valeur
numérique vers un degré d’appartenance).
Question 2 : Trouver la température x pour la quelle μF (x) = 0.25.
x−18
 Il suffit de mettre : −3
= 0.25 Ce qui donne x=17.25 °C
Ce type de calcul correspond à une Defuzzification (dans le sens : passage d’un degré
d’appartenance vers une valeur numérique).

3.3.2 Proposition floue

Une proposition floue élémentaire prend la forme « Terme linguistique est
ensemble flou » [4]. Notons qu’une proposition floue comme : « Température est
Moyenne » a pour valeur de vérité le degré d’appartenance de Température à
l’ensemble floue M.

3.3.3 Opérations de la logique floue

En appliquant les opérations de la logique floue sur des propositions floues
élémentaires, on peut construire des propositions floues générales. Notons que les
opérations de la logique floue sont fortement liées aux définitions des opérations sur
les ensembles flous.

Opération Relation Fonction d’appartenance

Négation R : Non A 𝜇𝑅 (𝑥) = 1 − 𝜇𝐴 (𝑥)
Disjonction R : 𝐴 𝑜𝑢 𝐵 𝜇𝑅 (𝑥) = max{𝜇𝐴 (𝑥), 𝜇𝐵 (𝑥)}
Conjonction R : 𝐴 𝑒𝑡 𝐵 𝜇𝑅 (𝑥) = min{𝜇𝐴 (𝑥), 𝜇𝐵 (𝑥)}
Implication R :(𝑥 = 𝐴) ⟶ (𝑦 = 𝐵) Implication de Zadeh :
𝜇𝑅 (𝑥) = max{min{𝜇𝐴 (𝑥), 𝜇𝐵 (𝑦)}, 1 − 𝜇𝐴 (𝑥)}
Implication de Mamdani :
𝜇𝑅 (𝑥) = min{𝜇𝐴 (𝑥), 𝜇𝐵 (𝑦)}
Implication de Larsen :
𝜇𝑅 (𝑥) = 𝜇𝐴 (𝑥) × 𝜇𝐵 (𝑦)
Implication de Godel:
1 𝑠𝑖 𝜇𝐴 (𝑥) ≤ 𝜇𝐵 (𝑦)
𝜇𝑅 (𝑥) = {
𝜇𝐵 (𝑦) 𝑠𝑖𝑛𝑜𝑛
Implication de Lukasiewicz :
𝜇𝑅 (𝑥) = min{1 ,[1 − 𝜇𝐴 (𝑥) + 𝜇𝐵 (𝑦)]}

Tableau 3.2 Opérations de la logique floue [3].

Remarque
Les définitions de l’implication les plus utilisées dans la pratique sont celles de
Mamdani et de Larsen.

Page | 55
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

3.4 Système d’inférence floue de type MAMDANI

Un SIF effectue un passage non linéaire d’un vecteur de variables numériques, en
entrée, à une sortie scalaire également numérique. Un SIF de type Mamdani peut-être
schématisé comme dans la figure 3.4. A savoir, ce type de SIF a été proposé en 1975
par Ebrahim Mamdani [5] pour le contrôle d’une machine à vapeur (steam engine).

Figure 3.4 Les différents modules d’un SIF de type MAMDANI [3].

Dans ce qui suit, nous expliquons le fonctionnement des différents modules [3] :
 Module de Fuzzification : Ce module associe aux paramètres d’entrée
numériques des ensembles flous d’entrée tout en déterminant le degré
d’appartenance à chacun de ces ensembles.
 Base des règles : La base des règles représente la stratégie de décision ou de
contrôle utilisée par le système. Les règles sont généralement établies par les
experts du domaine de l’application envisagée. Une règle possède la forme
d’une implication «SI - ALORS». La partie SI de l’implication est appelé
antécédent, condition ou prémisse tandis que la partie ALORS est nommée
conséquent, conclusion ou action.
La partie antécédent contient une ou plusieurs propositions floues combinées par
des opérateurs flous de conjonction, de disjonction ou de négation. Dans le cas
des SIFs structurés selon le modèle de Mamdani conventionnelle dit modèle
linguistique, la forme la plus commune est celle conjonctive. Alors, dans une base
composée de M règles, la 𝑙 eme règle est exprimée comme suit :
𝑅 (𝑙) : 𝑺𝑰 𝑢1 𝑒𝑠𝑡 𝐹1𝑙 𝐸𝑇 𝑢2 𝑒𝑠𝑡 𝐹2𝑙 𝐸𝑇 … 𝑢𝑝 𝑒𝑠𝑡 𝐹𝑝𝑙 𝑨𝑳𝑶𝑹𝑺 𝑣 𝑒𝑠𝑡 𝐺 𝑙
Où 𝑢 = (𝑢1 , 𝑢2 , … , 𝑢𝑝 ) ∈ 𝑈1 × … × 𝑈𝑝 et 𝑣 ∈ 𝑉 sont des variables linguistiques. 𝐹𝑖𝑙
pour tout 𝑖 ∈ {1. . 𝑝} et 𝐺 𝑙 sont des ensembles flous des univers de discours 𝑈𝑖 ⊂ ℝ
et 𝑉 ⊂ ℝ, respectivement.
Notons que les règles d’inférence sont reliées par « ELSE » d’où l’application
de l’opérateur MAX lors de l’agrégation des sorties floues obtenues [5].
 Moteur d’inférence: Etant donnée une collection de règles, le moteur d’inférence
a pour rôle d’associer aux entrées numériques du système un seul ensemble flou
de sortie. Durant le processus d’inférence, les opérations suivantes sont
invoquées :
a) Calcul du degré d’accomplissement ou d’activation de chaque règle à partir
des degrés d’appartenance des variables floues d’entrées. Une règle est
activée dès qu’elle a une prémisse ayant une valeur de vérité non nulle.

Page | 56
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

b) Pour chaque règle activée, trouver la fonction d’appartenance de la
conclusion.
c) Agrégation des conclusions inférées.
Plusieurs méthodes d’inférence ont été proposées. Les plus utilisées sont :
MAX-MIN (inférence de Mamdani), Max-Produit (inférence de Larsen) et Somme-
Produit. De par sa simplicité, l’inférence de Mamdani est de loin la méthode la
plus utilisée. Elle consiste à : utiliser le MIN pour la conjonction et l’implication et
le MAX pour la disjonction.
 Defuzzification: La sortie d’un SIF est souvent orientée pour être utilisée par une
machine. Il convient donc de convertir la sortie floue obtenue à une valeur
numérique exploitable : c’est exactement le rôle du module de défuzzification.
Plusieurs méthodes de défuzzification ont été proposées, les plus cités dans la
littérature sont:
a) Le centre de gravité (Centroid en anglais): cette méthode consiste à prendre
comme sortie, l'abscisse du centre de gravité de la fonction
d’appartenance de la sortie issue de l’inférence floue.
b) Méthode du maximum: La sortie correspond à l’abscisse du maximum de la
fonction d’appartenance résultante. Lorsqu’il existe plusieurs valeurs
pour lesquelles la fonction d’appartenance résultante est maximale, on
peut opter pour [6]: SOM (Smallest Of Maximum), MOM (Middle Of
Maximum) ou LOM (Largest Of Maximum).

Figure 3.5 Méthodes de défuzzification [6].

Exemple [7]
Considérons un SIF (MAX-MIN) avec deux entrées : X et Y et une sortie Z . On se
donne la base des règles suivante :
R1 : si X est A3 OU Y est B1 alors Z est C1
R2 : si X est A2 ET Y est B2 alors Z est C2
R3 : si X est A1 alors Z est C3

Dans la figure ci-dessous sont récapitulées les étapes d’inférence floue de la sortie du
système si on considère que : 𝑋 = 𝑥1 𝑒𝑡 𝑌 = 𝑦1.

Page | 57
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Figure 3.6 Exemple d’un SIF de type MAMDANI [7]

Page | 58
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

3.5 Modèle de Sugeno

Un scientifique a toujours besoin d’estimer (en s’appuyant sur son savoir-faire) si
les conditions actuelles d’un système conviennent pour y appliquer des formules
mathématiques déjà définies [3]. En réponse à ce besoin, vient les SIF de type Sugeno
dit aussi TSK en honneur des chercheurs : Takagi, Sugeno et Kang ayant proposé ce
modèle en 1985 [8].
Les règles d’un SIF de type TSK servent à déterminer le degré d’applicabilité
d’une formule qui détermine la valeur d’une variable d’intérêt. En opposition avec le
modèle linguistique de Mamdani, la sortie d’une règle TSK est numérique. Elle peut
avoir la forme d’une constante, d’un polynôme, d’une équation différentielle, etc. La
sortie est dépendante des variables associées à la partie antécédent [3].
Une règle dans le modèle TSK s’écrit dans le format général suivant [3]:
𝑅: 𝑺𝒊 𝑓 ( 𝑥1 𝑒𝑠𝑡 𝐴1 , 𝑥2 𝑒𝑠𝑡 𝐴2 , … , 𝑥𝑘 𝑒𝑠𝑡 𝐴𝑘 ) 𝑨𝑳𝑶𝑹𝑺 𝑦 = 𝑔(𝑥1 , 𝑥2 , . . , 𝑥𝑘 )
𝑜ù:
 𝑓 est la fonction logique qui relie les propositions de la partie prémisse.
𝑥1 , 𝑥2 , . . , 𝑥𝑘 sont les variables de la partie prémisse et qui apparaissent aussi

dans la partie conséquence.
 𝐴1 , 𝐴2 , … , 𝐴𝑘 dénotent les ensembles flous d’entrée.
 𝑦 est la variable de sortie dont la valeur doit être inférée.
 𝑔 est la fonction qui permet de calculer la valeur de la sortie 𝑦 quand la
partie prémisse est satisfaite.
Si la fonction 𝑔 est linéaire, on aura la forme suivante:
𝑅: 𝑆𝑖 𝑓( 𝑥1 𝑒𝑠𝑡 𝐴1 , 𝑥2 𝑒𝑠𝑡 𝐴2 , … , 𝑥𝑘 𝑒𝑠𝑡 𝐴𝑘 )𝐴𝐿𝑂𝑅𝑆 𝑦 = 𝑝0 + 𝑝1 𝑥1 + 𝑝2 𝑥2 + ⋯ + 𝑝𝑘 𝑥𝑘

Dans un modèle TSK d’ordre zéro, y est une constante c'est-à-dire 𝑝1 = 𝑝2 … = 𝑝𝑘 = 0 ,

et les règles sont de la forme:
𝑅: 𝑆𝑖 𝑓( 𝑥1 𝑒𝑠𝑡 𝐴1 , 𝑥2 𝑒𝑠𝑡 𝐴2 , … , 𝑥𝑘 𝑒𝑠𝑡 𝐴𝑘 ) 𝐴𝐿𝑂𝑅𝑆 𝑦 = 𝑝0
Clairement, dans un SIF de Sugeno aucune défuzzification n’est nécessaire. La sortie,
y, d’un système TSK composé de r règles d’inférence se calcule en utilisant la
méthode du centre de gravité comme suit :
∑rl=1 |y = 𝑦𝑙 | × 𝑦𝑙
y=
∑rl=1 |y = 𝑦𝑙 |

 𝑦𝑙 dénote la conclusion obtenue par la règle 𝑙.

 |y = 𝑦𝑙 | dénote le degré d’accomplissent de la règle 𝑙.

Exemple [8]
Le système possède deux entrées 𝑥1 et 𝑥2 et une sortie 𝑦. Les fonctions
d’appartenance de 𝑥1 et 𝑥2 aux ensembles flous Petit et Grand sont montrées par la
figure ci-dessous.

Page | 59
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

La Base des règles utilisée est la suivante :

R1: SI x1 est petit ET x2 est petit ALORS y = x1 + x2
R2: SI x1 est grand ALORS y = 2x1
R3: SI x2 est grand ALORS y = 3x2
Considérons que 𝑥1 = 12 et 𝑥2 = 5. Récapitulons les étapes d’inférence de la valeur
de la sortie y [3]:

3.6 Contrôle flou d’une machine à laver

Sur le marché, il existe déjà des machines à laver utilisant des systèmes de
contrôle flou (chez LG, Samsung et bien d’autres). Pour une machine à laver, les
caractéristiques de la charge de linge constituent les entrées du contrôleur flou
(poids, types de tissu, quantité de saleté, etc.). Selon ces données, on peut contrôler
certains paramètres de lavage tel que : la quantité du détergent et de l’eau, le temps
de lavage, la consommation d’électricité, etc. Le contrôle efficace de ces paramètres
assure un lavage plus propre mais aussi plus économique.
Considérons, l’exemple d’une machine à laver hypothétique directement pris
de la référence [9]. On suggère de contrôler la quantité du détergent en fonction du
poids et de la saleté du linge.

Page | 60
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

(a)

(b)
Figure 3.7 Les ensembles flous pour l’entrée (a) Saleté (b) poids [9].

Figure 3.8 La sortie quantité détergent [9].

En examinant la sortie de ce contrôleur, on comprend qu’il s’agit d’un SIF de

type Sugeno. C’est une bonne pratique de présenter l’ensemble des règles sous une
forme matricielle (ici on aura 4X4=16 Règles conjonctives).

La base des règles du contrôleur de la machine à laver est comme suit [9] :
Poids Très léger Léger Lourd Très lourd
Saleté
Presque Très peu Peu Presque Presque
propre beaucoup beaucoup
Sale Peu Peu Presque Beaucoup
beaucoup
Souillé Presque Presque Beaucoup Maximum
beaucoup beaucoup
Crasseux Beaucoup Presque Beaucoup Maximum
beaucoup

Page | 61
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

On donne ici un exemple de lecture d’une règle à partir de la matrice précédente:
Si Saleté est presque propre ET poids et très léger alors détergent = très peu
(exactement c’est une quantité de 10 unités de détergent)

3.7 Contrôleur flou pour la navigation d’un robot mobile de

type voiture
Afin de réaliser la commande intelligente de la navigation autonome d’un
robot de type voiture, les auteurs dans la référence [10] ont proposé un régulateur
flou. Ce dernier possède deux entrées : l’erreur de position (E_Pos) et l’erreur
angulaire (E_Ang). Les sorties du régulateur sont la vitesse de translation et l’angle
de braquage tous les deux nécessaires pour atteindre une position désirée.

Figure 3.9 Le robot voiture RobuCar utilisé dans les expérimentations [10].

Les entrées E_Pos et E_Ang numériques sont calculées comme suit [10]:

𝐸𝑝𝑜𝑠 = √𝐷𝑥2 + 𝐷𝑦2 𝐸𝐴𝑛𝑔 = 𝜃𝑚 − 𝜃

Tel que :
𝐷𝑥 = 𝑋𝑏 − 𝑋𝑚
{ 𝐷𝑦 = 𝑌𝑏 − 𝑌𝑚
𝜃 = tan−1 (𝐷𝑦 , 𝐷𝑥 )
Sachant que :
 (𝑋𝑚 , 𝑌𝑚 , 𝜃𝑚 ) : position et orientation du robot.
 (𝑋𝑏 , 𝑌𝑏 , 𝜃𝑏 ) : position et orientation du but.
 𝑉𝑚 : vitesse de translation du robot
 𝜑 : angle de braquage du robot
Les termes utilisés dans la description des différentes variables linguistiques sont :
Z : Zéro P : Petite PP : Positive Petite
M : Moyenne G : Grande PG : Positive Grande
NG : Négative Grande F : Faible
NP : Négative Petite TG : Très grande
PM : Positive Moyenne NM : Négative Moyenne

Page | 62
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Les figures ci-dessous représentent les ensembles flous utilisés pour les
entrées/sorties.

Voici un exemple d’une règle qui régit la navigation du robot :

Si l’erreur de position est petite ET l’erreur d’angle est nulle (c’est-à-dire que le
but est tout droit mais à une petite distance) Alors le robot doit avancer avec
une vitesse faible sans changer de direction.

Dans l’ensemble, 70 règles sont proposées pour réguler aussi précisément que
possible la navigation du robot. Le choix des règles reflète le savoir-faire d’un expert.
Néanmoins, la définition des fonctions d’appartenance reste une tâche difficile (elle se
fait par expérimentation).
La base des règles complète est donnée par la matrice suivante [10]:

Page | 63
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

3.8 Conclusion
A la fin de ce chapitre, l’étudiant sera capable d’implémenter des agents
intelligents qui utilisent des SIFs de type MAMDANI et/ou Sugeno. Ces SIFs
présentent l’avantage d’être simples et efficaces. Ceci explique leur prolifération dans
les applications industrielles.
La logique floue, comme déjà vue dans le chapitre, est une extension de la
logique classique qui permet d’attribuer un degré de vérité à un énoncé. D’autres
logiques non classiques qui ont une grande importance en IA seront présentées dans
le chapitre suivant : il s’agit des logiques modales.

Page | 64
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Travaux Pratiques

Sujet 1
L’objet de ce TP est la conception et ensuite l’implémentation du programme agent
qui utilise un SIF pour contrôler un ventilateur de maison. Le programme agent
ajuste la vitesse du ventilateur en fonction de la Température et de l’Humidité de
l’air dans la maison.
Pour réaliser ce TP :
 Définir les différents ensembles flous nécessaires.
 Définir une base des règles adéquate.
 Dans un langage de votre choix : Implémenter le SIF correspondant
(Mamdani ou Sugeno ?)
Sujet 2
Réaliser, en langage C, un contrôler flou du zoom GPS d’une voiture. Le zoom se
définit en fonction de la distance au prochain changement de direction et de la
vitesse de la voiture. Pour réaliser ce TP, on donne les différents ensembles flous
nécessaires ainsi que la base des règles à utiliser [11]:

Page | 65
 Systèmes Intelligents

Chapitre 3 : Systèmes d’inférence floue

Références du chapitre

[1] L. Zadeh, "Is there a need for fuzzy logic?", Information Sciences, vol. 178, no.
13, pp. 2751-2779, 2008.
[2] L. Zadeh, "Fuzzy sets", Information and Control, vol. 8, no. 3, pp. 338-353,
1965.
[3] S. Chettibi, "Intelligence Computationnelle pour les problèmes de Routage adaptatif
efficace en énergie et multicritère dans les Réseaux Mobiles Ad-hoc", Thèse de
doctorat en sciences (Chapitre 3) , Université de Constantine 2, 2015.
[4] B. Bouchon-Meunier, C. Marsala and J. Pomerol, Logique floue, principes, aide à
la décision. Paris: Hermès Science publications, 2003.
[5] E.H. Mamdani and S. Assilian, "An experiment in linguistic synthesis with a
fuzzy logic controller," International Journal of Man-Machine Studies, Vol. 7, No.
1, pp. 1-13, 1975.
[6] [Link]
[Link]
[7] M. Negnevitsky, “Artificial intelligence: A Guide to Intelligent Systems”. Harlow:
Addison Wesley,2010.
[8] T. Takagi and M. Sugeno, "Fuzzy identification of systems and its applications to
modeling and control", IEEE Transactions on Systems, Man, and Cybernetics,
vol. -15, no. 1, pp. 116-132, 1985.
[9] A. Ibrahim, “Fuzzy logic for embedded systems applications”. Amsterdam:
Newnes, 2004.
[10] N. Ouadah, 0. Azouaoui, M. Hamerlain, ‘’Implémentation d'un contrôleur flou
pour la navigation d'un robot mobile de type voiture’’. Troisième Congres
francophone, MAJECSTIC 2005, 16-18 Novembre 2005, Rennes (France).
[11] V. Mathivet, ‘’L'Intelligence Artificielle pour les développeurs’’, ISBN: 978-2-7460-
9215-0, Editions ENI, Décembre 2014.

Page | 66
 CHAPITRE 4
Logiques Modales

4.1 Introduction
La formalisation logique des systèmes mono-agent ou multi-agent se fait dans
deux perspectives différentes, à savoir [1] : i) l’implémentation du raisonnement
automatique dans des agents cognitifs ; ii) la spécification et la vérification du
comportement des agents (qui ne sont pas forcément cognitifs) situés dans des
environnements dynamiques. De par leurs expressivités, les logiques modales sont
souvent utilisées dans ce contexte.
En linguistique, une modalité a pour effet de modifier le sens d’un énoncé. En
logique, une modalité sert à qualifier le mode de vérité des assertions. On peut citer
par exemple:
 les modalités aléthiques comme : « il est nécessaire que », « il est possible que »,
 les modalités épistémiques comme: « un tel sait que »,
 les modalités doxastiques comme: « un tel croit que »,
 les modalités temporelles permettant d’exprimer le futur et le passé.
Ces modalités sont celles étudiées dans : la logique propositionnelle modale, la
logique des savoir et des croyances et les logiques temporelles, respectivement.
La logique modale peut être définie comme [2] « l’étude du raisonnement sur des
modalités et de l’inférence à partir de prémisses modales qu’une certaine conclusion modale
est valide ».

Page | 67
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

4.2 Logique modale propositionnelle

La logique modale propositionnelle étend la logique propositionnelle avec les
opérateurs modaux universel et existentiel. L’interprétation généralement attribuée à
ces opérateurs est celle de nécéssité/possibilité. On utilise la notation suivante :
□ 𝑄: « il est nécessaire que Q ». ◊ 𝑄 : « il est possible que Q».
Au fait, ces deux opérateurs sont duaux (Cf. Figure 4.1) :
□ 𝑄 ↔ ¬ ◊ ¬𝑄 ◊ 𝑄 ↔ ¬□¬𝑄

Figure 4.1 Le carré modal1.

Notons que d’autres interprétations à part la nécessité et la possibilité peuvent
être associées à ces opérateurs à condition que ces interprétations satisfassent la
relation de dualité. En voici des exemples :

Interprétations de □ 𝑸 Interprétations de ◊ 𝑸
Il sera toujours vrai que Q Il sera parfois vrai que Q
Il est su que Q L’inverse de Q n’est pas su
Il est cru que Q L’inverse de Q n’est pas cru
Il faut que Q Il est permis que Q
Toute exécution du programme Il y a une exécution du programme qui
produit le résultat Q produit le résultat Q

Tableau 4.1 Interprétations des opérateurs modaux [3].

Soulignons que les deux dernières interprétations dans le tableau précédent
donnent lieu à la logique déontique et la logique dynamique, respectivent (cf. Section
4.2.6) .
Exemple
Soit la proposition atomique « Q : la porte est fermée ». Donner la signification
des formules suivantes en utilisant l’interprétation « savoir » pour un certain agent
situé dans une pièce :

1
[Link]

Page | 68
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

□𝑄 l’agent sait que la porte est fermée.

□¬𝑄 l’agent sait que la porte n’est pas fermée.
◊𝑄 l’agent ne sait pas si la porte n’est pas fermée.
◊ ¬𝑄 l’agent ne sait pas si la porte est fermée.
□□𝑄 l’agent sait qu’il sait que la porte est fermée.
□¬□𝑄 l’agent sait qu’il ne sait pas que la porte est fermée.

4.2.1 Syntaxe de la logique modale propositionnelle

Soit ℒ𝑝 le langage propositionnel et Φ l’ensemble des propositions atomiques. Le
langage modal ℒ𝑀 est défini comme suit [1]:
 Vrai et Faux ∈ ℒ𝑀
 Si 𝜓 ∈ Φ Alors 𝜓 ∈ ℒ𝑀
 Si p, q ∈ ℒ𝑀 Alors 𝑝 ∧ 𝑞, ¬𝑝, 𝑝 ∨ 𝑞, 𝑝 → 𝑞, 𝑝 ↔ 𝑞 ∈ ℒ𝑀
 Si 𝑝 ∈ ℒ𝒑 Alors □𝑝, ◊ 𝑝 ∈ ℒ𝑀
4.2.2 Mondes possibles et structure de Kripke
L’idée est de considérer que chaque agent peut envisager un certain nombre
de mondes concevables. On dit alors qu’un agent sait une proposition si elle est vraie
dans tous les mondes qu’il imagine. En effet, la vérité n’est pas absolue, elle peut
dépendre de la « réalité » autrement dit du « monde » dans lequel on se trouve.
On appelle interprétation en terme de mondes possibles un modèle de Kripke2
ℳ =< 𝑾, 𝑳, 𝑹 > tel que [1]:
 W : un ensemble de mondes ou situations possibles.
 L : 𝑾 → 𝟐Φ : une fonction qui renvoie l’ensemble des propositions atomiques
satisfaites dans un monde (𝟐Φ dénote l’ensemble des parties de Φ).
 𝑅 ⊑ 𝑊 × 𝑊 : est une relation d’accessibilité binaire. (𝜔, 𝜔′) ∈ 𝑅 indique que le
monde 𝜔′ est accessible depuis le monde 𝜔.
Récapitulons, pour chaque interprétation de □ 𝑄 , le sens qu’on peut attribuer à la
relation d’accessibilité :
Interprétations de □ 𝑸 Sens de R(𝝎, 𝝎′)
Il est nécessairement vrai que Q 𝜔′ est un monde possible selon 𝜔
Il sera toujours vrai que Q 𝜔′ est un monde future de 𝜔
L’agent A sait que Q 𝜔′ peut être le monde actuel selon les
connaissances de A dans 𝜔
L’agent A croit que Q 𝜔′ peut être le monde actuel selon les
croyances de A dans 𝜔
Il est obligatoire que Q 𝜔′ est un monde acceptable selon
l’information dans 𝜔
Après toute exécution du programme 𝜔′ est un état résultant possible après
P, Q arrive l’éxécution de P dans 𝜔.
Tableau 4.2 Interprétations de la relation d’accessibilité [4].

2
En l’honneur de Saul Kripke Philosophe et logicien américain, auteur de l’article
révolutionnaire intitulé « A Completenes Theorem for Modal Logic » portant sur la
sémantique de la logique modale.

Page | 69
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

[Link] Sémantique des mondes possibles

Dans ce qui suit, 𝑤 dénote le monde par rapport auquel on évalue une
formule. La valeur de vérité des formules modales est définie inductivement comme
suit [1] :
ℳ, 𝑤 ⊨ 𝜓 𝑆𝑆𝐼 𝜓 ∈ 𝐿(𝑤) 𝑡𝑒𝑙 𝑞𝑢𝑒 𝜓 ∈ Φ
ℳ, 𝑤 ⊨ 𝑝 ∧ 𝑞 𝑆𝑆𝐼 ℳ, 𝑤 ⊨ 𝑝 𝑒𝑡 ℳ, 𝑤 ⊨ 𝑞
ℳ, 𝑤 ⊨ ¬𝑝 𝑆𝑆𝐼 ℳ, 𝑤 ⊭ 𝑝
ℳ, 𝑤 ⊨ ◊ 𝑝 𝑆𝑆𝐼 ( ∃ 𝑤`: 𝑅 (𝑤, 𝑤`) ∧ ℳ, 𝑤′ ⊨ 𝑝)
ℳ, 𝑤 ⊨ □ 𝑝 𝑆𝑆𝐼 ( ∀ 𝑤`: 𝑅 (𝑤, 𝑤`) → ℳ, 𝑤′ ⊨ 𝑝)
On peut donner une interpretation informelle pour les deux dernières règles
comme suit :
 La formule ◊ 𝑝 est satisfaite dans un monde possible 𝜔 ssi la formule p est
satisfaite dans au moins un monde possible accessible à partir de 𝜔
 La formule □ 𝑝 est satisfaite dans un monde possible 𝜔 ssi la formule p est
satisfaite dans tous les mondes possibles accessibles à partir de 𝜔.
Exemple
Soit la structure de Kripke ℳ ci-dessous.

On peut constater par exemple que :

ℳ, 𝑤1 ⊨ 𝑝1
ℳ, 𝑤2 ⊨ 𝑝1
ℳ, 𝑤1 ⊨ □(𝑝1 ∨ 𝑝2)
ℳ, 𝑤2 ⊭ □ (𝑝1 ∨ 𝑝2)

[Link] Propriétés algébriques des relations d’accessibilité

Dans un modèle ℳ = < 𝑊, 𝐿, 𝑅 > , la relation d’accessibilité peut être [4] :
 Réflexive SSI (∀𝜔: (𝜔, 𝜔) ∈ 𝑅)
 Sérielle SSI (∀𝜔: (∃𝜔′ : (𝜔, 𝜔′) ∈ 𝑅))
 Transitive SSI (∀𝜔 , 𝜔′ , 𝜔′′ : (𝜔, 𝜔′) ∈ 𝑅 ∧ (𝜔′ , 𝜔′′ ) ∈ 𝑅 → (𝜔, 𝜔′′) ∈ 𝑅)
 Symétrique SSI (∀𝜔 , 𝜔′ : (𝜔, 𝜔′) ∈ 𝑅 → (𝜔′ , 𝜔) ∈ 𝑅)
 Euclidienne SSI (∀𝜔 , 𝜔′ , 𝜔′′: (𝜔, 𝜔′) ∈ 𝑅 ∧ (𝜔, 𝜔′′ ) ∈ 𝑅 → (𝜔′ , 𝜔′′) ∈ 𝑅)
Et on parle dans ce cas de modèle réflexif, sériel, transitif, symétrique et
euclidien, respectivement [4].
Notons que la relation d’accessibilité définie dans l’exemple précédent, est :
réflexive, sérielle, non transitive, symétrique mais non euclidienne.

Page | 70
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

4.3 Axiomes de la logique modale

Les principaux axiomes de la logique modale sont [1,4] :
 Axiome K (ou axiome de distribution), en l’honneur de Saul Kripke, dont le
schéma est le suivant:
□ (𝑝 → 𝑞) → (□ 𝑝 → □ 𝑞)
Si un agent croit/sait une implication entre deux termes, alors s’il croit/sait le
premier, il croit/sait aussi le second. Cet axiome est souvent considéré comme
l’élément principal des logiques des savoirs et des croyances. Il est valide dans tout
modèle de Kripke quelque soit la relation d’accessibilité.
 Axiome T ou encore axiome de connaissance , possède le schéma suivant:
□𝑝 →𝑝
Cet axiome est valide dans la classe des modèles caractérisés par une relation
d’accessibilité réfléxive. Il exprime que l’agent sait seulement ce qui est actuellement
vrai. Autrement, une connaissance est une information vraie.
 Axiome 4 ou encore axiome d’introspection3 positive, exprimé comme suit:
□𝑝 →□□𝑝
C’est l’axiome caractéristique de la classe des modèles avec une relation
d’accessibilité transitive. Il exprime qu’un agent est conscient de ce qu’il connait.
 Axiome 5 ou encore axiome d’introspection négative:
◊𝑝 → □◊𝑝
C’est l’axiome caractéristique de la classe des modèles avec une relation
d’accessibilité Euclidienne. Cet axiome exprime qu’un agent est conscient de ce qu’il
ignore.
 Axiome D ou encore axiome de non contradiction :
□ 𝑝 →◊ 𝑝
C’est l’axiome caractéristique de la classe des modèles avec une relation
d’accessibilité Sérielle. Cet axiome exprime que si un agent croit/sait quelque chose,
alors il ne croit/sait pas son contraire.

4.4 Systèmes de la logique modale

Le système formel K contient uniquement [5]:
1) Les tautologies du calcul propositionnel
2) L’axiome K : □(𝑝 → 𝑞) → (□𝑝 → □𝑞)
3) La formule duale : ◊ 𝑝 ↔ ¬□¬𝑝
La logique modale minimale est construite à base du système formel K clos par [5]:
o Le modus ponens:
𝑝 𝑝→𝑞
𝑞
o Ainsi que la règle de nécessité suivante:
𝑝
□𝑝

3
Observation individuelle de la conscience elle-même.

Page | 71
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

En effet, plusieurs systèmes logiques peuvent être obtenus en conservant

différents axiomes comme le montre la figure ci-dessous.

Figure 4.2 Systèmes de la logique modale [6].

Le choix d’un système modal dépendra du concept à modéliser [3] :

 Si on veut caractériser la connaissance d’un agent intelligent ayant une
parfaite capacité d’introspection logique sur ce qu’il connait, on choisira le
système modale S4. Si, en plus, l’agent est conscient de ce qu’il ne connait
pas on choisira le système modal S5.
Les systèmes S4 et S5 sont la base des logiques de savoir.
 Si on désire caractériser les croyances d’un agent idéalement rationnel (i.e. un
agent dont certaines croyances peuvent se révéler erronées mais qui
cependant possède une parfaite faculté d’introspection logique sur ce qu’il
croit et ne croit pas), on choisira le système K45.
Les systèmes K45 et KD45 sont la base des logiques de croyance.
Exemples [4]
1) Montrer par déduction naturelle que : ⊢𝐾 (□𝑝 ∧ □𝑞) → □(𝑝 ∧ 𝑞)
En plus des règles de déduction naturelle de la logique propositionnelle, on
ajoute les deux règles suivantes:

Tel que :
□𝑖 : indique l’introduction de l’opérateur modal □
□𝑒 : indique l’élimination de l’opérateur modal □
Notons qu’il n’ya pas de règles explicite pour l’opérateur de possibilité : il est écrit
dans les preuves sous la forme équivalente ¬□¬𝑝.
Dans une preuve :
 Le fait d’entrer dans une boîte en ligne continue désigne qu’on est en train
d’établir une hypothèse.
 Le fait d’entrer dans une boîte en pointillés indique qu’on est en train de
raisonner dans un monde possible arbitraire.

Page | 72
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

Rappelons les règles de déduction de la logique propositionnelle utilisées

dans cet exemple et qui servent respectivement à l’introduction/élimination de la
conjonction et à l’introdution de l’implication :

2) Montrer par déduction naturelle que :

⊢𝐾𝑇45 (𝑝 → □ ◊ 𝑝)
En plus des règles déjà vues, exploitons les deux règles suivantes qui servent
à l’introduction/élimination de la négation :

Page | 73
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

4.5 Raisonnement sur les connaissances dans un système

multi-agent
Au sein d’un même système multi-agent, les différents agents ont différentes
connaissances sur le monde. Dans certaines applications, un agent doit raisonner non
seulement sur ses propres connaissances mais aussi sur les connaissances des autres
agents. Contrairement à l’être humain, un agent artificiel peut suivre aisément une
imbrication d’énoncés du genre: « Papa ne sait pas si le Voisin sait que Papa sait que le
Voisin sait que le facteur est passé ce matin ».
Néanmoins, la formalisation de tels énoncés (et donc le raisonnement sur ces
derniers) requière la généralisation des logiques modales déjà vues au contexte multi-
agent. La logique 𝐾𝑇45𝑛 [4] constitue un exemple dont le soin est laissé aux étudiants
curieux.

4.6 Logique dynamique et Logique déontique

La logique dynamique peut être vue comme la logique modale de l’action. La
logique dynamique propositionnelle des programmes réguliers est la variante la plus
populaire de cette logique. La sémantique de cette dernière est donnée
respectivement à un model composé d’un ensemble d’états (ou mondes possibles) où
la transition d’un état à un autre se fait en exécutant un programme atomique (une
action que l’agent exécute directement) [1].
La logique déontique, quant à elle, sert à modéliser l’obligation et la
permission et par dualité le facultatif et l’interdiction. Etant un ensemble d’actions
possibles, quelle action doit choisir l’agent si son fonctionnement est régi par une
norme ou une loi ? La réponse n’est pas du tout évidente, d’ailleurs plusieurs
paradoxes sont soulevés contre la logique déontique (consulter la référence [5] pour en
avoir une idée).

4.7 Logiques temporelles

En logique temporelle, les mondes possibles représentent les états du monde
évalués à différents moments. La relation d’accessibilité peut prendre le sens de
postériorité (ce qui permet d’exprimer le futur) ou d’antériorité (ce qui permet d’exprimer
le passé):

Lecture de 𝝎 𝐑 𝝎′ Lecture □ 𝐐 Lecture ◊ 𝐐

t est postérieur à s à tous les instants futurs Q à au moins un instant futur Q
t est antérieur à s à tous les instants passés Q à au moins un instant passé Q

Tableau 4.3 Interprétations de la relation d’accessibilité et des opérateurs

modaux en logique Temporelle [3].
Selon la représentation du temps qu’on adopte : linéaire ou arborescente, on
distingue deux familles de logique temporelle, à savoir : la logique LTL et la logique
CTL. Ces deux logiques font l’objet des sous-sections suivantes.

Page | 74
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

4.7.1 Logique LTL

La logique LTL (Linear Temporal Logic) a été introduite la première fois par
Amir Pnueli en 1977 dans le cadre de vérification des programmes informatiques4.
L’interprétation d’une formule LTL est définie en termes de chemins (séquences
d’état) : où à chaque état est associé un seul successeur ou autrement « un seul futur
possible».

[Link] Syntaxe de la logique LTL

La logique LTL étend la logique propositionnelle avec des opérateurs temporels.
Soit ℒ𝑝 le langage propositionnel , le langage LTL ℒ𝐿 est défini comme suit [1]:
 Les règles de ℒ𝑝 s’appliquent sur ℒ𝐿
 Si 𝑝, 𝑞 ∈ ℒ𝐿 alors 𝑝𝑼𝑞, 𝑿𝑝, 𝑭𝑝, 𝑮𝑝 ∈ ℒ𝐿
Formule Lecture Sémantique
𝒑𝑼𝒒 𝑝 𝑈𝑛𝑡𝑖𝑙 𝑞 p est toujours vrai jusqu’à un moment où q soit vrai
𝑿𝒑 𝑁𝑒𝑥𝑡 𝑝 p sera vérifié au prochain moment
Fp Finally p p sera vérifié plus tard dans le future
Gp Globally p p est toujours vérifié.

Tableau 4.4 Signification des opérateurs de la logique LTL.

Remarques
𝐹𝑝 ≡ True ∪ p 𝐺𝑝 ≡ ¬F¬p
Exemple [7]
« Un ascenseur qui se déplace vers le haut et se trouve en deuxième étage ne change jamais sa
direction quand il a des clients qui souhaitent se rendre au cinquième étage ».
On veut modéliser cette règle de fonctionnement en LTL. Pour ce faire, on utilise les
propositions atomiques suivantes:
 Etage_2 : l’ascenseur se trouve au deuxième étage.
 Etage_5 : l’ascenseur se trouve au cinquième étage.
 Haut : la direction de l’ascenseur est vers le haut.
 BApp_5 : bouton 5 appuyé.
La formule correspondante est: 𝐆(𝐄𝐭𝐚𝐠𝐞_𝟐 ∧ 𝐇𝐚𝐮𝐭 ∧ 𝐁𝐀𝐩𝐩_𝟓 → (𝐇𝐚𝐮𝐭 𝐔 𝐄𝐭𝐚𝐠𝐞_𝟓))

[Link] Sémantique de la logique LTL

Soient l’ensemble Φ des propositions atomiques et la structure de Kripke
ℳ =< 𝑊, 𝐿, w0 , 𝑅 > où w0 ∈ 𝑊 désigne l’état initial. Un chemin infinie dans la
structure ℳ est une suite π = w0 w1 … w𝑡 … tel que :∀ 𝑡 ∈ ℕ: (w𝑡 , w𝑡+1 ) ∈ 𝑅. En plus,
considérons les notations suivantes :
π(i) ∶ dénote le ieme état dans le chemin π.
π𝑖 : dénote la queue du chemin π qui commence à la position i.

4
LTL a été introduite dans l’article intitulé «The temporal logic of programs» pour la
vérification des programmes séquentiels et parallèles.

Page | 75
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

La relation de satisfaction entre un chemin π et une formule LTL se définit

comme suit [8]:
ℳ, π ⊨ 𝜓 𝑆𝑆𝐼 𝑝 ∈ 𝐿(π(0) ) 𝑡𝑒𝑙 𝑞𝑢𝑒 𝜓 ∈ Φ
ℳ, π ⊨ ¬𝑝 𝑆𝑆𝐼 ℳ, π ⊭ 𝑝
ℳ, π ⊨ 𝑝 ∧ 𝑞 𝑆𝑆𝐼 ℳ, π ⊨ 𝑝 𝑒𝑡 ℳ, π ⊨ 𝑞
ℳ, π ⊨ 𝑋𝑝 𝑆𝑆𝐼 ( ℳ, π1 ⊨ 𝑝)
ℳ, π ⊨ 𝑝 𝑈 𝑞 𝑆𝑆𝐼 ( ∃ 𝑘 ∈ ℕ ∶ ℳ, π𝑘 ⊨ 𝑞 𝑒𝑡 ∀ 0 ≤ 𝑖 < 𝑘 ℳ, π𝑖 ⊨ 𝑝 )
La sémantique est ici définie par rapport à un chemin quelconque. Par extension, une
structure de Kripke ℳ d’origine w0 satisfait une formule si et seulement si elle est
vérifiée pour tout chemin dans ℳ d’origine w0 .
Exemple
Soit la structure de Kripke ci-dessous. Donner des exemples de formules LTL
satisfaites dans cette dernière.

4.7.2 Logique CTL

Edmund M. Clarke et Allen Emerson ont inventé la logique CTL (Computation
Tree Temporal Logic) et le model checking en 1981. En CTL, le temps est vu comme
une structure d’arbre où pour chaque état du système plusieurs futurs sont possibles
selon l’action qui sera effectuée.

[Link] Syntaxe de la logique CTL

La logique CTL étend la logique LTL par les quantificateurs de chemin A et E.
Soit p une formule LTL :
 Ap: signifie que tous les chemins (exécutions) partant de l’état courant
satisfont p.
 Ep: signifie qu’il existe au moins un chemin partant de l’état courant qui
satisfait p.
Notons que les deux opérateurs sont duaux : 𝑬𝒑 ≡ ¬𝑨¬𝑷
Soit ℒ𝐿 le langage LTL, le langage CTL ℒ𝐶 est défini comme suit :
 Les règles de ℒ𝐿 s’appliquent sur ℒ𝐶
 Si 𝑝, 𝑞 ∈ ℒ𝐶 alors 𝐴𝑋𝑝, 𝐸𝑋𝑝, 𝐴𝐹𝑝, 𝐸𝐹𝑝, 𝐴𝐺𝑝, 𝐸𝐺𝑝, 𝐴(𝑝 𝑈𝑞), 𝐸(𝑝𝑈𝑞) ∈ ℒ𝐶
[Link] Sémantique de la logique CTL
Soit ℳ une structure de Kripke. La sémantique des formules CTL se définit
par rapport à un sommet de ℳ, en considérant les chemins ayant pour origine ce
sommet [8] :

Page | 76
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

ℳ, s ⊨ 𝜓 𝑆𝑆𝐼 𝑝 ∈ 𝐿 (s ) 𝑡𝑒𝑙 𝑞𝑢𝑒 𝜓 ∈ Φ

ℳ, s ⊨ ¬𝑝 𝑆𝑆𝐼 ℳ, s ⊭ 𝑝
ℳ, s ⊨ 𝑝 ∧ 𝑞 𝑆𝑆𝐼 ℳ, s ⊨ 𝑝 𝑒𝑡 ℳ, s ⊨ 𝑞
ℳ, s ⊨ 𝐸𝑋𝑝 𝑆𝑆𝐼 (∃ π tel que π(0) = s et ℳ, π1 ⊨ 𝑝)
ℳ, s ⊨ 𝐴𝑋𝑝 𝑆𝑆𝐼 ( ∀ π tel que π(0) = s et ℳ, π1 ⊨ 𝑝)
ℳ, s ⊨ 𝐸(𝑝 𝑈 𝑞) 𝑆𝑆𝐼 ( ∃ π tel que π(0) = s ,
∃ 𝑘 ∈ ℕ ∶ M, π𝑘 ⊨ 𝑞 𝑒𝑡 ∀ 0 ≤ 𝑖 < 𝑘 ℳ, π𝑖 ⊨ 𝑝
ℳ, s ⊨ 𝐴(𝑝 𝑈 𝑞) 𝑆𝑆𝐼 ( 𝑠𝑖 π est un chemin tel que π(0) = s 𝑎𝑙𝑜𝑟𝑠
∃ 𝑘 ∈ ℕ ∶ M, π𝑘 ⊨ 𝑞 𝑒𝑡 ∀ 0 ≤ 𝑖 < 𝑘 ℳ, π𝑖 ⊨ 𝑝
Et par extention :
ℳ ⊨ 𝑝 𝑆𝑆𝐼 ℳ, w0 ⊨ 𝑝
On peut donner une description informelle aux quatre dernières règles comme suit :
 La formule EXp est satisfaite dans un état si la formule p est satisfaite dans au
moins un de ses successeurs.
 La formule AXp est satisfaite dans un état si la formule p est satisfaite dans
tous ses successeurs.
 La formule E(pUq) est satisfaite dans un état s’il existe au moins un chemin
issu de cet état tel que p est toujours satisfaite jusqu’à un état qui vérifie q.
 La formule A(pUq) est satisfaite dans un état si sur chaque chemin issu de cet
état p est toujours satisfaite jusqu’à un état qui vérifie q.
Pour mieux comprendre la sémantique des différents opérateurs, on donne la
représentation graphique ci-dessous 5.

4.7.3 Vérification de modèle (ou Model Checking)

L’objectif du model checking est la vérification des propriétés de bon
fonctionnement sur un système réactif. (Au fait, un agent intelligent peut être vu comme
un système réactif).
Un algorithme de model checking prend en entrée : i) une abstraction du
système réactif étudié (présentée via un modèle de Kripke ℳ ) et ii) une spécification du

5
[Link]

Page | 77
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

comportement désiré (exprimée pas une formule écrite en logique temporelle 𝜑).
L’algorithme vérifie si l’abstraction satisfait ou non la formule ℳ ⊨ 𝜑 ? (c.-à-d. si elle
est un modèle pour cette formule d’où le terme anglais model checking). Si la réponse est
négative : un contre-exemple est retourné [9].
Souvent, on cherche à vérifier les propriétés suivantes:
 Invariance : tous les états du système satisfont une bonne propriété.
 Accessibilité : une certaine situation peut être atteinte.
 Sûreté : quelque chose de mauvais n’arrive jamais.
 Vivacité : sous certaines conditions, un certain évènement souhaitable
finira par se produire.
Pratiquement, SPIN6 et NuSMV7 sont les model-checker les plus utilisés. Mise à
part la différence dans les langages de modélisation utilisés par les deux logiciels,
SPIN supporte seulement des propriétés écrites en LTL tandis que NuSMV supporte
à la fois LTL et CTL [11].

Exemple (LTL) [10]

Considérons un feu de circulation routière avec les trois états : vert, jaune et
rouge. Spécifions en LTL les propriétés désirables suivantes:
 « Le feu devient finalement vert » :
F vert
 « Une fois rouge, le feu ne peut pas devenir vert directement » :
𝐺(𝑟𝑜𝑢𝑔𝑒 → ¬𝑋𝑣𝑒𝑟𝑡)
 « Une fois rouge, le feu devient vert après avoir été jaune pour un certain
temps » :
𝐺(𝑟𝑜𝑢𝑔𝑒 → 𝑋( 𝑗𝑎𝑢𝑛𝑒 ∧ 𝑋(𝑗𝑎𝑢𝑛𝑒 𝑈 𝑣𝑒𝑟𝑡))

Exemple (CTL)
Imaginons un distributeur de boisson qui fonctionne comme suit. La machine se
trouve dans un état initial d’attente. Pour avoir du thé, le client doit insérer une pièce
de monnaie. Pour avoir du café, il faut insérer deux pièces de monnaie (une après
l’autre). Ensuite, le bouton OK doit être appuyé. Enfin, la machine doit revenir sur
son état initial. Considérons Φ = {a, b, c, d, e, f, g, h} tel que :

 a : Machine en état d’attente  e: Café en cours de préparation

 b : 1 pièce de monnaie déjà insérée  f : Thé en cours de préparation
 c : 2 pièces de monnaie déjà insérées  g : Café servi
 d : Bouton ok déjà appuyé  h : Thé servi

1. On veut spécifier quelques propriétés de bon fonctionnement pour ce

distributeur de boisson :

6
[Link]
7
[Link]

Page | 78
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

 La machine peut préparer du café.

 La machine finit toujours par préparer du thé si une pièce de monnaie est
insérée et qu’ensuite le bouton Ok a été appuyé.
 La machine ne serve jamais du thé si l’utilisateur a inséré deux pièces de
monnaie.
 Une fois une boisson est servie, la machine doit se remettre directement en
attente.
2. Soit la structure de Kripke ℳ ci-dessous qui modélise le fonctionnement de notre
machine (des actions sont utilisées pour étiqueter les transitions).

 Définir la fonction L.
 Quelles propriétés algébriques vérifie la relation d’accessibilité ?
 Soit le chemin infini : 𝜋 = 𝑤0 𝑤1 𝑤3 …. Vérifier si (justifier votre réponse):
ℳ, π ⊨ X ¬c
ℳ, π2 ⊨ X (c ∧ d)
ℳ, π3 ⊨ X a

4.8 Conclusion
Le thème général de ce chapitre est les logiques modales. Nous avons mis en
avant la diversité des logiques sur lesquelles on peut s’appuyer dans la formalisation
d’une telle composante ou autre au sein d’un système mono ou multi agent. Nous
incitons l’étudiant à imaginer comment mêler ces différentes logiques ensemble ?
Dans un système intelligent, on parle aussi d’une composante très
importante qui est l’interface homme-machine. Le développement de cette dernière
repose, entre autres, sur les outils du TALN (Traitement Automatique du Langage
Naturel). Le chapitre suivant constitue une introduction à cette branche fondamentale
de l’intelligence artificielle.

Page | 79
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

Recueil d’exercices
Logiques des propositions, des prédicats, modales, CTL et LTL.

Les exercices 1 à 4 sont inspirés de la référence [12].

Exercice 1 (Modélisation à l’aide de la logique des propositions)
Un système de sécurité d’une automobile peut être caractérisé par les propositions
atomiques suivantes:
Proposition Fait représenté
M Moteur en état de marche
C La caméra en état de marche
A Marche arrière enclenchée
Pi (i=1,..,4) La porte i est ouverte
H La pression d’huile est suffisante
R La voiture roule
AP L’alerte porte est en marche
AH L’alerte pression d’huile est en marche
Q1. Donner les formules représentant les axiomes suivants (dits invariants du
système):
 F1 : La caméra se met en marche lorsque la marche arrière est enclenchée.
 F2 : Si le moteur est en marche et la pression d’huile est insuffisante, l’alerte
pression d’huile doit être enclenchée.
 F3 : L’alerte porte doit être enclenchée lorsque la voiture roule et une des portes
est ouverte.
Q2. Soit les assignations des propositions A1, A2, A3 et A4 :
A1 A2 A3 A4
M V V V V
C F V V V
A F F F V
P1 F F F F
P2 F F F F
P3 F F V F
P4 F F F F
H V V V V
R V V V F
AP F F F F
AH F F F F
Etant donnée l’assignation A1, le système est-il dans un état correct ?
Q3. Pour que le système reste dans un état correct, tout évènement qui modifie la
valeur de vérité d’une ou de plusieurs propositions n’est admissible que s’il fait
passer les invariants du système d’un modèle à un autre. Alors, les évènements
suivants sont-ils interdits (considérons que le système se trouve initialement dans A1) ?
o Activer la caméra.
o Activer la caméra et ouvrir la porte 3.
o Enclencher la marche arrière, activer la caméra et s’arrêter de rouler.

Page | 80
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

Exercice 2 (La logique des propositions a un pouvoir d’expression limité)

Considérons un domaine de connaissance composé de 3 objets, 2 propriétés, 1
relation binaire symétrique.
 Combien de variables propositionnelles a-t-on besoin pour représenter nos
connaissances sur le domaine en question?
 Représenter en LP les énoncés suivants:
o Il y a au moins un objet pour lequel la propriété 2 est vraie.
o Il y a au moins deux objets pour lesquels la propriété 2 est vraie et qui sont en
relation.
 Refaire les mêmes questions pour: 10 objets, 15 propriétés et 15 relations.
Commenter.
 Maintenant, on ne sait pas combien il y a d’objets dans le système. Représenter
l’énoncé suivant: Tout objet possède soit la propriété 1 soit la propriété 2.

Exercice 3 (Rappel de la Syntaxe de la logique des prédicats)

Soit les prédicats suivants :
P(x) : x est un professeur
H(x) : x est un humain
S(x) : x est un étudiant
L(x) : x est un cours
B(x,y) : x assiste le cours y
Exprimer en logique des prédicats les énoncés suivants:
 Tous les étudiants sont des humains
 Aucun étudiant n’est professeur
 Quelques humains sont des professeurs
 Certains étudiants assistent à tous les cours
 Tous les étudiants n’assistent pas à tous les cours

Exercice 4 (Sémantique, domaine de connaissance, fonction d’interprétation)

Soit le langage composé des symboles:
 Constantes: a, b, c, d, k1, k2, k3, k4
 Prédicats: P (unaire), E (unaire), C (unaire), H (binaire), S(unaire), T (binaire)
 Variables: x, y, z.
On interprète ce langage dans le domaine suivant:
Personne = {Ali, Lila ,Omar,Dina}
Etudiant = {Ali, Lila,Omar}
Cours = {Logique, Algèbre,Analyse,statistique}
On définit une interprétation sur ce domaine comme suit:
ℐ (𝑎) = 𝐴𝑙𝑖 ℐ (𝑘1) = 𝐿𝑜𝑔𝑖𝑞𝑢𝑒 ℐ (𝑃 ) = 𝑃𝑒𝑟𝑠𝑜𝑛𝑛𝑒, ℐ (𝐸 ) = 𝐸𝑡𝑢𝑑𝑖𝑎𝑛𝑡
ℐ (𝑏) = 𝐿𝑖𝑙𝑎 ℐ (𝑘2) = 𝐴𝑙𝑔è𝑏𝑟𝑒 ℐ (𝐶 ) = 𝐶𝑜𝑢𝑟𝑠,
ℐ (𝑐) = 𝑂𝑚𝑎𝑟 ℐ (𝑘3) = 𝐴𝑛𝑎𝑙𝑦𝑠𝑒 ℐ(𝑆) = 𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑎𝑛𝑡
ℐ (𝑑) = 𝐷𝑖𝑛𝑎 ℐ (𝑘4) = 𝑆𝑡𝑎𝑡𝑖𝑠𝑡𝑖𝑞𝑢𝑒 ℐ (𝑇) = 𝐸𝑛𝑠𝑒𝑖𝑔𝑛𝑒

Page | 81
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

ℐ (𝐻) = 𝐼𝑛𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛={(Ali,Logique),(Lila,statistique), (Omar,Logique)}

Evaluer les formules suivantes (Vrai ou faux) selon l’interprétation ℐ :
 𝐶(𝐾3)
 𝐶(𝑎)
 𝐻(𝑐, 𝐾1)
 ∃ 𝑥 𝐻(𝑥, 𝑘2)
 ∀𝑥 ∃ 𝑦 𝐻(𝑥, 𝑦)

Exercice 5 (Logique Modale)

Considérer un modèle de Kripke ℳ =< 𝑊, 𝐿, 𝑅 > :
1. Quand ℳ, 𝑤 ⊨ 𝑝 ⇒ 𝑞 ?
2. Vérifier que :
« Si ℳ est un modèle quelconque alors l’axiome K est valide (formellement :
ℳ, 𝑤 ⊨ □(𝑝 ⇒ 𝑞) ⇒ (□𝑝 ⇒ □𝑞)) »
3. Vérifier que :
« Si ℳ est muni d’une relation d’accessibilité réflexive alors l’axiome T est
valide (formellement : ℳ, 𝑤 ⊨ (□𝑝 ⇒ 𝑝)) »

Exercice 6 (Logiques Temporelles)

1. Exprimer en LTL et en CTL les énoncés suivants :
o p n’est jamais vérifié.
o À chaque fois que p arrive, q doit éventuellement arriver.
2. Soit ℳ le modèle (système de transition) de la figure. Vérifier si ℳ ⊨ 𝐺(𝑝 ∨ 𝑞) et si
ℳ ⊨ 𝐺𝑝 ∨ 𝐺𝑞

3. Vérifier si ℳ ⊨ 𝐹(𝑝 ∧ 𝑞) et si ℳ ⊨ 𝐹𝑝 ∧ 𝐹𝑞 pour le modèle suivant :

Exercice 7 [10]
Considérons un canal de communication unidirectionnel entre deux processus S
(émetteur) et R (récepteur). S est équipé par un tampon de sortie [Link] et R est
équipé par un tampon d’entrée [Link]. Quand S envoie un message, il le met dans
[Link]. Le récepteur R reçoit un message en le supprimant de [Link].

Page | 82
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

Soient les propositions atomiques:

X : un message m est dans [Link] Y: un message m est dans [Link]

Formaliser en LTL, les spécifications de fonctionnement suivantes qui doivent être

toujours vérifiées:
 Si un message est dans [Link] alors m sera finalement reçu.
 Un message m reste dans [Link] jusqu’à sa réception.
 Un message ne peut être en même temps dans [Link] et [Link].
 Si l’émetteur envoie un message m suivi d’un autre message p alors le
récepteur doit recevoir m avant p (préservation de l’ordre d’envoie).

Page | 83
 Systèmes Intelligents

Chapitre 4 : Logiques Modales

Références du chapitre

[1] M. P. Singh, A. S. Rao, and M. P. Georgeff. Formal methods in DAI: Logic based
representation and reasoning. In G. Weis, editor, Multiagent Systems—A Modern
Approach to Distributed Artificial Intelligence, chapter 8, pages 331–376.
[2] R. Mastop Modal Logic for Artificial Intelligence: notes de cours, 2012. Accessible
à [Link]
[3] A. Thayse, De la logique modale à la logique des bases de données. Paris: Dunod,
1989. MIT Press, Cambridge, MA, 1999.
[4] M. Huth and M. Ryan, Logic in computer science. Cambridge: Cambridge
University Press, 2000.
[5] J. Duparc, La logique pas à pas, Presses polytechniques et universitaires
romandes. ISBN 978-2-88915-126-4, 2015.
[6] J. Ferber, Les systèmes multi-agents. Vers une intelligence collective. Paris :
InterEditions, 1995.
[7] J. Johnson, Temporal Logic and the NuSMV Model Checker: notes de cours CS 680
Formal Methods, Drexel university.
[8] P. Bourdil, Contribution à la modélisation et la vérification formelle par model-
checking – Symétries pour les Réseaux de Petri Temporels : Thèse de doctorat
(Chapitre 1), INSA de Toulouse, 2015.
[9] S. Bardin, Introduction au Model Checking : notes de cours, Université de Paris-
Saclay, 2017.
[10] C. Baier and J. Katoen, Principles of model checking. Cambridge [MA]: The MIT
Press, 2008.
[11] Y. Jiang and Z. Qiu, S2N: Model Transformation from SPIN to NuSMV. In:
Donaldson A., Parker D. (eds) Model Checking Software. SPIN 2012. Lecture
Notes in Computer Science, vol 7385. Springer, Berlin, Heidelberg, 2012.
[12] G. Falquet, Fondements formels des systèmes d’information (chapitre 4 : logique
propositionnelle), Université de Genève, Faculté SES, département HEC, Centre
universitaire d’informatique, 2012.

Page | 84
 CHAPITRE 5
Introduction au Traitement Automatique
du Langage Naturel

5.1 Introduction
Un langage est un système qui contient un ensemble de symboles, une syntaxe et
une sémantique. La syntaxe permet de former, à partir des symboles, des
expressions complexes dont l’interprétation est définie par la sémantique. En ce sens,
les systèmes logiques, les langages de programmation et les langues naturelles sont
tous des langages. Par langage naturel (en opposition au langage formel), on entend un
langage parlé et écrit par des humains comme: l’Arabe, le Français, etc.
Dans ce chapitre, nous nous intéressons au Traitement Automatique du Langage
Naturel (TALN). Le TALN regroupe l’ensemble des recherches et développements
visant à modéliser et reproduire, à l’aide de machines, la capacité humaine à
produire et à comprendre des énoncés linguistiques dans des buts de communication
[1]. Le TALN est un champ pluridisciplinaire qui fait appel bien évidement à
l’informatique et la linguistique mais aussi à la logique, les statistiques, la
psychologie et les sciences cognitives.
Une langue naturelle est intrinsèquement ambiguë. Malgré cela, l’être humain est
capable de désambiguïser le sens des différentes constructions linguistiques. La
reproduction d’une telle faculté au sein d’une application de TALN n’est pas du tout
une tâche triviale.

Page | 85
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
Le traitement de la langue se fait à différent niveaux superposés : lexical,
syntaxique et sémantique. Au sein d’un même niveau, différentes voies peuvent être
prises. Pour ce chapitre, qui est loin d’être exhaustif, l’étudiant est initié à l’utilisation
de l’approche logique (où on fait recours notamment au langage Prolog) et aussi à
l’approche statistique/probabiliste (où nous référons au modèle de Markov caché
pour la résolution du problème particulier d’étiquetage morphosyntaxique). Nous
nous intéressons également au calcul de mesures de similarité à base de thésaurus
comme une alternative pour le traitement sémantique lexicale.
Afin de bien assimiler certaines notions théoriques présentées dans le chapitre,
l’utilisation du langage Python conjointement avec la bibliothèque NLTK est
recommandée. L’étudiant doit surtout apprendre à manipuler des ressources
textuelles via NLTK.

5.2 Niveaux d’analyse linguistique dans une application du

TALN
Le traitement de la langue permettrait à l’ordinateur d’analyser et de
comprendre d’énormes quantités de données textuelles, de communiquer avec nous
par écrit ou par parlé, de capturer nos mots indépendamment de l’interface
d’entrée (à travers du clavier ou par reconnaissance de parole), d’analyser nos
phrases, de comprendre nos propos, de répondre à nos questions voire même de
mener des conversations avec nous [2]. Aujourd’hui, les applications du TALN sont
multiples, on cite entre autres: la correction orthographique, la recherche et
l’indexation d’information, les interfaces vocales, la reconnaissance de l’écriture, la
traduction automatique, le résumé automatique, la dictée vocale, etc.
Le processus général du TALN passe par les étapes schématisées dans la
figure ci-dessous. Ce processus constitue sans doute l’axe principal de ce chapitre.
Mais avant d’aborder les différents traitements, soulignons que:

Traitement Traitement Traitement

Phonétique Morphologique Syntaxique

Traitement Traitement
Pragmatique Sémantique

Figure 5.1 Processus général du TALN.

 Pour aller du son au sens, différentes techniques peuvent être utilisées à
chaque niveau (traitement de signal, statistiques, probabilité, logique,
raisonnement automatique…)
 Le traitement phonétique n’est effectué que lorsque l’entrée du système est
vocale (ce n’est pas d’ailleurs le cas pour toutes les applications citées ci-avant).

Page | 86
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
 Etant donnée une phrase, l’analyse morphologique permet de déterminer les
« mots » qui sont par la suite regroupés en structures par l’analyse
syntaxique.
 Le traitement sémantique se fait aux niveaux lexical et syntaxique. Il s’agit
dans les deux cas d’une sémantique hors contexte.
 Le traitement pragmatique peut être vu comme un traitement sémantique en
contexte. Dans cette phase, on fait lier le sens de la phrase à son contexte
spécifique pour aboutir à sa signification réelle. La pragmatique a pour objet
l’étude des actes du langage où on se préoccupe des concepts importants
suivants [3]:
 l’implicature qui se réfère à ce qui est signifié implicitement par le
locuteur. Par exemple, la phrase: « Pouvez-vous fermer la porte ? » n’est
pas une question, mais plutôt une forme de politesse via laquelle on
demande à quelqu’un de fermer la porte.
 les présuppositions qui sont les faits qui doivent être vrais afin qu’une
phrase peut être évaluée comme vraie ou fausse. Par exemple, si on dit
«Ahmed est guéri» cela présuppose qu’Ahmed était malade.
 l’étude de discours c’est-à-dire la manière dont l’homme connecte des
phrases pour transmettre l’information.
Par manque de temps, nous n’abordons pas dans ce cours les travaux menés en
matière de pragmatique. La discussion de la sémantique syntaxique nous renvoie à
l’approche logique dans la représentation/interprétation du sens : une compétence
déjà acquise par les étudiants au cours des chapitres précédents. Néanmoins, nous
allons un peu plus profondément en termes de sémantique lexicale qui est
naturellement à la base de la sémantique syntaxique.

5.3 Modèles et Algorithmes

En TALN, on doit représenter les diverses connaissances linguistiques
nécessaires à chaque niveau d’analyse (phonétique, morphologique, syntaxique,
sémantique et pragmatique). Dans ce but, généralement on fait recours aux automates à
états finis, aux grammaires formelles, à la logique du premier ordre mais aussi à des
modèles probabilistes pour remédier aux problèmes d’ambiguïté [4].
Une fois la phase de modélisation est accomplie, on est amené typiquement à
résoudre des problèmes de recherche dans un espace d’états. Pour cette fin, des
algorithmes bien connus comme la recherche en profondeur d’abord (pour des tâches
non probabilistes) et de programmation dynamique (pour des tâches probabilistes)
peuvent être appliqués [4].
Dans ce chapitre, nous donnons des exemples sur l’utilisation du langage Prolog,
qui est un langage basé sur la logique des prédicats, en TALN. Prolog est exploité
pour implémenter des automates et des grammaires et puis mener des recherches
pour répondre à des problèmes de reconnaissance et de génération souvent
rencontrés aux niveaux lexical et syntaxique. Aussi, le Modèle de Markov Caché
(MMC) est présenté conjointement avec l’algorithme de Viterbi (qui implémente le
principe de la programmation dynamique) dans le contexte particulier d’étiquetage

Page | 87
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
morphosyntaxique. Enfin, nous abordons le calcul de similarité lexicale par
thésaurus.

5.4 Quelques notions préliminaires en TALN

Dans cette section sont définies les notions de n-grammes, de corpus et de
thésaurus : des notions auxquelles nous faisons recours dans le reste du chapitre.

5.4.1 N-grammes
Dans un modèle probabiliste du langage, on fait l’hypothèse que chaque mot ne
dépend que des (n-1) mots qui le précèdent. On parle souvent de [5] :
 Trigramme (n = 3) : un mot dépend des deux mots qui le précèdent.
 Bigramme (n = 2) : un mot dépend du mot qui le précède.
 Unigramme (n = 1) : un mot ne dépend d’aucun mot qui le précède.
L’apprentissage de la distribution de probabilité des n-grammes se fait à partir d’un
corpus.

5.4.2 Corpus
Un corpus est [6] : « une collection de données langagières qui sont
sélectionnées et organisées selon des critères linguistiques et extralinguistiques
explicites pour servir d’échantillon d’emplois déterminés d’une langue.
Pratiquement, un corpus doit exister sous un format électronique où il est encodé de
manière standardisée et homogène pour permettre des extractions non limitées à
l’avance».
Le corpus de Brown est un exemple de corpus annoté (avec 87 étiquettes
morphosyntaxiques). C’est une collection de 1 million de mots provenant de 500
textes de différents genres (journaux, romans, académiques, etc.), rassemblés à
l'Université Brown en 1963 [4].

5.4.3 Thésaurus
Un thésaurus, aussi appelée ontologie en linguistique, est une organisation
hiérarchique de termes censés être représentatifs d’un certain domaine. Les termes
sont liés entre eux notamment par la relation spécifique/générique (par exemple : un
bateau est un véhicule), la relation de synonymie (par exemple : un navire est synonyme de
bateau) et la relation «terme associé» (par exemple : navigation est un terme associé à
bateau). Les thésaurus sont souvent utilisés pour l'indexation de documents et la
recherche de ressources documentaires.
Le thésaurus WordNet est une base lexicale de la langue anglaise qui couvre
plus de 150 000 mots qui varient entre noms, verbes, adjectifs et adverbes. Sa
richesse mais aussi sa disponibilité en ligne1 (peut-être même téléchargé sous forme de
faits Prolog) sont les clés de son grand succès. WordNet arrange les mots ainsi que les
significations de mots dans une matrice lexicale, tel que [2]:

1 [Link]

Page | 88
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
 Une ligne horizontale définit un ensemble de mots synonymes dits synset
dans le vocabulaire WordNet.
 Une colonne montre les différentes significations que peut avoir un mot.

5.5 Programmation Logique avec Prolog

Un algorithme consiste d’une partie logique qui décrit les connaissances
nécessaires (le quoi ou le sens de l’algorithme) et d’une partie contrôle qui décrit
comment exploiter ces connaissances pour trouver la solution désirée. Dans le
paradigme impératif traditionnel, on décrit explicitement les étapes de résolution
d’un problème. En revanche, en programmation déclarative y compris en
Programmation Logique (PL), on s’intéresse plutôt au sens du programme.
Les caractéristiques d’un langage de programmation logique peuvent être
résumées dans les points suivants :
 Un langage de programmation logique est destiné à la programmation
symbolique où les données traitées sont des informations non numériques.
 Dans un programme logique, on décrit des objets, des propriétés et des
relations ce qui donne l’aspect déclaratif.
 Etant donné un programme logique, qui n’est rien autre qu’un ensemble de
faits et de règles, un langage de programmation logique utilise le processus
d’inférence logique pour répondre aux requêtes.
5.5.1 Rappel des notions de la logique des prédicats utilisées en PL
a) Forme clausale [7] : toutes les formules de la logique des prédicats peuvent s’écrire
dans le format suivant
𝐴1 ∧ 𝐴2 ∧ … 𝐴𝑚 → 𝐵1 ∨ 𝐵2 … ∨ 𝐵𝑛
Informellement « si tous les A sont vrais alors au moins un B est vrai ». Voici un exemple
d’une formule écrite en forme clausale :
Père (Ali, Omar) ∧ Mère (Lila, Omar) ∧ GrandPère(Ahmed, Omar)
→ Père(Ahmed, Ali) ∨ Père(Ahmed, Lila)

Exemple (adapté de la référence [8])

Représenter les énoncés en langage naturel suivants dans la forme clausale :
« Tout Américain qui vend des armes à des pays hostiles est un criminel (1). Le pays B
possède des missiles (2), B est un ennemi de l’Amérique(3). Toutes ses missiles lui ont été
vendu par colonel C (4) qui est américain (5)»
(1) 𝐴𝑚é𝑟𝑖𝑐𝑎𝑖𝑛(𝑥) ∧ 𝐴𝑟𝑚𝑒(𝑦) ∧ 𝑉𝑒𝑛𝑑(𝑥, 𝑦, 𝑧) ∧ 𝐻𝑜𝑠𝑡𝑖𝑙𝑒(𝑧) → 𝐶𝑟𝑖𝑚𝑖𝑛𝑒𝑙(𝑧)
(2) ∃ 𝑥 𝑃𝑜𝑠𝑠è𝑑𝑒 (𝐵, 𝑥) ∧ 𝑀𝑖𝑠𝑠𝑖𝑙𝑒(𝑥) , par instanciation existentielle où on introduit
une constante M1 on obtient:
𝑃𝑜𝑠𝑠è𝑑𝑒 (𝐵, 𝑀1)
𝑀𝑖𝑠𝑠𝑖𝑙𝑒(𝑀1)
(3) 𝐸𝑛𝑛𝑒𝑚𝑖 (𝐵, 𝐴𝑚é𝑟𝑖𝑞𝑢𝑒)
Il faut aussi ajouter (pour faire le lien entre Hostile et Ennemi):
𝐸𝑛𝑛𝑒𝑚𝑖 (𝑥, 𝐴𝑚é𝑟𝑖𝑞𝑢𝑒 ) → 𝐻𝑜𝑠𝑡𝑖𝑙𝑒(𝑥)
(4) 𝑀𝑖𝑠𝑠𝑖𝑙𝑒(𝑥) ∧ 𝑃𝑜𝑠𝑠è𝑑𝑒(𝐵, 𝑥) → 𝑉𝑒𝑛𝑑(𝐶, 𝑥, 𝐵)
(5) 𝐴𝑚é𝑟𝑖𝑐𝑎𝑖𝑛(𝐶)

Page | 89
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
(6) 𝑀𝑖𝑠𝑠𝑖𝑙𝑒(𝑥) → 𝐴𝑟𝑚𝑒(𝑥)
b) Clauses de Horn [7] : sont les clauses ayant au maximum un littéral positif. On
distingue trois formes de clause de Horn :
 Règle : composée d’un littéral positif avec au moins un littéral négatif.
 Fait : avec seulement un littéral positif.
 Objectif ou requête : avec seulement des littéraux négatifs.
c) Résolution / unification [7] : la résolution s’applique sur des formules écrites au
format clausale. Elle permet de déduire de nouvelles connaissances en
appliquant le mécanisme suivant:
 Appliquer la conjonction entre les parties gauches et la disjonction entre
les parties droites.
 Supprimer les éléments qui apparaissent dans les deux côtés.
Exemple
Dans cet exemple : a, b, c sont des constantes.
𝑝𝑎𝑟𝑒𝑛𝑡(𝑎, 𝑏) → 𝑝è𝑟𝑒(𝑎, 𝑏) ∨ 𝑚è𝑟𝑒(𝑎, 𝑏)
𝑝è𝑟𝑒(𝑎, 𝑏) ∧ 𝑝è𝑟𝑒(𝑏, 𝑐) → 𝑔𝑟𝑎𝑛𝑑𝑝è𝑟𝑒(𝑎, 𝑐)
La résolution mène à :
𝑝𝑎𝑟𝑒𝑛𝑡(𝑎, 𝑏) ∧ 𝑝è𝑟𝑒(𝑏, 𝑐) → 𝑔𝑟𝑎𝑛𝑑𝑝è𝑟𝑒(𝑎, 𝑐) ∨ 𝑚è𝑟𝑒(𝑎, 𝑏)
En présence de variables, il faut trouver des valeurs pour ces variables permettant de
réussir le processus d’appariement : on parle d’unification.
Exemple
𝑝è𝑟𝑒(𝑥) → ℎ𝑜𝑚𝑚𝑒(𝑥)
𝑝è𝑟𝑒(𝐴𝑙𝑖)
Il faut substituer x par Ali :
𝑝è𝑟𝑒(𝐴𝑙𝑖 ) → ℎ𝑜𝑚𝑚𝑒(𝐴𝑙𝑖)
𝑝è𝑟𝑒(𝐴𝑙𝑖 )
La résolution de ces deux clauses donne :𝑝è𝑟𝑒(𝐴𝑙𝑖 ) → ℎ𝑜𝑚𝑚𝑒 (𝐴𝑙𝑖) ∨ 𝑝è𝑟𝑒(𝐴𝑙𝑖 )
Ce qui coïncide avec le fait : ℎ𝑜𝑚𝑚𝑒 (𝐴𝑙𝑖)

5.5.2 Langage Prolog

Prolog2 (PROgrammation LOGique) est sans doute le langage logique le plus
connu. Il a été inventé à Marseille en 1972 par Alain Colmerauer. Prolog est un langage
de l’intelligence artificielle conçu à l’origine pour des applications du traitement
automatique du langage naturel et des grammaires formelles. Nous résumons les
principales propriétés du langage Prolog à travers plusieurs exemples [7]:
a) Prolog utilise les clauses de Horn (les faits, les règles et les requêtes).
Voici un programme ou une base de connaissance Prolog qui contient deux faits
et une règle:
𝑝𝑙𝑢𝑣𝑖𝑒𝑢𝑥 (𝑏𝑎𝑡𝑛𝑎 ).
𝑓𝑟𝑜𝑖𝑑 (𝑏𝑎𝑡𝑛𝑎 ).
𝑛𝑒𝑖𝑔𝑒𝑢𝑥 (𝑋) : − 𝑝𝑙𝑢𝑣𝑖𝑒𝑢𝑥(𝑋), 𝑓𝑟𝑜𝑖𝑑(𝑋).
𝑆𝑜𝑖𝑒𝑛𝑡 𝑙𝑒𝑠 𝑟𝑒𝑞𝑢ê𝑡𝑒𝑠:

2 Les captures d’écrans figurant dans cette section sont obtenues par l’environnement swi-
prolog téléchargeable à [Link]

Page | 90
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
? − 𝑓𝑟𝑜𝑖𝑑 (𝑏𝑎𝑡𝑛𝑎).
? − 𝑛𝑒𝑖𝑔𝑒𝑢𝑥 (𝑏𝑎𝑡𝑛𝑎).
? − 𝑛𝑒𝑖𝑔𝑒𝑢𝑥(𝐴).
Pour répondre à une requête, la base de connaissance est parcourue de la première
clause à la dernière.
b) Prolog utilise le chainage en arrière et effectue une recherche en profondeur
d’abord (preuve sous-but par sous-but):
Essayons de répondre à : ? − 𝑛𝑒𝑖𝑔𝑒𝑢𝑥 (𝐴). Pour ce faire, construisons un arbre :

Examinons de près la trace d’exécution Prolog correspondante (où call désigne le

début d’une vérification, Exit indique que le but est vérifié, le symbole = dénote
l’unification) :

c) Prolog effectue un retour arrière, s’il échoue dans la vérification d’un sous but :
Ajoutons en tête de la BC de l’exemple précédent le fait pluvieux (jijel) et exécutant la
même requête précédente. On obtiendra la trace suivante (où Fail désigne l’echec
d’une vérification, Redo indique un retour arrière et l’essai d’une nouvelle instanciation) :

Page | 91
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
d) L’ordre des clauses dans la BC et celui des termes dans les règles affectent
l’efficacité du processus d’inférence :
 Dans l’exemple précédent, si on n’a pas ajouté pluvieux (jijel) en tête de la
BC on aurait pu aboutir à une réponse plus rapidement (en évitant le
retour arrière).
 Etant donnée la requête : ? − ℎ𝑜𝑠𝑡𝑖𝑙𝑒 (𝑋). Il vaut mieux utiliser la règle :
ℎ𝑜𝑠𝑡𝑖𝑙𝑒(𝑋) : − 𝑒𝑛𝑛𝑒𝑚𝑖(𝑋, 𝑎𝑚é𝑟𝑖𝑞𝑢𝑒), 𝑝𝑎𝑦𝑠 (𝑋). que d’utiliser :
ℎ𝑜𝑠𝑡𝑖𝑙𝑒 (𝑋) : − 𝑝𝑎𝑦𝑠(𝑋), 𝑒𝑛𝑛𝑒𝑚𝑖(𝑋, 𝑎𝑚é𝑟𝑖𝑞𝑢𝑒). puisqu’il y a logiquement
moins d’ennemis que de pays (on minimise le nombre des retours arrières
qu’on peut y avoir).
e) Prolog utilise l’opérateur Cut, symbolisé par (!), pour contrôler la recherche. Voici
un exemple comparatif (sans et avec Cut) :
chemin (X,Y) :- arc (X,Z), arc (Z,Y). chemin (X,Y) :- arc (X,Z), !, arc (Z,Y).
arc(1,6). arc(1,6).
arc(1,8). arc(1,8).
arc(6,7). arc(6,7).
arc(6,1). arc(6,1).
arc(8,3). arc(8,3).
arc(8,1). arc(8,1).
Soit la requête ?- chemin (1,V). Soit la requête ?- chemin (1,V).

ici Z est unifié à 6 seulement, le retour

arrière est bloqué par le cut (!)

f) Prolog, tout comme les langages fonctionnels, utilise intensivement les listes :
On donne ici l’exemple du prédicat append qui permet de concaténer des listes. Il
est prédéfini dans Prolog:
𝑎𝑝𝑝𝑒𝑛𝑑([], 𝑋, 𝑋).
𝑎𝑝𝑝𝑒𝑛𝑑([𝑋|𝑌), 𝑍, [𝑋|𝑊]) ∶ − 𝑎𝑝𝑝𝑒𝑛𝑑(𝑌, 𝑍, 𝑊).
g) Prolog est basé sur l’hypothèse du monde fermé : en réalité, Prolog est un
système de type True|Fail et non pas True| False (Prolog retourne false quand il
échoue à démontrer le True à partir de sa base de connaissance).
h) La négation dans Prolog prend le sens de l’échec. Voici un exemple : la requête:
? − 𝑛𝑜𝑡 (𝑒𝑛𝑛𝑒𝑚𝑖 (𝑋, 𝑎𝑙𝑔é𝑟𝑖𝑒)). est équivalente à : ¬ ∃𝑋 (𝑒𝑛𝑛𝑒𝑚𝑖(𝑋, 𝑎𝑙𝑔é𝑟𝑖𝑒)).On ne
peut pas exprimer qu’on cherche des pays qui ne sont pas des ennemis de
l’Algérie , c’est-à-dire ∃𝑋 (¬𝑒𝑛𝑛𝑒𝑚𝑖 (𝑋, 𝑎𝑙𝑔é𝑟𝑖𝑒)) ?

Page | 92
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

5.6 Chaines de Markov

Une chaine ou processus de Markov est une séquence de variables aléatoires
{𝑋1 , 𝑋2 , … , 𝑋𝑇 } qui prennent leurs valeurs dans l’espace d’états : 𝑆 = {𝑞1 , 𝑞2 , … , 𝑞𝑁 }. Un
processus stochastique est dit markovien s’il vérifie les deux propriétés suivantes [2]:
 Historique limité : l’état courant dépend d’un nombre constant d’états
précédents. Par exemple, on parle de processus du premier ordre lorsque:
𝑃(𝑋𝑡 = 𝑞𝑗 |𝑋1 , 𝑋2 , … , 𝑋𝑡−1 ) = 𝑃(𝑋𝑡 = 𝑞𝑗 |𝑋𝑡−1 )
 Indépendance du temps : la probabilité de passage d’un état à un autre ne varie
pas avec le temps ; cela est formellement exprimé comme suit (toujours pour
un processus du premier ordre):
𝑃(𝑋𝑡 = 𝑞𝑗 |𝑋𝑡−1 = 𝑞𝑖 ) = 𝑎𝑖𝑗 avec 𝑎𝑖𝑗 ≥ 0 𝑒𝑡 ∑𝑁 𝑗=1 𝑎𝑖𝑗 = 1
Tel que : 1 ≤ 𝑖, 𝑗 ≤ 𝑁
Dans ce qui suit, on dénote par A la matrice des probabilités de transition.
Une chaine de Markov peut être alors vue comme un automate probabiliste.
Différemment d’un automate ordinaire, l’état initial (à l’instant t=1) peut être
n’importe quel élément dans S. Plus formellement, on définit la loi de probabilité de
l’état initial Π = {π𝑖 } tel que [2,4]:
𝑁

π𝑖 = 𝑃(𝑋1 = 𝑞𝑖 ) 𝑎𝑣𝑒𝑐 ∑ π𝑖 = 1
𝑖=1
L’évolution d’un modèle de Markov au cours du temps peut être schématisée
par un treillis [2] comme dans la figure ci-dessous (sur l’axe vertical se trouvent les
états).

Figure 5.2 Représentation du modèle de Markov par un Treillis.

5.6.1 Modèles de Markov Cachés

Dans un modèle de Markov caché, la séquence d’états est inobservable (d’où le
nom caché du modèle). Ce qu’on peut plutôt observer est la séquence des symboles
émis par les états et qu’on dénote : 𝑂 = 𝑂1 , 𝑂2 , … , 𝑂𝑇 .
Un modèle de Markov caché [2,4] est défini par un quintuple < 𝑆, 𝑉, Π, 𝐴, 𝐵 >
où 𝑉 = {𝑣1 , 𝑣2 , . . . , 𝑣𝑀 } est l’alphabet des symboles émis par les états. B dénote la

Page | 93
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
matrice des probabilités d’émission ; la probabilité que l’état 𝑞𝑗 emet le symbole
𝑣𝑘 , 𝑏𝑗 (𝑣𝑘 ), est définie comme suit :
𝑏𝑗 (𝑣𝑘 ) = 𝑃(𝑜𝑡 = 𝑣𝑘 |𝑋𝑡 = 𝑞𝑗 )
S, Π et T sont comme déjà définis dans la section précédente.
Exemple
Considérons l’expérience aléatoire qui consiste à lancer trois pièces de monnaie
biaisées. Définissons les éléments du modèle de Markov caché correspondant:
 S= {𝑞1 , 𝑞2 , 𝑞3 } tel que : 𝑞1 : 𝑝𝑖è𝑐𝑒 1, 𝑞2 : 𝑝𝑖è𝑐𝑒 2, 𝑞3 : 𝑝𝑖è𝑐𝑒 3
0.4 0.5 0.1
 La matrice de transition 𝐴 = [0.2 0.6 0.2]
0.1 0.4 0.5
On peut schématiser les transitions entre les états par l’automate suivant :

 𝑉 = {𝑃, 𝐹} (P : Pile, F : Face)

0.48 0.52
 La matrice des probabilités d’émission 𝐵 = [ 0.80 0,20 ]
0.55 0.45
 Les probabilités de l’état initial : π1 = π2 = 0.3 π3 = 0.4

Imaginons que nous avons observé la séquence des symboles 𝑂 =

𝑂1 , 𝑂2 , … , 𝑂7 =FPPFPPP, la question qui se pose est « quelle est la suite d'états ou bien
le chemin la/le plus probable ayant généré cette séquence ?».
Afin de répondre à une telle question, on peut procéder d’une manière très
naïve à calculer la probabilité de tous les chemins pouvant générer cette séquence, et
puis choisir celui dont la probabilité est maximale. Cette solution est clairement très
coûteuse, il existe heureusement des algorithmes plus appropriés. Particulièrement,
nous nous intéressons dans ce qui suit à l’algorithme de Viterbi. Ce dernier est vu
comme une application du principe de la programmation dynamique.

5.6.2 Algorithme de Viterbi

Etant donnés une observation et un modèle de Markov caché en entrée,
l’algorithme de Viterbi permet de calculer la séquence d’états optimale qui a généré
cette observation. Cette problématique est souvent connue par la problématique de
décodage. Cet algorithme est souvent appliqué en TALN dans le cadre de l’étiquetage
morphosyntaxique et dans celui de la reconnaissance de la parole. Définissons quelques
notations [2]:

Page | 94
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
Etant donné un modèle de Markov caché, on défini 𝜆 = (𝐴, 𝐵, Π) .
Notons par 𝛿𝑡 (𝑗 ) la probabilité maximale d’une observation 𝑜1 , 𝑜2 , … , 𝑜𝑡 sous la
condition que l’état courant soit 𝑞𝑗 à l’instant t :
𝛿𝑡 (𝑗) = max 𝑃(𝑠1 , 𝑠2 , … , 𝑠𝑡−1 , 𝑜1 , 𝑜2 , … , 𝑜𝑡 , 𝑠𝑡 = 𝑞𝑗 |𝜆)
𝑠1 ,𝑠2 ,…,𝑠𝑡−1
𝜓𝑡 (𝑗) est le chemin optimal correspondant.
Algorithme de Viterbi (adapté de la référence [2])
1. Initialisation pour t=1
Pour i=1 à N faire
𝛿1 (𝑖 ) = π𝑖 × b𝑖 (𝑜1 )
𝜓1 (𝑖 ) = 𝑛𝑢𝑙𝑙
Fin Pour
2. Boucle d’induction
t =2
Tant que 𝑡 ≤ 𝑇 faire
j= 1
Tant que 𝑗 ≤ 𝑁 faire
𝛿𝑡 (𝑗 ) = b𝑗 (𝑜𝑡 ) × max 𝛿𝑡−1 (𝑖 ). 𝑎𝑖𝑗
1≤𝑖≤𝑁
𝜓𝑡 (𝑗 ) = arg max 𝛿𝑡−1 (𝑖 ). 𝑎𝑖𝑗
1≤𝑖≤𝑁
𝑗 = 𝑗+1
𝐹𝑖𝑛 𝑇𝑄
t=t+1
𝐹𝑖𝑛 𝑇𝑄
3. Terminaison
𝑃̂ = max 𝛿𝑇 (𝑖 )
1≤𝑖≤𝑁
𝑆̂𝑇 = arg max1≤𝑖≤𝑁 𝛿𝑇 (𝑖 )
Le chemin optimal est déterminé par un retour en arrière :
̂
𝑆𝑇 , 𝜓 𝑇−1 (𝑆̂𝑇 ), 𝜓 𝑇−2 (𝑆̂
𝑇−1 ),…

5.7 Traitement phonétique

Le traitement phonétique [2] concerne la production et la perception des sons. On
appelle phonème l’unité acoustique minimale qui peut être une voyelle ou une
consonne. La concaténation des phonèmes donne lieu aux syllabes qui construisent
les mots. La capture des sons se fait à l’aide d’un microphone ce qui produit des
signaux comme celui de la figure ci-dessous.

Figure 5.3 Un signal de la parole correspondant à “this is” [2].

En phonétique, on distingue deux types de traitements [2]:

Page | 95
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
 La synthèse vocale : ce traitement consiste à créer de la parole artificielle à
partir du texte.
 La reconnaissance de la parole : il s’agit d’analyser la voix humaine afin de la
transformer en texte exploitable par la machine.
Rapportons ici un exemple, pris de la référence [2], qui illustre le problème
d’ambiguïté qui peut survenir dans la reconnaissance de la parole. Notons qu’on
commence d’abord par la reconnaissance des phonèmes, des syllabes et ensuite des
mots.
Soit la phrase «The boys eat the sandwiches». Partons des mêmes phonèmes, un
système de reconnaissance vocale peut produire des résultats différents comme :
 The boy seat the sandwiches.
 The boy seat this and which is.
 The boys eat this and which is.
 The boys eat the sand which is…

5.8 Traitement morphologique

La morphologie [9] a pour objet l’étude des morphèmes et de leurs modes de
combinaison. Un morphème est l’unité linguistique minimale ayant un sens (un
morphème n’est donc pas forcément un mot). Voici des exemples de morphèmes:
Mot Morphème
Pomme de terre Pomme Pomme de terre
De
Terre
Livres Livres Livre
s (désignant le pluriel)

On distingue deux types de morphèmes [2,9]:

 Morphèmes lexicaux (dits aussi lexèmes): il s’agit des quatre catégories noms,
verbes, adjectifs et adverbes.
 Morphèmes grammaticaux: incluent les catégories des articles, des prépositions,
des conjonctions, des verbes auxiliaires. A cela s’ajoutent les morphèmes qui
caractérisent le genre et le nombre des noms, les temps de conjugaison et les
personnes des verbes.
Les mots dans une phrase peuvent être annotés par leurs catégories lexicales, voici
un exemple [2]:
Le gros chat mange la souris grise
article adjectif nom verbe article nom adjectif
On distingue habituellement deux modes de combinaison de morphèmes [9]:
 La composition : qui consiste à concaténer des morphèmes lexicaux comme
dans: chou-fleur, portemanteau, etc.
 L’affixation : il s’agit de la composition des mots en faisant interagir des
morphèmes lexicaux (les racines) et des morphèmes grammaticaux (les
affixes).
Pour les affixes, on peut discriminer [9]:

Page | 96
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
 Les affixes dérivationnels : comme les préfixes et les suffixes (en résultat en crée
de nouveaux mots)
 Les affixes flexionnels : la flexion est la variation d’un mot sous certaines
conditions grammaticales notamment le genre, le nombre, le temps, etc.
Alors, les affixes flexionnels sont les morphèmes qu’on ajoute pour exprimer
telle ou telle variation (en résultat, on ne crée pas de nouveaux mots).
Exemple
Mot Racine Préfixe dérivationnel Suffixe dérivationnel Suffixe flexionnel
intolérables tolér in able s
Les règles morphologiques permettent de générer toutes les formes de mots à
partir d'un lexique. Les analyseurs morphologiques font l'opération inverse et
récupèrent la racine du mot et ses différents affixes (dérivationnels ou flexionnels).
Les parseurs morphologiques utilisent généralement les automates à état fini [2].

5.8.1 Automates à état fini

L’automate est un modèle de l’informatique théorique qui permet de
représenter les découpages morphologiques sous la forme de règles. Cela permet de
prédire la forme des mots qui peuvent apparaitre dans une langue [9].
Un automate à état fini A est défini par 𝐴 =< 𝑄, 𝑉, 𝛿 > :
 Q est un ensemble fini d’états avec au moins un état initial et un état final.
 V est un vocabulaire fini. Dans notre contexte, il est constitué de l’ensemble
des morphèmes considérés.
 𝛿 est une fonction de transition définie depuis 𝑄 × 𝑉 vers Q.
Les automates finis reconnaissent ou engendrent selon le point de vue adopté
une classe particulière de langages appelée langages réguliers ou langages rationnels.
Tout langage régulier peut être exprimé sous la forme d’une ou de plusieurs
expressions régulières (et vice versa). Une expression régulière est une suite de
symboles construite à partir d’un alphabet Σ et de la chaîne vide ε, à l’aide des
opérations de concaténation (.) , de disjonction (|) et de la clôture de Kleen « * » .
L’avantage des automates finis et des expressions régulières vient de ce qu’ils
permettent de caractériser un nombre infini de mots différents à l’aide d’un nombre
fini d’éléments [9].
Exemple

L’automate ci-avant reconnait le langage défini par l’expression régulière suivante :

(in| 𝝐).(imit|analys).((é.( 𝝐 |e|s|es))|able(𝝐 |s))
L’implémentation de cet automate peut être faite via un programme Prolog comme
suit:

Page | 97
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

Cet automate peut être utilisé en génération en utilisant la

requête ? −𝑟𝑒𝑐𝑜𝑛𝑛𝑎𝑖𝑠𝑠𝑎𝑛𝑐𝑒(𝐿). (tous les mots possibles sont énumérés) ou en
reconnaissance (les mots appartenant au langage sont acceptés et les autres sont rejetés) en
utilisant une requête comme ? −𝑟𝑒𝑐𝑜𝑛𝑛𝑎𝑖𝑠𝑎𝑛𝑐𝑒([𝑖𝑛, 𝑎𝑛𝑎𝑙𝑦𝑠, é]).

5.8.2 Etiquetage morphosyntaxique avec l’algorithme de Viterbi

L’étiquetage morphosyntaxique consiste à faire associer à chaque mot sa
catégorie grammaticale. Dans le tableau ci-dessous, se trouve une projection du modèle
de Markov Caché sur cette application [2] :

Page | 98
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

MMC Application en étiquetage morphosyntaxique

S Ensemble des catégories morphosyntaxiques.
V Ensemble des mots (le vocabulaire).
O Une séquence de T mots observés qui prennent leurs valeurs dans V.
A Probabilités que deux catégories morphosyntaxiques se suivent.
B Probabilités d’observer un mot étant donnée une catégorie morphosyntaxique.
Π La probabilité de débuter par une catégorie morphosyntaxique.
Exemple d’application (Reformulé à partir de la référence [4]).
Donnons tout d’abord, la liste des catégories morphosyntaxiques utilisées dans cet
exemple :
Symbole Description
<𝒔> Début d’une phrase
VB Verb
NN Noun
TO infinitive marker
PPSS nominative pronoun (comme: I, they,we)
Le MMC est défini par les éléments suivants :
 𝑆 = {< 𝑠 >, 𝑉𝐵, 𝑇𝑂, 𝑁𝑁, 𝑃𝑃𝑆𝑆}
 𝑉 = {𝐼, 𝑡𝑜, 𝑤𝑎𝑛𝑡, 𝑟𝑎𝑐𝑒}
 𝑃 (𝑋1 = < 𝑠 >) = 1 (un seul état initial possible)
 La matrice A est définie comme suit :
VB TO NN PPSS
<𝒔> 0.019 0.0043 0.041 0.067
VB 0.0038 0.035 0.047 0.007
TO 0.83 0 0.00047 0
NN 0.004 0.016 0.087 0.0045
PPSS 0.23 0.00079 0.0012 0.00014
 La matrice B est définie comme suit :
𝑰 𝒘𝒂𝒏𝒕 𝒕𝒐 𝒓𝒂𝒄𝒆
VB 0 0.0093 0 0.00012
TO 0 0 0.99 0
NN 0 0.000054 0 0.00057
PPSS 0.37 0 0 0
NB. Les probabilités dans A et B sont calculées à base du corpus Brown.

Considérons la suite des mots observés : O = o1 , o2 , o3 , o4 , o5 =< s >, I , want, to , race.

Utiliser l’algorithme de Viterbi pour trouver la séquence d’états correspondante la
plus probable.
Initialisation
𝛿1 (< 𝑠 >) = 1 𝛿1 (𝑃𝑃𝑆𝑆) = 0 𝛿1 (𝑉𝐵) = 0 𝛿1 (𝑇𝑂) = 0 𝛿1 (𝑁𝑁) = 0
𝜓1 (< 𝑠 >) = 𝑁𝑢𝑙𝑙 𝜓1 (𝑃𝑃𝑆𝑆) = 𝑁𝑢𝑙𝑙 𝜓1 (𝑉𝐵) = 𝑁𝑢𝑙𝑙 𝜓1 (𝑇𝑂) = 𝑁𝑢𝑙𝑙 𝜓1 (𝑁𝑁) = 𝑁𝑢𝑙𝑙
Etape 2
𝛿𝑃𝑃𝑆𝑆 (𝐼) = 0.37 × 0.067 × 1 ≈ 0.025 𝑒𝑡 𝜓2 (𝑃𝑃𝑆𝑆) =< 𝑆 >
𝛿𝑉𝐵 (𝐼) = 0 × 0.019 × 1=0 et 𝜓2 (𝑉𝐵) =< 𝑆 >
𝛿𝑇𝑂 (𝐼) = 0 × 0.0034 × 1=0 et 𝜓2 (𝑇𝑂) =< 𝑆 >
( )
𝛿𝑁𝑁 𝐼 = 0 × 0.41 × 1=0 et 𝜓2 (𝑁𝑁 ) =< 𝑆 >

Page | 99
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
Etape 3
𝛿𝑉𝐵 (𝑤𝑎𝑛𝑡) = 0.0093 × max(𝟎. 𝟎𝟐𝟓 × 𝟎. 𝟐𝟑, 0 × 0.0038,0 × 0.83,0 × 0.004) ≈ 0.000053
et 𝜓3 (𝑉𝐵) = 𝑃𝑃𝑆𝑆
𝛿𝑁𝑁 (𝑤𝑎𝑛𝑡) = 0.000054 × max(𝟎. 𝟎𝟐𝟓 × 𝟎. 𝟎𝟎𝟏𝟐, 0 × 0.047,0 × 0.00047,0 × 0,0087)
= 0.162 × 10−8 𝑒𝑡 𝜓3 (𝑁𝑁 ) = 𝑃𝑃𝑆𝑆
𝛿𝑃𝑃𝑆𝑆 (𝑤𝑎𝑛𝑡) = 0 et 𝜓3 (𝑃𝑃𝑆𝑆) = 𝑃𝑃𝑆𝑆
𝛿𝑇𝑂 (𝑤𝑎𝑛𝑡) =0 et 𝜓3 (𝑇𝑂) = 𝑃𝑃𝑆𝑆
Etc.

5.9 Analyse syntaxique

Le niveau de la syntaxe explique comment mettre bout à bout des unités
lexicales afin de bâtir des énoncées dont le sens global est plus que la simple somme
des sens de ces unités [9]. Les travaux de Noam Chomsky, linguiste américain, sont
sans doute les plus influençant au niveau de la syntaxe.
La théorie de Chomsky [2] suggère que « la syntaxe est indépendante de la
sémantique et peut être exprimée en terme de grammaires formelles ». Ces grammaires
consistent en un ensemble de règles qui décrivent la structure d’une phrase dans un
langage. En outre, les règles peuvent générer la totalité des phrases (dont le nombre
peut être infini) d’un langage donné. Les grammaires nous permettent alors de mener
des opérations d’analyse syntaxique et de génération.

5.9.1 Grammaires formelles

Une grammaire formelle G est définie par le quadruplet < 𝑽, 𝑵, 𝑷, 𝑺 > tel que :
 V dénote le vocabulaire ou le lexique (ensemble des symboles terminaux).
 N dénote les symboles non-terminaux y compris le symbole initial S qui sert
de point de départ.
 P est l’ensemble des règles de production ou de réécriture.
Les grammaires que nous utilisons dans ce cours sont des grammaires hors contexte
(dites aussi d’ordre 2) dont les règles de production sont de la forme : 𝑋 → 𝛽 tel que 𝑋
est un symbole non terminal et 𝛽 est une séquence de symboles quelconques
(terminaux ou non).
Prenons l’exemple d’une grammaire décrivant un sous ensemble très limité de
l’anglais ou du français. Cette grammaire contient les règles suivantes [2]:
 Une phrase (S) consiste d’un groupe nominal (GN) et d’un groupe verbal (GV).
𝑆 → 𝐺𝑁 𝐺𝑉
 Un groupe nominal consiste d’un déterminant (Det) et d’un nom
𝐺𝑁 → 𝐷𝑒𝑡 𝑁𝑜𝑚
 Un groupe verbal consiste d’un verbe suivi d’un groupe nominal.
𝐺𝑉 → 𝑉𝑒𝑟𝑏𝑒 𝐺𝑁
Si on considère le lexique ou le vocabulaire composé des déterminants (le, la), des
noms (garçon, balle) et du verbe (frappe) alors on doit rajouter les règles :
𝐷𝑒𝑡 → 𝑙𝑒|𝑙𝑎
𝑁𝑜𝑚 → 𝑔𝑎𝑟ç𝑜𝑛 | 𝑏𝑎𝑙𝑙𝑒
𝑉𝑒𝑟𝑏𝑒 → 𝑓𝑟𝑎𝑝𝑝𝑒

Page | 100
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
A partir des règles précédentes, on peut générer les phrases suivantes qui sont toutes
syntaxiquement correctes (bien formées):
 La garçon frappe le balle
 La balle frappe le garçon
 Le garçon frappe la balle….
Cette grammaire nous permet aussi de construire un arbre d’analyse pour la
phrase « la balle frappe la balle » :
 Par une approche Top-down [3] (en commençant par les règles)

 Par une approche Bottom-up [3] (en commençant par les mots de la phrase)

Le formalisme syntaxique de Chomsky est basé sur le concept des syntagmes.

On appelle syntagme un groupe de mots ayant une signification et une même
fonction syntaxique. Pratiquement, un syntagme correspond à un sous arbre dans
l’arbre d’analyse syntaxique. Dans l’exemple précédent, « la balle » et « frappe la
balle » sont des syntagmes mais pas « la balle frappe».
L’ambiguïté syntaxique se manifeste principalement dans les scénarios suivants [9]:
 Une même succession de catégories grammaticales qui ne donne pas un
même arbre d’analyse. Par exemple :
L’élève met les cahiers sur la table.
Les enfants adorent les gâteaux avec du chocolat.
 Une même phrase ayant plusieurs interprétations peut être analysée
différemment. Par exemple :
L’homme observe l’enfant avec des jumelles.
L’analyse syntaxique n’est pas indépendante de l’analyse sémantique. En effet, pour
analyser correctement une phrase (surtout en cas d’ambiguïté) il faut revenir
absolument au sens désiré.

Page | 101
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

5.9.2 Grammaires à Clauses Définies en Prolog

La traduction des règles de grammaires à des règles DCG (Definite Clause
Grammars) est directe. Cette notation utilise l’opérateur −−> pour exprimer qu’un
syntagme peut être composé d’une séquence de syntagmes plus simples [2]. Une fois
le programme Prolog écrit en notation DCG est chargé en mémoire, il est
systématiquement traduit en clauses Prolog [3]. A savoir, une clause est une
affirmation inconditionnelle (i.e. fait) ou conditionnelle (i.e. règle).
Illustrons dans ce qui suit l’utilisation du Prolog en analyse syntaxique à
travers un exemple. Dans cet exemple, nous introduisons de nouveaux symboles
préposition (Prep), groupe prépositionnel (GP), verbe intransitif (Vintr) et verbe
transitif (Vtr). Soit la grammaire 𝐺 = < 𝑉, 𝑁, 𝑃, 𝑆 > , tel que :
𝑉 = {𝑙𝑒, 𝑙𝑎, 𝑠𝑒𝑟𝑣𝑒𝑢𝑟, 𝑐ℎ𝑎𝑡, 𝑝𝑙𝑎𝑡, 𝑡𝑎𝑏𝑙𝑒, 𝑑𝑜𝑟𝑡, 𝑚𝑒𝑡, 𝑠𝑢𝑟, 𝑠𝑜𝑢𝑠}
𝑁 = {𝑆, 𝐺𝑁, 𝐺𝑉, 𝐺𝑃, 𝐷𝑒𝑡, 𝑁𝑜𝑚, 𝑃𝑟𝑒𝑝, 𝑉𝑡𝑟, 𝑉𝑖𝑛𝑡𝑟}
P={ 𝑆 → 𝐺𝑁𝐺𝑉 , 𝐺𝑁 → 𝐷𝑒𝑡 𝑁𝑜𝑚 , 𝐺𝑁 → 𝐺𝑁 𝐺𝑃, 𝐺𝑃 → 𝑃𝑟𝑒𝑝 𝐺𝑁, 𝐺𝑉 → 𝑉𝑖𝑛𝑡𝑟,
𝐺𝑉 → 𝑉𝑖𝑛𝑡𝑟𝑛 𝐺𝑃, 𝐺𝑉 → 𝑉𝑡𝑟 𝐺𝑁 , 𝐷𝑒𝑡 → 𝑙𝑒|𝑙𝑎, 𝑁𝑜𝑚 → 𝑠𝑒𝑟𝑣𝑒𝑢𝑟|𝑐ℎ𝑎𝑡|𝑝𝑙𝑎𝑡|𝑡𝑎𝑏𝑙𝑒,
𝑃𝑟𝑒𝑝 → 𝑠𝑢𝑟|𝑠𝑜𝑢𝑠, 𝑉𝑖𝑛𝑡𝑟 → 𝑑𝑜𝑟𝑡, 𝑉𝑡𝑟 → 𝑚𝑒𝑡}
Le programme prolog, écrit en notation DCG, correspondant à cette déclaration est
montré dans la figure ci-dessous :

Remarque
Au fait, chaque non terminal définit un prédicat d’arité 2. Par exemple, la règle
s − −> gn, gv est équivalente à la clause suivante [2]:
𝑠(𝐿1, 𝐿) ∶ − 𝑔𝑛(𝐿1, 𝐿2), 𝑔𝑣(𝐿2, 𝐿).
Cette dernière est en réalité équivalente à [2]:
𝑠(𝐿) ∶ − 𝑔𝑛(𝐿1), 𝑔𝑣(𝐿2), 𝑎𝑝𝑝𝑒𝑛𝑑(𝐿1, 𝐿2, 𝐿).

L’interpréteur Prolog nous permet de chercher toutes les phrases bien formées
générées par cette grammaire en utilisant la syntaxe suivante :
?- s(L,[]).
L= [le, serveur, dort] ;
L= [le, chat, dort, sur, le, plat] ;
L= …
On peut tester la grammaticalité des phrases, comme dans les requêtes suivantes :

Page | 102
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

On peut consulter la trace du processus d’analyse mené par Prolog (qui utilise une
approche top-down). Voici un exemple :

A cause de la règle récursive à gauche : gn − −> gn, gp, une requête portant sur une
phrase syntaxiquement incorrecte entrainera une boucle infinie et donc un message
d’erreur sera affiché en réponse. Pour se débarrasser de la récursivité, on peut ajouter
un symbole auxiliaire [2] comme suit :
ngroupe − −> det, nom.
gn − −> ngroupe.
gn − −> ngroupe, gp.
Dans ce cas, Prolog échoue (renvoie false), comme le confirment les requêtes
suivantes :

Page | 103
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

5.10 Sémantique Lexicale

La sémantique lexicale est l'étude du sens des morphèmes d'une langue. Cette
définition est en réalité assez problématique puisque pour définir le "sens" d'un mot
on fait recours à d'autres mots (circularité du sens) [9]. La sémantique lexicale est très
importante pour les applications du TALN, comme en [10]:
 Traduction automatique : un même mot peut avoir différentes traductions.
Par exemple, le verbe « fuit » en français, selon le contexte doit être traduit
en arabe à « ‫ » يهرب‬ou «‫»يتسرب‬
 Recherche des documents : on peut éviter le silence en exploitant les
synonymes et éviter le bruit en se référant au contexte.
 Génération de texte pour choisir les bonnes collocations (une collocation est
une association habituelle d'un mot à un autre au sein d'une phrase). Par
exemple : il faut dire « réaliser un souhait » au lieu de « effectuer un
souhait », « tenir une promesse » au lieu de « satisfaire une promesse »,
etc.

5.10.1 Décomposition en primitives sémantiques

L'analyse sémique [9] est une des premières tentatives de décomposition du
sens d'un mot en unités de sens élémentaires : appelées sèmes. Un sème est un trait
sémantique minimal dont les seules valeurs possibles sont : positif (+), négatif (-) ou
sans objet (Ø). Un sémème est un faisceau de sèmes correspondant à une unité
lexicale.
Naturellement, les mots ayant des sèmes positifs communs appartiennent au
même champ sémantique. Pour illustrer cette idée, on s’inspire ici d’un exemple
classique d'analyse sémique dû à Bernard Pottier et qui porte sur les sièges. D’après
le dictionnaire Larousse un siège est un: « Meuble ou tout autre objet fait pour
s'asseoir ». En ce sens, fauteuil, tabouret et chaise sont des sièges comme le montre
les triangles sémiotiques ci-dessous :

Figure 5.4 Triangles sémiotiques pour fauteuil, tabouret et chaise.

Page | 104
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
On veut effectuer une analyse sémique pour ces mots. Dans cette fin, on se
donne les traits sémantiques :
 S1 : pour s’asseoir.
 S2 : pour une personne.
 S3 : avec dossier.
 S4 : avec bras.
Cela donne la matrice d’analyse suivante :
S1 S2 S3 S4
Fauteuil + + + +
Tabouret + + - -
Chaise + + + -

5.10.2 Polysémie et ambiguïté

Par polysémie, on désigne la pluralité du sens liée à un même sémème. C’est
la mise en contexte (ou encore en discours) qui permettra de lever l’ambiguïté qui
en découle. Pour expliquer cela, nous nous servons de l’analyse sémique du mot
canard proposé par Katz et Fodor [9] qu’ils ont présenté sous forme d'arborescence.

Figure 5.5 Analyse sémique du mot canard (schéma de Katz et Fodor) [9].

Montrons comment cette analyse sémique peut être exploitée dans la

désambiguïsation du mot canard dans la phrase suivante [9]:
« Il tenait le canard dans ses mains.... malheureusement le canard s’envola».
Le verbe tenir contraint son complément d’objet à avoir un trait matériel. Cela
permet d’éliminer la branche (non matériel). S’envola vérifie le trait animé alors
l’ambiguïté est levée : il s’agit d’un oiseau. Mais est-ce que cette analyse est
suffisante pour lever l’ambiguïté apparaissant dans une phrase comme : « Il continue
à lancer des canards » ?

5.10.3 Similarité entre mots d’après thésaurus

Parmi les relations sémantiques pouvant exister entre les mots, la synonymie est
la relation la plus étudiée puisque elle a plusieurs applications pratiques. La relation

Page | 105
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
de similarité est une version assouplie de la synonymie où on parle plutôt d’un degré
de similarité entre deux mots [4].
Le calcul de similarité des mots est utile pour de nombreuses applications du
TALN comme [4] : la recherche d'information, les systèmes questions-réponses, le
résumé automatique, la traduction automatique, etc. Dans les métriques basées sur
thésaurus, la distance entre deux mots est déterminée à partir d’un thesaurus
électronique comme WordNet généralement en exploitant la relation de
subsomption (est-un). Voici des exemples de ces métriques [4]:
 Similarité basée sur la longueur de chemin : Plus le chemin entre deux mots dans le
graphe défini par la hiérarchie du thésaurus est court, plus ils sont similaires.
Cette notion peut être opérationnalisée en mesurant le nombre d'arêtes entre les
deux mots dans le graphe thésaurus. Naturellement, la similarité est inversement
proportionnelle à la longueur du chemin. La définition la plus utilisée pour cette
métrique est la suivante (𝑚1 𝑒𝑡 𝑚2 sont des mots, L dénote la longueur de chemin):
𝑠𝑖𝑚𝑐ℎ𝑒𝑚𝑖𝑛 (𝑚1 , 𝑚2 ) = − log 𝐿(𝑚1 , 𝑚2 )
 Similarité de Resnik : l’intuition derrière cette métrique est que plus deux mots ont
de contenu sémantique en commun, plus ils sont similaires. Le contenu
sémantique d’un mot est défini comme le logarithme négatif de sa probabilité
d’apparition dans un corpus. Cette probabilité est estimée à base des occurrences
des mots subsumés par ce mot comme suit (N est le nombre total des mots dans le
corpus apparaissant également dans le thésaurus, mots(M) est l’ensemble des mots
subsumés par M) :
1 𝑠𝑖 𝑀 = 𝑅𝑎𝑐𝑖𝑛𝑒
∑
𝑃 (𝑀) = { 𝑚∈𝑚𝑜𝑡𝑠(𝑀) 𝑓𝑟é𝑞𝑢𝑒𝑛𝑐𝑒(𝑚)
𝑆𝑖𝑛𝑜𝑛
𝑁
Etant donnés deux concepts, leur facteur commun en quelque sorte coïncide avec
leur subsumant commun le plus spécifique (LCS : Lowest Common Subsumer).
D’après Resnik, la similarité entre deux mots est égale au contenu sémantique de
leur LCS comme le reflète la définition suivante:
𝑠𝑖𝑚𝑅𝑒𝑠𝑛𝑖𝑘 (𝑚1 , 𝑚2 ) = − log 𝑃(𝐿𝐶𝑆(𝑚1 , 𝑚2 ))
D’autres métriques qui sont conceptuellement proches à celle de Resnik sont les
suivantes [4]:
 Similarité de Lin :
2 log 𝑃(𝐿𝐶𝑆 (𝑚1 , 𝑚2 ))
𝑠𝑖𝑚𝐿𝑖𝑛 (𝑚1 , 𝑚2 ) =
log 𝑃 (𝑚1 ) + log 𝑃(𝑚2 )
 Similarité de Jiang-Conrath :
1
𝑠𝑖𝑚𝐽𝑐 (𝑚1 , 𝑚2 ) =
2 log 𝑃(𝐿𝐶𝑆 (𝑚1 , 𝑚2 )) − (log 𝑃 (𝑚1 ) + log 𝑃(𝑚2 ))
Exemple
Soit le fragment d’hiérarchie WordNet ci-dessous où à chaque mot M est attachée sa
probabilité d’apparition P(M) [4]:

Page | 106
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

Déterminer 𝐿(ℎ𝑖𝑙𝑙, 𝑛𝑎𝑡𝑢𝑟𝑎𝑙_𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛), 𝐿(ℎ𝑖𝑙𝑙, 𝑒𝑛𝑡𝑖𝑡𝑦) , 𝐿(ℎ𝑖𝑙𝑙, 𝑠ℎ𝑜𝑟𝑒), 𝐿(ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡).

Calculer la similarité entre les mots « ℎ𝑖𝑙𝑙 » et « 𝑐𝑜𝑎𝑠𝑡 » , en utilisant les métriques
déjà vues.
Réponse
𝐿(ℎ𝑖𝑙𝑙, 𝑛𝑎𝑡𝑢𝑟𝑎𝑙_𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛) = 1
𝐿(ℎ𝑖𝑙𝑙, 𝑒𝑛𝑡𝑖𝑡𝑦) = 5
𝐿(ℎ𝑖𝑙𝑙, 𝑠ℎ𝑜𝑟𝑒) = 3
𝐿(ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) = 4
𝑠𝑖𝑚𝑐ℎ𝑒𝑚𝑖𝑛 (ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) = − log 𝐿 (ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) = − log 4 ≈ −0.6
𝑠𝑖𝑚𝑅𝑒𝑠𝑛𝑖𝑘 (ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) = − log 𝑃(𝐿𝐶𝑆(ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡))
= −𝑙𝑜𝑔𝑃(𝑔𝑒𝑜𝑙𝑜𝑔𝑖𝑐𝑎𝑙 − 𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛) = −log(0.00176) ≈ 2.75
2 × log 𝑃(𝑔𝑒𝑜𝑙𝑜𝑔𝑖𝑐𝑎𝑙 − 𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛)
𝑠𝑖𝑚𝐿𝑖𝑛 (ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) =
log 𝑃 (ℎ𝑖𝑙𝑙 ) + log 𝑃(𝑐𝑜𝑎𝑠𝑡)
2 × log(0.00176)
= ≈ 0.59
log(0.0000189) + log (0.0000216)

1
𝑠𝑖𝑚𝐽𝑐 (ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡) =
2 × log 𝑃(𝑔𝑒𝑜𝑙𝑜𝑔𝑖𝑐𝑎𝑙 − 𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛) − (log 𝑃 (ℎ𝑖𝑙𝑙 ) + log 𝑃(𝑐𝑜𝑎𝑠𝑡))
1
= ≈ 0.26
2 × log 0.00176 − (log 0.0000189) + log(0.0000216))
( ) (

5.11 Conclusion
Le TALN est un des champs de l’IA les plus importants avec beaucoup
d’applications pratiques. De nos jours, nous utilisons fréquemment des moteurs de
recherche d’information, des traducteurs automatiques, des interfaces vocales, etc.
Même si nous nous ne sommes pas complètement satisfaits de la qualité de ces
applications, elles nous sont quand même d’une grande utilité.
A la fin de ce chapitre, l’étudiant doit réaliser la complexité du TALN mais il
doit comprendre également les sources d’imperfections enregistrées dans ses
applications même les plus contemporaines.

Page | 107
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN

Travail Pratique

NLTK3 (Natural Language Toolkit) est une plate-forme qui permet la création de
programmes Python de TALN. Elle fournit des interfaces à plusieurs corpus et
thésaurus ainsi qu'une suite de bibliothèques de traitement de texte pour la
tokenization, l’étiquetage, l’analyse, le raisonnement sémantique, etc.
Installation
1. Télécharger /Installer Python ([Link]
2. Télécharger /Installer NLTK ([Link]
Exploration du Corpus Brown
Importer le corpus Brown et faire lister les différentes catégories de textes qu’il
contient en utilisant la syntaxe suivante [11]:
>>> from [Link] import brown
>>> [Link]()

Maintenant, on veut par exemple collecter quelques statistiques sur la catégorie

«news». Nous nous intéressons au calcul de la fréquence des verbes modaux. Nous
utilisons particulièrement la fonction FreqDist (…) [11]:
>>> from [Link] import brown
>>> news_text = [Link](categories='news')
>>> fdist = [Link]([[Link]() for w in news_text])
>>> modals = ['can', 'could', 'may', 'might', 'must', 'will']
>>> for m in modals:
... print m + ':', fdist[m],

Dans le cours, nous avons mentionné que Brown est un corpus annoté. Nous voulons
savoir quelle est la fréquence de chaque étiquette morphosyntaxique appartenant à
L’Universal Part-of-Speech Tagset , toujours dans la catégorie news [11] :

Universal Part-of-Speech Tagset

3
[Link]

Page | 108
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
>>> from [Link] import brown
>>> brown_news_tagged = brown.tagged_words (categories='news',
tagset='universal')
>>> tag_fd = [Link](tag for (word, tag) in brown_news_tagged)
>>> tag_fd.most_common()
[('NOUN', 30640), ('VERB', 14399), ('ADP', 12355), ('.', 11928), ('DET', 11389),
('ADJ', 6706), ('ADV', 3349), ('CONJ', 2717), ('PRON', 2535), ('PRT', 2264),
('NUM', 2166), ('X', 106)]

Exploration du Thésaurus Wordnet

Importer Wordnet et chercher les synonymes des mots « entity » et « coast » :
>>>from [Link] import wordnet
>>>[Link]('entity’)
…?
>>> [Link](' coast’)
…?
Mesures de Similarité4
Nous allons refaire l’exemple déjà vu dans le cours concernant le calcul des
métriques de similarité entre mots :
 Déterminer la mesure de similarité basée sur les chemins entre les paires
(ℎ𝑖𝑙𝑙, 𝑛𝑎𝑡𝑢𝑟𝑎𝑙_𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛), (ℎ𝑖𝑙𝑙, 𝑒𝑛𝑡𝑖𝑡𝑦) , (ℎ𝑖𝑙𝑙, 𝑠ℎ𝑜𝑟𝑒), 𝐿(ℎ𝑖𝑙𝑙, 𝑐𝑜𝑎𝑠𝑡).
Pour ce faire exploiter: wordnet.path_similarity(…)
 Calculer la similarité entre « ℎ𝑖𝑙𝑙 » 𝑒𝑡 « 𝑐𝑜𝑎𝑠𝑡 » en utilisant les métriques de :
Resnik en utilisant wordnet.res_similarity(…)
Lin en utilisant wordnet.lin_similarity(…)
Jiang-Conrath en utilisant jcn_similarity(…)
Afin de pourvoir appliquer ces métriques, il faut d’abord collecter un contenu
informationnelle (ic), dans notre exemple, à base du corpus Brown. Pour ce faire, on
procède comme suit :
>>> from [Link] import wordnet_ic
>>> brown_ic = wordnet_ic.ic('[Link]')

4
[Link]

Page | 109
 Systèmes Intelligents
Chapitre 5 : Introduction au TALN
Références du chapitre

[1] F. Yvon, Une petite introduction au Traitement Automatique des Langues

Naturelles ([Link]
[2] P. Nugues, Introduction to Language Processing with Perl and Prolog: An Outline
of Theories, Implementation, and Application with Special Consideration of English,
French, and German, Springer, 2010.
[3] M. Covington, Natural language processing for Prolog programmers. Upper
Saddle River N.J.: Prentice Hall, 2002.
[4] D. Jurafsky and J. Martin, Speech and language processing: An introduction to
natural language processing, computational linguistics, and speech recognition.
[India]: Dorling Kindersley Pvt, Ltd., 2014.
[5] B. Bigi, Modélisation Statistique du Langage ([Link]
[Link]/~bigi/Doc/bigi2006_02_ML1.pdf)
[6] B. Bigi, Corpus ([Link]
[7] M. Scott, Programming Language Pragmatics (SECOND EDITION).Elsevier,
2006.
[8] S. Russell and P. Norvig, Intelligence artificielle. Paris: Pearson Education, 2010.
[9] I. Tellier , Introduction au TALN et à l’ingénierie
linguistique ([Link]
[Link])
[10] F. Gayral, Sémantique Lexicale pour le TAL, cours de l'option "Traitement
automatique des langues" en master 2eme année MICR, Institut Galilée -
Université Paris 13,2006.
[11] S. Bird, E. Klein and E. Loper, Natural language processing with Python. USA:
O’Reilly Media, 2009.

Page | 110
 Systèmes Intelligents

Annexe : Sujets des examens

Annexe : Sujets des Examens

Page | 111
 Systèmes Intelligents

Annexe : Sujets des examens

Examen des Systèmes Intelligents

Département d’Informatique, Master II IA
Année universitaire 2015/2016

Exercice 1 [3 points]
1. Le niveau cognitif de NEWELL est un niveau de description des connaissances
indépendant de toute représentation informatique. Une ontologie est codée en
OWL alors sa spécification ne se fait pas au niveau cognitif. Vrai ou faux ?
Argumenter !
2. Un agent implémentant un SLF de type TSK peut être vu comme un agent réactif.
L’architecture de type réactive vue dans le cours est celle de subsomption. Alors,
cet agent possède une architecture de subsomption. Vrai ou faux ? Argumenter !
3. Les morphèmes « Ontologie, Taxonomie, Vocabulaire, Thésaurus » appartiennent
au même champ sémantique. Mettre en évidence cet énoncé par une analyse
sémique: proposer au moins 4 sèmes différents tout en donnant une définition
claire pour chacun.

Exercice 2 [4 points]
Imaginons qu’on dispose de deux ontologies décrivant : « les Enseignants, les
Chercheurs ainsi que les Documents rédigés par ces derniers» :
 La première ontologie est construite selon le point de vue « tâche pédagogique»
(utilisée par exemple au sein du département) ; Voici son ABOX complète 1:
ABOX de la première ontologie
Enseignant (Omar) Enseignant (Ali) Enseignant (Sonia)
Enseignant (Lila) Enseignant (Dina)
Enseignant Vacataire () Chargé de cours (Ali) Chargé de TD (Lila)
Chargé de TP (Omar) Chargé de TP (Sonia) Chargé de TP (Dina)
Support de cours (doc3) Support de cours (doc4)
 La deuxième ontologie est construite selon le point de vue « grade scientifique»
(utilisée par exemple au sein du laboratoire de recherche) ; Voici son
ABOX complète 2 :

ABOX de la deuxième ontologie

Maitre-assistant classe A (Omar) Maitre-assistant classe A (Sonia)
Maitre de conférences (Lila) Professeur (Ali)
Enseignant-chercheur (Omar) Enseignant-chercheur (Ali)
Enseignant-chercheur (Sonia) Enseignant-chercheur (Lila)
Article de recherche (doc1) Article de recherche (doc2)

On veut fusionner les deux ontologies. Exprimer en LD la TBOX de l’ontologie

fusionnée (résultante) tout en donnant les justifications formelles adéquates.

12
Tous les individus sont mentionnés.

Page | 112
 Systèmes Intelligents

Annexe : Sujets des examens

Exercice 3 [5,5 points]

Considérons un contrôleur flou d’un ventilateur de maison qui fonctionne selon les
règles suivantes :
Si Température est Faible ou Humidité est Sec Alors Vitesse est Lente
Si Température est Moyenne et Humidité est Humide Alors Vitesse est Moyenne
Si Température est Elevée Alors Vitesse est Rapide

1. Déduire la spécification PEAS utilisée dans la conception de l’agent ventilateur

flou.
2. Faire le parallèle entre le modèle de l’agent ventilateur flou et le modèle formel
abstrait des agents : pour répondre à cette question déterminer à quoi
correspondent les ensembles S, A, P et les fonctions See et Action.
3. Refaire la question précédente pour le cas d’un SLF de type TSK quelconque.

Exercice 4 [6,5 points]

Imaginons un robot aspirateur qui fonctionne par des ordres vocaux. Ce robot est
capable d’éviter les obstacles et les vides. En outre, il est conscient de son niveau
d’énergie. Considérons que :
 Initialement, le robot est rangé dans sa base.
 Le robot reconnait et obéit les sons « Begin » et « End ».
 Le robot navigue dans une pièce tout en nettoyant jusqu’à ce que la saleté soit
définitivement éliminée.
 Le robot évite les obstacles en changeant de direction et évite les vides en
reculant.
 Le robot commence à se recharger une fois un niveau critique de sa batterie
est atteint.
 Le robot se range une fois sa tâche est terminée ou s’il reconnait « End ».
 Le robot se recharge et se range dans la même base.
1. Comment appelle-t-on Begin et End dans le vocabulaire du TALN ?
2. La sémantique de Begin et End est-elle vraiment acquise par le robot ? Expliquer !
3. Le choix d’une interface vocale pour la commande de l’agent est-il sans
inconvénient ?
4. En s’inspirant de l’architecture de subsomption, établir les règles susceptibles de
bien piloter notre robot aspirateur.
5. Exprimer en langue naturelle : une propriété de sûreté et une autre de vivacité (de
votre choix) que le robot doit vérifier.

Question Indépendante [1 point]

Donner une structure de Kripke qui satisfait la formule CTL : EF (p v q) (p et q sont
des formules logiques atomiques).

Page | 113
 Systèmes Intelligents

Annexe : Sujets des examens

Examen des Systèmes Intelligents

Département d’Informatique, Master II IA
Année universitaire 2016/2017

Exercice 1 [Logique Temporelle – 2 Pts]

Soit une maison à trois étages plus un rez-de-chaussée (le rez-de-chaussée
correspond à l’étage 0). A chaque étage, il y a une porte pour l’ascenseur. On définit
les propositions suivantes :
Oi : La porte de l’étage i est ouverte
Ei : L’ascenseur est à l’étage i
Formaliser en LTL les deux propriétés suivantes:
 L’ascenseur toujours fini par retourner à l’étage 0.
 Une porte ne s’ouvre que si l’ascenseur est derrière la porte.
Exercice 2 [TALN, Ontologie, Logique de Description – 9 Pts]
Soit le texte suivant: « Le mot domotique vient de domus qui signifie domicile et de
tique qui fait référence à la technique. La domotique est l'ensemble des techniques
permettant de centraliser le contrôle des différents sous-systèmes de la maison
(chauffage, porte de garage, portail d'entrée, etc.). La domotique vise à répondre aux
besoins de confort (gestion d'énergie, optimisation de l'éclairage et du chauffage), de
sécurité et de communication (commandes à distance, signaux visuels ou sonores,
etc.)»
1. Déterminer les morphèmes constituant les mots: domotique, sous-systèmes.
2. Sachant qu’un groupe nominal peut être formé d’un nom sans déterminant,
donner une grammaire permettant de dériver la phrase:
« tique fait référence à la technique »
3. Donner l’arbre syntaxique correspondant à la phrase précédente.
4. Donner la hiérarchie de concepts qu’on peut construire à partir de ce texte.
5. Formaliser en LD la partie de la hiérarchie extraite de la dernière phrase.
Exercice 3 [Agents Intelligents, Système TSK, Système de MAMDANI – 9 Pts]
Ahmed possède une maison intelligente. Imaginons l’agent « box-domotique » qui,
en fonction des informations obtenues via internet ou recueillies par les différents
capteurs disséminés à travers la maison, commande: la porte du garage, le robot
aspirateur et les stores.
I) L’agent contrôleur de l’ouverture de la porte du garage fonctionne selon les
règles suivantes:
Si Ahmed travaille et Ahmed est chez lui Alors ouvrir la porte du garage à 7H30.
Si Ahmed ne travaille pas et Ahmed est chez lui Alors ouvrir la porte du garage à
10H30.
Si Ahmed ne travaille pas et Ahmed est chez lui et c’est Vendredi Alors ouvrir la
porte du garage à 12H30.
1. Quel est le type de cet agent : réactif ou proactif ? Justifier votre réponse.
2. Donner la spécification PEAS correspondante à cet agent.
3. Donner la modélisation correspondante à cet agent (définir S, A, Action).

Page | 114
 Systèmes Intelligents

Annexe : Sujets des examens

II) Le robot aspirateur de Ahmed évite les obstacles en utilisant un système de

type TSK d’ordre 0 qui en fonction de la distance de l’obstacle ajuste l’angle
de rotation comme suit :
Si la distance est petite alors l’angle est -10°
Si la distance est moyenne alors l’angle est 0°
Si la distance est grande alors l’angle est +10°

Question. Calculer l’angle de

rotation si l’obstacle se trouve à
une distance de :
 6.5 cm
 9.5 cm
 11.5 cm

III) Dans la maison de Ahmed, la monté et la descente des stores est automatisée.
Tous les stores sont gérés par un système de type MAMDANI qui a deux
entrées : la température (°C) et l’éclairage (KLux) et comme sortie la hauteur
du store (cm).
Si Température est Froid et Eclairage est Faible Alors Store est Remonté
Si Température est Chaud et Eclairage est Faible Alors Store est Remonté
Si Température est Froid et Eclairage est Fort Alors Store est Mi-Hauteur
Si Température est Chaud et Eclairage est Fort Alors Store est Fermé

Question. Calculer la hauteur du store si :

 Température = 3 et Eclairage = 50
 Température = 22 et Eclairage = 66
 Température = 25 et Eclairage = 45

Une dernière Question. A la lumière des données précédentes, déduire la

spécification PEAS de l’agent « box-domotique».

Page | 115
 Systèmes Intelligents

Annexe : Sujets des examens

Examen des Systèmes Intelligents

Département d’Informatique, Master II IA
Année universitaire 2017/2018

Exercice 1 (4 points)
Cocher la bonne réponse :
1. Le Système expert MyCin ne peut pas être considéré comme un agent puisque :
 Il n’est pas rationnel
 Il n’interagit pas directement avec un environnement
 Il n’est pas intentionnel
2. « Désambiguïsation » est un :
 Phonème
 Morphème
 Mot
3. Une règle de grammaire permet d’exprimer que:
 Une phrase est composée de plusieurs morphèmes.
 Un syntagme est composé de plusieurs syntagmes plus simples.
 Aucune réponse n’est juste.
4. L’analyseur syntaxique écrit en Prolog vu dans le cours effectue une:
 Analyse Top-Down
 Analyse Bottom-up
5. La probabilité d’un mot calculée à partir d’un corpus est élevée quand:
 Il a moins de contenu sémantique
 Le nombre des occurrences de ses subsumant est petit
 Aucune réponse n’est juste.
6. La logique LTL permet d’exprimer :
 La précédence entre les évènements
 Le temps précis des évènements
 Les deux réponses sont correctes
7. La formule p doit être au moins une fois suivie par sa négation :
 𝐹(𝑝 ∧ 𝑋¬𝑝)
 𝑝𝑈¬𝑝
 𝑝𝑈𝑋¬𝑝
8. La formule p doit arriver une seule fois :
 ¬𝑝 𝑈 (𝑝 ∧ 𝑋𝐺¬𝑝)
 𝐹𝑝
 ¬𝐺¬𝑝

Exercice 2 (7 points)
1. Montrer par déduction naturelle que : ⊢𝐾𝑇45 □ ◊ □𝑝 → □𝑝
2. Exprimer en LTL et en CTL que: « Chaque requête finit par avoir une réponse ».
3. Cocher la/les bonne(s) réponse(s) :
Soit la structure de Kripke suivante ℳ :
 ℳ ⊢ 𝐴𝐹𝑎
 ℳ ⊢ 𝐴𝐹¬𝑎
 ℳ ⊢ 𝐸¬𝐹𝑎
 ℳ ⊢ 𝐸𝐹𝑎

Une structure de Kripke satisfait une formule LTL si tous les chemins initiaux
satisfont cette formule. Soit la structure ℳ ci-dessous :

Page | 116
 Systèmes Intelligents

Annexe : Sujets des examens

 ℳ ⊢ 𝐺𝑎
 ℳ ⊢ 𝑋(𝑎 ∧ 𝑏)

Exercice 3 (9 points)
Imaginons un moteur de recherche sémantique des images qui fonctionne en mode
recherche vocale. Ce moteur est doté d’une base de données d’images annotées
respectivement à une ontologie: les images joueront le rôle des individus.
L’ontologie est formalisée en Logique de Description comme suit :

C1 ⊑ 𝑇 C4 ⊑ 𝐶5
C2 ⊑ 𝐶1 C5 ⊑ 𝐶1
C3 ⊑ 𝐶1 C6 ⊑ 𝐶5
C3 ⊑⊥
C6 ⊑⊥ 𝐶1(𝑖𝑚𝑎𝑔𝑒1)
C4 ⊑⊥ 𝐶2(𝑖𝑚𝑎𝑔𝑒2)
C4 ⊑ 𝐶3 𝐶5(𝑖𝑚𝑎𝑔𝑒3)

Ce moteur de recherche exploite des mesures de similarité pour répondre à une

requête utilisateur. Pour simplifier, considérons que la requête consiste en un seul
mot. Les résultats d’une recherche sont organisés par ordre décroissant de pertinence.
1. Ce moteur de recherche peut être vu comme un agent intelligent: donner une
spécification PEAS adéquate.
2. Quels sont les traitements du TALN exploités dans ce moteur de recherche ?
3. Supposons que l’utilisateur cherche le concept C3. Donner les résultats renvoyés
suite à cette requête si la métrique basée sur la longueur de chemin est utilisée.
4. Même question si on cherche C6 et la métrique utilisée est celle de Resnik.
5. On veut vérifier si une image est déjà indexée par notre ontologie : quelle
procédure doit-on mener pour ce faire ?

Page | 117