Evaluation des performances dans

les SRI

1
 Qu’est ce qui marche ?

BM25

Indexer
Statistique vs. linguistique
e
ab ilist
Pr ob n isme

Mots vid
n
exio

les pass
n
thésaurus Con
tf
hr ases
p s
ot²

es

ages
e m liens web
Vectoriel u pes d
Gro

Evaluer
2
 Objectif

•  Evaluer la performance d’une approche, d’une

technique, d’un système
–  En RI, on ne mesure pas la performance absolue
d’un système/technique/approche car non
significative

–  Mais, ..
•  Evaluation comparative entre approches
•  Mesurer la performance relative de A par rapport à B

3
 Critères d’évaluation

•  Identifier la tâche à évaluer

•  Identifier les critères (Cleverdon 66)
– Facilité d’utilisation du système
– Coût accès/stockage
– Présentation des résultats

– Capacité d’un système à sélectionner

des documents pertinents.
4
 Deux facteurs

•  Rappel
–  La capacité d’un système à sélectionner tous
les documents pertinents de la collection

•  Précision
–  La capacité d’un système à sélectionner que
des documents pertinents

5
 Précision et Rappel

relevant irrelevant
Collection
Sélection. & Non sélection. &
de documents document documents
pertinents sélectionnés Non Pert. Non Pert.

Sélection. & not sélection.

Pert mais Pert.

retrieved not retrieved

Nombre de documents pertinents séléctionnés

rappel =
Nombre total de documents pertinents

Nombre de documents pertinents sélectionnés

précision =
Nombre total de documents sélectionnés

6
 Pourquoi deux facteurs ?

Collection documents
sélectionnés
de documents document
pertinents

•  FACILE de faire du rappel il suffit de sélectionner toute la

collection

•  MAIS, la précision sera très faible

7
 Pertinent vs. Sélectionné

Collections
Sélectionné

Pertinent

8
 Sélectionné vs. Pertinent

Précision très élevée, rappel très faible

Sélectionné

Pertinent

9
 Sélectionné vs. Pertinent

Précision très faible, rappel très faible (en fait, 0)

Pertinent

10
 Sélectionné vs. Pertinent

Rappel élevé, mais précision faible

Pertinent

11
 Sélectionné vs. Pertinent

Précision élevée, rappel élevé (idéal, mais difficile)

Sélectionné

Pertinent

12
 Lien entre Rappel et Précision

1
Precision

0,1 0,2 0,5 1

Rappel

Précision moyenne : une seule valeur reliant le rappel et

précision

13
 Démarche d’évaluation

•  Démarche Analytique (formelle) :

–  Difficile pour les SRI, car plusieurs facteurs :
pertinence, distribution des termes, etc. sont
difficiles à formaliser mathématiquement

•  Démarche Expérimentale
–  par « benchmarking ».
–  Evaluation effectuée sur des collections de tests
–  Collection de test : un ensemble de documents,
un ensemble de requêtes et des pertinences
(réponses positives pour chaque requêtes)
14
 Démarche expérimentale

•  Lancée dès les années 1960, par Cleverdon,

dans le cadre du projet Cranfield

•  Objectif du projet Cranfield

–  Construire des collections de test
–  Evaluer les systèmes sur ces collections de test

•  Evaluation à la Cranfield

15
 Evaluation à la Cranfield
Documents de tests Requêtes de test
?

1 9
7 ?
3 6
4 5

Système à
évaluer

Liste 5 0,9
documents 0,8
9 0,7 Syst A
7 0,6

Précision
0,5
0,4
0,3
Evaluation 0,2
Liste de bonnes 0,1
réponses Précision 0
et rappel 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
Rappel
? 1, 9

? 4

16
 Test Collections
• 
Collection Number Of Number Of Raw Size
Name Documents Queries (Mbytes)
CACM 3,204 64 1.5
CISI 1,460 112 1.3
CRAN 1,400 225 1.6
MED 1,033 30 1.1
TIME 425 83 1.5

•  COLLECTION TREC

17
Calcul du rappel et la précision

18
 Calcul du rappel et de la précision

•  On suppose qu’on dispose d’une collection

de test
–  Lancer chaque requête sur la collection de test
–  Marquer les documents pertinents par rapport à
la liste de test.
–  Calculer le rappel et la précision à pour chaque
document pertinent de la liste.

19
 Calcul du rappel et de la précision
Exemple
n doc # relevant
Le nombre total de documents
1 588 x pertinents est = 6
2 589 x
3 576
R=1/6=0.167; P=1/1=1
4 590 x
5 986
R=2/6=0.333; P=2/2=1
6 592 x
7 984 R=3/6=0.5; P=3/4=0.75
8 988
9 578 R=4/6=0.667; P=4/6=0.667
10 985
Il manque un
11 103
document pertinent.
12 591 On n’atteindra pas le
13 772 x R=5/6=0.833; p=5/13=0.38 100% de rappel
14 990
20
 Calcul du rappel et de la précision
Exemple 2

Ra Pr Pr

0,07 1,00
1,20
0,13 0,50
1,00
0,20 0,75
0,27 0,67 0,80

0,33 0,71 0,60

Pr

0,40 0,67
0,40
0,47 0,64
0,53 0,67 0,20

0,60 0,64 0,00

0,07 0,13 0,20 0,27 0,33 0,40 0,47 0,53 0,60 0,67 0,90
0,67 0,67
0,90 0,01

21
 Interpolation de la courbe
Rappel/Précision
•  Interpoler une précision pour chaque point de
rappel :
–  rj ∈{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}
•  La précision interpolée au point de rappel rj est
égale à la valeur maximale des précisions
obtenues aux points de rappel r, tel que r>=rj

P(rj ) = max P(r )

r ≥rj
22
Exemple Interpolation des Précisions

Ra Pr Ra Pr
0,07 1,00 0,0
0,13 0,50 0,1
0,20 0,75 0,2
0,27 0,67 0,3
0,33 0,71 0,4
0,40 0,67 0,5
0,47 0,64 0,6
0,53 0,67 0,7
0,60 0,64 0,8
0,67 0,67 0,9
0,90 0,01 1

23
 Précision moyenne
•  On souhaite souvent avoir une valeur unique
–  Par exemple pour les algorithmes d’apprentissage pour
contrôler l‘amélioration
•  La précision moyenne est souvent utilisée en RI
•  Plusieurs moyennes
–  Précision moyenne non interpolée (PrecAvg) :
•  Calculer la moyenne des précisions à chaque apparition d’un
document pertinent

24
 Précision moyenne non interpolée
Exemple
n doc # relevant
Le nombre total de document
1 588 x pertinent est = 6
2 589 x
3 576
R=1/6=0.167; P=1/1=1
4 590 x
5 986
R=2/6=0.333; P=2/2=1
6 592 x
7 984 R=3/6=0.5; P=3/4=0.75
8 988
9 578 R=4/6=0.667; P=4/6=0.667
10 985
11 103 AP¨=AvgPrec=(1+1+0,75+0,667+0,38)/6
12 591
13 772 x R=5/6=0.833; p=5/13=0.38
14 990
25
 Autres mesures de moyennes
•  F-Mesure
–  Mesure tenant compte à la fois du rappel et de
la précision.
–  Introduite par van Rijbergen, 1979
–  Moyenne harmonique entre R et P

2 PR 2
F= =1 1
P + R R+P
 Autres mesures de moyennes

•  E-Mesure (F-Mesure paramétrique)

–  Une variante de F-Mesure qui tient compte du
poids accordé à la précision vis-à-vis du rappel
2 2
(1 + β ) PR (1 + β )
E= 2
= β2 1
β P+R +
R P

•  β contrôle le compromis R, P:
–  β = 1: même poids précision et recall (E=F).
–  β > 1: préviligie la précision au rappel
–  β < 1: plus d’importance au rappel.
Exemple de résultats renvoyés par le
Programme TREC_EVAL
Total number of documents over all queries
Retrieved: 1000
Relevant: 80
Rel_ret: 30
Interpolated Recall - Precision Averages:
at 0.00 0.4587
at 0.10 0.3275
at 0.20 0.2381
at 0.30 0.1828
at 0.40 0.1342
at 0.50 0.1197
at 0.60 0.0635
at 0.70 0.0493
at 0.80 0.0350
at 0.90 0.0221
at 1.00 0.0150
Average precision (non-interpolated) for all rel docs:
0.1311
28
R-P courbes sur l’ensemble des requêtes

Illisible, difficile de comparer deux approches/systèmes requête par requête

On a besoin d’une moyenne entre les requêtes 29
 Moyenne sur plusieurs requêtes

•  Deux façons de calculer la moyenne

–  Micro-moyenne – chaque document pertinent est
un point de la moyenne
–  Macro-moyenne – faire la moyenne par requête

•  On calcule également la moyenne des

précisions moyennes

30
 Courbe des moyennes sur plusieurs requêtes

•  Macro moyenne
–  Calculer la précision moyenne à chaque point
de rappel pour l’ensemble des requêtes.

–  Tracer la courbe rappel-précision

31
 Exemple
Ens des
Requete1 Requete2 requêtes
R Pr R Pr R Pr
0 0,629 0 0,5017 0 0,56535
0,1 0,451 0,1 0,332 0,1 0,3915
0,2 0,393 0,2 0,248 0,2 0,3205
0,3 0,3243 0,3 0,171 0,3 0,24765
0,4 0,271 0,4 0,155 0,4 0,213
0,5 0,2424 0,5 0,125 0,5 0,1837
0,6 0,164 0,6 0,089 0,6 0,1265
0,7 0,134 0,7 0,056 0,7 0,095
0,8 0,09 0,8 0,032 0,8 0,061
0,9 0,04 0,9 0,027 0,9 0,0335
1 0,031 1 0,02 1 0,0255
AvrPrec 0,2329 AvrPrec 0,1443 AvrPrec 0,1886

32
 Exemple

0,7

0,6

0,5

0,4 Req1
Req2
0,3 Req1+Req2

0,2

0,1

0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

33
 Comparaison de deux systèmes sur un
ensemble de requêtes

1
0,8 NoStem Stem
Precision

0,6

0,4
0,2
0
0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
Recall

34
 Mesures focalisées sur le “top” de la
liste
•  Les utilisateurs se focalisent davantage sur les
documents pertinents se trouvant en “top” des
résultats
•  La mesure de rappel n’est pas toujours appropriée
–  Il existe des stratégies de recherche pour lesquelles il y a
une réponse unique
–  e.g., navigational search, question answering

•  Solution : mesurer plutôt la capacité d’un SRI à

trouver les documents pertinents en top de la liste
 Mesures focalisées sur le “top” de la
liste
•  Precision au Rang X (Precision at rank X)
–  X =5, 10, 20
•  Discounted Cumulative Gain
–  Prise en compte de la pertinence graduelle des
documents
–  Les documents très pertinents sont plus utiles que
ceux qui sont marginalement pertinents
•  Reciprocal Rank
–  Rang inverse du premier document pertinent
sélectionné
 Précision à X documents
•  Précision à différent niveau de documents
–  Précision calculée à 5 docs, 10 docs, 15docs, …

n doc # relevant
1 588 x
2 589 x
Prec. à 5 docs = 3/5
3 576
4 590 x
Prec. à 10 docs = 4/10
5 986
6 592 x
7 984
8 988
9 578
10 985
11 103
12 591
13 772 x
14 990
37
 R- Précision
•  Une façon de calculer une valeur de précision unique :
précision au R ème document de la liste des documents
sélectionné par la requête ayant R documents pertinents dans
la collection.
n doc # relevant
1 588 x
2 589 x R = # documents pertinents = 6
3 576
4 590 x
5 986
6 592 x R-Precision = 4/6 = 0,66
7 984
8 988
9 578
10 985
11 103
12 591
13 772 x
14 990 38
Exemple R-précision

  Précision
at 5 docs 0,224
at 10 docs 0,177
at 15 docs 0,142
at 30 docs 0,114
at 100 docs 0,073
at 200 docs 0,053
at 500 docs 0,013
R-précision=
Précision
Exacte 0,144

39
 Discounted Cumulative Gain
•  Deux hypothèses:
•  Prise en compte de la pertinence graduelle des
documents
•  Les documents très pertinents sont plus utiles que ceux
qui sont marginalement pertinents
–  Plus un document pertinent est loin du début de la
liste moins il est utile pour l'utilisateur, car il a
peu de chance d'être examiné
 Discounted Cumulative Gain
•  Utilise la pertinence graduelle comme une mesure
de l'utilité, ou du gain, obtenu en examinant un
document

•  Le gain est accumulé en commençant par le haut du

classement et il est réduit (diminué) au fur et à
mesure on l’on va vers le fond de la liste

•  La réduction peut être de 1/log (rang)

–  Avec un log base 2, une réduction au rang 4 serait de
1/2, au rang 8 de 1/3
 Discounted Cumulative Gain

•  Le gain cumulé au rang p

•  Autre formulation
 DCG Exemple

•  Soit une liste de 10 documents jugés sur une

échelle de 4 : 0, 1, 2, 3:
3, 2, 3, 0, 0, 1, 2, 2, 3, 0
•  Gain réduit (DG) = rel/log(rank)
3, 2/1, 3/1.59, 0, 0, 1/2.59, 2/2.81, 2/3, 3/3.17, 0
= 3, 2, 1.89, 0, 0, 0.39, 0.71, 0.67, 0.95, 0
•  DCG:
3, 5, 6.89, 6.89, 6.89, 7.28, 7.99, 8.66, 9.61, 9.61
 DCG normalisé

•  Moyenne des DCG sur un ensemble de

requêtes
–  e.g., DCG au 5 est 6.89 et 9.61 rang 10

•  Les valeurs de DCG sont souvent

normalisées selon la valeur DGC du
classement parfait (Ideal DCG)
 NDCG Exemple

•  Classement parfait:
3, 3, 3, 2, 2, 2, 1, 0, 0, 0
•  DCG idéal :
3, 6, 7.89, 8.89, 9.75, 10.52, 10.88, 10.88, 10.88, 10
•  NDCG (valeurs de DCG normalisées)
–  NDCGp=DCGp/iDCGp
–  1, 0.83, 0.87, 0.76, 0.71, 0.69, 0.73, 0.8, 0.88, 0.88
–  NDCG ≤ 1
 Retour sur la comparaison de systèmes

•  L’évaluation en RI est comparative

–  Vérifier si le système A est meilleur que le système
B?
–  Quelle est la démarche ?
•  Comparer les performances en termes de (précisions
moyennes, R, F) des deux systèmes
–  (Val(A)-Val(B)/Val(B))*100
–  …. partir de 5% on peut considérer que A et meilleur que B
•  Comparer les courbes R/P
–  La courbe de A est toujours supérieure à celle de B

•  Que se passe t-il quand on change de collection?

46
 Retour sur la comparaison de systèmes :
test statistiques
•  Vérifier si la différence de performances entre
deux systèmes est significative à Test statistique
-  Test de “significativité” permet de
-  Rejeter l’hypothèse nulle (pas de différence entre A et B)
-  Accepter l’hypothèse alternative (A et B sont différents)

•  Plusieurs facteurs :
–  t-test, test de wilcoxon, Kendall (tau)

47
 t-Test

•  Calculer la performance (par exemple

P@10, MAP, …) pour chaque requête
•  Calculer la différence entre les valeurs de de
A et B
•  On calcule
Degré de liberté (v=N-1)
N=taille de l’échantillon)
à lire dans la table de la loi de student

•  H0 est rejetée à α si tcalc ≤ t(α:υ)

48
 t-Test
•  Dire qu’une différence est significative à
-  x% si p-value < x/100

-  Valeurs de x considérées
-  0.05 (ou 5%) signifie : il y a 95% de chances que la
différence ne soit pas due au hasard
-  0.01 (ou 1%) signifie : il y a 99% de chances que la
différence ne soit pas due au hasard
-  0.10 (ou 10%) signifie : il y a 90% de chances que la
différence ne soit pas due au hasard

49
Exemple
 Exemple : t-Test

•  Hypothèse Null : la moyenne de la

distribution de ces différences est zéro
•  Calculer t

–  Exemple

Chercher la valeur dans la table, alpha=98% , t_table_student(98,9)=2.821

t_cal<t_table
P-value=0.02
L’hypothèse est rejetée à 98% donc les deux distributions sont différentes
 Questions

•  Comment construire une collection de test ?

–  Quels / combien de documents ?
–  Quelles / combien de requêtes ?
–  Comment identifier les documents pertinents
pour chaque requête ?

•  Evaluer la validité de la collection

52
Comment identifier les documents pertinents ?

•  Pour répondre d’une façon sûre, il faut

–  Juger tous les documents de la collection pour
chaque requête
–  Qui juge ?
•  Humain : 1, 2 .. n personnes
•  Faisable pour des petites collections
•  Impossible sur des collections volumineuses
–  TREC collections ont plus d’un millions de documents

53
 Comment identifier les documents
pertinents ?
•  Autres approches
–  Pooling
–  Sampling

54
 Comment identifier les documents
pertinents ?
•  Pooling
–  Pour chaque requête
•  Sélectionner des documents en utilisant différents techniques
•  Juger les n meilleurs documents obtenus par chaque technique
•  La liste des documents pertinents = l’union des documents pertinents
d de chaque technique
•  Sous ensemble de vrai jugement de pertinence
•  Echantillonnage
–  Possible d’estimer le nombre de documents pertinents par des
techniques d’échantillonnage
•  Incomplète, problème ?
–  Comment doit-on traiter les documents non jugés
–  Comment ceci peut affecter les performances calculées ?

55
Avantages et inconvénients des collections de
tests
•  Avantages
–  Mesures de performances
–  Possibilité de comparaison avec d’autres
travaux
•  Inconvénients
–  Les résultats obtenus sont propres à la
collection.
–  Ne répondent pas à toutes les tâches de RI,
notamment celles orientées utilisateur

56
 TREC

Expérience de TREC

57
 TREC
The Text REtrieval Conference

•  Competition/collaboration between IR research

groups worldwide

•  Run by NIST, just outside Washington DC

•  Common tasks, common test materials, common

measures, common evaluation procedures

•  Now various similar exercises (CLEF, INEX,

NCTIR etc.)
58
 The TREC Benchmark
•  TREC: Text REtrieval Conference (http://trec.nist.gov/)
Originated from the TIPSTER program sponsored by
Defense Advanced Research Projects Agency (DARPA).

•  Became an annual conference in 1992, co-sponsored by the

National Institute of Standards and Technology (NIST) and
DARPA.

•  Uniform, appropriate scoring procedures

59
 The TREC Objective

•  TREC is a mordern example of the Cranfield Tradition

–  System evaluation based on text collections

•  Sharing of resources and experiences in developing the

benchmark.
–  With major sponsorship from government to develop large
benchmark collections.
•  Encourage participation from industry and academia.
•  Development of new evaluation techniques, particularly for
new applications.
–  Retrieval, routing/filtering, non-English collection, web-based
collection, question answering.

60
61
62