Indexation sémantique par coupes de redondance minimale dans une ontologie

Florian Seydoux

Jean-Cédric Chappelier

Artificial Intelligence Laboratory

Institute of Core Computing Science

EPFL / Switzerland

Plan

Indexation

Indexation sémantique

La ressource EDR

Utilisation d’ontologie pour l’indexation

Coupe de redondance minimum

Evaluation en RD (tâche ad-hoc)

Pré-traitements

Indexation

Résultats

Conclusions et travaux futurs

Indexation - cadre

Quoi : bases de documents textuels

But :	associer à chaque document un
descripteur (en vue d’une action)

Cadre RD vs:

Établir une correspondance (similarité) entre documents.

Indexation - principe

Baseline:

extraction du lexique des documents;

indexation par vecteurs de fréquence (occurrences).

Améliorations:

Filtrage par anti-dictionnaire, selon la fréquence, la CMS, etc.

Pondération des fréquences brutes (idf)

Stemming, lemmatisation, …

Ajout d’information pertinente
Suppression d’information inutile

Méthodes statistiques
Connaissances supplémentaires

Ontologie: EDR

Relations hypo/hypernonyme
# ~520’000

Dog

mouse

mice

dog

can

house

PN

N

N

N

N

N

N

N

* Incluant mots composés et expressions idiomatiques

Formes de surface*

# ~225’000

Dictionnaire
des mots
# ~420’000

Dictionnaire
des concepts

# ~506’000

Indexation sémantique

But:

Intégrer dans le modèle (tout ou
partie) de l’information additionnelle

Méthodes:

Indexer par un ensemble de
synonymes (synsets)

Indexer par la totalité des éléments de l’ontologie (concepts + hyperonymes)

Niveau intermédaire ?

Dans un arbre:

une coupe  est un ensemble de sommets {c1, c2, …, cn}

définissant une partition sur les feuilles.

Dans un graphe orienté sans cycle (DAG):

une coupe  sera définie comme un ensemble minimal*
de sommets {c1, c2, …, cn} couvrant	l’ensemble des
feuilles du graphe.

* Aucun sommet ne peut être retiré sans diminuer la couverture

Coupe  - définition

Est-ce une coupe ?

NON !

feuille non couverte

non minimale - deux sommets sont
liés par relation d’hyperonymie

Coupe  : objectif - critère

Objectifs:

Degré de description adapté aux documents à indexer

Limiter l’influence des différences de granularité dans l’ontologie

Coupe de redondance minimale

(théorie de l’information)

Propriétés:

Équilibre les probabilités d’occurrence des termes d’index

Limite le plus possible le nombre de termes

Coupe de redondance minimale

Redondance R() d’une coupe probabilisée :

Avec H() l’entropie de la coupe :

f(ci) : # occurrences* de ci dans D, la collection de doc.

|D| : # total d’occurrences dans D

* Occurrence de ci lorsque occurrence d’un mot couvert par ci

Critère:

maximiser

Critère MRC : problème

N’identifie pas une coupe unique

Optimum global « difficile » à calculer efficacement
(évaluer l’ensemble des coupes possible étant exclu)

	Requiert un critère supplémentaire quelconque
(selon le nombre de sommets, leur profondeur, au hasard, etc.)

	Renoncer à l’optimum global

Algorithme proposé :

Constituer la coupe par combinaison d’optimums locaux
obtenus par programmation dynamique

Algorithme

MRC(s) :

Si s est une feuille
retourner {s}
Sinon
Pour ci  s+
scuti := MRC(ci)
Pour i de 1 à n, avec n = |s+|)
Ti := (Uj1:n\i scutj) U {ci}
Tn+1 := Uj1:n scutj
Tn+2 := Uj1:n {cj}
retourner Argmaxi1:n+2 (R(Ti))

Avec s+ l'ensemble des successeurs de s

On initie la recherche avec MRC(racine)

Recherche docum. (synopsis)

Prétraitement documents et requêtes.

Calcul du jeu d’indexation sémantique, sur les documents.

Indexation des documents.

Indexation des requêtes.

Recherche des documents correspondant aux requêtes
 standard, au moyen du logiciel Smart.

Évaluation (au moyen d’un référentiel)
détermination des valeurs de précision et rappel
 également avec Smart.

Pretraitements

Filtrage des informations non textuelles
 suppression des éventuelles info.
additionnelles, concaténation des
éléments textuels.

Segmentation + lemmatisation +
étiquetage morpho-syntaxique
 au moyen du logiciel Sylex.

Filtrage selon CMS
 conservation des noms,
verbes et adjectifs.

In the safari park.

You can see monkeys and lions, as in a zoo, but a lot of others exotics animals, like elephants.

[M. Dupond, BaliTour, 1995]

In the safari park.
You can see monkeys and lions, as in a zoo, but a lot of others exotics animals, like elephants.

… (see, see, Vi) (monkeys, monkey, CN) (and, and, C) (lions, lion, CN) (as in, as, Ajd) (in, in, AdvPart) (a, a, D) (zoo, zoo, CN) (but, but, Cadv) …

(safari_park, safari_park, CN) (see, see, V) (monkeys, monkey, CN) (lions, lion, CN) (zoo, zoo, CN) (animals, animal, CN)

Coupe et indexation

Pour tous les documents

Extraction des graphies EDR.

Extraction des autre graphies
(indexation standard, lemmes).

Association des ‘mots’ (EDR) correspondants aux graphies

tous les mots (1ère série exp)

le plus fréquent uniquement (dans l’absolu) (2e série exp).

Expansion de l’ontologie des (concepts) hyperonymes.

Calcul d’une coupe de redondance minimale  jeu d’indexation sémantique.

Indexation des documents (sémantique + standard).

Idem pour les requêtes, sauf (4)

c1

c5

[c1, c2, c3, c4, c5]

(safari_park, safari_park, CN) (see, see, V) (monkeys, monkey, CN) (lions, lion, CN) (zoo, zoo, CN) (animals, animal, CN)

[safari_park, …]



Évaluation (1)

0.9053

0.5565

31612

0.8036

0.4536

70091

Concept 1er niveau

Concept coupe

Index complet

Baseline (lemmes)

0.5162

0.8760

0.8901

Rappel (30d)

0.2729

0.5143

0.5496

Précision (11Pt)

4814

53140

21815

Taille de l’index

Mots les plus fréquents

0.6026

0.7642

0.8901

Rappel (30d)

0.2683

0.4231

0.5496

Précision (11Pt)

6760

93707

21815

Taille de l’index

Tous les mots

Collection ‘Time’ (423 documents, 83 requêtes)
[articles de presse divers à caractère généraliste]

Autre approche ?

2.	Optimum global « difficile » à calculer efficacement
(évaluer l’ensemble des coupes possible étant exclu)

	Renoncer à l’optimum global

Algorithme proposé :

Rechercher une coupe de redondance minimale
locale dans le voisinage des feuilles

Évaluation (2)

0.5162

0.2729

4814

0.6026

0.2683

6760

Concept coupe A

0.9053

0.5565

31612

0.8036

0.4536

70091

Concept 1er niveau

Concept coupe B

Index complet

Baseline (lemmes)

0.8968

0.8760

0.8901

Rappel (30d)

0.5602

0.5143

0.5496

Précision (11Pt)

18465

53140

21815

Taille de l’index

Mots les plus fréquents

0.8904

0.7642

0.8901

Rappel (30d)

0.5512

0.4231

0.5496

Précision (11Pt)

18565

93707

21815

Taille de l’index

Tous les mots

Collection ‘Time’ (423 documents, 83 requêtes)
[articles de presse divers à caractère généraliste]

Conclusions & travaux futurs

Potentiel d’amélioration des traitements avec une indexation sémantique des documents !

Avec une ontologie adaptée aux thèmes des documents, coupe de redondance minimale (2e version) améliore les perf. d’une recherche, avec un jeu d’index réduit !

Nécessité d’une désambiguisation sémantique* !

Nécessité de valider l’approche sur des collections plus actuelles (taille et validation de pertinence) …

Critère d’information mutuelle ?

Liens sémantiques* autres que l’hyperonymie ?

Autres domaines d’application (classification, filtrage, topic extraction, etc) ?

Questions ?

[+] Nombre de coupes

Pour un arbre complet T, d’arité a, le nombre de coupes possible T à la profondeur p est donné (récursivement) par :

Ordre de

avec N=a p le nombre de feuilles,
et p la profondeur de l'arbre T

[+] EDR - données

relations Hypo/hyperonyme
# ~520’000

* Y.c. mots composés et expressions idiomatiques.

headword* link

syllable division

pronunciation and accent

part of speech

syntactic struct. (for compound)

word form, inflexion

grammatical attributes

concept link

general usage

frequency (word/headword)

headconcept (meaning - word)

explanation (phrasal)

Other binary relations :

object	 agent

a-object	 place

goal	 scene

cause	 implement

dict. des Mots

# ~420’000

dict. des Concepts

# ~506’000

[+] Ontologie : EDR (détails)

xyz

abc

de

bzz

hgh

Abc

Forme de surface EDR

Mots EDR

Concepts associés aux mots

Concepts hyperonymes

[+] EDR - données (exemple)

Headword *:	dictionary

Syllable division:	dic/tion/ar/y

Pronunciation:	d'ikSXen`eri:

Part of Speech:	Common Noun

Word form info:	Invariable Portion of Noun

Inflection info:	Inflection Pattern y

Gram. attrib:	Countable; Neutral gender;
Must occur with an article

Concept link:	0f6f4b

Frequency:	15/73

* Invariable portion of HW and adjacency attributes pair:
dictionar (Noun with Initial Consonant Sound, Invariable Portion of Noun Headword - followed by y and ies)

id :	0f6f4b

headconcept:	dictionary

explanation:	a reference book
providing a list of words in
some stated order, with their
forms, pronunciations,
meaning and uses

Dictionnaire des Mots

Dictionnaire
des Concepts

Bas de page: taln

Logo taln

Soit plus précis (cibler le propos), soit virer (fusion avec le suivant)

Manque une visualisation / exemple

manque Illustration

manque transition vers slide suivant, plus topos sur reseaux semantiques

Finalement tres moche... qqch de plus 'table' serait preferable (event slide exhaustif laisse de cote actuellement)

Remarques:

Dog -> constellation du chien

dog -> le chien

Ce qui explique les 2 formes de surface pointant vers 2 mots, chacun d’eux associés à un concept différent.

Element importants:

- pas tous les concepts sont dans la hierarchie hypo/hyper;

- il y a deux jeux d’ontologie [generale et technique (computer & information processing + champs liés (p.ex. electronique)] attention, ce n’est pas uniquement 2 dag hypo/hyper; tous les dicos (mots, concepts, relations hypo/hyper et relations suppl) sont disponible dans technical… c’est David qui avait fusionné les infos.

Dans le dico des mots, les fréquences donne le nb de fois ce mot est présent dans le corpus représentatif, et le nb de fois que la forme de surface est présente.

Dico de base: ~340’000 mots, 83% cpt

Dico technique: ~80’000 mots (overlap), 17% cpt

Cpt associés à mots:

dico de base ~38%, autres cpt~59%, hors hierarchie:~3% (noms propres)

dico technique: ~14% mots, 86% cpt entre eux

On peut voir la un meme but que lemmatisation : integrer de l’information additionnel dans le model

But: réduire la perplexité des synonymes (factorisation)

Animation super moche – a refaire (avec visibilité du jeu d'index constituê)

La non-minimalité n’est pas ‘très’ grave pour nous.

La mauvaise coupe n'apporte pas grand chose – l'anim. n'est pas tres au point (rendre plus visible les sommets concernés)

1 et 2, exemple avec branche (médecine) surdéveloppée, mais pas de documents y-relatifs, ou au contraire,

2 branches surdéveloppées, et des documents traitant de l’une uniquement : degré de description plus fin nécessaire dans ce cas.

Propriétés: découle de la maximisation de l’entropie

Manque sérieusement une vraie anim qui montre l'algo en fonctionnement.

Problème: DAG structure: implique de ‘nettoyer’ les coupes obtenue par combinaison (les subordonnés sont retirés)

Optimisation: les fils feuilles sont nécessairement dans la coupe (constitution d’un préfixe)

Autre problème: avec les nœuds à fort branchage (cas de EDR), la combinatoire reste grande

-> dans ce cas, on court-circuite l’évaluation, en gardant la combinaison Tn+1 (sous-coupes)

Attention – changements frequents / slide pas necessairement a jour

Rem: le filtrage par CMS ne se justifie pas (reproductibilite)

-> event. le faire avec les tag EDR

necessite de plus expliciter le deroulement des op,

** en particulier avec les rq, en re-indexation (comment on retourne sur la coupe) **

!! plus d'eval !!!!

(graphe prec/rp)

infos sur le schema de ponderation ?

anim pour illustrer le fct de l'algo

Tester sur des bases plus appropriées, autres domaines

+ autre critère de choix de la coupe

+ autre méthodes pour intégrer l’info au modèle (agire sur les similarités plutot que l’indexation (optique IR))

+ intégrer plus d’info sémantique (méronymes, antonymes, lien thématique)

Dans le dico des mots, les fréquences donne le nb de fois ce mot est présent dans le corpus représentatif, et le nb de fois que la forme de surface est présente.

Dico de base: ~340’000 mots, 83% des cpt

Dico technique: ~80’000 mots (overlap), 17% des cpt

Cpt associés à mots:

dico de base ~38%, autres cpt~59%, hors hierarchie:~3% (noms propres)

dico technique: ~14% mots, 86% cpt entre eux

Les mots sont l’unité centrale; ils pointent chacun:

- 1 forme de surface

- 1 concept associé

Les concepts associés aux mots peuvent être des concepts hors hiérarchie (gris), hyponyme uniquement (jaune), hyper&hyponyms (violet)

Les concepts ‘supplémentaires’ (non-associé à un mot) sont dans la hiérarchie, hyperonymes & hyponyme (sauf root)

[todo] idéalement, il faudrait aussi donner la hierarchie du concept (via l’outil de david?),

Et les liens sémantiques additionnels…

Conceptual Document Indexing Using Semantic Dictionary

2005-06-06T22:34:49