Master Web Intelligence ICM - Option Informatique 2008

Mardi 18 novembre 20081

Master Web IntelligenceICM - Option Informatique

2008/2009

Web Sémantique

Philippe BeauneENSM-SE/G2I/SMA

mailto : [email protected]


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


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 ...


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


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 ?


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)


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

http://www.scientificamerican.com/

http://www.emse.fr/~beaune/websem


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


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


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.


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.


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.


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


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, ...)


Web sémantique : structuration











http://ww

w.w3.org

/2007/03

/layerCak

e.png


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, ...


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.


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


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


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


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, ...


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


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.


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.


Formalisme de représentation

Rechercher la justesse de représentationrichesserigueursouplesse

et l'efficacité permettre les traitementsproblèmes de complexitépermettre les évolutions


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, ...


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), …


L'arbre de Porphyre


KL-ONE (70's)


Héritage, conflits


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


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


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)


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


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


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


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»


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, ...)


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


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


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


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.


Exemplede scriptcélèbre


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).


Exemple emprunté à J. Lehuen (Univ Le Mans)



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


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.


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


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


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)


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


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


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


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


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 connaissances pour produire de nouveaux faits (éven- tuellement de nouvelles connaissances)


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


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


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.


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


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


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.


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


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


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".

http://www.hum.auc.dk/cg/Module_I/1142.html#Agnt


Graphes conceptuels : exemple


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


Graphes conceptuels : exemple

simplification}


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/

http://www.hum.auc.dk/cg/

http://www.jfsowa.com/


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


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)))


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


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


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


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


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


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 ?


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) ...


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)


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


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


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é).


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 !!!


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]


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 ...

Documents

Master Web Intelligence ICM - Option Informatique 2008