32
1 CSI 4506: Introduction CSI 4506: Introduction à l’intelligence à l’intelligence artificielle artificielle Représentation et Logique III

1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

Embed Size (px)

Citation preview

Page 1: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

1

CSI 4506: Introduction CSI 4506: Introduction à à l’intelligence artificiellel’intelligence artificielle

Représentation et Logique III

Page 2: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

2

Partie IIIPartie III

Logique Non-Monotone et

représentation des connaissances de sens commun

Page 3: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

3

Plan du CoursPlan du CoursLa logique non-monotone

– Supposition de monde fermé– Raisonnement abductif et par défaut– Modèles minimaux

Systèmes de recherche par déduction– Chaînage en avant et en arrière– Reason Maintenance Systems

Représentation des connaissances de sens commun– Survol– Connaissances taxonomiques

Réseaux sémantiquesFrames

Page 4: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

4

La Logique non-monotone: La Logique non-monotone: SurvolSurvol

Définition: Une logique est monotone si, pour toute formule qui est un théorème dans une théorie formelle particulière, cette formule reste un théorème si la théorie originale est augmentée en y ajoutant des axiomes.

Définition: Dans la logique non-monotone, si une formule est un théorème dans une théorie formelle ne reste pas nécessairement un théorème lorsque cette théorie est augmentée: Nos croyances précédentes peuvent changer

Nous allons étudier 3 types d’inférences non-monotones:– La supposition du monde ferme– Le raisonnement abductif et par défaut– Les modèles minimaux

Page 5: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

5

La Logique non-monotone: La La Logique non-monotone: La supposition de monde fermésupposition de monde fermé

Dans les domaines du monde réels, les théories sont typiquement très touffues, et le plus souvent incomplètes

Exemple: Si vous voulez savoir si Fred travaille dans votre compagnie mais que vous ne pouvez pas trouver son dossier. C’est vrai que employee(Fred) n’est pas dan votre base de données, mais comme employee(Fred) n’y est pas non plus, vous ne pouvez rien prouver.

Solution: On peut compléter la théorie en ajoutant la négation de toutes les formules atomique sur terre (grounded) qui ne sont pas des théorèmes

Page 6: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

6

La logique non-monotone: La logique non-monotone: raisonnement par défautraisonnement par défaut

Raisonnement par Défaut: 1. Engineer(x)2. C(practical(x))3. Practical(x)C représente le pseudo-predicat

“Consistent” [Pseudo car on ne peut pas prouver des théorèmes de la forme C(a)]

R1

Page 7: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

7

La logique non-monotone: La logique non-monotone: raisonnement par défautraisonnement par défaut

Problèmes avec le raisonnement par défaut: Ajoutons 1. Scientist(x) 2. C(theoretical(x)) 3. Theoretical(x), Ainsi que la croyance: x theoretical(x) practical(x) Et, si Lynne est ingénieur et scientifique Problème! Si on applique R1 le premier, on conclura que Lynne est

pratique mais pas théorique. Si on applique R2 le premier, on tirera la conclusion opposée L’ordre a de l’importance (ce qui ne devrait pas arriver en logique non-monotone)

R2

Page 8: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

8

La Logique Non-Monotone: La Logique Non-Monotone: Raisonement AbductifRaisonement Abductif

Souvent utilise dans les systèmes de diagnostique

Exemple:1. gas(x) start(x)2. start(x)3. C(gas(x))4. gas(x)

Page 9: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

9

La logique non-monotone: La logique non-monotone: Modèles minimauxModèles minimaux

Exemple: x (bird(x) abnormal(x) flies(x)) Étant donne bird(Ralph), on ne peut pas toujours

prouver que flies(Ralph) car, dans certaines interprétations, Ralph peut être anormal.

Solution: On défini l’ensemble des interprétations minimalement anormales. i.e., on réduit le monde au monde des interprétations dans lesquelles Ralph va toujours être normal et, donc, va pouvoir voler.

(Voir illustration en classe)

Page 10: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

10

Systèmes de recherche par Systèmes de recherche par déduction: Survoldéduction: Survol

Définition: Un système de recherche par déduction est un système qui sauvegarde des connaissances sous la forme de règles et qui implante des procédures qui permettent de tirer des conclusions de ces connaissances (exemple: Les systèmes experts)

Page 11: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

11

Systèmes de recherche par Systèmes de recherche par déduction: Survoldéduction: Survol

Structure typique d’un tel système:– Base de données (DB) de faits et de règles– Procédures qui opèrent sur cette base de donnée:

Répondant à des questionsRéalisant quand certaines conclusions peuvent être tiréesÉtendant les faits et les règles lorsque de nouvelles

données sont ajoutéesNettoyant la base de données lorsque des données sont

retirées La base de données est plus qu’un répositoire passif pour faits et

règles

Page 12: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

12

Systèmes de recherche par Systèmes de recherche par déduction: Chaînage en avant déduction: Chaînage en avant

et chaînage en arrière (1)et chaînage en arrière (1) Dans les systèmes de recherche par déduction, les

inférences sont initiées lorsque l’utilisateur:– Ajoute des informations– Efface des informations– Pose des questions

Le chaînage en avant et en arrière sont des méthodes standards d’exécution de ces inférences.

Le chaînage en avant: If (P1 P2 … Pn) then A Exemple: If (son(x,y) son(y,z)) then add to DB

grandson(x,z)

Page 13: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

13

Systèmes de recherche par Systèmes de recherche par déduction: Chaînage en avant déduction: Chaînage en avant

et chaînage en arrière (2)et chaînage en arrière (2)

Q (P1 P2 … Pn) [Si vous voulez prouver Q, alors prouvez (P1 P2 … Pn)

Exemple: Preuve de théorèmes par réduction de but

L’unification est utilisée pour instancier les variables aussi bien dans le chaînage en avant que dans le chaînage en arrière

Page 14: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

14

Systèmes de recherche par Systèmes de recherche par déduction : Reason déduction : Reason

Maintenance Systems (1)Maintenance Systems (1) Veuillez supposer que Q est ajouté à la base de données

basé sur le fait que P et P Q sont tous les deux dans la base de données. Il serait utile d’avoir une méthode qui effacerait Q automatiquement si P était effacé C’est ce que font les Reason Maintenance Systems!!!

Les relations ente les formules sont représentées dans des graphes de dépendances entre des formules de justifications, de justificateurs et de justifies. Ces graphes sont vérifies à chaque fois qu’une opération modifie la base de donnée.

(Voir exemple en classe)

Page 15: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

15

Systèmes de recherche par Systèmes de recherche par déduction : Reason déduction : Reason

Maintenance Systems (2)Maintenance Systems (2) Algorithme pour la modification du graphe de dépendance Supposez que nous ayons juste ajoute ou efface une

justification du noeud n 1. Donnez a toutes les étiquettes des noeuds atteignables le

statut “visite” en appliquant la sous-routine récursive suivante: a} Si le noeud à déjà l’étiquette “visite”, retournez nil b} Si le noeud n’a pas l’étiquette “visite”, alors donnez-lui

cette étiquette et appliquez cette sous-routine récursivement. 2. Re-étiquetez tous les noeuds en appliquant la sous-routine

récursive suivante, en partant de n:

Page 16: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

16

Systèmes de recherche par Systèmes de recherche par déduction : Reason déduction : Reason

Maintenance Systems (3)Maintenance Systems (3) Algorithme pour la modification du graphe de dépendance a) Si le noeud a des justifications dont tous les justificateurs

sont IN, alors donnez l’étiquette IN au noeud; Sinon, donnez l’étiquette OUT au noeud.

B) Si l’étiquette du noeud a été changée à l’étape précédente, alors appliquez cette sous-routine récursivement à tous les justifiés du noeud.

(Voir exemple en Classe)

Page 17: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

17

Représentation des connaissances Représentation des connaissances de sens communde sens commun

Exemples: Si un objet vous échappe de la main, il tombera Le poissons vivent dans l’eau et meurent si on les en sort Les gens n’existent pas avant qu’ils soient nés Les gens achètent du pain et du lait dans les

supermarchés. etc… On n’a pas besoin d’équations compliquées ou d’autres

caractérisation théoriques Simplement du sens commun!

Page 18: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

18

Difficultés en représentation des Difficultés en représentation des connaissances de sens communconnaissances de sens commun

Beaucoup de connaissances de ce type sont nécessaire pour les tâches de tous les jours [beaucoup plus que pour les systèmes très spécialises tels que les systèmes experts]

Doug Lenat a essaye de construire une grande base de connaissances (le projet CYC). Il pensait qu’il avait besoin de un à dix millions de faits de sens commun (alors que les systèmes experts n’en utilisent qu’entre cent ou mille) A date, son projet n’a pas vraiment aboutit.

Les connaissances de sens commun ne sont pas bien compartimentalisées: elles sont toutes interdépendantes. De plus, ces connaissances sont de type diffus plutôt que bien définies (bruit vs musique)

Page 19: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

19

Difficultés en représentation des Difficultés en représentation des connaissances de sens communconnaissances de sens commun

Ces connaissances ne sont pas bien captures par de simples descriptions. Exemples: Est-ce que le visage de quelqu’un peut être décrit avec des mots de manière a ce qu’une personne ne l’ayant jamais vu peut le reconnaître? Comment utiliser des mots pour capturer un arbre, un paysage de montagne, un coucher de soleil tropical?

Les connaissance de sens commun sont souvent approximatives [Solution possible: L’utilisation de la théorie des probabilités]

Comment conceptualiser certains sujets? Exemple: Comment conceptualiser le monde de manière à ce que la phrase “Si je n’avais pas fait droit, je ne t’aurais pas rencontre” soit comprise?

Page 20: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

20

Difficultés en représentation des Difficultés en représentation des connaissances de sens commun (2)connaissances de sens commun (2) Beaucoup de connaissances de ce type sont nécessaire pour les tâches

de tous les jours [beaucoup plus que pour les systèmes très spécialises tels que les systèmes experts]

Doug Lenat à essaye de construire une grande base de connaissances (le projet CYC). Il pensait qu’il avait besoin de un a dix millions de faits de sens commun (alors que les systèmes experts n’en utilisent qu’entre cent ou mille) A date, son projet n’a pas vraiment aboutit.

Les connaissances de sens commun ne sont pas bien compartementalisées: elles sont toutes interdépendantes. De plus, ces connaissances sont de type diffus plutôt que bien définies (bruit vs musique)

Page 21: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

21

L’importance des connaissances de L’importance des connaissances de sens communsens commun

Nécessaire à la construction de robots domestiques (qui nettoient la maison, font la lessive et préparent et servent des repas)

Utile pour améliorer les systèmes experts (aussi appelés “savants idiots”):– Le système pourrait prédire quand ses connaissances

s’appliquent à la tâche et quand elles ne s’y appliquent pas– Une conceptualisation de sens commun de base lui

permettrait d’étendre ses connaissances avec peu d’augmentation ou de révisions

Requis pour la compréhension des langues naturelles

Page 22: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

22

Connaissance taxonomiquesConnaissance taxonomiques

Souvent, les connaissances peuvent être arrangées dans des structures hiérarchiques qui organisent et simplifient le raisonnement

(Voir Exemple en Classe) Les hiérarchies taxonomiques peuvent être

encodées ou bien:– Dans des réseaux appelés “réseaux

sémantiques”– Dans des structures de données appelées

“Frames”

Page 23: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

23

Connaissance taxonomiques: Connaissance taxonomiques: exemple de travailexemple de travail

Veuillez supposer que l’on cherche a représenter les faits suivants:– P222 est une imprimante au laser– Toutes les imprimantes au laser sont des

imprimantes– Toutes les imprimantes sont des machines– La source d’énergie de toutes les machines de

bureau est une prise électrique au mur.

Instance

Categories

Proprietes

Page 24: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

24

Connaissance taxonomiques: Connaissance taxonomiques: raisonnementraisonnement

Transitivité des catégoriesExemple: p222 est aussi une imprimante et

aussi une machineHéritage des propriétés de la super-

catégorie à la sous-catégorieExemple: Les imprimantes au laser utilisent

également une prise de courant au mur pour leur énergie.

Page 25: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

25

Connaissance taxonomiques: Connaissance taxonomiques: Réseaux sémantiquesRéseaux sémantiques

Un réseau sémantique est une structure de graphe qui encode les connaissances taxonomiques d’objets ainsi que leurs propriétés

Ils ont deux types de noeuds:– Les noeuds étiquettes par des constantes de relations (représentant

ou bien des catégories taxonomiques ou des propriétés)– Les noeuds étiquettes par des constantes d’objets (représentant les

objets du domaine)Ils ont trois types d’arcs connectant les noeuds:

– Les arcs sous-ensemble (aussi appelés liens isa)– Les arcs d’appartenance aux ensembles (aussi appelés liens

d’instances)– Les arc fonction (Voir Exemple en Classe)

Page 26: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

26

Connaissance taxonomiques: Connaissance taxonomiques: Raisonnement dans un Raisonnement dans un

réseau sémantiqueréseau sémantique Afin de déterminer si un objet, représente par un noeud A, est

membre d’un ensemble, représenté par un noeud B, il faut suivre tous les arcs allant de A vers le haut (arc isa et arcs d’instances) pour voir si on rencontre le noeud B. [Exemple R2D2 (voir exemple précèdent au tableau) est une machine de bureau]

Afin de déterminer la valeur de certaines propriétés d’un objet représente par le noeud A, on suit les arcs allant de A vers le haut (comme précédemment) jusqu’a ce que l’on trouve un noeud ayant cette propriété (arc de fonction). [Exemple: La source d’énergie pour p222 est: prise de courant au mur].

Page 27: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

27

Connaissances taxonomiques: Connaissances taxonomiques: Avantage des réseaux sémantiques Avantage des réseaux sémantiques

sur le calcul avec prédicatssur le calcul avec prédicats (Voir l’exemple exprimé en calcul avec prédicats

en classe) Avec le calcul avec prédicats, la transitivité et

l’héritage peuvent être déduits pour des objets, mais ces relations ne peuvent pas être établies entre des catégories

C’est inefficace puisque le même raisonnement doit être appliqué à chaque objet d’une même catégorie: pas de généralisation possible!

Page 28: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

28

Connaissances taxonomiques: Connaissances taxonomiques: raisonnement non-monotonique raisonnement non-monotonique dans les réseaux sémantiquesdans les réseaux sémantiques

Nous, êtres humains, faisons souvent des inférences par défaut: des inférences que nous voulons bien considérer comme vraies puisque nous n’avons pas les connaissances nécessaires pour les réfuter. Néanmoins, si nous acquérons de nouvelles connaissances contradictoires a celles que nous avons assumées par défaut, nous devons retracer notre inférence.

Avec les réseaux sémantiques, on approche ce problème en utilisant un mécanisme appelé: anullement de l’héritage

Exemple: On peut dire que, par défaut, la source d’énergie de machines de bureaux est une prise de courant au mur, mais que, par exception, la source d’énergie d’un robot est une pile. (Voir l’exemple en classe)

Page 29: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

29

Connaissances taxonomiques: Connaissances taxonomiques: Éviter la contradiction dans les Éviter la contradiction dans les

réseaux sémantiquesréseaux sémantiques On évite la contradiction en utilisant le réseau sémantique de la

sorte: l’information sur les catégories les plus spécifiques (ordonnées selon les arcs isa ou les arcs d’instances) prend précédence sur l’information concernant les catégories moins spécifiques

[E.g.: Quelle est la source d’énergie de R2D2? Une pile] L’information associée aux noeuds places plus haut dans la

hiérarchie taxonomique est de l’information générale, de l’information par défaut, qui peut être annulée par de l’information plus spécifique associée avec les noeuds places plus bas dans la hiérarchie.

Page 30: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

30

Connaissances Taxonomiques: Connaissances Taxonomiques: Problème d’héritage multipleProblème d’héritage multiple

Voir exemple en Classe

Dans les cas d’héritage multiple au même niveau de spécificité, il n’est pas possible de tirer de conclusions.

Page 31: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

31

Connaissances taxonomiques: Connaissances taxonomiques: FramesFrames

Lorsqu’il y a beaucoup de connaissances a enregistrer sur les objets ou les catégories d’une application, il vaut mieux représenter ces connaissances dans des “Frames”

Les Frames ont:– Un nom [Frame Name]– Des pairs Attribut-Valeur [Slots]

[<Slot Name>: <Slot-filler>] Correspondance avec les réseaux sémantiques:

– Frame Name Noeud– Slot-Name Nom des arcs associes au noeud– Slot-filler Noeud a l’autre bout des arcs

Page 32: 1 CSI 4506: Introduction à lintelligence artificielle Représentation et Logique III

32

Connaissances taxonomiques: Connaissances taxonomiques: Continuation de l’exemple Continuation de l’exemple

Imprimante:– Sous-ensemble de: Machine de bureau– Super-ensemble de: {Imprimantes au laser,

imprimantes à jet d’encre}– Source d’énergie: Prise de courant au mur

Frame Name, Slot-Names, Slot-Fillers