Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Extraction de la terminologiedans un processus global
de fouille de textes
Mathieu RocheEquipe Inférence et Apprentissage - LRI
11 avril 2005Bordeaux
2
La fouille de textes
Objectifs, exemples :– Recherche des pages pertinentes sur le Web.– Traitement automatique des courriels (spams, réponses
automatisées aux courriels, etc.).– Recherche des informations précises dans des textes
techniques (médecine, biologie, etc.).– Conception de systèmes de questions/réponses.
Approches : – méthodes linguistiques – méthodes statistiques – méthodes mixtes
3
Le processus global en fouille de textes [Kodratoff et al., JDS'03 ; Roche et al., IIPWM'04]
- - - - -
- - - - -
- - - - -
Corpus brut
- - - - -
- - - - -
- - - - -
Corpus normalisé
- - - - -
- - - - -
- - - - -
Corpus étiqueté
- - - - -
- - - - -
- - - - -
TermesClassification conceptuelle
- Règles d’association
- extraction d’informationspar patrons d’extraction
Normalisation Étiqueteur
Extraction des "termes"
Détection des traces de concepts
Extraction d’informations
Acquisition
4
Les corpus étudiés
Tests de psychologie - Ressources Humaines (Société PerformanSe) - 3784 Ko (en français).
Curriculum Vitæ (Groupe VediorBis) - 2470 Ko (en français).
Introductions d’articles sur la Fouille de Données (acquisition par un expert) - 369 Ko (en anglais).
Résumés d’articles sur la Biologie Moléculaire (acquisition par une base de données spécialisée) - 9424 Ko (en anglais).
=> Corpus journalistique de TREC'04 (Text REtrieval Conferences)
5
Problème spécifique étudié :les termes (1/2)
Importance de la caractérisation des termes
– Exemple : traduction automatique
Constitution européenne, article III-10 :
The right to vote and to stand as a candidate in elections...
Le droit de vote et d'éligibilité aux élections ...
6
Problème spécifique étudié : les termes (2/2)
Collocation (candidat-terme) : groupe de mots dont le sens global est déductible des unités composant le groupe [Clas 1994].
– Exemple, "maire de Paris"
Terme : collocation ayant des propriétés syntaxiques + trace linguistique de concepts pour
une tâche en cours.– Exemples, "intelligence artificielle" et "génie logiciel"
sont des termes– Exemple, "chalon sur saône" est-il un terme ?
7
Plan de l'exposé
1. Contexte
2. État de l'art
3. Système EXIT (EXtraction Itérative de la Terminologie)
4. Extraction de la terminologie : une approche d'apprentissage supervisé
8
État de l'art (1/5)
[Bourigault et Fabre 2000]XXSYNTEX
[Biskri et al. 2004]XXESATEC
[Nerima et al. 2003]XXFIPS
[Kilgarriff et Tugwel 2001]XXWASPBENCH
[Frantzi et al. 2000]XXC/NC VALUE
[Dagan et Church 1997]XXTERMIGHT
[Evans et Zhai 1996]XXCLARIT
[Daille 1994]XXACABIT
[Smadja 1993]XXXTRACT
[Frath et al. 2000]XMANTEX
[Enguehard 1993]XANA
[Silberztein1994 ; Ibekwe-SanJuan 2001]XINTEX
[Jacquemin 1996]XFASTR
[Bourigault 1993]XLEXTER
[David et Plante 1990]XTERMINO
référencesstatistiqueslinguistiquesSystèmes
9
État de l'art (2/5)
Exemple de système linguistique : FASTR [Jacquemin 1996]
Entrée : termes de base (congé de formation)Sortie : termes variants (congé annuel de formation).3 types de règles (linguistiques) :
Limite : nécessite de considérer une fenêtre plus grande [Ville-Ometz et al. 2004].Exemple : thymus gland thymus and adrenal gland
contexte : rat thymus and adrenal gland
knowledge discovery discovery of knowledgepermutationsMRI image MRI brain imageinsertionsassociation rule association and classification rules coordinations
10
État de l'art (3/5)
Exemple de système statistique : ANA [Enguehard 1993]
Module Familiarisation qui initialise la liste de bootstrap. – Exemple : {chef, contrat, rayon, etc.}
Module Découverte qui construit de manière incrémentale une liste de termes fréquents en utilisant les mots du bootstrap.Exemple : chef de rayon
Entrée : {chef, contrat, rayon, etc.}Sortie : {chef, contrat, chef de rayon, etc.}
11
État de l'art (4/5)
Exemple de système mixte : ACABIT [Daille 1994]
Extraction de collocations respectant des patrons d'extraction simples Nom-Nom, Nom-Préposition-Nom, Nom-Adjectif, etc.
Les termes variants sont détectés grâce à des règles morpho-syntaxiques (par exemple, centre de formation centre régional de formation).
Comptabilisation de tous les couples de mots en collocation notés par exemple (centre, formation).
Classement statistique des couples de mots.
12
État de l'art (5/5)
[Bourigault et Fabre 2000]XXSYNTEX
[Biskri et al. 2004]XXESATEC
[Nerima et al. 2003]XXFIPS
[Kilgarriff et Tugwel 2001]XXWASPBENCH
[Frantzi et al. 2000]XXC/NC VALUE
[Dagan et Church 1997]XXTERMIGHT
[Evans et Zhai 1996]XXCLARIT
[Daille 1994]XXACABIT
[Smadja 1993]XXXTRACT
[Frath et al. 2000]XMANTEX
[Enguehard 1993]XANA
[Silberztein1994 ; Ibekwe-SanJuan 2001]XINTEX
[Jacquemin 1996]XFASTR
[Bourigault 1993]XLEXTER
[David et Plante 1990]XTERMINO
référencesstatistiqueslinguistiquesSystèmes
Itératif
Coopératif
[Roche et al. 2004]XXEXIT
13
Plan de l'exposé
1. Contexte
2. État de l'art
3. Système EXIT (EXtraction Itérative de la Terminologie)
4. Extraction de la terminologie : une approche d'apprentissage supervisé
14
Présentation du système EXIT(EXtraction Itérative de la Terminologie)
Système mixte (linguistique et statistique)
Système itératif
Système coopératif
Extension du TF X IDF aux termes
15
3.1. Processus itératif (1/3) [Roche, EGC'03 ; Roche et al., IIPWM'04 ; Roche et al., JADT'04]
Processus itératif pour extraire les termes nominaux, adjectivaux et adverbiaux.
- - - - -
- - - - -
- - - - -
Corpus normalisé
- - - - -
- - - - -
- - - - -
Corpus étiqueté
- - - - -
- - - - -
- - - - -
Termes
ETIQ [Amrani et al. 04]
Introduction des termes avec "-"
Extraction
Exemple :
1ère itération : assistant de gestion2ème itération : assistant-de-gestion de production
16
3.1. Processus itératif (2/3)
Extraction des collocations typées
– Adjectif-Adjectif– Adverbe-Adverbe– Adverbe-Adjectif– Adjectif-Nom– Nom-Nom– ...
collocations de modifieurs
(adjectif et adverbe)
collocations nominales
exploitation des itérations
+ connaissances de l'expert
17
3.1. Processus itératif (3/3)
Paramètre CIP (Coefficient Itérations Précédentes)
But : utiliser les connaissances de l’expert CIP privilégie les collocations – avec des mots inclus dans les collocations pertinentes
des itérations précédentes.– avec des mots absents des collocations non pertinentes
des itérations précédentes.
=> pourcentage de collocations pertinentes amélioré(+2% à +16%).
18
Plan de l'exposé
1. Contexte
2. État de l'art
3. Système EXIT (EXtraction Itérative de la Terminologie)3.1. Processus itératif3.2. Mesures statistiques
3.2.1. État de l'art des mesures statistiques3.2.2. Évaluation expérimentale des mesures existantes3.2.3. Proposition de mesures hybrides
3.3. Extension du TF X IDF aux termes3.4. L'interface d'EXIT
4. Extraction de la terminologie : une approche d'apprentissage supervisé
19
3.2. Mesures statistiques[Roche et al., JFT'03 ; Roche et al., INFORSID'04]
144
...
...
74
...
67
...
43
...
4
3
2
1
NbCollocationsRang
...
...
69
...
64
63
...
50
...
4
3
2
1
NbCollocationsRang
chalon sur saône 4chalon sur saône 4
traitement de textes 57traitement de textes 57
mise en place 111mise en place 111
assistante de direction 60
hôtesse de caisse 28
assistante de direction 60
hôtesse de caisse 28
jéjunum de rat 3 jéjunum de rat 3
beurre de karité 3 beurre de karité 3
puy en velay 3 puy en velay 3
Rapport de Vraisemblance Information Mutuelle
20
3.2.1. État de l'art des mesures statistiques (1/4)
Exemples de mesures fondées sur l'Information MutuelleInformation Mutuelle [Church et Hanks 1990]
Information Mutuelle au Cube [Daille 1994]
))(log())(log()),((log.3),( 23 ynbxnbyxnbyxI −−=
)()(),(log),( 2 yPxPyxPyxIM =
))(log())(log()),((log),( 2 ynbxnbyxnbyxI −−=
21
3.2.1. État de l'art des mesures statistiques (2/4)
Mesure d’Association [Jacquemin 1997] : – isobarycentre des valeurs normalisées de l’information
mutuelle et du nombre d’occurrences.
),(min),,(max
),(min),,(max
),(21),(
21),(
qpnbmnbqpnbMnb
qpImIqpIMI
nbnbyxnb
IIyxIyxAss
mMmM
==
==
−+
−=
22
3.2.1. État de l'art des mesures statistiques (3/4)
Rapport de Vraisemblance [Dunning, 1993]
dcx' avec x' ≠ xbax
y' avec y' ≠ yy
RV (x,y) = a.log(a) + b.log(b) + c.log(c) + d.log(d) - (a+b).log(a+b)- (a+c).log(a+c) - (b+d).log(b+d) - (c+d).log(c+d) + (a+b+c+d).log(a+b+c+d)
23
3.2.1. État de l'art des mesures statistiques (4/4)
Mul
MC
Conv
J
SeSc
Ttest
Khi 2
RV
Dice
Ass
I3I
Mesures
[Manning et Scütze 1999; Curran et Moens 2002]Khi 2
[Manning et Scütze 1999; Curran et Moens 2002]T-test
[Sebag et Schoenauer 1988]Sebag - Schoenauer[Goodman et Smyth 1988]J-mesure
[Brin et al. 1997]Conviction[Azé et Kodratoff 2003]Moindre Contradiction
[Lallich et Teytaud 2004]Multiplicateur de Cote
[Dunning 1993]Rapport de Vraisemblance
[ Smadja et al. 1996]Coefficient de Dice
[Jacquemin 1997]Mesure d'Association
[Daille 1994]Information Mutuelle au Cube
[Church et Hanks 1990]Information Mutuelle
Références
TALN
Règles d'association
24
3.2.2. Évaluation expérimentale des mesures existantes (1/6)
Objectif : Choix d'une mesure pour une tâche en cours
Critères de performance :– Précision– Courbe d'élévation ("lift chart")– Rappel– Fscore– Courbes ROC
25
3.2.2. Évaluation expérimentale des mesures existantes (2/6)
Corpus de Fouille de Données (FD), des Ressources Humaines (RH) et des CVs.
4481628X34555768XNom-Adjectif
103478176129112602411Adjectif-Nom
162112231781982070Nom-Nom
3071268736344703313Nom-Prep-Nom
CVRHFDCVRHFD
Nb collocationsaprès élagage (3)
Nb collocations Exemples :emploi solidaritéaction communicationfichier clientservice achat…
26
3.2.2. Évaluation expérimentale des mesures existantes (3/6)
Les résultats présentés portent sur le corpus FD (relation Nom-Nom).
Sur ce corpus, 1074 termes sont associés à un concept par l'expert du domaine.
Protocole expérimental :– Expérimentations sur la tâche d’extraction des collocations
pertinentes pour la classification conceptuelle.– 12 mesures de qualité expérimentées.
27
3.2.2. Évaluation expérimentale des mesures existantes (4/6)
80%
60%
40%
20%
59.662.362.965.160.561.761.762.361.760.663.458.9
62.162.463.971.465.465.465.469.966.163.967.660.1
60.665.165.179.765.169.669.675.273.066.273.066.2
61.377.259.084.065.970.470.488.668.170.475.059.0
MulMCConvJSeScTtestKhi 2RVDice AssI3I
Précision (en %) sur le corpus de FD avec les collocations Nom-Nom.
28
3.2.2. Évaluation expérimentale des mesures existantes (5/6)
Courbes d'élévation avec le corpus FD.
20
30
40
50
60
70
80
90
100
0 50 100 150 200
Pre
cisi
on (
%)
Nombre de collocations fournies aux experts
Rapport de vraisemblance (RV)J mesure (J)
Information mutuelle au cube (I3)Information mutuelle (I)
29
3.2.2. Évaluation expérimentale des mesures existantes (6/6)
Résultats similaires avec les 3 autres corpus – CV – Ressources Humaines– Biologie
Bon comportement global des mesures suivantes :– Rapport de Vraisemblance– Information Mutuelle au Cube– J-mesure
30
3.2. Proposition de mesures hybrides (1/2)[Roche et al., INFORSID'04]
Motivations d'utiliser une nouvelle mesure.Ajout de λ à la mesure d’association :
Problème d'optimisation avec λ.=> λ* = 0
mMmM nbnbyxnb
IIyxIyxAss
−−+
−=
),()1(),(),( λλλ
=> Mise en place de la mesure OccRV
- classement selon le nombre d'occurrences- classement des collocations ayant le même nombre d'occurrences avec RV
31
3.2. Proposition de mesures hybrides (2/2)[Roche et al., INFORSID'04]
Courbes d'élévation avec le corpus FD.
20
30
40
50
60
70
80
90
100
0 50 100 150 200
Pre
cisi
on (
%)
Nombre de collocations fournies aux experts
Occ_RVRapport de vraisemblance (RV)
J mesure (J)Information mutuelle au cube (I3)
Information mutuelle (I)
32
Plan de l'exposé
1. Contexte
2. État de l'art
3. Système EXIT3.1. Processus itératif3.2. Mesures statistiques3.3. Extension du TF X IDF aux termes3.4. L'interface d'EXIT
4. Extraction de la terminologie : une approche d'apprentissage supervisé
33
3.3. Extension du TFXIDF pour les termes (1/2) [Roche, EGC'03 ; Roche et al., JADT'04]
∑ ∑=
−
=
−=
N
i
yxnb
ji
i jyxnbyxDiffTextes1
1),(
1)
10),(),(
texteiledansprésenteestncollocatiouneoùfoisdenombrenbcorpusdutextesdetotalnombreN
èmei :
.:
Paramètre privilégiant les collocations présentes dans des textes différents.
Paramètre DiffTextes
– Exemple : nombre de collocations : 3 nombre de textes : 1
Paramètre TF/IDF
DiffTextes = 2.7 ( 3-(3/10) )
34
3.3. Extension du TFXIDF pour les termes (2/2)
Expérimentation du paramètre DiffTextes sur le corpus FD.
80%
60%
40%
20%
+2.1+4.4+0.9+2.6
+2.5+0.1-1.5+1.6
-0.3+1.9+2.9+0.5
+4.4+4.3+4.4+1.7
OccRVJRVI3
Amélioration globale de la précision
35
3.4. L'interface d'EXIT [Roche et al., JADT'04; Heitz et al., EGC'05]
36
Plan de l'exposé
1. Contexte
2. État de l'art
3. Système EXIT
4. Extraction de la terminologie : une approche d'apprentissage supervisé
37
Approche supervisée pour apprendre une mesure [Roche et al., ROCAI'04 ; Azé et al., ICCI'04]
Entrée : quelques collocations étiquetées (positives ou négatives).Sortie : fonction de rang [Cohen et al. 1999]
Évaluation d’une fonction de rang : somme des rangs des exemplespositifs.
Minimiser la somme des rangs des exemples positifs ⇔ maximiserl'aire sous la courbe ROC
Σrangs = 25h2 : +++-+++---
AUC
Σrangs = 21h1: ++++++----
AUCArea Under the Curve
38
Protocole expérimental (1/2)
Données utilisées
9.190.91028Biologie
43.456.62822CV, rares
14.385.7376CV, fréquents
% collocationsnon pertinentes
% collocationspertinentes
# collocations
39
Protocole expérimental (2/2)
0.30 0.31 I - Information Mutuelle [Church and Hanks 1990]
0.31 0.39 Dice - Coefficient de Dice [Smadja et al. 1996]
0.35 0.40 I3 - Information Mutuelle au cube [Daille et al. 1998]
0.42 0.43 RV - Rapport de Vraisemblance [Dunning 1993]
0.57 0.58OccRV - Occurrence + RV [Roche et al. 2004]
AUCcollocation fréquentes
corpus de Biologie
AUCcollocations fréquentes
corpus de CVs
Critères statistiques
Combinaison de mesures
40
Algorithme ROGER (ROC based GEnetic learneR) (1/2)
Approche linéaireh(Coll) = ∑wi x mesi (Coll) avec (Coll, +/-)
Approche non linéaireh(Coll) = ∑wi x | mesi (Coll) - ci | avec (Coll, +/-)
Hypothèses : Aire sous la courbe ROCh → (rang(Coll), Etiq(Coll))classer les exemples par rangs croissants
++++-+---++-----+++-----------
+ : collocation pertinente- : collocation non pertinente
rang
41
Algorithme ROGER (2/2)
Protocole expérimental
– 90% Apprentissage, 10% Test, 10 validations croisées
– 21 exécutions indépendantes
– Soit h1,...,hT les meilleurs hypothèses retenues à partir de T (T=21) exécutions indépendantes de ROGER.
{ })..1),(()( TtxhMédianexBh t ==
42
Algorithme ROGER (2/2)
Validation expérimentale sur les ensembles tests
CV, fréquents
Biologie, fréquents
0.52 ± 0.070.42 ± 0.140.46 ± 0.130.61 ± 0.110.59 ± 0.100.58
0.32 ± 0.070.54 ± 0.120.51 ± 0.130.67 ± 0.050.61 ± 0.040.57
QuadratiqueGaussienLinéaireNon linéaireLinéaireOccRV
Bagged-SVMBagged-Roger
Etude de généralité– différents domaines– différentes langues– différentes fréquences des collocations
43
Étude de généralité (1) : apprentissageCVs / application Biologie (fréquents)
0.30 I 0.31 Dice0.35 I30.42 RV 0.57 OccRV
AUCCollocation fréquentesCorpus de Biologie
0.59
Linéaire
SVM Bagged-ROGER
0.710.63
Non LinéaireLinéaire0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Tru
e re
leva
nt r
ate
False relevant rate
Bagged-Roger non lineaireBagged-Roger lineaire
SVM lineaireOcc+L
taux de faux positifs
taux
de
vrai
s po
sitif
s
Autres noyaux donnent des résultats plus faibles
44
Étude de généralité (2) : apprentissageBiologie / validation CVs (fréquents)
0.31I 0.39Dice0.40 I30.43RV 0.58OccRV
AUCCollocations fréquentes
Corpus de CVs
0.65
Linéaire
SVM Bagged-ROGER
0.630.64
Non LinéaireLinéaire0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Tru
e re
leva
nt r
ate
False relevant rate
Bagged-Roger non lineaireBagged-Roger lineaire
SVM lineaireOcc+L
taux de faux positifs
taux
de
vrai
s po
sitif
s
45
Étude de généralité (3) : apprentissagecoll. fréquentes / application coll. rares (CVs)
0.29I 0.30I30.30 RV0.32Dice 0.37OccRV
AUCCollocations raresCorpus de CVs
Bagged-ROGERSVM
0.56
Linéaire
0.700.67
Non LinéaireLinéaire0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Tru
e re
leva
nt r
ate
False relevant rate
Bagged-Roger non lineaireBagged-Roger lineaire
SVM lineaireOcc+L
taux
de
vrai
s po
sitif
s
taux de faux positifs
46
Conclusions
La méthode supervisée proposée donne de bons résultats.
– bonne généralisation selon les langues, les domaines et la fréquence des collocations.
Principales caractéristiques d'EXIT :– Approche itérative– Approche coopérative– Ajout de paramètres
CIP (Coefficient Itérations Précédentes)critères statistiquesDiffTextes
47
Perspectives
Apprentissage actif : demander à l'expert de valider un nombre restreint de collocations à chaque exécution de ROGER.
Étude approfondie de la terminologie verbale.
Étude du bruit et du silence.
Étude de la terminologie à partir d'autres langues.
48
Annexe
49
Méthode (1/2)
Utilisation des courbes ROC (Receiver Operating Characteristic): courbe dont le taux de vrais positifs est représenté en ordonnées et le taux de faux positifs est représenté par l'axe des abscisses.
Avantage : pas de sensibilité dans le cas d'un déséquilibreentre les classes.
But : optimiser l'aire sous les courbes ROC (AUC) [Sebag et al. 2003].
0 1
1
taux de faux positifs
taux devrais positifs
50
Méthode (2/2)
Etape d'optimisationmaximiser l'aire sous la courbe ROC
⇔ minimiser la somme des rangs des exemples positifs
Σrangs = 21 Σrangs = 25 Σrangs = 26h1: ++++++---- h2 : +++-+++--- h3 : ++-+-++-+-
51
Exemple
Type de collocations : adj3 adj2 adj1 nom1 et adj3 adj2 adj1 nom2
Elagage : élagage 1 à la première itération et 2 à la deuxième
Extraction :
1. Type Adjectif-Adjectif
Itération 1 : adj3 adj2 (2 fois)
Itération 2 : adj3-adj2 adj1 (2 fois)
2. Type Adjectif-Nom
Itération 1 : adj3-adj2-adj1 nom1 (1 fois)
adj3-adj2-adj1 nom2 (1 fois)
Extraction :
1. Type Adjectif-Nom
Itération 1 : adj1 nom1 (1 fois)
adj1 nom2 (1 fois)
2. Type Adjectif-Adjectif
Itération 1 : adj3-adj2 (2 fois)
adj3-adj2-adj1-nom1
et adj3-adj2-adj1-nom1 non extraites
Exemple : latent semantic analysislatent semantic indexing