Mardi 18 novembre 20081
Master Web IntelligenceICM - Option Informatique
2008/2009
Web Sémantique
Philippe BeauneENSM-SE/G2I/SMA
mailto : [email protected]
Mardi 18 novembre 20082
Le Web SémantiqueL'expression « web sémantique » est récente : Tim Berners-Lee, en 1998 et/ou 2001, au sein du W3CFait référence au web de demain qui serait un vaste espace échange de ressources entre êtres humains et machinesExploitation qualitativement supérieure de grands volumes d'informations et de services variésDécharger l'utilisateur
Mardi 18 novembre 20083
Les trois générations du Web
Le Web statique : HTML à la main ou assisté, accès uniformisé, maintenance difficile ;
Le Web dynamique : génération des contenus à la demande (bases de données, transformations XML, scripts, ...)
Le Web Sémantique ...
Mardi 18 novembre 20084
Le Web d'aujourd'huiL'information sur le Web est actuellement essentiellement prévue pour être affichée (écran, imprimante, ...) et lue par des humains.Il est essentiellement syntaxique : contenu quasi inaccessible aux traitements machinesSeuls les humains peuvent interpréter ces contenus
Mardi 18 novembre 20085
Le Web d'aujourd'huiLa recherche d'infos n'est pas simple (les documents et les liens entre documents n'ont pas de sémantique)Ai-je trouvé toutes les infos pertinentes (un document avec des mots différents est oublié) ? Combien de documents trouvés sont réellement pertinents (mêmes mots mais sujet différent)? Exemple de requête : quel est le domaine de recherche du directeur du Master Web Intelligence proposé par l'ENSM-SE ?
Mardi 18 novembre 20086
le futur Web Sémantique
Une description structurelle de l'ENSM-SE indiquera que le master est co-habilité par l'UJM, et donc que master WI de l'ENSM-SE équivaut à master WI de l'UJMUne recherche à l'UJM échoueraMais une équivalence entre directeur et responsable permettra de trouver qu'il s'agit de Marc Sebban, ... donc sa page, et donc son domaine de recherche (par traduction de research interests)
Mardi 18 novembre 20087
Web sémantique : objectif
"The Semantic Web is an extension of the current web in which information is given well-defined meaning, better enabling computers and people to work in cooperation."
Tim Berners-Lee, James Hendler, Ora Lassila, The Semantic Web, Scientific American, May 2001
Article disponible sur http://www.scientificamerican.com/
et sur http://www.emse.fr/~beaune/websem
Mardi 18 novembre 20088
Web Sémantique : objectifs
Le web actuel :Pas de structure explicite globaleLiens non exploitables sémantiquementTravail limité sur les infos
Le Web SémantiqueConnaissances formalisées (cf. théorie des modèles)Liens sémantiques entre informationsAnnotations plus richesStandards à base d'XML, et ouverture
Mardi 18 novembre 20089
Web sémantique : définition
« The Semantic Web is the representation of data on the World Wide Web. It is a collaborative effort led by W3C with participation from a large number of researchers and industrial partners. It is based on the Resource Description Framework (RDF), which integrates a variety of applications using XML for syntax and URIs for naming. » -- W3C
Mardi 18 novembre 200810
Vision a priori de l'AS Web Sémantique
Le web sémantique se veut un web dont le contenu peut être appréhendé et exploité par des machines. Ainsi, le web sémantique pourra fournir des services plus aboutis à ses utilisateurs (trouver l'information pertinente, sélectionner, localiser et activer le service nécessaire...). Il peut être vu comme une infrastructure complémentant le contenu informel du web actuel avec de la connaissance formalisée. Il peut conduire à faire cohabiter plusieurs degrés de formalisations allant de schémas de métadonnées figés (comme celui du Dublin core) à des langages de représentation plus complexes (comme DAML+OIL et différentes logiques). Le Web sémantique représente un champ de recherches en plein développement dans lequel de nombreux travaux peuvent s'inscrire.
Mardi 18 novembre 200811
Vision de l'AS Web Sémantique(décembre 2003)
Le Web sémantique, concrètement, est d'abord une infrastructure pour permettre l'utilisation de connaissances formalisées en plus du contenu informel actuel du Web, même si aucun consensus n'existe sur jusqu'où cette formalisation doit aller. Cette infrastructure doit permettre d'abord de localiser, d'identifier et de transformer des ressources de manière robuste et saine tout en renforçant l'esprit d'ouverture du Web avec sa diversité d'utilisateurs. Elle doit s'appuyer sur un certain niveau de consensus portant, par exemple, sur les langages de représentation ou sur les ontologies utilisés. Elle doit contribuer à assurer, le plus automatiquement possible, l'interopérabilité et les transformations entre les différents formalismes et les différentes ontologies. Elle doit faciliter la mise en oeuvre de calculs et de raisonnements complexes tout en offrant des garanties supérieures sur leur validité. Elle doit offrir des mécanismes de protection (droits d'accès, d'utilisation et de reproduction), ainsi que des mécanismes permettant de qualifier les connaissances afin d'augmenter le niveau de confiance des utilisateurs. Mais restreindre le Web sémantique à cette infrastructure serait trop limitatif. Ce sont les applications développées sur celle-ci qui font et feront vivre cette vision et qui seront, d'une certaine manière, la preuve du concept.
Mardi 18 novembre 200812
Buts du Web Sémantique(AS – décembre 2003)
Le but du Web sémantique est principalement que les services soient mieux rendus sans engendrer de surcharge pour les utilisateurs. Dans cette perspective, les usages ne devraient se voir impacter que positivement par les langages développés. Mais l'idée du Web est que les usagers en soient les contributeurs. C'est en ce sens que les langages développés pour le Web sémantique pourront avoir un impact sur ceux qui les utiliseront pour décrire leurs ressources voire leurs services.
Mardi 18 novembre 200813
Web Sém. : caractéristiques
Espace d'échanges de ressources entre machinesLibérer l'utilisateur grâce à des capacités accrues dans
la recherche d'infos,l'intégration de sources d'infos,la découverte, l'exploitation et la combinaisons de services,le raisonnement des machines
Pas vraiment de techniques fondamentalement nouvelles mais changement de contexte
Mardi 18 novembre 200814
Web Sém. : autres caractéristiques
Nouveau contexte = nouveaux défisChangement d'échelleBesoins d'ouverture : intégration, interopérabilité, extranet, ...Besoins de standardisation, de consensusNouvelles opportunités : wireless, wap, ...De futurs nouveaux usages ... des applications nouvelles (médecine, mémoires d'entreprise, traduction, e-commerce, web services sémantiques, ...)
Mardi 18 novembre 200815
Web sémantique : structuration
Mardi 18 novembre 200816
Web sémantique : structuration
Mardi 18 novembre 200817
Web sémantique : structuration
Mardi 18 novembre 200818
Web sémantique : structuration
Mardi 18 novembre 200819
Web sémantique : structuration
Mardi 18 novembre 200820
Web sémantique : structuration
http://ww
w.w3.org
/2007/03
/layerCak
e.png
Mardi 18 novembre 200821
Objectifs de cette structuration
Outils généralistes pour utilisateurs mal définis (esprit d'ouverture)Mais aussi applications complexes spécialisées (mémoire d'entreprise par exemple)Nécessité de langages pour exprimer les données et méta-données, pour exprimer des ontologies, des espaces de noms, pour exprimer des services, ...Besoin de méthodes, de mécanismes d'inférences, ...
Mardi 18 novembre 200822
Travaux à mener pour un Web Sémantique (AS – décembre 2003)
développer des langages de représentation (des connaissances) de la sémantique des contenus ou des ressources, et quand cela est nécessaire, support de mécanismes d'inférence aux bonnes propriétés (validité, complétude, complexité) ;développer des ressources linguistiques ou conceptuelles (espaces de noms, thésaurus, ontologies, ...) utilisant ces langages, les standardiser - si possible - et les rendre disponibles ;développer des outils et des architectures ouvertes permettant la rapide expérimentation de ces nouvelles technologies ;appliquer ces technologies à un large champ d'applications et montrer le saut qualitatif obtenu.
Mardi 18 novembre 200823
et le Web 2.0 ?
« Web 2.0 does not deliver inter-application integration »« Semantic Web does not provide cool interfaces to data »
« Good separately ... Great together »
Tim Berners Lee, 2006
Mardi 18 novembre 200824
Plan général du cours
Mardi 18 novembre : repr. des connaissancesMercredi 26 novembre : ontologies
séances suivantes (janvier 09) : Alain Légermardi 27 janvier 09 : exam
Mardi 18 novembre 200825
Plan du cours (aujourd'hui)
Représentation des connaissances en IA :Généralités (informations, connaissances, ...)Réseaux sémantiquesFrames, scriptsLogiques classiquesGraphes conceptuelsLogiques modalesRégles de production et systèmes expertsL'ingénierie des connaissances
Mardi 18 novembre 200826
Informations, connaissancesInformation = codage
7398f627a71420bd765234fc76283a0983f87172Connaissance = signification
rapport d'un sujet à un objetReprésenter des connaissances :
trouver des structures permettant d'énoncer, de coder, de mémoriser, de modifier, de valider, … de manipuler des connaissances (sur ordinateur, pour nous)quoi représenter ? : faits et objets du domaine, définitions, concepts, relations, méta-connaissances, heuristiques, stratégies, algorithmes, événements, actions ...difficultés : représenter l'implicite, l'incertain, l'imprécis, les exceptions, l'incomplet, le point de vue, l'évolution dans le temps, le temps, ...
Mardi 18 novembre 200827
données/info/connaissance -1
Données = symboles, signaux
Informations : données interprétées et contextualisées par l'homme
Connaissances : informations appropriées intériorisées par un homme ; croyance justifiée ; d'abord individuelles puis collectives
Mardi 18 novembre 200828
données/info/connaissance -2THOMAS H. DAVENPORT ET DONALD MARCHAND (in Les Échos, 1999)
Les données, l'information et les connaissances constituent autant de points d'un continuum le long duquel la valeur et la contribution humaine vont croissant. Les données - signes des événements et des activités humaines de tous les jours - ont peu de valeur en elles-mêmes ; elles ont néanmoins à leur crédit d'être faciles à manipuler et à stocker sur ordinateur.
L'information, c'est ce que deviennent les données lorsque l'homme les interprète et les contextualise. C'est aussi le support que nous utilisons pour exprimer et communiquer les connaissances à l'intérieur des entreprises et dans la vie de tous les jours. L'information a plus de valeur que les données, et, en même temps, une plus grande ambiguïté, comme en attestera tout manager qui a discuté des nombreuses interprétations que les termes « client », « commande » et « livraison » pouvaient avoir à l'intérieur d'une même entreprise.
Les connaissances, quant à elles, sont de l'information contenue à l'intérieur du cerveau humain ; sans une personne lucide pour détenir ces connaissances, point de connaissances. La valeur des connaissances est élevée, parce que, grâce à elles, l'homme a de nouvelles idées, de nouvelles intuitions et de nouvelles interprétations, qu'il applique directement à l'utilisation des informations et à la prise de décision. Pour les managers, il est difficile de gérer les connaissances de leurs collaborateurs car elles sont d'ordre mental. Elles sont invisibles et leur extraction, leur partage et leur utilisation relèvent de la motivation et de la bonne volonté de leur détenteur.
Mardi 18 novembre 200829
données/info/connaissance -3
http://www.pmequebeclic.com/
Prenons l'exemple d'un bulletin météo pour l'illustrer. Quiconque a déjà écouté un bulletin météo est en mesure de faire la distinction entre les termes données, information et connaissances. Ainsi, quand Jocelyne Blouin affirme qu'il faisait 14 degrés celcius avant-hier à Québec, 12 degrés hier et 10 degrés aujourd'hui, elle communique de simples données. Quand Stéphane Bureau conclut, à la suite de l'exposé de sa collègue, que « cela se refroidit tranquillement », il transmet de l'information. Enfin, lorsque votre conjointe souligne, en les écoutant, qu'« il faudrait bien sortir les tuques et les mitaines», elle partage avec vous un savoir acquis par l'expérience.
Mardi 18 novembre 200830
Formalisme de représentation
Rechercher la justesse de représentationrichesserigueursouplesse
et l'efficacité permettre les traitementsproblèmes de complexitépermettre les évolutions
Mardi 18 novembre 200831
Modèles de représentation des K.
Sources d'inspiration : psychologie cognitive (raisonnement humain)informatique (structures de données)logique (sciences du raisonnement)
Beaucoup de modèles dont :tout ce qui est «procédural» …les réseaux sémantiquesles frames (cadres sémantiques)la logiqueles règles de production, ...
Mardi 18 novembre 200832
Réseaux sémantiquesIdée de base :
modéliser le mécanisme d'association d'idéesutiliser les classifications
réseau sémantique= (multi)graphe + sémantique
nœuds : objets, concepts, situations, événements, …arcs : relations qui lient les nœuds :
est-un (is-a), sorte-de (kind-of), partie-de (part-of), …
Mardi 18 novembre 200833
L'arbre de Porphyre
Mardi 18 novembre 200834
KL-ONE (70's)
Mardi 18 novembre 200835
Héritage, conflits
Mardi 18 novembre 200836
Réseaux sémantiques : exemple
chose
voiture
roue
pierre
jeanmembres
tronc
tête
pneu
aile
avion
véhiculepersonne
canari
oiseau
animal
V14324
sorte-de sorte-de
sorte-de
sorte-de
sorte-desorte-de
sorte-de
partie-de
partie-de
partie-departie-de
partie-de
partie-de
est-un est-un
est-un
possède
Mardi 18 novembre 200837
Limites des réseaux sémantiques
Imprécision sur la sémantique des arcs et des noeuds :des faits, des pointeurs, le sens de phrases, des propositions, des actions, des événements, des propriétés, des assertions, des prédicats, des objets, des classes, des ensembles, des relations sémantiques, des relations linguistiques, des relations conceptuelles et arbitraires, entre autres choses
Ces différents niveaux de représentation sont mélangés, donc confusion de notation et difficulté d'expliquer le fonctionnement des interpréteurs
Mardi 18 novembre 200838
Réseaux sémantiques : manipulationDistance sémantique :
concepts ou objets voisins, …Recouvrement («matching»)
x est-un personne, x possède V1243, ...Héritage (éventuellement multiple)
Pierre est-un étudiant, étudiant sorte-de personne, …Valeurs par défaut
un oiseau vole, … Propagation de marqueurs
pour faire des inférencesAttachement procédural : calculer des propriétés, …Cf. Graphes Conceptuels (Sowa)
Mardi 18 novembre 200839
Exemple avec exception
Animal gris
Éléphant royal
Clyde
Éléphant d'asie
Éléphant
est-unest-un
sorte-desorte-de
sorte-de
n'est-pas
Mardi 18 novembre 200840
Exemple d'algo de marquage
Marquer le concept initial par M1Tant qu'il existe des arcs dont l'origine est marquée M1 et l'extrémité n'est pas marquée :
Marquer M2 l'extrémité des liens d'exceptions dont l'origine est marquée M1Marquer M1 l'extrémité des liens d'héritage dont l'origine est marquée M1 et l'extrémité n'est pas marquée M2
Le noeud initial n'hérite que des noeuds marqués M1
Mardi 18 novembre 200841
Réseaux partitionnés
ministre
s1
croire Jean
négation
Pierre
savoir
Paul
n1
n2c1
s2
e
e
e ee
e agent
agent
agent
objet
objetobjet
arg
arge
Mardi 18 novembre 200842
Frames (cadres sémantiques)Idée de base :
accéder à une connaissance progressivement, par fragments d'informations (cf. vision)
Notion d'attente, d'analogie, de prototypeMélange de déclaratif et de procédural avec valeurs par défaut, typicalité, héritages, exceptions, … C'est un ancêtre de la notion d'«objets»
Mardi 18 novembre 200843
Frames [Minsky 1975]
Un frame est une unité de connaissance (prototype) décrivant une situation ou un objetUn frame possède des attributs décrits par des facettes. Les facettes décrivent la sémantique de l'attribut. Une facette peut pointer vers un autre frame...Les facettes sont :
déclaratives (domaine, valeur, défaut, ...)procédurales (réflexes, démons, ...)
Mardi 18 novembre 200844
Frames : exempleFrame chaise :
spécialisation : mobiliernombre-de-pieds = un entier (default=4)dossier : droit, coussin, …nombre-de-bras = 0, 1 ou 2prix = (si-besoin : question = «quel est le prix ?»)
Occurrence chaise-de-pierrespécialisation : chaisedossier : coussinnombre-de-bras : 0
Mardi 18 novembre 200845
Scripts [Schank & Abelson 1977]
Traitement de la langue naturelleUn script est une représentation structurée d'une séquence d'événements dans un contexte particulier. Un script est composé de :
Entry conditions : descriptions that must be true for the script to be calledResults : they become true when the script terminatesProps : make up the content of the scriptRoles : the actions the individual participants performScenes : each scene presents a temporal aspect of the script
Mardi 18 novembre 200846
Conceptual Dependencies[Schank 1972]
11 primitives :ATRANS, PTRANS, MTRANS : transfers (of possession, of physical objects, and of ideas)MOVE, PROPEL, GRASP : movement of body parts, application of force, grasping of objectsINGEST, EXPEL : eating and anti-eatingATTEND, SPEAK : sensory attention, verbal outputMBUILD : mental construction
DO : anything not covered by the primitive 11 actions
Mardi 18 novembre 200847
Le modèle de Schank
11(+1) primitives de dépendances conceptuellesSix rôles conceptuels permettant de construire un graphe :
ACTEUR : animé qui produit une action (deux traits)OBJET : ce sur quoi porte l'action (o)RELATION : donneur + bénéficiaire (r)DIRECTION : direction d'un mouvement (d)ETAT : valeur d'un attribut (trois traits)INSTRUMENT : élément qui contribue à l'action (i)
Modalités précisant divers aspects de la proposition :passé (p) ; futur (f) ; conditionnel (c) ; négation (/) ; interrogation (?) ; etc.
Mardi 18 novembre 200848
Exemplede scriptcélèbre
Mardi 18 novembre 200849
Utilisation d'un scriptJohn went to the restaurant last night. He orderd steak. When he paid he noticed that he was running out of money. He hurried home since it had started to rainUsing the script, questions such as the following can be answered.
Did John eat dinner last night? yes! John went to the restaurant (restaurant script is invoked). John paid, therefore he must have eaten since in order to pay john had to eat (the paying path of scene 4 is entered from scene 3 which is eating).Did John use cash or credit card? Cash, according to scene 4 of the script (S ATRANS money to M).How could John get a menu? He either found the menu on the table, or asked the waiter to bring the menu (scene 2).What did John buy? John bought a steak (Since John paid for the food and the food was steak).
Mardi 18 novembre 200850
Exemple emprunté à J. Lehuen (Univ Le Mans)
Mardi 18 novembre 200851
Mardi 18 novembre 200852
Plan du cours
Représentation des connaissances en IA :Généralités (informations, connaissances, ...)Réseaux sémantiquesFrames, scriptsLogiques classiquesGraphes conceptuelsLogiques modalesRégles de production et systèmes expertsL'ingénierie des connaissances
Mardi 18 novembre 200853
La logique : pour quoi faire ?
Construire un système logique :définir un aspect formel
aspects syntaxiques : la forme
en donner une interprétation aspects sémantiques : le fond
isomorphisme entre une réalité et un système formel sensé la représenter.
Mardi 18 novembre 200854
La logique des propositions
Vocabulaire : propositions, connecteursrègles de formation des fbfdomaine sémantique (vrai, faux)modèle : interprétationrègles d'inférenceformules valides, consistantes, inconsistantes, …réfutation : preuve par résolution
Mardi 18 novembre 200855
Interprétation
Π : {atomes} → {vrai , faux}Π = pssi Π(p)=vrai
Π = ~p ssi Π ≠ pΠ = p∧q ssi Π = p et Π = q Π = p∨q ssi Π = p ou Π = qΠ = p→q ssi si Π = p alors Π = q
Mardi 18 novembre 200856
La logique des prédicats
Ajouter des variables, des quantificateurs (∃ , ∀), des prédicats, des fonctions, règles d'inférences
principe de résolution, réfutation
langage Prolog (clauses de Horn)
Mardi 18 novembre 200857
Règles de productionÉléments de connaissance déclaratifs et autonomes de la forme :
si conditions alors actionssi conditions alors conclusions
Le moteur ne démarre pas :si le moteur est froid, tirer le starter
si le moteur est chaud, pousser le starter
changer les bougies si elles sont vieilles
si le starter est OK et les bougies neuves, aller voir le garagiste
Mardi 18 novembre 200858
Approche algorithmique
état du moteur ?
starter ?
POUSSER STARTER
bougies
VOIR GARAGISTE
CHANGER BOUGIES
starter ?
TIRER STARTER
chaud froid
tiré tiré poussépoussé
neuves vieilles
codage des données
et du traitement
dans le programme
Mardi 18 novembre 200859
Approche déclarativeSI starter ok
ET bougies = neuves ALORS voir garagiste
SI moteur = froid ET starter = poussé
ALORS tirer le starter
SI moteur = chaud ET starter = tiré
ALORS pousser le starter
SI (moteur = froid ET starter = tiré)
OU (moteur = chaud ET starter = poussé)
ALORS starter ok
SI bougies neuves ALORS changer les bougies
Mardi 18 novembre 200860
ModificationsQuand les bougies sont-elles vieilles ?
SI km parcourus > 10 000 ALORS bougies ≠ neuves
Existence des vis platinées :SI starter ok ET bougies = neuves ET vis platinées = neuves ALORS voir garagisteSI vis platinées ≠ neuves ALORS changer les vis platinées
dans l'approche algorithmique il faut aller changer
non seulement les données mais aussi le traitementdans l'approche déclarative, il suffit d'ajouter les
nouvelles règles
Mardi 18 novembre 200861
Schéma de base
MOTEUR D'INFÉRENCES
Base de FAITS
Base de CONNAISSANCES
mémoire à long terme : modélisation de la connaissance d'un ou plusieurs experts, savoir faire du domaine
mémoire à court terme : caractérisation du problème en cours de résolution
mécanisme d'exploitation des connaissances : met en relation faits et con- naissances pour produire de nouveaux faits (éven- tuellement de nouvelles connaissances)
Mardi 18 novembre 200862
Schéma fonctionnel
INTERFACE D'UTILISATION
INTE
RFA
CE
EX
PER
T ou CO
GN
ITICIE
N
Module d'acquisition de la connaissance
Moteur
d'inférences
Module
d'explications
Base de
connaissances
Base de
faits
Mardi 18 novembre 200863
Systémesexperts
UN SYSTÈME EXPERT : logiciel de résolution deproblèmes dans un domaine délimité pour lequel ilexiste un (des) expert(s)OBJECTIF : informatiser des fonctions intellectuelles
UN EXPERT : humain ayant une grande connaissance deson domaine de compétence et capable de résoudreefficacement des problèmes de ce domaine. Il est mêmecapable d'expliquer sa démarche et son expertise
UN SYSTÈME EXPERT est un logiciel spécialisé dansun domaine de savoir-faire plutôt que dans une tâcheparticulière comme les logiciels classiques
DIFFICULTÉS :- représentation des connaissnces- modélisation du raisonnement- acquisition de la connaissance
OBJECTIF : être capable de résoudre un problème de lameilleure façon possible (comme le ferait un expert, maissans forcément l'imiter) et non pas trouver ou prouver unesolution optimale
Mardi 18 novembre 200864
3 principesLa connaissance doit être donnée sous formedéclarative. Ainsi l'expert (ou le cogniticien)pourra ajouter, modifier ou supprimer deséléments de connaissances sans aucunenouvelle programmation (révision facile)
La base de connaissance doit être indépendante dumécanisme de son exploitation : le processusd'interprétation ne doit pas changer en l'utilisantdans un autre domaine (??)
Le système expert doit être capable d'expliquer sonraisonnement, surtout s'il s'agit d'un système d'aideà la décision. Il doit pouvoir expliquer et justifier leraisonnement qu'il a effectué et qui lui a permisd'aboutir à la solution proposée. Ces explicationsdoivent correspondre à une démarche «admissible»par un expert.
Mardi 18 novembre 200865
Générateur de systèmes experts
C'EST UN SYSTÈME EXPERT AVEC UNE BASE DE CONNAISSANCES VIDE.C'est à dire un moteur d'inférences, un module d'explications, éventuellement un module d'acquisition, des interfaces appropriées, et un langage d'expression de la connaissance.
autres dénominations : - système général - système essentiel - noyau de systèmes experts - shell de systèmes experts
Exemples du commerce : - G2 (temps réel) - NExpert Object - GURU - SMECI - CLIPS
- et beaucoup d'autres
Mardi 18 novembre 200866
Plan du cours
Représentation des connaissances en IA :Généralités (informations, connaissances, ...)Réseaux sémantiquesFrames, scriptsLogiques classiquesRégles de production et systèmes expertsGraphes conceptuelsLogiques modalesL'ingénierie des connaissances
Mardi 18 novembre 200867
Graphes conceptuels [Sowa 1984]
Conceptual graphs (CGs) are a system of logic based on the existential graphs of Charles Sanders Peirce and the semantic networks of artificial intelligence. They express meaning in a form that is logically precise, humanly readable, and computationally tractable. With a direct mapping to language, conceptual graphs serve as an intermediate language for translating computer-oriented formalisms to and from natural languages. With their graphic representation, they serve as a readable, but formal design and specification language. CGs have been implemented in a variety of projects for information retrieval, database design, expert systems, and natural language processing.
Mardi 18 novembre 200868
Graphes conceptuels
Les sommets du graphes sont des concepts [Graph: {*}] ou des relations conceptuelles (Attr).La phrase « graphe conceptuel » devient :[Graph: {*}]->(Attr)->[Conceptual]
le graphe est biparti car il n'y a pas d'arc entre 2 concepts, ni entre 2 relations
Graph: {*} ConceptualAttr
Mardi 18 novembre 200869
Graphes conceptuels : les concepts
Les concepts : [Type: Referent][Person: John]
il existe une personne dont le nom est John[Bus]
il existe un busLes types sont décrits dans un treillis
Mardi 18 novembre 200870
Graphes conceptuels : les relations
Une relation est définie par :Un type : sur, dans, destination, agent, ...Une valence : nb d'arcs qui lui appartiennentUne signature : <t1, t2, ..., tn> si n=valence
la signature de Agnt est <Act,Animate>
•[Sing]→(Agnt)→[Bird]→(In)→[SycamoreTree]
"There is a bird which is the agent of Sing. This same bird is in a sycamore tree""A bird is singing in a sycamore tree".
Mardi 18 novembre 200871
Graphes conceptuels : exemple
Mardi 18 novembre 200872
Graphes conceptuels : opérations
Spécialisation (restriction) :Remplacer un concept par un individuRemplacer un concept par un sous-conceptPermet l'héritage
Généralisationinverse de la spécialisation
JointureCombiner 2 graphes en un seul
SimplificationSupprimer les relations redondantes
Mardi 18 novembre 200873
Graphes conceptuels : exemple
simplification}
Mardi 18 novembre 200874
Graphes conceptuels :pour aller plus loin
Un bon cours avec même une intro en vidéo :http://www.hum.auc.dk/cg/
Un site maintenu par Sowa lui-même :http://www.jfsowa.com/
Mardi 18 novembre 200875
Plan du cours
Représentation des connaissances en IA :Généralités (informations, connaissances, ...)Réseaux sémantiquesFrames, scriptsLogiques classiquesRégles de production et systèmes expertsGraphes conceptuelsLogiques modalesL'ingénierie des connaissances
Mardi 18 novembre 200876
Limites des logiques classiques
Paradoxes : p → (q → p)~ p → (p → q)(p → q) ∨ (q → r)
Croyances :croit(jean, (père(zeus, cronos)))(zeus = jupiter)croit(jean, (père(jupiter, cronos)))
Mardi 18 novembre 200877
Logiques modales (1)
vrai et faux : trop pauvres2 sortes de vrai :
universel (la terre est ronde)contingent (il fait beau)
itou pour le faux□ : nécessité et : possibilité□p =par définition ~~p
Mardi 18 novembre 200878
Logiques modales (2)
Implication stricte :(p → q) équivaut à (~(p ∧ ~q))
plusieurs logiques modales :ontique : nécessaire et possibledéontique : obligatoire et autoriséépistémique : savoir et compatibledoxastique : croire et compatibletemporelle : toujours et parfois
Mardi 18 novembre 200879
Mondes possibles [Hintikka 1962]
Logique classique : 1! monde
Logique modale : évaluation dans un ensemble de mondes W
□ : dans tous les mondes accessibles
: dans au moins un monde accessible
une relation d'accessibilité R :R ⊆ W x W
Mardi 18 novembre 200880
Extension de la logique des propositions :un ensemble de mondes : Wune relation binaire R sur Wune extension de Π :
Π : W x {atomes} → {vrai , faux}
interpréter une fbf modale : à partir de M=<W,R,Π> et dans un monde particulier w
Log. mod. : structure formelle
Mardi 18 novembre 200881
Log. mod. : sémantique formelleM,wi∣=p ssi Π(wi,p) = vrai
M,wi∣=~p ssi M,wi∣≠ p
M,wi∣=p∧q ssi M,wi∣=p et M,wi ∣=q
M,wi∣=p∨q ssi M,wi∣=p ou M,wi∣=q
M,wi∣=p→q ssi si M,wi∣=p alors M,wi∣=q
M,wi∣= □p ssi ∀wk si R(wi,wk) alors M,wk∣=p
M,wi∣= p ssi ∃wk/R(wi,wk) et M,wk∣=p
Mardi 18 novembre 200882
p□p p
p
~p
p ~p
p
~p ~p
□p ~p p
~p p
p
~p ~p
□p p p
~p p
~p
Log. mod. : exemples formels
bons exemples ?
Mardi 18 novembre 200883
Relation d'accessibilité (1)
La relation R dans M=<W,R,Π> peut être :réflexive : ∀ wi R(wi,wi) transitive : ∀ wi wk wn si R(wi,wk) et
R(wk,wn) alors R(wi,wn)terminante : si R est transitive et wi∈W alors
∃wk / R(wi,wk) et wk est terminalbien fondée : si R est transitive alors il n'existe pas de chemins infinis. Par exemple : R(wi,wk) R(wk,wn) R(wn,wp) ...
Mardi 18 novembre 200884
La relation R dans M=<W,R,Π> peut être :
sérielle : ∀wi ∃wk / R(wi,wk)
symétrique : ∀ wi wk si R(wi,wk) alors
R(wk,wi)
euclidienne : ∀wi wk wn si R(wi,wk) et
R(wi,wn) alors R(wk,wn)etc.
Relation d'accessibilité (2)
Mardi 18 novembre 200885
L'axiome de base :K: □(p → q) → (□p → □q) est valide
Autres axiomes :D: □p → pT: □p → pB: p → □p4: □p → □□p5: p → □p
Logiques modales : axiomes
Mardi 18 novembre 200886
Correspondance axiomes / R
Validité des axiomes :si R est réflexive : □p → psi R est transitive : □p → □□psi R est terminante : □p → □p si R est bien fondée : □(□p → p) → □p si R est symétrique : p → □psi R est sérielle : □p → psi R est euclidienne : p → □p
Mardi 18 novembre 200887
Log. modales : axiomatiquesAvec les axiomes K, D, 4 et 5 (KD45) on obtient la logique des croyances (cf. 4).
Si on y ajoute T (S5) on obtient la logique du savoir (cf. T).
Attention : par exemple S5 ne convient pas pour une logique déontique, ou temporelle (cf. 5). De même une logique temporelle a besoin de 4 (transitivité).
Mardi 18 novembre 200888
Pb. de l'omniscience logiqueen logique espitémique
Si p est valide alors □p est valide (si p est un théorème, alors il est vrai dans tous les mondes possibles, dont ceux accessibles).
'On' connaît toute formule valide (et donc toutes les tautologies) !
Avec K : 'on' connaît toutes les conséquences logiques de ses propres connaissances !!
Les croyances fausses sont interdites !!!
Mardi 18 novembre 200889
Représentation des K. : conclusion3 niveaux :
knowledge levelniveau le plus abstrait : celui dans lequel nous nous exprimons, nous pensons, …
logical levelniveau auquel seront codées formellement les connaissances
implementation levelniveau le plus bas = codage physique des connaissances
cf «knowledge level hypothesis» [Newell, 1982]
Mardi 18 novembre 200890
Plan du cours
Représentation des connaissances en IA :Généralités (informations, connaissances, ...)Réseaux sémantiquesFrames, scriptsLogiques classiquesRégles de production et systèmes expertsGraphes conceptuelsLogiques modalesL'ingénierie des connaissances ...