Upload
johnna
View
26
Download
0
Embed Size (px)
DESCRIPTION
Annotations sémantiques pour la localisation de ressources par des graphes étiquetés. Michel Chein LIRMM (Université Montpellier 2 et CNRS ). Une annotation : qu’est-ce que c’est ? (1). Annotation de quelque chose : annotation et ressource (« document enrichment ») - PowerPoint PPT Presentation
Citation preview
COSI'07, Oran, juin 2007 1
Annotations sémantiques
pour la localisation de ressources par des graphes étiquetésMichel Chein
LIRMM (Université Montpellier 2 et CNRS )
COSI'07, Oran, juin 2007 2
Une annotation : qu’est-ce que c’est ? (1)
Annotation de quelque chose : annotation et ressource (« document enrichment »)
Annotation et metadonnées objectives et subjectives
Annotation sémantique : pas seulement contenu, mais aussi commentaire, remarque, usage, …(ex. dans Annotea rdf:type Annotation a 7 sous-classes prédéfinies : Advice, Change, Comment, Example,
Explanation, Question, et SeeAlso)
COSI'07, Oran, juin 2007 3
Une annotation : qu’est-ce que c’est ? (2)
Annotation = connaissance sur une ressource : annotation sur des annotations ( l’auteur de l’annotation #33 est un imbécile, l’auteur de la ressource R11 a été financé par l’auteur de l’annotation #12, …)
Base d’annotations sur un ensemble de ressources annotations formelles, ressources informelles (textes, images, videos,…) ou formelles (BdD, base d’annotations, base de composants, …), entre base de connaissances et index sophistiqué
COSI'07, Oran, juin 2007 4
Comment représenter des annotations ? (1)
Il n’y a pas de « sens » dans une annotation sémantique seulement des connaissances au sens IA, i.e. des structures de données auxquelles un être humain peut donner un sens, les mettre en relation avec le « monde réel »
Knowledge-based (souvent restreint à ontology-based) semantic mark-up
COSI'07, Oran, juin 2007 5
Comment représenter des annotations ? (2)
Annotations représentées dans un langage formel de représentation de connaissances (sinon les annotations ne sont que des documents en langue naturelle ex. résumés…),
ontologies ( « domain ontologies » et pas « visual descriptor ontology » ou « multimedia structure ontology »)
connaissances non explicites dans les ressources (pour compléter des annotations)
contextes (ce qui est supposé connu du lecteur) contraintes (pour assurer une certaine cohérence des
annotations) Pour pouvoir faire des raisonnements (déduction et autres) :
réponses à une requête, complétion d’une annotation, vérification de contraintes, …
COSI'07, Oran, juin 2007 6
Quelques autres questions importantes liens ressources/annotations : deux bases une de
ressources et une d’annotations, ou annotation dans les ressources
construction : manuelle, automatique, assistée, outil pour parcourir et fractionner les ressources
construction/usage collectif/individuel de la base d’annotations
qui construit les connaissances du système (ontologies)? qui construit les annotations (spécialistes d’un domaine,
spécialiste de documentation, tout le monde, …) ?
COSI'07, Oran, juin 2007 7
Pourquoi des annotations : à quoi ça sert ? Catégorisation, Certification Recherche d’information « Semantic annotation is a
specific metadata generation and usage schema, aiming to enable new information access methods and to extend the existing ones. » (Kiryakov)
Publication assistée sélectionner des parties de documents, les réutiliser pour construire un nouveau document mulimédia (recontextualisation)
Valeur ajoutée aux ressources
COSI'07, Oran, juin 2007 8
Et le web « sémantique » ?
Ajouter des connaissances (RDF) aux documents du web
Etendre HTML pour décorer un document HTML par des connaissances (semantic XHTML, langage XTiger au dessus d’Amaya)
Notre approche est « meilleure » que RDF mais …
COSI'07, Oran, juin 2007 9
…tout aussi insatisfaisante que RDF pour le web
« sémantique » !
COSI'07, Oran, juin 2007 10
Ce dont je vais parler
un langage permettant de définir des annotations sémantiques, des contraintes, des règles (e.g. connaissances implicites), et des requêtes
une méthodologie pour aider à construire des annotations
un mot sur les algorithmes de recherche tout doit être simple à construire et à comprendre (y
compris les raisonnements, i.e. le pourquoi des réponses fournies) car Nimporteki doit pouvoir construire des annotations et utiliser le système
COSI'07, Oran, juin 2007 11
Equipe RCR
Le modèle est basé sur un modèle de représentation de connaissances développé au LIRMM depuis 1992 M.-L. Mugnier, M. Leclère, O. Haemmerlé, B.Carbonneill, O. Guinaldo, E. Salvat, D. Genest, J.-F. Baget, …
et des outils COGITO, COGITANT, COGUI, A. Gutierrez, N. Moreau
Utilisés dans des applications en annotation et RI dans le cadre de divers projets :
MOGADOR (recherche documentaire, ABES et BNF) OPALES (annotations de vidéos, INA et MSH) SAPHIR (annotations de vidéos pour publication assistée, INA et
MSH) LOGOS (annotations de tout type de documents pour e-learning) EIFFEL (RI tourisme)
COSI'07, Oran, juin 2007 12
COSI'07, Oran, juin 2007 13
COSI'07, Oran, juin 2007 14
COSI'07, Oran, juin 2007 15
1
1
1
1
1
1
1
1
computer sc.
instragt
circ
circ
circ
agt
journalists
politic. discourses
medias
politicians
obj
ling. analysis
2
2
2
2
2
22
“L’analyse du discours assistée par ordinateur : concepts, méthodes, outils”
COSI'07, Oran, juin 2007 16
1
2
1
2
2Chat : Garfield Canapé
Couleur : RougeBouteilleCoussin
Lait
entre
sur
cont.
attr.
1
32
12
tenir
1
Vocabulaire
• ens. ordonnéde concepts
• ens. ordonnéde relations
• marqueurs individuels [...]
COSI'07, Oran, juin 2007 17
2
1
2
Chat : Garfield Canapé
Couleur : Rouge
Couleur : Rouge
Objet
Chat
2Chat : Garfield Canapésur 1
1 1
Couleur : RougeBouteilleCoussin
Lait
entre
cont.
attr.32
12
tenir
G
donc Q se déduit de G (et du vocabulaire)
2
1
proche
1
2
Q
attr.
Une requête simple
COSI'07, Oran, juin 2007 18
Sémantique logique
xyzu Chat(Garfield) Canapé(x) Coussin(y) Bouteille(z) Lait(u) Couleur(Rouge) sur(Garfield,x) entre(Garfield,y,z) tenir(Garfield,z) attr(x,Rouge) cont(z,u)
x
y
u
zRouge
Garfield
1
2
1
2
2Chat : Garfield Canapé
Couleur : RougeBouteilleCoussin
Lait
entre
sur
cont.
attr.
1
32
12
tenir
1
ainsi que les formules du vocabulaire traduisant les ordres partiels
COSI'07, Oran, juin 2007 19
Exemple d’ontologie simple
Universel
EtreVivant Document
Image VidéoPersonne
Homme
Femme
Journaliste
estAuteurDe(Personne,Document)
estRéalisateurDe(Personne,Vidéo)
PPDA Journaliste
http://www.icones.bg/ic37.jpg Image
X
X
X
COSI'07, Oran, juin 2007 20
COSI'07, Oran, juin 2007 21
Ontologie
Une ontologie (simple) GC : Tc un ensemble de types de concepts ordonnés B ensemble d’ensembles de types de concepts
interdits Tr un ensemble de types de relations ordonnés Sr : TrTc* définissant la signature des relations I un ensemble d’individus ontologiques
COSI'07, Oran, juin 2007 22
Exemple (Règles)
« Tout chercheur est membre d'une équipe »
« La relation 'collabore' est symétrique »
Chercheur membre EquipeR1
Person Personcoll
coll
R2
x (Chercheur (x) y Equipe(y) membre(x,y))
x y ( coll(x,y) coll(y,x))
COSI'07, Oran, juin 2007 23
Exemple (Contraintes)
Bureau
aff aff
Person Person
Equipe
membre membre
Contrainte négative"Synergie inter-équipes"
Bureau
aff aff
Person Person
Equipe
membre membre
Contrainte positive"Cloisonnement"
COSI'07, Oran, juin 2007 24
Langage de données et de requêtes Fondamentalement des graphes bipartis étiquetés
Une classe de sommets représentant des entités (analogie : mots-clés)
l’autre classe des relations entre ces entités (analogie : relations sémantiques entre les mots-clés, agent , instrument, …)
les étiquettes sont ordonnées (spéc./géné.)
Pourquoi des graphes étiquetés ? un langage utilisable par des non informaticiens, facilement
visualisable suffisamment riche et extensible bons algorithmes
COSI'07, Oran, juin 2007 25
Project:P
Researcher Researcher:K Researcher:J
Office:#124
Office
member
in in
in
near
Query Q Fact G
member
Person Person
member
Project Project
Q: “Are there people working together, who are each member of a project?”
worksWith
worksWith
member member
COSI'07, Oran, juin 2007 26
Project:P
Researcher Researcher:K Researcher:J
Office:#124
Office
member member member
in in
inworksWith
near
Query Q Fact G
member
worksWith
Person Person
member
Project Project
COSI'07, Oran, juin 2007 27
Homomorphisme de graphes• Un homomorphisme h de G=(VG, EG) dans H=(VH,EH) est une application de VG dans VH qui préserve les arcs :
si (x,y) est dans EG, alors (h(x),h(y)) est dans EH
a
b
cd
3
1 2
• Homomorphisme de graphes bipartis étiquetés ajoutent
des conditions sur la structure et sur les étiquettes labels
G
H
COSI'07, Oran, juin 2007 28
Spécialisation/Généralisationrelation de préordre sur les SGs
G H (H G)
ssi il existe un homomorphisme de G dans H
T Tp T Tp
p T
T Tp
p T
Tp
p
G est plus général que H
H est plus spécifique que G
COSI'07, Oran, juin 2007 29
Base logique
Vocabulaire S
t < t’r < r’
SGs
predicats, constantesx t(x) t’(x)x1... xk r(x1,..., xk) r’(x1,..., xk) ( , ) fbfs
Consistance: si G H alors (G) est déductible de (H), (S)
Complétude: si (G) est déductible de (H), (S) alors G H
• le SG modèle est équivalent au fragment FOL( , ) (on peut se débarasser des quantificateurs universels)
• Homomorphisme équivalent à la déduction
COSI'07, Oran, juin 2007 30
Problèmes équivalents Hom de graphes étiquetésEtant donnés deux SGs G et H, H G?
Hom d’hypergraphes étiquetés Hom de structure relationnelle CSP
Un réseau de contraintes est-il satisfiable? Inclusion de requêtes conjonctives
Etant données deux requêtes conjonctives Q et Q’, Q contient-elle Q’ ?
Déduction dans le fragment positif, conjonctif et existentiel de FOL
COSI'07, Oran, juin 2007 31
Une extension : la négation atomique
Deux problèmes de décision fondamentaux :
- Déduction (Q se déduit-il de la base B?)
- Existence d'une réponse (B contient-elle une réponse définie à Q?)
Sur les SGs ces problèmes sont les mêmesAvec négation ce n’est plus le cas
COSI'07, Oran, juin 2007 32
Cube : A
sur
vert
¬vert
Cube : B
sur
Cube : C
Cube
sur
vert
Objet ¬vert
G
C
B
A
Existence d'une réponse : non
Déduction : oui
Q[hypothèse du monde ouvert]
(correspond à la déduction en logique intuitionniste)
?
vert ¬vert
Négation atomique dans les SGs
COSI'07, Oran, juin 2007 33
Une autre extension : les graphes typés emboîtés
les graphes sont typés par un type d’annotation (e.g. contenu, thème, rhétorique, commentaire, …)
le vocabulaire est décomposé en modules, un module définit le vocabulaire utilisable pour un type d’annotation
structure hiérarchique : on peut mettre une boîte (un graphe) dans une boîte (un sommet concept)
COSI'07, Oran, juin 2007 34
Différents contenus sémantiques Le contenu sémantique d’une annotation peut être décrit selon
plusieurs domaines Rhétorique Pragmatique Thématique Médias MatièresAV Tournage Physique
A tout « domaine » est associé une ontologie (de domaine) Contrainte Les graphes dans un type d’emboîtement sont
construits en utilisant uniquement le vocabulaire de l’ontologie de domaine associée à ce type de graphes
COSI'07, Oran, juin 2007 35
Une seule ontologie (modulaire) Deux domaines peuvent partager une partie de leur
vocabulaire Ex. des JT : le thème d’une séquence est une personne
(thématique), et cette personne est à l’écran (Médias) Tous les graphes d’une base d’annotation sont
construits relativement à une unique ontologie mais chaque emboîtement est relatif à une sous-ontologie de cette ontologie
COSI'07, Oran, juin 2007 36
Ontologie modulaire
Universel
EtreVivant Document
Image VidéoPersonne
Homme
Femme
Journaliste
X
X
X
Personnes
Medias
COSI'07, Oran, juin 2007 37
Annotation : idD01
Physique
Icon : http...ic37.jpg Anonym : *
Entity : Chania
Wood : *
Oil : * School : Y
Century : XVIe
createdBy
medium
location
support
belongsTo
timeLoc
Description
Entity : Virgin Baby :TheChildholding
COSI'07, Oran, juin 2007 38
Graphe final (base d’annotations)
Annotation : idD01Physique
Icon : http...ic37.jpg Anonym : *
Entity : Chania
Wood : *
Oil : *School : Y
Century : XVIe
createdBy
medium
location
support
belongsTo
timeLoc
Description
Entity : Virgin Baby :TheChildholding
Person : PatrickCauteur
Description
Entity : VirginEye :* isPartOf
Annotation : idD02
auteur
détail
COSI'07, Oran, juin 2007 39
Méthodologie pour construire des annotations
Une ontologie (vocabulaire, contraintes, règles) partagée
Des (graphes) patrons d’annotation pour un type
Des (graphes) prototypiques pour un type de concept ou de relation
Des graphes individuels
COSI'07, Oran, juin 2007 40
Graphe patron
COSI'07, Oran, juin 2007 41
Graphe prototypique
COSI'07, Oran, juin 2007 42
Prototype d’une relation
COSI'07, Oran, juin 2007 43
Réponses approchées, plausibles, partielles se limiter aux réponses exactes silence réponses inexactes basées sur le principe
d’incertitude de van Rijsbergen “ Given any two sentences d and q the
measure of the uncertainty of d → q relative to a knowledge set, is determined by the minimal transformation of d in d’, to establish the truth of d’ → q ”
rend “vivante” la base d’annotations
COSI'07, Oran, juin 2007 44
Les transformations
Substitutions d’une étiquette compatible à une autre réponses approchées
Identifications de deux sommets (joints) (+ substitutions) réponses plausibles ( nbre de joints)
Ajouts de concepts réponses partielles ( nbre de concepts ajoutés, nbre de relations ajoutées)
COSI'07, Oran, juin 2007 45
Mise en oeuvre (1)
MOGADOR thesaurus RAMEAU 400.000 termes UF (Used For), SA (See Also), BT
(Broader Topic), NT (Narrower Topic), RT (Related Topic)
12 relations (obj, time, loc, geo, agt, comp, …)
COSI'07, Oran, juin 2007 46
compatible-term(x,y) : il existe un chemin de y à x tel que sa lg 4, le nbre de RT est 1, le nbre de NT et le nbre de BT sont 2, le nbre de SA et le nbre de UF sont 3
compatible-relation(x,y) : 2 relations qcq sont compatibles.
acceptable-sequence(s) quasi-ordre total s ≤ s’ (fonction de ranking)
Mise en oeuvre (2)
COSI'07, Oran, juin 2007 47
C0 séquence vide. C1 séquences de substitutions de termes utilisant SA. C2 séquences de subst. de termes utilisant SA and UF. C3 séquences de subst. de termes utilisant SA, UF et BT. C4 séquences de subst. de termes utilisant SA, UF, BT et NT. C5 séquences de subst. de termes utilisant les 5 relations. C6 séquences de subst. de termes ou de relations . C0 C1 C2 C3 C4 C5 C6 s Ci -Ci−1, i = 1, ..., 6, et s’ Cj et j <i s’ < s s, s’ Ci -Ci−1, s’ ≤ s ssi lg(s’) ≤ lg(s)
Mise en oeuvre (3)
COSI'07, Oran, juin 2007 48
C7 séquences de substitutions d’étiquettes et de joints.
C6 C7.
C8 séquences de substitutions d’étiquettes et de joints et d’ajouts de relations.
C7 C8.
C9 séquences de substitutions d’étiquettes et de joints et d’ajouts de termes ou de relations.
C8 C9 s Ci -Ci−1, i = 1, ..., 9, et d s Cj et j < i , s’ < s
s, s’ Ci -Ci−1, s’ ≤ s ssi lg(s’) ≤ lg(s)
Mise en oeuvre (4)
COSI'07, Oran, juin 2007 49
“Expression d’idées politiques dans la presse écrite”
1political ideas circ newspapers2
1
1
1
1
1
1
1
1
computer sc.
instragt
circ
circ
circ
agt
journalists
politic. discourses
medias
politicians
obj
ling. analysis
2
2
2
2
2
22
COSI'07, Oran, juin 2007 50
1
1
1
1
1
1
11
computer sc.
instragt
circ
circ
circ
agt
journalists
politic. ideas
medias
politicians
obj
ling. analysis
pol. ideas BT pol. sciences NT pol. communication NT pol. language UF pol. discourses
COSI'07, Oran, juin 2007 51
1
1
1
1
1
1
11
computer sc.
instragt
circ
circ
circ
agt
journalists
politic. ideas
newspapers
politicians
obj
ling. analysis
newspapers SA news BT media
COSI'07, Oran, juin 2007 52
1
1
1
1
1
1
11
computer sc.
instragt
circ
circ
circ
agt
journalists
politic. ideas
newspapers
politicians
obj
ling. analysis
1
polit. ideas circ newspaper
COSI'07, Oran, juin 2007 53
Conclusion
les limites : construction à la main (guidée) contrôlée et enrichie automatiquement par des contraintes et des règles. Normal pour des commentaires, très coûteux pour des indexations. La valeur ajoutée doit être importante.
utilisation : importance des commentaires non constructibles automatiquement (ex. rhétorique, car non présente explicitement dans le document) ou indexation automatique non réalisable (aujourd’hui ex. images)
demain : utilisation plus large dès que l’on saura automatiquement associer des formules logiques à des documents.
COSI'07, Oran, juin 2007 54
Améliorations
Modèles hybrides SGBD et GCs, DLs et GCs Apprentissage automatique de connaissanes
prototypiques Méthodes de recherches approchées utilisant
des connaissances prototypiques Dynamicité du vocabulaire Intégration de l’utilisateur dans la boucle etc.
COSI'07, Oran, juin 2007 55
Références récentes et adresses http://www.lirmm.fr/~mugnier http://www.lirmm.fr/cogui/doc/getting_started
_with_cogui_onto5.htm http://cogitant.sourceforge.net Genest, D., Chein, M. (2005), A Content-search Information
Retrieval Process Based on Knowledge Graphs and the Uncertainty Principle. Knowledge and Information Systems, (KAIS), vol. 8, n° 3, 2005
Moreau, N., Leclère M., Chein M., Gutierrez A. (2007), Formal and Graphical Annotations For Digital Objects, SADPI’07, Intern. Work. Semantically Aware Document Processing and Indexing, Montpellier, May 2007 (le même en français à IC’07)
COSI'07, Oran, juin 2007 56
COSI'07, Oran, juin 2007 57
COSI'07, Oran, juin 2007 58
COSI'07, Oran, juin 2007 59
COSI'07, Oran, juin 2007 60
Graphe prototypique
COSI'07, Oran, juin 2007 61
Une règle
COSI'07, Oran, juin 2007 62
SG
SR
+règles
SGC
+contraintes
SRC SEC
SREC
faits
+règles d'inférence +règles d'évolution
Décidabilité/complexité des problèmes de baseAlgorithmes efficaces à base de graphesSémantique logique, expressivité
Résultats théoriques : Famille SG
COSI'07, Oran, juin 2007 63
Famille SG : décidabilité/complexité (1)
NP-Complet
2P-Complet
indécidable
Des cas particuliers décidables?
SG
SR
+règles
SGC
+contraintes
SRC SEC
SREC
faits
+règles d'inférence +règles d'évolution
[ problème de déduction ]
semi-décidable
semi-décidable
COSI'07, Oran, juin 2007 64
NP-Complet
Si ensemble de règles à expansion finie : tous problèmes décidables
En particulier, règles range-restricted (= règles Datalog usuelles)
2P-Complet
2P-Complet
3P-Complet
3P-Complet
SG
SR SGC
+contraintes
SRC SEC
SREC
faits
NP-Complet
Famille SG : décidabilité/complexité (2)
COSI'07, Oran, juin 2007 65
Graphe orienté étiqueté aux arcs
2
Chat : Garfield
1 1
BouteilleCoussin
entre 32
tenir
chatanimal entité
G
coussin entitéentitébouteille
1
2
32
1entre
rel3
tenirrel2
COSI'07, Oran, juin 2007 66
Un théorème fondamental de Hell Système relationnel binaire = multigraphe
orienté avec arcs étiquetés t.q. le multigraphe partiel des arcs avec même étiquette est un graphe.
Une étiquette correspond à un symbole de relation binaire
Les arcs d’une même étiquette correspondent aux couples de la relation associée à la couleur
COSI'07, Oran, juin 2007 67
L’opération de remplacement d’une étiquette
G*J On remplace tous les arcs du graphe G ayant
la même étiquette par le graphe J qui est sans étiquette et a deux sommets distingués
G Jxy
G*Ja b c
x y
a bc
COSI'07, Oran, juin 2007 68
Plusieurs étiquettes Chaque étiquette est remplacée par un Jk
qui constituent une famille de graphes de remplacement rigides, forts et incomparables
Rigide = pas d’autre endomorphisme que l’identité
Fort = pour tout G et tout homomorphisme f de J dans G*J, f(J) est inclus dans une copie Jxy de J
COSI'07, Oran, juin 2007 69
x y
x’ y’
J1
J2
G
G*{J1,J2}
Exemple
COSI'07, Oran, juin 2007 70
Le théorème de Hell Il existe un « mapping » linéaire qui transforme le
pb de l’homomorphisme de graphes étiquetés dans celui de l’homomorphisme de graphes non étiquetés qui réalise une bijection entre les ensembles d’homomorphismes.
G et H deux multi-graphe étiquetés h : {multi-graphes étiquetés}{graphes} Taille (h(g)) O(#étiqtaille(g)) Bijection entre Hom(G,H) et Hom(h(G),h(H))
h : GG*{J1,…,Jk}
COSI'07, Oran, juin 2007 71
Catégories
Le théorème de Pultr et Trnkova (1980) Toute catégorie concrête peut être
représentée dans la catégorie Graphe (des graphes non orientés dont l’ensemble des sommets est une partie finie des naturels)
(Catégorie concrête = sous-catégorie de la catégorie Ensemble celle des ensembles finis munis des applications comme morphismes)