80
Système à base Système à base de connaissance de connaissance

Système à base de connaissance

  • Upload
    berny

  • View
    37

  • Download
    0

Embed Size (px)

DESCRIPTION

Système à base de connaissance. Système à base de connaissance. L’intelligence artificielle Définition IA. Artificiel. désigne ce qui n'est pas un produit de la nature. - PowerPoint PPT Presentation

Citation preview

Page 1: Système à base  de connaissance

Système à base Système à base de connaissancede connaissance

Page 2: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

L’intelligence artificielleL’intelligence artificielle– Définition IADéfinition IA

• L’IA est une discipline de l’informatique dont le but est que les ordinateurs puissent raisonner comme les humains.• Elle s’adresse à une classe de problèmes exponentiels.

• Intelligence. "Faculté de connaître, de comprendre et de s'adapter [...]". Jean-Pol Tassin (Pour la Science, Décembre 1998).• Produire une IA consisterait donc à utiliser une technique (informatique) pour concevoir un système capable de raisonnement (résoudre un problème, s'adapter à des situations nouvelles,...).

• Artificiel. désigne ce qui n'est pas un produit de la nature.

Page 3: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

L’intelligence artificielleL’intelligence artificielle– Exemple du jeu d’échecExemple du jeu d’échec

La programmation classique utilise l'algorithmique pour calculer et La programmation classique utilise l'algorithmique pour calculer et analyser tous les coups possibles à chaque étape du jeu.analyser tous les coups possibles à chaque étape du jeu.

L‘IA, quant à elle, introduit une nouvelle vision du jeu :L‘IA, quant à elle, introduit une nouvelle vision du jeu :

– chaque coup joué fait maintenant partie d'une tactique qui chaque coup joué fait maintenant partie d'une tactique qui consiste à réaliser un objectif : la victoire. consiste à réaliser un objectif : la victoire.

– L'IA a donc une vision globale du jeu, élabore des stratégies, L'IA a donc une vision globale du jeu, élabore des stratégies, s'adapte aux coups joués par l'adversaire, etc. s'adapte aux coups joués par l'adversaire, etc.

– L’IAL’IA L'IA est une conception différente de la résolution de problèmes.L'IA est une conception différente de la résolution de problèmes. D'après JL. Laurière, D'après JL. Laurière, "Tout problème pour lequel aucune "Tout problème pour lequel aucune

solution algorithmique n'est connue relève a priori de l'IA".solution algorithmique n'est connue relève a priori de l'IA".

Page 4: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

L’intelligence artificielleL’intelligence artificielle– Reprenons la phrase de Marvin Minsky, figure Reprenons la phrase de Marvin Minsky, figure

célèbre de l'IA des années 50 : célèbre de l'IA des années 50 : "[...] the science of making machines do things that "[...] the science of making machines do things that

would require intelligence if done by humans". would require intelligence if done by humans". L'IA est la branche de l'informatique qui consiste L'IA est la branche de l'informatique qui consiste

à concevoir des systèmes intelligents, c'est-à-à concevoir des systèmes intelligents, c'est-à-dire qui soient capables de produire un dire qui soient capables de produire un raisonnement proche de celui de l'être humain.raisonnement proche de celui de l'être humain.

Page 5: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Débuts de l’IADébuts de l’IA– 19501950 : le mathématicien britannique  : le mathématicien britannique Alan TuringAlan Turing publie, dans le journal publie, dans le journal

philosophique philosophique MindMind, un article intitulé , un article intitulé Computing Machinery and Computing Machinery and IntelligenceIntelligence. Dans cet article, il décrit le . Dans cet article, il décrit le test de Turingtest de Turing..

– 1955 - 19561955 - 1956 : Allen  : Allen NewellNewell, John , John ShawShaw, et Herbert , et Herbert SimonSimon créent le créent le ""Logic TheoristLogic Theorist", considéré comme le premier programme d'IA.", considéré comme le premier programme d'IA.

– 19561956 :  : John McCarthyJohn McCarthy, considéré comme le père de l'IA, organise "The , considéré comme le père de l'IA, organise "The Dartmouth summer research project on Artificial Intelligence".Dartmouth summer research project on Artificial Intelligence".

– 19591959 : élaboration du  : élaboration du GPRGPR (General Problem Resolver), qui consiste à (General Problem Resolver), qui consiste à définir un état initial, un ou plusieurs états finaux, et des opérateurs de définir un état initial, un ou plusieurs états finaux, et des opérateurs de transition entre les états. transition entre les états.

Page 6: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Débuts de l’IADébuts de l’IA– 19671967 : Echec et abandon du GPR : Echec et abandon du GPR– 19721972 : Hubert : Hubert DreyfusDreyfus, un des détracteurs de l’IA, écrit , un des détracteurs de l’IA, écrit

""What Computers Can't DoWhat Computers Can't Do" dénonçant les sommes " dénonçant les sommes importantes dépensées par le gouvernement US pour le importantes dépensées par le gouvernement US pour le développement de l'IA. développement de l'IA.

– Problèmes des premiers systèmes en IA :Problèmes des premiers systèmes en IA : incapacité à imiter la capacité de l'homme à utiliser le incapacité à imiter la capacité de l'homme à utiliser le

contexte d'un problème pour déterminer le sens des mots contexte d'un problème pour déterminer le sens des mots et des phraseset des phrases. .

Page 7: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Débuts de l’IADébuts de l’IA– Années 70Années 70 : de nombreuses nouvelles méthodes de : de nombreuses nouvelles méthodes de

développement de l'IA sont testées. En 1971, le langage développement de l'IA sont testées. En 1971, le langage PROLOGPROLOG est créé par Colmerauer. est créé par Colmerauer.

– 19741974 : verra l‘arriver des premiers : verra l‘arriver des premiers systèmes expertssystèmes experts.. dont le plus célèbre dont le plus célèbre MYCIN MYCIN (Edward H. Shortliffe), conçu pour (Edward H. Shortliffe), conçu pour

l'aide au diagnostic et au traitement de maladies bactériennes l'aide au diagnostic et au traitement de maladies bactériennes du sang. En 1979, Mycin sera considéré par le "Journal of du sang. En 1979, Mycin sera considéré par le "Journal of American Medical Assoc" comme aussi bon que les experts American Medical Assoc" comme aussi bon que les experts médicaux.médicaux.

La même année, le premier robot piloté par ordinateur est La même année, le premier robot piloté par ordinateur est conçu. conçu.

On notera également dans les années 70, l'abandon des On notera également dans les années 70, l'abandon des subventions versées par les gouvernements (US pour la subventions versées par les gouvernements (US pour la plupart) pour quelques programmes de recherche en IA. plupart) pour quelques programmes de recherche en IA.

Page 8: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Débuts de l’IADébuts de l’IA– 1980-1990 1980-1990 : Accélération du mouvement.: Accélération du mouvement.

Avec l'efficacité prouvée des systèmes experts, les Avec l'efficacité prouvée des systèmes experts, les ventes de matériels IA (hardware ou logiciel) grimpent ventes de matériels IA (hardware ou logiciel) grimpent en flèche. en flèche.

L'IA commence à intéresser les grandes firmes L'IA commence à intéresser les grandes firmes (Boeing, General Motors, etc). (Boeing, General Motors, etc).

Face aux détracteurs, les "pro-IA" se défendent : en Face aux détracteurs, les "pro-IA" se défendent : en 1982, Minsky écrit "1982, Minsky écrit "Why People Think Computers Why People Think Computers Can'tCan't", en réponse notamment aux critiques de ", en réponse notamment aux critiques de Dreyfus.Dreyfus.

Page 9: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Les systèmes expertsLes systèmes experts

Page 10: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Les systèmes expertsLes systèmes experts– Un Un système expertsystème expert est un outil capable de est un outil capable de

reproduire les mécanismes cognitifs d'un reproduire les mécanismes cognitifs d'un expert, dans un domaine particulier.expert, dans un domaine particulier.

– Plus précisément, un système expert est un Plus précisément, un système expert est un logiciel capable de répondre à des questions, logiciel capable de répondre à des questions, en effectuant un raisonnement à partir de faits en effectuant un raisonnement à partir de faits et de règles connus.et de règles connus. Il peut servir notamment comme outil d’aide à la Il peut servir notamment comme outil d’aide à la

décision.décision.

Page 11: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Les systèmes expertsLes systèmes experts– Un système expert se compose de 3 parties : Un système expert se compose de 3 parties : 

une base de faits ; une base de faits ; une base de règles ;une base de règles ; Un moteur d’inférence : Un moteur d’inférence :

– Le moteur d'inférence est capable d'utiliser faits et règles Le moteur d'inférence est capable d'utiliser faits et règles pour produire de nouveaux faits, jusqu'à parvenir à la pour produire de nouveaux faits, jusqu'à parvenir à la réponse à la question experte posée.réponse à la question experte posée.

Page 12: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Les systèmes expertsLes systèmes experts

Page 13: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Mécanismes de raisonnementMécanismes de raisonnement– La plupart des systèmes experts existants reposent sur des mécanismes La plupart des systèmes experts existants reposent sur des mécanismes

de logique formelle (logique aristotélicienne) et utilisent le raisonnement de logique formelle (logique aristotélicienne) et utilisent le raisonnement déductif.déductif.

– Pour l'essentiel, ils utilisent le syllogisme :Pour l'essentiel, ils utilisent le syllogisme :si P est vrai (si P est vrai (faitfait ou ou prémisseprémisse) et si on sait que P ) et si on sait que P Q Q (règle)(règle)alors, Q est vrai (alors, Q est vrai (nouveau faitnouveau fait ou ou conclusionconclusion). ).

– Les plus simples des systèmes experts s'appuient sur la logique des Les plus simples des systèmes experts s'appuient sur la logique des proposition (dite aussi « proposition (dite aussi « logique d'ordre 0logique d'ordre 0 »). »). Dans cette logique, on n'utilise que des propositions, qui sont vraies, Dans cette logique, on n'utilise que des propositions, qui sont vraies,

ou fausses. ou fausses.

– D'autres systèmes s'appuient sur la logique des prédicats du premier D'autres systèmes s'appuient sur la logique des prédicats du premier ordre (dite aussi « ordre (dite aussi « logique d'ordre 1logique d'ordre 1 »), que des algorithmes permettent de  »), que des algorithmes permettent de manipuler aisément.manipuler aisément.

Page 14: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

HistoriqueHistorique– Les premiers systèmes experts voient le jour aux USA dans les Les premiers systèmes experts voient le jour aux USA dans les

années 1970. années 1970. – MYCINMYCIN, qui manipulait de l'expertise dans le domaine médical, est , qui manipulait de l'expertise dans le domaine médical, est

l'un des plus connus.l'un des plus connus. Dans les années 1970, une équipe de Stanford University, sous Dans les années 1970, une équipe de Stanford University, sous

la direction d'Ed Feigenbaum, a fait l’hypothèse que la direction d'Ed Feigenbaum, a fait l’hypothèse que l’intelligence repose sur le stockage des grandes quantités de l’intelligence repose sur le stockage des grandes quantités de connaissance.connaissance.

Connaissances représentées sous forme de règles.Connaissances représentées sous forme de règles. En 1973, ils ont cherché un nouveau domaine pour refaire une En 1973, ils ont cherché un nouveau domaine pour refaire une

étude. Ils ont retenu le domaine de “Thérapie Anti-Biotique”.étude. Ils ont retenu le domaine de “Thérapie Anti-Biotique”. Résultat = MYCIN (500 règles avec des faits fortement typés).Résultat = MYCIN (500 règles avec des faits fortement typés).

Page 15: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

MYCINMYCIN– Qu’est-ce que c’est?Qu’est-ce que c’est?

C’est un "programme de consultation" qui donne des avis aux médecins C’est un "programme de consultation" qui donne des avis aux médecins concernant les thérapies anti-microbiennes.concernant les thérapies anti-microbiennes.

– DomaineDomaine anti-microbien ou antibiotiqueanti-microbien ou antibiotique

– PrincipePrincipe Il existe un grand choix de médicaments anti-microbiens ainsi qu'un Il existe un grand choix de médicaments anti-microbiens ainsi qu'un

grand nombre de microbes.grand nombre de microbes. Chaque antibiotique agit différemment avec chaque microbe.Chaque antibiotique agit différemment avec chaque microbe. À cause de cette grande variété, seuls certains médecins spécialisés À cause de cette grande variété, seuls certains médecins spécialisés

connaissent bien ce domaine.connaissent bien ce domaine.

Page 16: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

MYCINMYCIN– La séquence de tâchesLa séquence de tâches

1) Demande des informations sur le cas.1) Demande des informations sur le cas.

2) Applique ses connaissances.2) Applique ses connaissances.

3) Donne son jugement et conseille.3) Donne son jugement et conseille.

4) Répond aux questions sur son raisonnement.4) Répond aux questions sur son raisonnement.– Buts à atteindreButs à atteindre

Facile à utiliserFacile à utiliser FiableFiable Manipule un grand nombre de connaissancesManipule un grand nombre de connaissances Utilise des renseignements inexacts ou incompletsUtilise des renseignements inexacts ou incomplets Explique et justifie ses conseilsExplique et justifie ses conseils

Page 17: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

MYCINMYCIN– Répond à 4 questionsRépond à 4 questions

1) Quelles infections importantes existent ?1) Quelles infections importantes existent ?

2) Quel microbe est la cause de chaque infection ?2) Quel microbe est la cause de chaque infection ?

3) Quels médicaments sont efficaces ?3) Quels médicaments sont efficaces ?

4) Quel est le meilleur traitement ?4) Quel est le meilleur traitement ?

– A tout instant, l'utilisateur peut demander :A tout instant, l'utilisateur peut demander : Pourquoi ? Pourquoi ?

– Trace de la chaîne de raisonnement en cours.Trace de la chaîne de raisonnement en cours.

Comment ?Comment ?– Trace la source d'un fait.Trace la source d'un fait.

Page 18: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement dans MYCINRaisonnement dans MYCIN– Chaînage arrière, dirigé par un butChaînage arrière, dirigé par un but– Règles sous forme d’abductionRègles sous forme d’abduction

A A B B C C Pour prouver C, il faut Pour prouver C, il faut

prouver A et B.prouver A et B.

11

8

910

7

Infection streptocoque de la gorge ?

Infection streptocoque de la gorge ?

Signes d’infection de la gorge

Signes d’infection de la gorge

Organisme = streptocoque

Organisme = streptocoque

Gorge rougeGorge rouge

Tâche en Grampos

Tâche en Grampos

Morphologie coccidie

Morphologie coccidie

Croissance en chaîne

Croissance en chaîne

1

2

3

4 5

6

12

Page 19: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement dans MYCINRaisonnement dans MYCIN– La base de connaissance statique comporte des règles :La base de connaissance statique comporte des règles :

– On dispose donc d’un ensemble de règles (ici, déduction), On dispose donc d’un ensemble de règles (ici, déduction), approximatives.approximatives.

Page 20: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Les inférencesLes inférences

– Moteur d'inférenceMoteur d'inférence : déduit des faits à partir de faits initiaux et : déduit des faits à partir de faits initiaux et des règles.des règles.

– Deux approches de base :Deux approches de base : A partir de ce qu'on veut trouver et remonter vers les faits A partir de ce qu'on veut trouver et remonter vers les faits

(chaînage arrière) ;(chaînage arrière) ; A partir des faits et aller vers ce qu'on veut trouver A partir des faits et aller vers ce qu'on veut trouver

(chaînage avant).(chaînage avant).

– La structure classique des systèmes experts utilisaient La structure classique des systèmes experts utilisaient toujours un ensemble de toujours un ensemble de règles de productionrègles de production..

Page 21: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Evaluation de MYCINEvaluation de MYCIN– En 1979 : MYCIN en compétition face à 8 médecins sur 10 En 1979 : MYCIN en compétition face à 8 médecins sur 10

cas réel, MYCIN arrive premier.cas réel, MYCIN arrive premier.– Limites de MYCINLimites de MYCIN

Peu de flexibilité (adapté à un problème précis) ;Peu de flexibilité (adapté à un problème précis) ; Connaissances difficiles à entrer :Connaissances difficiles à entrer :

– beaucoup de règles ;beaucoup de règles ;– dépendantes du système d'inférence.dépendantes du système d'inférence.

Manque d'explications sur le résultat.Manque d'explications sur le résultat.

– MYCIN était un programme de recherche et n'a jamais été MYCIN était un programme de recherche et n'a jamais été réellement utilisé à l'hôpital, car :réellement utilisé à l'hôpital, car : incomplet, difficile à évaluer, mauvaise interface... incomplet, difficile à évaluer, mauvaise interface... Mais il a montré qu'on peut approcher un domaine d'expertise.Mais il a montré qu'on peut approcher un domaine d'expertise.

Page 22: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Systèmes à base de connaissanceSystèmes à base de connaissance

Page 23: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Qu’est-ce qu’un SBC ?Qu’est-ce qu’un SBC ?– Un programme construit pour :Un programme construit pour :

modéliser les compétences de résolution de modéliser les compétences de résolution de problèmes des humains.problèmes des humains.

avoir la même performance que les humains (avoir la même performance que les humains (Test de Test de TuringTuring).).

Human interrogator

Human

Page 24: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

SE vs. SBCSE vs. SBC– Système expert (SE) : Système informatique permettant Système expert (SE) : Système informatique permettant

de résoudre les problèmes dans un domaine de résoudre les problèmes dans un domaine d'application déterminé à l'aide d'une base de d'application déterminé à l'aide d'une base de connaissances établie à partir de l'expertise humaine.connaissances établie à partir de l'expertise humaine.

– Système à base de connaissances (SBC) : Système Système à base de connaissances (SBC) : Système informatique fonctionnant avec une base de informatique fonctionnant avec une base de connaissances sur un sujet donné.connaissances sur un sujet donné.

Page 25: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

SE vs. SBCSE vs. SBC– Les systèmes experts classiques seraient un Les systèmes experts classiques seraient un

cas particuliers des systèmes à base de cas particuliers des systèmes à base de connaissances.connaissances.

– Tout système informatique utilise de la Tout système informatique utilise de la connaissance, mais dans un système à base de connaissance, mais dans un système à base de connaissances, celle-ci est représentée de connaissances, celle-ci est représentée de façon explicite.façon explicite.

Page 26: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

ConnaissanceConnaissance– Différence entre donnée, information, connaissance :Différence entre donnée, information, connaissance :

• Une donnée transporte l'information. Ce sont des signaux non interprétés. Exemple. ! ...- - -... C

• L’information est une interprétation de la donnée.Exemple. (!, point d’exclamation), (...- - -..., SOS), (C, lettre) ou (C, note)

• La connaissance utilise l'information dans le cadre d'actions, dans un but précis. Les actions peuvent être la prise de décisions, la création de nouvelles informations, etc.Exemple.• écrire un “!” pour marquer une exclamation en fin de phrase• si le signal ...- - -... reçu alors déclencher l’alerte et envoyer des secours• si C apparaît sur une partition alors la référence est la gamme de Do, jouer dans la gamme associée.

Page 27: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Tâches utilisant des connaissancesTâches utilisant des connaissances– Classement issu de la Classement issu de la méthodologie CommonKADSméthodologie CommonKADS : :

Tâches d'analyseTâches d'analyse– classification, diagnostique, évaluation, supervision, classification, diagnostique, évaluation, supervision,

prédiction.prédiction. Tâches de synthèseTâches de synthèse

– conception/configuration, modélisation, planification, conception/configuration, modélisation, planification, ordonnancement, répartition.ordonnancement, répartition.

– Ce classement se veut relativement exhaustif des différentes Ce classement se veut relativement exhaustif des différentes tâches demandant de la connaissance.tâches demandant de la connaissance.

Page 28: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Types de problèmes résolus par les SBCTypes de problèmes résolus par les SBC– ContrôleContrôle– ConceptionConception– DiagnosticDiagnostic– InstructionInstruction– InterprétationInterprétation– MonitoringMonitoring– PlanificationPlanification– PrédictionPrédiction– PrescriptionPrescription– SélectionSélection– SimulationSimulation

0

5

10

15

20

25

30

Contrôle Instruction Planification Sélection

% applications

Page 29: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Pourquoi utiliser un SBC ?Pourquoi utiliser un SBC ?– Remplacer un expertRemplacer un expert

Automatiser une tâche routinière nécessitant un expert ;Automatiser une tâche routinière nécessitant un expert ; Un expert quitte la compagnie ;Un expert quitte la compagnie ; Besoin d’une expertise dans un environnement hostileBesoin d’une expertise dans un environnement hostile

– Assister un expertAssister un expert Améliorer la productivité ;Améliorer la productivité ; Gérer la complexité Gérer la complexité

Page 30: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Utilisation des SBCUtilisation des SBC– AgricultureAgriculture– AffairesAffaires– ChimieChimie– CommunicationsCommunications– InformatiqueInformatique– ÉducationÉducation– ÉlectroniqueÉlectronique– IngénierieIngénierie– GéologieGéologie– Domaine juridiqueDomaine juridique

Manufacture Mathématiques Médecine Météorologie Militaire Prospection et exploitation minière Production d’énergie Hydrologie / hydroélectricité Espace

Page 31: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Exemple de problèmesExemple de problèmes

Le problème des seaux à remplirLe problème des seaux à remplir– On dispose de deux seaux, l’un de trois litres et l’autre de 4 litres.On dispose de deux seaux, l’un de trois litres et l’autre de 4 litres.– Comment mesurer 2 litres dans le seau de 4 litres ?Comment mesurer 2 litres dans le seau de 4 litres ?

– Variante :Variante : Une personne a une bonbonne de douze litres de vin ; elle veut en Une personne a une bonbonne de douze litres de vin ; elle veut en

donner 6 litres à un ami. Pour les mesurer, elle n’a que deux autres donner 6 litres à un ami. Pour les mesurer, elle n’a que deux autres bouteilles, l’une contenant 7 litres et l’autre contenant 5 litres. Comment bouteilles, l’une contenant 7 litres et l’autre contenant 5 litres. Comment doit-elle opérer pour avoir les 6 litres dans la bonbonne de 7 litres ? doit-elle opérer pour avoir les 6 litres dans la bonbonne de 7 litres ?

3 litres 4 litres2

litres

Page 32: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Exemple de problèmesExemple de problèmes

Le problème du taquinLe problème du taquin– Trouver la séquence de déplacements la plus courte qui Trouver la séquence de déplacements la plus courte qui

permet de passer de l’état initial à l’état final.permet de passer de l’état initial à l’état final.

11 22 33

88 ** 44

77 66 55

22 88 33

11 66 44

77 ** 55

Page 33: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Exemple de problèmesExemple de problèmes

Un problème de crypto-arithmétiqueUn problème de crypto-arithmétique– Une lettre correspond à un nombre (entre 0 et 9) et un Une lettre correspond à un nombre (entre 0 et 9) et un

seul, décrypter l’addition.seul, décrypter l’addition. S E N D

M O R E

M O N E Y

Page 34: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Exemple de problèmesExemple de problèmes

Un problème logiqueUn problème logique– Bernard, Jacques et Sylvain sont prévenus de fraude Bernard, Jacques et Sylvain sont prévenus de fraude

fiscale et déclarent :fiscale et déclarent : BernardBernard : «  : « Jacques est coupable et Sylvain est innocent ».Jacques est coupable et Sylvain est innocent ». JacquesJacques : «  : « Si Bernard est coupable alors Sylvain est Si Bernard est coupable alors Sylvain est

coupable »coupable »..

SylvainSylvain : «  : « Je suis innocent mais au moins un des deux Je suis innocent mais au moins un des deux autres est coupable »autres est coupable »..

– Qui est coupable ?Qui est coupable ?

Page 35: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Exemple de problèmesExemple de problèmes

Un problème de contrainteUn problème de contrainte– Patrick, Antoine et Émilie sont musiciens ; il y a un Patrick, Antoine et Émilie sont musiciens ; il y a un

saxophoniste, un guitariste, et un violoniste :saxophoniste, un guitariste, et un violoniste : Une personne a peur du chiffre 13, une autre des chats, et une Une personne a peur du chiffre 13, une autre des chats, et une

autre a le vertige.autre a le vertige. Patrick et le guitariste font de la montagne ; Patrick et le guitariste font de la montagne ; Antoine et le saxophoniste aiment les chats ;Antoine et le saxophoniste aiment les chats ; Le violoniste habite l’appartement 13 au 13ième étage.Le violoniste habite l’appartement 13 au 13ième étage.

– Qui est qui ?Qui est qui ?

Page 36: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance

Exemple de problèmesExemple de problèmes

Les tours de HanoiLes tours de Hanoi– L’univers du problème consiste en un ensemble de trois piliers L’univers du problème consiste en un ensemble de trois piliers

notés de la gauche vers la droite, p1, p2 et p3, et de deux disques, notés de la gauche vers la droite, p1, p2 et p3, et de deux disques, notés d1 et d2, où le premier est plus petit et posé sur le second.notés d1 et d2, où le premier est plus petit et posé sur le second.

• Le problème consiste à faire passer les deux disques, d1 et d2, du pilier p1 au pilier p3 en se servant du pilier intermédiaire p2 en respectant la règle ci-dessous :

Le petit disque d1 ne peut jamais être sous la grand disque d2.

• Le problème se généralise à un nombre quelconque de disques.

Page 37: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Architecture d’un SBCArchitecture d’un SBC

Moteurd’inférence

Base de connaissances

Base de faits

Utilisateur

Interface

Page 38: Système à base  de connaissance

Architecture d’un SBCArchitecture d’un SBC

Page 39: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Caractéristiques majeuresCaractéristiques majeures

Séparation de la connaissance et du raisonnementSéparation de la connaissance et du raisonnement Contient de la connaissance experteContient de la connaissance experte Se focalise sur une expertise donnéeSe focalise sur une expertise donnée Raisonne avec des symbolesRaisonne avec des symboles Raisonne avec des heuristiquesRaisonne avec des heuristiques Permet le raisonnement « incertain »Permet le raisonnement « incertain » Résout des problèmes pour lesquels il existe des Résout des problèmes pour lesquels il existe des

expertsexperts

Page 40: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Représentation des connaissancesReprésentation des connaissances

Page 41: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

ConnaissanceConnaissance– Donnée Donnée information information connaissance connaissance– LLa représentation des connaissances est le a représentation des connaissances est le

problème clé en IA.problème clé en IA.– Les objets, actions, concepts, situations, Les objets, actions, concepts, situations,

relations, etc. sont représentés selon certains relations, etc. sont représentés selon certains formalismes (cerveau vs. mémoire de formalismes (cerveau vs. mémoire de l’ordinateur).l’ordinateur).

Page 42: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Représentation des connaissancesReprésentation des connaissances– C’est le transfert des connaissances d’un expert C’est le transfert des connaissances d’un expert

vers une machine vers une machine Psychologie cognitivePsychologie cognitive Changement de mediaChangement de media Changement de forme de représentationChangement de forme de représentation

– C’est une tâche de modélisation linguistique :C’est une tâche de modélisation linguistique : puissance expressivepuissance expressive applicable pour le raisonnementapplicable pour le raisonnement efficaceefficace

Page 43: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Types de connaissanceTypes de connaissance

Page 44: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Représentation des connaissancesReprésentation des connaissances– Triplets <objet, attribut, valeur>Triplets <objet, attribut, valeur>– Réseaux sémantiquesRéseaux sémantiques– FramesFrames– LogiqueLogique– RèglesRègles

Page 45: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Triplets <objet, attribut, valeur>Triplets <objet, attribut, valeur>– SyntaxeSyntaxe

ObjetObjet (sujet) = la ressource (URL ou nœud local) (sujet) = la ressource (URL ou nœud local) AttributAttribut (prédicat) = la propriété (prédicat) = la propriété ValeurValeur (objet) (objet)

– Exemple. Exemple. la ressource la ressource http://www.w3c.org/http://www.w3c.org/ a un propriété a un propriété titre titre

dont la valeur est dont la valeur est World Wide Web consortiumWorld Wide Web consortium..

http://www.w3c.org World Wide Web Consortiumtitre

Page 46: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Réseaux sémantiquesRéseaux sémantiques– Il s'agit de réseaux dont les nœuds représentent les Il s'agit de réseaux dont les nœuds représentent les

concepts et les arcs représentent les relations.concepts et les arcs représentent les relations.– Le but des réseaux sémantiques est de fournir une Le but des réseaux sémantiques est de fournir une

représentation souple des connaissances.représentation souple des connaissances.

Moyen de transport

Avion

Voiture

Avion de chasse

Aile

Airbus A380Citroën C4

est-un

sorte-de

est-un

possède

sorte-de

sorte-de

Page 47: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

FramesFrames L’origine des langages de frames peut être trouvée dans les RS. En fixant une relation hiérarchique de base (est-un) et une relation d'appartenance (appartient-à), on a la structure d'un langage de frames. Les autres relations se cachent dans les attributs des entités.

Les entités hiérarchisées sont les classes (avec au sommet une classe racine souvent appelée OBJET). Les autres entités, les objets proprement dits, appartiennent aux différentes classes.

Page 48: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance Logique (Calcul des propositions et prédicats)Logique (Calcul des propositions et prédicats)

– On peut représenter la situation de la figure de la manière suivante en On peut représenter la situation de la figure de la manière suivante en utilisant les prédicats 'sur', 'surtable', 'libre‘ : utilisant les prédicats 'sur', 'surtable', 'libre‘ : sur(C,A)sur(C,A) surtable(A)surtable(A) surtable(B)surtable(B) libre(C)libre(C) libre(B)libre(B)

– Par ailleurs, à l'aide d'opérateurs de la logique du premier ordre, il est Par ailleurs, à l'aide d'opérateurs de la logique du premier ordre, il est possible de définir de nouveaux prédicats: ‘ôter', 'empiler' et de donner possible de définir de nouveaux prédicats: ‘ôter', 'empiler' et de donner des équivalences :des équivalences :

1) libre(x) 1) libre(x) ¬ (y sur(y,x)) ¬ (y sur(y,x)) (il n'existe pas de y sur x)(il n'existe pas de y sur x)2) sur(y,x) 2) sur(y,x) oter(y,x) oter(y,x) libre(x) libre(x) ¬ sur(y,x) ¬ sur(y,x)3) libre(x) 3) libre(x) libre(y) libre(y) empiler(x,y) empiler(x,y) sur(x,y) sur(x,y)

– Il est possible de donner un but à atteindre (par un robot) de la même Il est possible de donner un but à atteindre (par un robot) de la même façon.façon.

Page 49: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

RèglesRègles– Connaissance servant à faire le lien entre des Connaissance servant à faire le lien entre des

informations connues et d’autres informations que informations connues et d’autres informations que l’on peut déduire ou inférer.l’on peut déduire ou inférer. Exemple. Exemple.

– Si <balle, couleur, rouge> alors j’aime la balleSi <balle, couleur, rouge> alors j’aime la balle– Si j’aime la balle alors j’achète la balleSi j’aime la balle alors j’achète la balle

– Peut exécuter des procédures.Peut exécuter des procédures. Si délai<30 et âge_étudiant<28 ="oui" Si délai<30 et âge_étudiant<28 ="oui"

et présent_communication = "oui" et présent_communication = "oui" alors réduction_congrés = 50% alors réduction_congrés = 50%

Page 50: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance RèglesRègles

– Représentent des formes de connaissances variées :Représentent des formes de connaissances variées : RelationRelation

RecommandationRecommandation

DirectiveDirective

StratégieStratégie

HeuristiqueHeuristique

Si batterie mortealors l’auto ne démarrera pas

Si l’auto ne démarre pasalors prendre un taxi

Si l’auto ne démarre pas & le système d’alimentation en essence est okalors vérifier le système électrique

Si l’auto ne démarre pas alors vérifier le système d’alim. en essence puis le système électrique

Si l’auto ne démarre pas & l’auto est une Ford de 1962 alors vérifier le radiateur

Page 51: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Règles avec variablesRègles avec variables– Réaliser la même opération sur un ensemble Réaliser la même opération sur un ensemble

d’objets.d’objets.– Exemple.Exemple.

Si Toto est employé & Toto âge Si Toto est employé & Toto âge > 65> 65

alors alors TotoToto peut prendre sa retraite peut prendre sa retraite

Page 52: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Règles incertainesRègles incertaines– TTraduisent des associations incertaines entre raduisent des associations incertaines entre

prémisses et conclusions. prémisses et conclusions. – Exemple.Exemple.

Si inflation élevéeSi inflation élevée

alors taux d’intérêt élevéalors taux d’intérêt élevé

Page 53: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Méta-règlesMéta-règles– Traduisent une connaissance sur l’utilisation et Traduisent une connaissance sur l’utilisation et

le contrôle de la connaissance du domaine. le contrôle de la connaissance du domaine. – Disent comment utiliser les autres règles.Disent comment utiliser les autres règles.– Exemple.Exemple.

Si auto ne démarre pas & système électrique normalSi auto ne démarre pas & système électrique normal

alors exploiter les règles concernant le système d ’alim. en alors exploiter les règles concernant le système d ’alim. en ess.ess.

Page 54: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Ensemble de règlesEnsemble de règles– Les règles sont divisées en ensembles. Les règles sont divisées en ensembles. – Chaque ensemble est applicable à un problème Chaque ensemble est applicable à un problème

donné.donné. Panne auto

Système électrique

Système alim. en essence

Page 55: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement dans les SBCsRaisonnement dans les SBCs

Page 56: Système à base  de connaissance
Page 57: Système à base  de connaissance

Architecture d’un SBCArchitecture d’un SBC

Page 58: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement = processus deRaisonnement = processus de– Faire coopérer connaissances, faits, et Faire coopérer connaissances, faits, et

stratégies de résolution de problèmes, dans le stratégies de résolution de problèmes, dans le but d’atteindre des conclusions.but d’atteindre des conclusions.

– Comprendre comment un expert humain Comprendre comment un expert humain raisonne lors de la résolution d’un problème.raisonne lors de la résolution d’un problème.

Page 59: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Types de raisonnementsTypes de raisonnements

Raisonnement

Déductif

Inductif

Abductif

Analogique

Du sens commun

Page 60: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Types de raisonnementsTypes de raisonnements– Raisonnement Raisonnement

A est vraiA est vrai A A B est vrai B est vrai On en déduit que : B est vraiOn en déduit que : B est vrai

– RaisonnementRaisonnement Un ensemble d’objets {a, b, c, d, …}Un ensemble d’objets {a, b, c, d, …} Une propriété P vraie pour les objets a, b, c, … de l’ensembleUne propriété P vraie pour les objets a, b, c, … de l’ensemble On induit que P est vraie pour tout On induit que P est vraie pour tout xx de l’ensemble de l’ensemble

– Raisonnement Raisonnement C’est une inférence plausible.C’est une inférence plausible. B est vraiB est vrai A A B est vrai B est vrai on abduit que A est vraion abduit que A est vrai

Déductif

Inductif

Abductif

Page 61: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance Types de raisonnementsTypes de raisonnements

– RaisonnementRaisonnement Faire une analogie entre 2 situations, rechercher les Faire une analogie entre 2 situations, rechercher les

similarités et différences, etc.similarités et différences, etc. Exploite par exemple la notion de frame pour raisonner.Exploite par exemple la notion de frame pour raisonner.

– RaisonnementRaisonnement S’appuie sur l’expérience de l’expert, sur la notion de S’appuie sur l’expérience de l’expert, sur la notion de

« bon » jugement, plus que sur la logique. Notion « bon » jugement, plus que sur la logique. Notion d’d’heuristiqueheuristique..

- Heuristique : Technique consistant à apprendre petit à petit, en tenant compte de ce Heuristique : Technique consistant à apprendre petit à petit, en tenant compte de ce que l'on a fait précédemment pour tendre vers la solution d'un problème.que l'on a fait précédemment pour tendre vers la solution d'un problème.

Analogique

Du sens commun

Page 62: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement à base de règleRaisonnement à base de règle– 3 composants essentiels :3 composants essentiels :

un ensemble de règles ;un ensemble de règles ; un ensemble de faits ;un ensemble de faits ; un moteur d’inférence ;un moteur d’inférence ;

– Avantages :Avantages : Facile à comprendre, naturel, modulaire.Facile à comprendre, naturel, modulaire.

Base de faits initiale

Base deconnaissance

Base de faits enrichie

Moteurd’inférence

Page 63: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement à base de règleRaisonnement à base de règle– Principe de fonctionnement :Principe de fonctionnement :

Trouver parmi les règles celles candidatesTrouver parmi les règles celles candidates Choisir une de ces règlesChoisir une de ces règles Exécuter la règleExécuter la règle

– Résolution de conflitsRésolution de conflits Si plusieurs règles satisfaites, choisir laquelle déclenchée Si plusieurs règles satisfaites, choisir laquelle déclenchée

– Critère d’arrêtCritère d’arrêt Pour déterminer la fin du processus d’inférence (plus Pour déterminer la fin du processus d’inférence (plus

aucune règle n’est déclenchée, une solution acceptable a aucune règle n’est déclenchée, une solution acceptable a été trouvée, impossibilité de trouver une solution, etc.)été trouvée, impossibilité de trouver une solution, etc.)

Page 64: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance Base de règlesBase de règles

– La base de règles rassemble la connaissance et le savoir-faire de La base de règles rassemble la connaissance et le savoir-faire de l’expert.l’expert.

– Elle n’évolue donc pas au cours d’une session de travail.Elle n’évolue donc pas au cours d’une session de travail.– Une règle se présente sous la forme : Une règle se présente sous la forme : si X alors Ysi X alors Y

X est la prémisseX est la prémisse– C’est une conjonction de conditions, i.e. une suite de comparaison d’attributs et de C’est une conjonction de conditions, i.e. une suite de comparaison d’attributs et de

valeurs à l’aide d’opérateurs.valeurs à l’aide d’opérateurs.

Y est la conclusionY est la conclusion– La conclusion est une affectation.La conclusion est une affectation.

– Exemple base de règlesExemple base de règles si si l’âge du patient < 18l’âge du patient < 18 etet si si il a de la fièvre > 39°il a de la fièvre > 39° etet si si présence d’un germe Xprésence d’un germe X alorsalors le patient a peut-être une méningitele patient a peut-être une méningite

Page 65: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance Base de faitsBase de faits

– La base de faits constitue la mémoire de travail du SBC.La base de faits constitue la mémoire de travail du SBC.– Elle est variable au cours de l’exécution et vidée lorsque Elle est variable au cours de l’exécution et vidée lorsque

l’exécution se termine.l’exécution se termine.– Au début de la session, elle contient tout ce qu’on sait à propos du Au début de la session, elle contient tout ce qu’on sait à propos du

cas examiné avant toute intervention du moteur d’inférence.cas examiné avant toute intervention du moteur d’inférence.– A la fin, elle est complétée par les faits déduits par le moteur ou A la fin, elle est complétée par les faits déduits par le moteur ou

demandés à l’utilisateur.demandés à l’utilisateur.– Exemple base de faitsExemple base de faits

Âge est 6Âge est 6 Fièvre est 40°Fièvre est 40° Germe XGerme X Sexe fémininSexe féminin

Page 66: Système à base  de connaissance

Système à base de connaissanceSystème à base de connaissance Moteurs d’inférenceMoteurs d’inférence

– Il existe de nombreux types de moteurs, capables de traiter différentes Il existe de nombreux types de moteurs, capables de traiter différentes formes de règles logiques pour déduire de nouveaux faits à partir de la formes de règles logiques pour déduire de nouveaux faits à partir de la base de connaissance.base de connaissance.

– On distingue 3 catégories, basées sur la manière dont les problèmes On distingue 3 catégories, basées sur la manière dont les problèmes sont résolus :sont résolus : les moteurs à « les moteurs à « chaînage avantchaînage avant »  » les moteurs à « les moteurs à « chaînage arrièrechaînage arrière » » les moteurs à « les moteurs à « chaînage mixtechaînage mixte » »

– Certains moteurs d’inférence peuvent être partiellement pilotés ou Certains moteurs d’inférence peuvent être partiellement pilotés ou contrôlés par des méta-règles qui modifient leur fonctionnement et contrôlés par des méta-règles qui modifient leur fonctionnement et leurs modalités de raisonnement.leurs modalités de raisonnement.

Page 67: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Chaînage avantChaînage avant

• Mécanisme simple : pour déduire un fait particulier, on déclenche les règles dont les prémisses sont connues jusqu’à ce que le fait à déduire soit également connu ou qu’aucune règle ne puisse être déclenchée.

Base de faits initiale

Considérer la première

règle

Appariement base de

faits – prémisses ?

Ajouter la conclusion à la base de

faits

Il reste des règles

?

STOP

Considérer la règle

suivante

T F

T

F

Page 68: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Chaînage avantChaînage avant• On va analyser chaque fait, et on va examiner toutes les règles où ce fait apparaît en prémisse.

• Pour les règles déclenchées, on va affecter les attributs en conclusion des valeurs qui leur correspondent.

• Ces attributs affectés feront partie du résultat final de l’expertise, et en même temps, ils seront eux-mêmes propagés.

• On fait cela jusqu’à l’épuisement des faits, et on communique le résultat à l’utilisateur.

Base de faits initiale

Considérer la première

règle

Appariement base de

faits – prémisses ?

Ajouter la conclusion à la base de

faits

Il reste des règles

?

STOP

Considérer la règle

suivante

T F

T

F

PRECISION

Page 69: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Chaînage arrièreChaînage arrière• Mécanisme consistant à partir du fait que l’on souhaite établir, à rechercher toutes les règles qui concluent sur ce fait, à établir la liste des faits qu’il suffit de prouver pour qu’elles puissent se déclencher, puis à appliquer récursivement le même mécanisme aux faits contenus dans ces listes.

• Le chaînage arrière est clairement un mécanisme d’induction : on vérifie les hypothèses en remontant depuis l’objectif. On cherche ainsi à vérifier si un fait est possible.

11

8

910

7

Infection streptocoque de la gorge ?

Infection streptocoque de la gorge ?

Signes d’infection de la gorge

Signes d’infection de la gorge

Organisme = streptocoque

Organisme = streptocoque

Gorge rougeGorge rouge

Tâche en Grampos

Tâche en Grampos

Morphologie coccidie

Morphologie coccidie

Croissance en chaîne

Croissance en chaîne

1

2

3

4 5

6

12

Exemple. MYCIN

Page 70: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Chaînage arrièreChaînage arrière• Pour prouver une hypothèse en recherchant les informations pouvant la supporter.

• On sélectionne alors les règles ayant ce but comme conclusion, et on vérifie si les prémisses de ces règles font partie de la base des faits.

• Les prémisses n’appartenant pas à la base de faits deviennent à leur tour des buts à prouver de la même façon.

• Le raisonnement se fait des solutions vers les faits initiaux.

11

8

910

7

Infection streptocoque de la gorge ?

Infection streptocoque de la gorge ?

Signes d’infection de la gorge

Signes d’infection de la gorge

Organisme = streptocoque

Organisme = streptocoque

Gorge rougeGorge rouge

Tâche en Grampos

Tâche en Grampos

Morphologie coccidie

Morphologie coccidie

Croissance en chaîne

Croissance en chaîne

1

2

3

4 5

6

12

Exemple. MYCIN

Page 71: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

ComparaisonComparaison

Page 72: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Chaînage mixteChaînage mixte– Les mêmes règles sont utilisées an chaînage avant et Les mêmes règles sont utilisées an chaînage avant et

arrière, selon que des faits nouveaux arrivent ou que arrière, selon que des faits nouveaux arrivent ou que l’on ait des faits à établir.l’on ait des faits à établir.

– On peut alors aussi bien raisonner à partir des faits que On peut alors aussi bien raisonner à partir des faits que l’on connaît comme prédicats ou comme objectifs.l’on connaît comme prédicats ou comme objectifs.

Faits initiau

x

Solutions

possibles

Page 73: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Quel chaînage utiliser ?Quel chaînage utiliser ?– Ce sont les caractéristiques du problème qui Ce sont les caractéristiques du problème qui

vont conditionner le chaînage qu’il est judicieux vont conditionner le chaînage qu’il est judicieux d’utiliser.d’utiliser.

– Ainsi, lorsque les faits sont peu nombreux ou Ainsi, lorsque les faits sont peu nombreux ou que le but est inconnu que le but est inconnu chaînage avant. chaînage avant.

– Par contre, dans les cas où les buts sont peu Par contre, dans les cas où les buts sont peu nombreux ou précis nombreux ou précis chaînage arrière. chaînage arrière.

Page 74: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Raisonnement monotone vs. non monotoneRaisonnement monotone vs. non monotone

Non monotoneNon monotone MonotoneMonotoneinformation dynamique ;information dynamique ;

l’état de véracité de l’information l’état de véracité de l’information change.change.

Sauvegarder les dépendances Sauvegarder les dépendances logiques entre faits.logiques entre faits.

Si on retire un fait A dont dépend Si on retire un fait A dont dépend un autre fait B, on doit retirer aussi un autre fait B, on doit retirer aussi le fait B.le fait B.

information statique ;information statique ;

l’état de véracité de l’information ne l’état de véracité de l’information ne change pas.change pas.

Exemple. Si Il pleut alors j’ouvre mon Exemple. Si Il pleut alors j’ouvre mon parapluieparapluie

Page 75: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Stratégies de parcours d’arbreStratégies de parcours d’arbre• Notion de réseau d’inférences et de parcours dans le réseau.

• Exemple.Si P1 alors C1 ;

Si P2 alors C2 ;

Si P3 & P4 alors P2 ;

Si P5 & P6 alors P1 ;

Si P7 alors P6 ;

Si P8 alors P4 ;

Si P9 alors C2 ;

Problème

C1 C2

P1

P5 P6

P7

P9P2

P3 P4

P8

Différentes stratégies de parcours de l’espace !

Page 76: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Stratégies de parcours d’arbreStratégies de parcours d’arbreProblèm

e

C1 C2

P1

P5 P6

P7

P9P2

P3 P4

P8

Parcours en profondeur d ’abord

• Parcourir le graphe verticalement d’abord, pour ensuite explorer d’autres nœuds (de gauche à droite).

• Lorsqu’il est connu que l’espace de recherche est profond, la stratégie en profondeur d’abord est un bon choix.

• De plus, cette stratégie se focalise sur une solution et est donc à même d’être comprise par un utilisateur qui interagit avec le système, car les questions sont relatives à un même chemin.

Page 77: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Stratégies de parcours d’arbreStratégies de parcours d’arbreProblèm

e

C1 C2

P1

P5 P6

P7

P9P2

P3 P4

P8

Parcours en largeur d’abord

• Parcourir d’abord les nœuds d’un même niveau, avant de considérer les nœuds du niveau inférieur.

• Si la solution se situe profondément dans l’espace de recherche, cette stratégie n’est pas payante.

• Les interactions avec un utilisateur sont difficiles en raison de l’exploration de chemins nombreux (manque de focalisation).

Page 78: Système à base  de connaissance

Système à base de Système à base de connaissanceconnaissance

Stratégies de parcours d’arbreStratégies de parcours d’arbre

Parcours « meilleur » d’abord

• C’est une solution non aveugle.

• Elle exploite des connaissances du problème pour guider la recherche.

• À chaque nœud, la technique juge du meilleur chemin à emprunter, suivant une heuristique donnée.

Exemples d ’heuristiques

• Ordonner les buts

• Ordonner les prémisses

• Utiliser des méta-règles

• Attribuer des priorités aux règles

• Utiliser des facteurs de confiance

• etc.

Page 79: Système à base  de connaissance

BibliographieBibliographie L’IAL’IA

– Arsac, Jacques : Arsac, Jacques : Les machines à penserLes machines à penser, Le Seuil, Paris, 1987. , Le Seuil, Paris, 1987. – Crevier, Daniel : Crevier, Daniel : A la recherche de l'IAA la recherche de l'IA, Flammarion, collection «champs», , Flammarion, collection «champs»,

Paris, 1999. Paris, 1999.

Les SBCLes SBC– C. L. Paris. Systèmes Experts Explicatifs. In EXPL 92 pp 3-23.C. L. Paris. Systèmes Experts Explicatifs. In EXPL 92 pp 3-23.– D. Kayser, La représentation des connaissances, HermèsD. Kayser, La représentation des connaissances, Hermès– (Paris), 1997.(Paris), 1997.– J.L. Laurière, Intelligence Artificielle (résolution de problèmes par l’homme J.L. Laurière, Intelligence Artificielle (résolution de problèmes par l’homme

et la machine), Eyrolles, Paris, 1987.et la machine), Eyrolles, Paris, 1987.– M. Stefik, Introduction to Knowledge Systems, Morgan Kaufmann M. Stefik, Introduction to Knowledge Systems, Morgan Kaufmann

Publishers, San Francisco (CA), 1995.Publishers, San Francisco (CA), 1995.– A. Thayse et al., Approche logique de l’Intelligence Artificielle (5 tomes), A. Thayse et al., Approche logique de l’Intelligence Artificielle (5 tomes),

Dunod Informatique (Paris), 1988.Dunod Informatique (Paris), 1988.– P.H. Winston, Artificial Intelligence, Addison-Wesley, Reading (MA), 1982.P.H. Winston, Artificial Intelligence, Addison-Wesley, Reading (MA), 1982.– E. Rich, Artificial Intelligence, Mac Graw Hill (New York), 1983.E. Rich, Artificial Intelligence, Mac Graw Hill (New York), 1983.– Systèmes Experts : Méthodes et outils"Systèmes Experts : Méthodes et outils", J.M. Chatain et A. Dussauchoy. , J.M. Chatain et A. Dussauchoy.

Eyrolles 1987Eyrolles 1987

Page 80: Système à base  de connaissance

EXEMPLEEXEMPLE

Soit la base de connaissances :Soit la base de connaissances : • • R1 : si B et D et E alors F • R6 : si A et X alors HR1 : si B et D et E alors F • R6 : si A et X alors H • • R2 : si D et G alors A • R7 : si C alors DR2 : si D et G alors A • R7 : si C alors D • • R3 : si C et F alors A • R8 : si X et C alors AR3 : si C et F alors A • R8 : si X et C alors A • • R4 : si B alors X • R9 : si X et B alors DR4 : si B alors X • R9 : si X et B alors D • • R5 : si D alors ER5 : si D alors E Base de faits : Base de faits : B, CB, C But : But : HH