1 Mettre tout ça ensemble Exemple de problème: Attachement du SP Le problème Méthodes possibles Implémentation en Perl Évaluation

1

Mettre tout ça ensemble

Exemple de problème: Attachement du SP

• Le problème

• Méthodes possibles

• Implémentation en Perl

• Évaluation

2

Le problème

SP complément du nom ou du verbe?

J’ai vu l’homme avec les jumelles

J’ai vu l’homme au chapeau

Je mange la pizza avec la fourchette

Je mange la pizza au fromage

Je mange la pizza avec une bière

3

Pourquoi faut-il résoudre ce problème?

Environ 70% des erreurs de construction de structure syntaxique pendant une analyse automatique sont des erreurs d’attachement de SP.

Donc, si on améliorait la performance de la résolution de ce problème, toute l’analyse serait améliorée.

4

Comment faut-il résoudre ce problème?

J’ai vu l’homme avec les jumelles

J’ai vu l’homme au chapeau

Je mange la pizza avec la fourchette

Je mange la pizza au fromage

Je mange la pizza avec une bière

Y-a-t-il des régularités visibles qui distinguent entre attachement au nom et attachement au verbe?

• L’information lexicale, quels mots sont utilisés dans la phrase, est cruciale.

5

Attachement du SP: méthode manuelle

1. Récolte d’un petit corpus d’exemples de SPs avec la distinction

entre complément du nom ou complément du verbe. En général, par introspection ou récolte non-systématique de données observationnelles

2. Création de règles régissant les différences entre ces deux cas de figure par observation jusqu’à couverture des toutes les données observées

3. Implémentation d’un système et extension aux exemples qui n’avaient pas été prévus

6

Méthode manuelle: problèmes

1. Récolte non-systématique des données observationnelles, donc

pas garantie de représentativité

2. Possibilité de complexité excessive du système de règles, surtout si on veut tenir compte des mots

3. Pas de tests systématiques, ni de tests sur un ensemble séparé d’exemples, pas d’évaluation quantitative, difficile à comparer avec d’autres méthodes

7

Structure d’une expérience informatique

Corpus d’entraînement filtre données d’entraînement

apprenant

modèle de classification

Corpus d’entraînement filtre données test classificateur

données test classifiées

évaluateur

mésures de performance

8

Mesures de performance : exactitude

Supposons qu’on ait un problème d’apprentissage automatique où il s’agit d’identifier, parmi un certain nombre d’objets, lesquels ont la propriété X. Pour chaque objet, on obtient à l’aide d’un modèle statistique la réponse « oui » ou la réponse « non ».

Comment peut-on évaluer la performance de notre modèle?

Il y a plusieurs méthodes. La plus simple est ce que nous appellerons l’exactitude ou, parfois, la précision—mais attention, le mot « précision » est ici ambigu, comme on va le voir plus tard.

Exactitude = Nombre de réponses correctesNombre total de réponses

9

Mesures de performance : exactitude

Parfois, l’exactitude n’est pas appropriée. Supposons qu’on évalue un engin de recherche comme Google et qu’il y ait 1’000’000 de documents dont 100 m’intéressent. Si je fais le recherche et Google me propose 50 documents dont 10 sont parmi ces 100, alors:

Nombre de réponses correctes =

10 (oui qui sont exacts) + 999’860 (non qui sont exacts)

Donc

exactitude = 999’870 / 1’000’000 = .999’87 !!!

Pourtant, ce résultat est en fait mauvais, puisque j’ai 40 documents que je ne veux pas et il en manque 90 que je voudrais.

10

Mesures de performance : précision et rappel

Réponse de l’algorithme

oui non

Vraie réponse

oui vp = Vrai positif fn = Faux négatif

Non fp = Faux positif vn = Vrai négatif

Deux autres mesures sont plus utiles ici : la précision et le rappel.

Étant donné les valeurs dans letableau suivants :

On définit ces mesures ainsi :

Précision = # oui corrects = vp / vp + fp# de oui trouvés

Rappel = # oui corrects = vp / vp + fn # de oui réels

11

Mesures de performance : précision et rappel

Alors pour notre recherche sur Google, nous avons :

Réponse de l’algorithme

oui non

Vraie réponse

oui 10 90

Non 40 999’860

Précision = 10 / 10 + 40 = .2

Rappel = 10 / 10 + 90 = .1

Ces mesures sont plus utiles dans ce cas-ci que

Exactitude = vp + vn / total

12

Mesures de performance : mesure F

Une autre mesure est utile, résumant la précision et le rappel en une seule mesure : la mesure F.

Si P est la précision et R est la rappel, alors F se définit comme:

F = 2PR / P + R

La mesure F nous donne un mesure de performance moyenne.

Question: pourquoi F et non pas simplement une moyenne?

F' = P + R /2

13

Mesures de performance : mesure FF se définit comme: F = 2PR / P + R

Elle est la moyenne harmonique

F = 2/ 1/P + 1/R

Elle donne un mesure de performance équilibrée. On veut une mesure equilibrée car on sait que, en pratique, précision et rappel sont en rélation inverse.

Précision inadéquate: Rappel inadéquat: « Équilibre »:

vp = 100 fn = 0

fp = 900 vn = 999’000

P = .1 R = 1 P = 1 R = .4 P = .8 R = .8

F = .18 F = .33 F = .8

vp = 20

fn = 80

fp = 0 vn = 999’900

vp = 80 fn = 20

fp = 20 vn = 999’880

14


P = .1 R = 1 P = 1 R = .4 P = .8 R = .8

F = .18 F = .33 F = .8

M = .55 M = .7 M = .8

P R M F

1 100 50.5 1.98

2 50 26 3.85

3 33.3 18 5.5

4 25 14.5 6.9

5 20 12.5 8

10 10 10 10

15


P = .1 R = 1 P = 1 R = .4 P = .8 R = .8

F = .18 F = .33 F = .8

M = .55 M = .7 M = .8

P R M F

1 100 50.5 1.98

2 50 26 3.85

3 33.3 18 5.5

4 25 14.5 6.9

5 20 12.5 8

10 10 10 10

16

Mesures de performance – exemple 2

Supposons d’avoir 20 verbes. En réalité la moitié des verbes appartient à la classe E, tandis que l’autre moitié appartient à un mélange d’autres classes qui ne nous intéressent pas. On l’appelle O. E est la classe d’observations expérimentales, tandis que O est la classe de contrôle.

Nous lançons notre algorithme et il nous dit que 8 verbes appartient à la classe E et 12 verbes appartient à la classe O.

•Voici un exemple des données résultats

17

Mesures de performance

Verbe Verité Algorithme

Floated E O

Hiked E E

Hurried E O

Jumped E E

Leaped E E

Marched E E

Paraded E E

Raced E E

Rushed E O

Skipped E E

Verbe Verité AlgorithmeBorrowed O OCarved O OInherited O OKicked O EKnitted O OOrganised O OPainted O OPlayed O OTyped O EWashed O OYelled O O

18


Quel sont le critères de performance qui nous intéressent?

Si l’algorithme me dit qu’un verbe est E, quel est la probabilité qu’il se trompe? Est-il précis?

Pour tous les verbes E qui m’intéressent, combien l’algorithme arrive-t-il à en trouver? A-t-il une bonne couverture?

Quel sont les erreurs possibles?

Verbes qui en réalité sont de E mais qui ont été classés comme OVerbes qui en réalité sont de O mais qui ont été classés comme E

19

Mesures de performance Verbe Verité Algorithme

Floated E O

Hiked E E

Hurried E O

Jumped E E

Leaped E E

Marched E E

Paraded E E

Raced E E

Rushed E O

Skipped E E

Verbe Verité AlgorithmeBorrowed O OCarved O OInherited O OKicked O EKnitted O OOrganised O OPainted O OPlayed O OTyped O EWashed O OYelled O O

Algorithme

Effectifs

E O Total

E 7 3 10

O 2 8 10

Total 9 11 20

20


Algorithme

Verité

E O Total

E 7 3 10

O 2 8 10

Total 9 11 20

Précision E = 7 / 9 O = 8/11

Rappel E = 7/10 O = 8/10

Exactitude E+O = 7+8/20

21

Mesures de performance–-Formules générales

Algorithme

Verité

X X’ Total

X a b a+b

X’ c d c+d

Total a+c b+d a+b+c+d

Si la classe d’observation qui nous intéresse est X alors

Précision: a/a+c

Rappel: a/a+b

Exactitude de l’algorithme: a+d/a+b+c+d

22

Attachement du SP: méthode basée sur le corpus

1. Annotation d’un corpus d’exemples de phrases spontanées.

2. Récolte de SPs dans le corpus avec la distinction entre complément du nom ou complément du verbe.

3. Création d’un algorithme apprenant automatiquement les règles qui régissent les différences entre complément du nom ou complément du verbe.

4. Implémentation de l’algorithme et son entraînement sur la base d’une partie du corpus.

5. Évaluation de la précision de l’algorithme sur la partie restante du corpus.

Représentativité

Exhaustivité, même si grande variabilité

Fiabilité de l’évaluation

23

Étape 1

1. Annotation d’un corpus d’exemples de phrases spontanées

Questions: toutes le questions concernant l’annotation vue auparavant. Années de travail de conception et annotation.

Penn TreeBank

annotation syntaxique qui distingue les deux types d’attachement

24

Exemples dans la PTB

( (S

(NP-SBJ

(NP (NNP Pierre) (NNP Vinken) )

(VP (MD will)

(VP (VB join)

(NP (DT the) (NN board) )

(PP-CLR (IN as)

(NP (DT a) (JJ nonexecutive)

(NN director) ))

(NP-TMP (NNP Nov.) (CD 29) )))

(. .) ))

( (S

(NP-SBJ (NNP Mr.) (NNP Vinken) )

(VP (VBZ is)

(NP-PRD

(NP (NN chairman) )

(PP (IN of)

(NP

(NP (NNP Elsevier) (NNP N.V.) )

(, ,)

(NP (DT the) (NNP Dutch)

(VBG publishing) (NN group) )))))

(. .) ))

25

Étape 2

2a. Récolte des SPs dans le corpus avec la distinction entre complément du nom ou complément du verbe

Questions

Qu’est-ce qu’on veut extraire? Sous-arbre qui couvre

verbe, nom et SP

Comment arrive-t-on à extraire le sous-arbre couvrant

Verbe, nom et SP, étant donné les arbres de la PTB?

Programme disponible tgrep2

(Essayez)

26

Étape 2

2b. Simplification et normalisation de données

• Tête d’un syntagme: nom pour SN, verbe pour SV etc.

• Lemmatisation : on utilise le lemme, soit l’infinitif pour les verbes et le singulier pour les noms. (Lemmatisation avec ER).

• On transforme le sous-arbre en une suite de têtes syntaxiques plus une valeur binaire qui indique le type d’attachement.

Exemple

manger pizza avec fourchette 1

manger pizza au fromage 0

27

SP : n-uplets

VERB NOUN PREP NOUN2 ATTACH

abolish levy for concern 0

accept payment from Linear 0

accompany President on tour 0

accrue dividend at % 0

accumulate wealth across spectrum 0

yank balloon to ground 1

yield % at bank 1

yield % in offering 1

yield % in week 1

zip order into exchange 1

28

Étape 3

3. Création d’un algorithme apprenant automatiquement les règles

qui régissent les différences entre complément du nom ou complément du verbe

Question: faut-il comprendre ce qu’on apprend ou pas?

Autrement dit, faut-il apprendre grâce à une explication ou par imitation?

La méthode basée sur les corpus utilise souvent l’apprentissage par imitation.

29

Quel algorithme? Essayez

VERB NOUN PREP NOUN2

abolish levy for concern 0

accept payment from Linear 0

accompany President on tour 0

accrue dividend at % 0

accumulate wealth across spectrum 0

yank balloon to ground 1

yield % at bank 1

yield % in offering 1

yield % in week 1

zip order into exchange 1

30

Étape 3 – Entraînement

Mémoriser les données d’entraînement,

c-à-d mémoriser les n-uplets (têtes,attachement)

si des exemples se répètent, mettre à jour un compteur

On obtient une base de données composé par tous les n-uplets observés avec leur fréquence.

31

Étape 3 – Test (Collins et Brooks, 1995)

Pour chaque donnée de test, on utilise la suite de back-offs suivante :

si on a déjà vu la même donnée (la même séquence de 4 mots),

alors attachement = attachement à l’entraînement

sinon si on a vu une (ou plusieurs) sous-séquence(s) des 3 mots à l’entraînement,

alors attachement = attachement majoritaire

de la (moyenne des) sous-séquences des 3 mots

sinon si on a vu une (ou plusieurs) sous-séquence(s) des 2 mots à l’entraînement,


de la (moyenne des) sous-séquences des 2 mots

sinon si on a vu une (ou plusieurs) sous-séquence(s) d’un mot à l’entraînement,


de la (moyenne des) sous-séquences d’un mot

sinon attachement majoritaire

32

Étape 3 – Test (Collins et Brooks, 1995)

Pour chaque donnée de test

if (verbe nom prép. nom2) in n-uplets d’entraînement

alors attachement = attachement du n-uplet

elsif (verbe nom prép.), (nom prép. nom2) ou (verbe prép. nom2) in n-uplets d’entraînement

alors attachement = attachement majoritaire de

(verbe nom prép.) + (nom prép. nom2) + (verbe prép. nom2)

elsif (verbe prép.), (nom prép.) ou (prép. nom2) in n-uplets d’entraînement

alors attachement = attachement majoritaire de

(verbe prép.) + (nom nom2) +(prép. nom2)

elsif (prép.) in n-uplets d’entraînement

alors attachement = attachement majoritaire de prép.

sinon attachement majoritaire dans le corpus d’entraînement

33

Back-off

Notes à propos de l’algorithme de Collins et Brooks (1995) :

• On utilise un suite de back-offs : s’il n’y a aucunes données à un niveau donné, on utilise plutôt de niveau suivant, plus général, moins précis (mais qui contient des données!).

• C’est un back-off « pur » : ici, on ne passe au niveau suivant que lorsqu’il n’y a aucunes données.

• Collins et Brooks ont constaté que c’était le back-off optimal pour ce problème.

• Ce n’est pas le cas pour la modélisation n-gram de langages, par exemple.

34

Back-off

Autres méthodes de back-off :

• On passe au niveau suivant si il y a trop peu de données, par ex. « moins de 5 ».

• « Back-off smoothing » : une formule qui passe graduellement au niveau suivant quand la quantité de données diminue.

Exemple : la méthode de Hindle et Rooth, 1993 :• Premier niveau : f(n,p) / f(n) ou f(v,p) / f(v), c-à-d fréquence

d’utilisation de la préposition avec le nom ou le verbe donné.• Deuxième niveau : f(N,p) / f(N) ou f(V,p) / f(V), c-à-d fréquence

d’utilisation de la préposition avec n’importe quel nom ou verbe.• p(prép.|nom) estimé par [f(n,p) + f(N,p)/f(N)] / [f(n) + 1].• p(prép.|verbe) estimé par [f(v,p) + f(V,p)/f(V)] / [f(v) + 1].• L’attachement se fait là où la probabilité est plus élevée.

35

Étape 4

4. Implémentation de l’algorithme et son entraînement sur la

base d’une partie du corpus

36

Exemple#!/usr/bin/perl –wuse strict; use warnings;

# Computes: collects tuples and updates counts# Loads: n-uplets <verbe nom prep nom2 attachement>

my (%noms, %verbes, $noms, $verbes);open(TRAINING, "training-quads") or die "Can’t open training-quads: $!\n";

while (<TRAINING>) {

my ($v, $n, $p, $n2, $a) = split;

if ($a == 0) {$noms{"$v $n $p $n2"}++;$noms{"$v $p $n"}++;$noms{"$n $p $n2"}++;$noms{"$v $p $n2"}++;$noms{"$v $p"}++;$noms{"$n $p"}++;$noms{"$p $n2"}++;$noms{$p}++;$noms++;

} else …

… {$verbes{"$v $n $p $n2"}++;$verbes{"$v $p $n"}++;$verbes{"$n $p $n2"}++;$verbes{"$v $p $n2"}++;$verbes{"$v $p"}++;$verbes{"$n $p"}++;$verbes{"$p $n2"}++;$verbes{$p}++;$verbes++;

} }

37

Étape 5 – Évaluation

5. Évaluation de la précision de l’algorithme sur un échantillon de nouvelles phrases

Exemple partiel en Perl :

open(TESTING, "testing-quads") or die "Can’t open testing-quads: $!\n";

while (<TESTING>) {

my ($v, $n, $p, $n2, $a) = split;

deviner l’attachement

calculer la précision des réponses

}

imprimer les résultats

38

SP : évaluation

Résultats de Collins et Brooks (1995) :

Niveau Total Correct Précision (%)

Quadruplets 242 224 92.6

Triplets 977 858 87.8

Doublets 1739 1433 92.4

Simplets 136 99 72.8

Restant 3 3 100.0

Total 3097 2617 84.5

39

SP : évaluation

Performance minimum et maximum pour Collins et Brooks (1995) :

Méthode Précision (%)

Attache toujours au nom 59.0

Attachement majoritaire de prép. 72.2

Moyenne de trois humains (quadruplets) 88.2

Moyenne de trois humains (toute la phrase) 93.2

Documents

1 Mettre tout ça ensemble Exemple de problème: Attachement du SP Le problème Méthodes possibles Implémentation en Perl Évaluation