Evaluierung von
Information Retrieval Systemen
Kursfolien
Karin Haenelt
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Evaluierungsveranstaltungen
• TREC Text Retrieval Evaluation Conference
– jährlich seit 1992
– Sponsoren:
• Defence Advanced Research Projects Agency (DARPA)
• National Institute of Standards and Technology (NIST)
• MUC Message Understanding Conference
– 3,1991; 4, 1992; 5, 1993; 6, 1995; 7, 1997, ..
– Sponsoren:
• – Advanced Research Projects Agency (ARPA)
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Logische Einteilung der Datenbasis
R
R
nicht-relevante
ausgegebene Dokumente
relevante
ausgegebene Dokumente
nicht-relevante
nicht ausgeg. Dokumente
relevante
nicht ausgeg. Dokumente
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Verfahren zur Bestimmung der
relevanten Dokumente
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Bestimmung durch Juroren
• Beobachtungen TREC:
– Übereinstimmung zwischen 2 Juroren: 70%
Kowalski, 1997
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Bestimmung durch Pooling
Kowalski, 1997
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Bestimmung durch Pooling
• German Indexing and Retrieval
Testdatabase (GIRT):
– 1389 relevante Dokumente durch Juroren
ermittelt
– 662 relevante Dokumente durch Pooling
ermittelt
Frisch/Kluck, 1997, 34
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Standardmaße zur Evaluierung
• Precision
Genauigkeit des Suchprozesses
# relevant_ ausgegeben
# gesam t_ ausgegeben
• Recall
Vollständigkeit des Suchprozesses
# relevant_ ausgegeben
# relevant_ gesam t
• Fallout
Effektivität des Suchprozesses
# irrelevant_ ausgegeben
# irrelevant_ gesam t
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Recall/Precision-Graph
• Gemessen an 11 Standardmesspunkten:
Recall 100%, 90%, 80% … 0%
• Punkte durch Geraden verbunden
• Geraden haben keine interpolierende
Bedeutung
• Zwischen den 11 Standardmesspunkten
sind keine Werte definiert
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,74
Berechnungsbeispiel
Menge der relevanten Dokumente
Rq={d3,d5,d9,d25,d39,d44,d56,d71,d89,d123}
Ranking für query q
1.
2.
3.
4.
5.
d123
d84
d56
d6
d8
6.
7.
8.
9.
10.
d9
d511
d129
d187
d25
11.
12.
13.
14.
15.
d38
d48
d250
d113
d3
Recall und Precision
d123
d56
d9
d25
d3
18.12.2002
Erweiterte Fassung 14.12.03
recall
precision
10% aller
100% (1 von 1)
20% relevanten
66% (2 von 3)
30% Dokumente 50% (3 von 6)
40%
40% (4 von 10)
50%
33% (5 von 15)
Karin Haenelt, IR-Evaluierung
60%
„0%“
Baeza-Yates/Ribeiro-Neto, 1999,74
Recall/Precision-Graph
120
Precision
100
80
60
40
20
0
10
20
30
40
50
60
Recall
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,74
Durchschnittliche Precision über
mehrere Queries
Nq
Pi (r )
P(r )  
i 1 Nq
P(r)  durchschnittlichePrecisionbei Recall- Ebene r
Nq  Anzahlder Queries
Pi (r )  Precisionbei Recall- Ebene r, für i - te Query
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,74
Durchschnittliche Precision über
mehrere Queries
• Recall-Ebenen können für einzelne
Queries verschieden sein von den 11
Standard-Recall-Ebenen
• Interpolationsprozedur erforderlich
P(rj )  max rj  r  rj1 P(r)
Interpolierte Präzision
bei j.ter Standard-Recall-Ebene:
höchste bekannte Präzision
auf einer Recall-Ebene zwischen
der j.ten und der j+1.ten Recall-Ebene
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,76
Berechnungsbeispiel,
interpolierte Werte
Menge der relevanten Dokumente
Rq={d3,d56,d129}
Ranking für query q
1.
2.
3.
4.
5.
d123
d84
d56
d6
d8
6.
7.
8.
9.
10.
d9
d511
d129
d187
d25
11.
12.
13.
14.
15.
d38
d48
d250
d113
d3
Recall und Precision
d56
d129
d3
18.12.2002
Erweiterte Fassung 14.12.03
recall
precision
33,3% aller
33,3% (1 von 3)
66,6% relevanten
25% (2 von 8)
100% Dokumente 20% (3 von 15)
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,77
Precision
Recall/Precision-Graph
100
90
80
70
60
50
40
30
20
10
0
10
20 30
40 50
60 70
80 90 100
Recall
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Baeza-Yates/Ribeiro-Neto, 1999,77
Stand der Inhaltserschließung
Information
Retrieval
No more than
40% precision for 20% recall
(Sparck Jones 1987)
60 % der Resultate sind falsch
80 % der relevanten Texte werden nicht
gefunden
• Eingeschränktes Fachgebiet
Message
Understanding • Anfragen vorher bekannt
• Beste Ergebnisse
18.12.2002
Erweiterte Fassung 14.12.03
55 % precision /
45 % recall
Karin Haenelt, IR-Evaluierung
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Status der Relevanzmenge
• ”In all cases, evaluation of Information Retrieval Systems will suffer
from the subjective nature of information. There is no deterministic
methodology for understanding what is relevant to a user’s search.”
(Kowalski, 1997, 244)
• ”non calculable in operational systems. If the system knew the total
set of relevant items in the database, it would have been retrieved.”
(Kowalski, 1997, 5)
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Bedeutung der Relevanzmenge
• Wieviel Information wird gebraucht?
– vollständige Information zu einem Sachverhalt
– hinreichende Information zur Erfüllung einer
Aufgabe
• Wie relevant ist relevant?
– sicher
– vielleicht
– weniger
– nicht
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung
Literatur
•
•
•
•
•
•
Kowalski, Gerald: Information Retrieval Systems: Theory and Implementation. Kluwer
Academic Publishers: Boston/Dordrecht/London,1997.
Frisch, Elisabeth und Michael Kluck: Pretest zum Projekt German Indexing and
Retrieval Testdatabase (GIRT) unter Anwendung der retrievalsysteme Messenger
und freeWAISsf. IZ-Arbeitsbericht 10. Bonn: Informationszentrum
Sozilawissenschaften, 1997.
Harman, Donna: Overview of the Fourth Text REtrieval Conference
(TREC-4). TREC-4 Proceedings. http://www–nlpir.nist.gov/TREC/t4_proceedings.html
Ricardo Baeza-Yates und Bertheir Ribeiro-Neto (Eds.) (1999): Modern Information
Retrieval.Essex: Addison Wesley Longman Limited, Kap. 13
Will, Craig A.: Comparing Human and Machine Performance for Natural Language
Information Extraction: Results for English Microelectronics from the MUC-5
Evaluation. In: Proc. of the Fifth Message Understanding Conference. Morgan
Kaufmann Publishers, 1993. pp. 53-67.
18.12.2002
Erweiterte Fassung 14.12.03
Karin Haenelt, IR-Evaluierung

Evaluierung von Information Retrieval Systemen. Kursfolien