Information Retrieval

Information Retrieval:
Evaluation
Die Evaluierung von IR-Systemen ist eine schwierige
Aufgabe, weil:
• es eine große Bandbreite an unterschiedlichen
Informationsbedürfnissen und Abfragen gibt;
• der jeweilige Die Evaluierung von IR-Systemen ist eine
schwierige Anteil der einzelnen Komponenten an der
Güte des Ergebnisses schwer zu bewerten ist:
–
–
–
–
Güte der Abdeckung durch Datensammlung
Indizierung der Dokumente
Formulierung der Abfrage
Algorithmus zur Auswahl der Dokumente
VO: IR & IE © 2006 Harald Trost
Evaluierung:
Das Laboratoriumsmodell
• Teste nur „Systemparameter“
– Index language devices für Beschreibung und Suche
– Methoden der Auswahl von Termen aus Dokumenten
– Algorithmus zur Bestimmung der
Dokumentenähnlichkeit
– Art der Benutzerschnittstelle
• Ignoriere den Einfluss der Systemumgebung
– Eigenschaften spezifischer Dokumente
→ verwende viele Dokumente
– Eigenschaften spezifischer Benutzer
→ verwende viele Abfragen
VO: IR & IE © 2006 Harald Trost
1
Evaluierung:
Was sind geeignete Testdaten?
• In den 60ern und 70ern, sehr kleine Testkollektionen, in zufälliger
Weise unterschiedlich, eine pro Project.
– in den 60ern: 35 Abfragen auf 82 Dokumenten
– um 1990: weiterhin nur 35 Abfragen auf 2000 Dokumenten
• Test- und Trainingsdaten wurden nicht immer getrennt gehalten, da
so viele Faktoren der Umgebung getestet wurden.
• TREC-3 (1994): 742,000 Dokumente
• Es sind große Textkollektionen nötig um
– Benutzervariation zu untersuchen
– Statistisch signifikante Resultate zu erhalten;
– Zu demonstrieren, dass die erreichte Performanz auch anhält, wenn die
Größe der Dokumentensammlung wächst → kommerzielle
Glaubwürdigkeit
• Es gibt praktische Schwierigkeiten, genügend Daten zu erhalten →
Probleme mit nicht balancierten Daten
VO: IR & IE © 2006 Harald Trost
Heutige Kollektionen von Testdaten
• Textkollektion
– Groß, um eine Vielfalt von Inhalten, Stilen, sowie Rauschen
(Schreibfehler etc.) zu enthalten.
• Abfragen/Themen
– kurze Beschreibung des Informationsbedarfs
– TREC:
• Themen: eine umfassendere Beschreibung, die Relevanzkriterien
umfasst.
• „frozen“ → wiederverwendbar
• Beurteilung der Relevanz
– binär
– durch dieselbe Person, die die Abfrage erstellt hat.
VO: IR & IE © 2006 Harald Trost
2
Beurteilung der Relevanz
• Relevanz ist inhärent subjektiv, muss also von
menschlichen Benutzer beurteilt werden.
• Problem: Relevanz ist situationsabhängig
– Informationsbedürfnis ist spezifisch für eine bestimmte Person
zu einem bestimmten Zeitpunkt.
– Beurteilungen werden sich also sowohl zwischen
unterschiedlichen Personen als auch bei einer Person zu
unterschiedlichen Zeitpunkten unterscheiden
• Es wird eine extensive Sammlung von Beispielen
benötigt, um die inhärente Variantion auszubalancieren:
– große Populationen von Benutzern
– große Populationen von Informationsbedürfnissen.
VO: IR & IE © 2006 Harald Trost
Beurteilung der Relevanz (2)
• Den beurteilenden Personen werden Richtlinien
gegeben, um Relevanz möglichst objektiv als Beziehung
zwischen Abfrage und Dokument zu definieren:
– Es wird weder die Erfüllung des Informations-bedürfnisses, noch
der Neuigkeitswert der Information gewertet.
– Relevanz wird unabhängig von der in anderen Dokumenten
enthaltenen Information (Redundanz) definiert.
• Solche Richtlinien gewährleisten, dass die Entscheidung
für jedes Dokument unabhängig von allen anderen
getroffen werden kann.
VO: IR & IE © 2006 Harald Trost
3
Evaluierung: TREC
• Text REtrieval Conference
• Veranstaltet vom National Institute of Standards and
Technology (NIST) der USA
• Beginnt eine neue Phase der Evaluierung von Text
Retrieval
– viele Teilnehmer
– gemeinsame Aufgaben und Datensammlungen
– Kontinuität (seit 1992)
• Große Sammlung an Testdaten:
– Texte, Abfragen, Bewertungen der Relevanz
• 2005 wurde TREC-14 veranstaltet
• 117 teilnehmende Gruppen aus 23 Ländern
VO: IR & IE © 2006 Harald Trost
TREC – Beispiel einer Abfrage
<num> Number: 508
<title> hair loss is a symptom of what diseases
<desc> Description:
Find diseases for which hair loss is a symptom.
<narr> Narrative:
A document is relevant if it positively connects the loss
of head hair in humans with a specic disease. In this
context, „thinning hair“ and „hair loss“ are synonymous.
Loss of body and/or facial hair is irrelevant, as is hair
loss caused by drug therapy.
VO: IR & IE © 2006 Harald Trost
4
Evaluierungsmetrik
selektiert
nicht selektiert
gesamt
relevant
irrelevant
gesamt
A
C
A+C
B
D
B+D
A+B
C+D
A+C+B+D
• Recall: Anteil der selektierten an den relevanten Dokumenten
⇒ A/(A+C)
• Precision: Anteil der relevanten an den selektierten Dokumenten
⇒ A/(A+B)
• Accuracy: Anteil der korrekt als relevant/irrelevant klassifizierten
Dokumente ⇒ (A+D)/(A+B+C+D)
– kein gutes Maß für IR, weil es die Performanz bei den relevanten
und bei den irrelevanten Dokumenten (die hier nicht interessieren)
vermengt.
VO: IR & IE © 2006 Harald Trost
Recall und Precision
• Alle Dokumente:
A+B+C+D = 100
• Für eine bestimmte
Abfrage relevante
Dokumente:
A+C = 28
VO: IR & IE © 2006 Harald Trost
5
Recall und Precision: System 1
Gesamt: A+B+C+D = 100
Relevant: A+C = 28
System 1:
selektiert: A1+B1 = 26
relevant: A1 = 10
R1 = A1/(A1+C1) = 10/20 = 0.5
P1 = A1/(A1+B1) = 10/27 = 0.37
A1 = (A1+D1)/(A1+B1+C1+D1) =
= 65/100 = 0.65
VO: IR & IE © 2006 Harald Trost
Recall und Precision: System 2
Gesamt: A+B+C+D = 100
Relevant: A+C = 28
System 2:
selektiert: A2+B2 = 49
relevant: A2 = 16
R2 = A2/(A2+C2) = 16/20 = 0.8
P2 = A2/(A2+B2) = 16/49 = 0.33
A2 = (A2+D2)/(A2+B2+C2+D2) =
= 63/100 = 0.63
VO: IR & IE © 2006 Harald Trost
6
Vergleich System 1 vs. System 2
Gesamt: A+B+C+D = 100
Relevant: A+C = 28
System 1:
selektiert: A1+B1 = 26
relevant: A1 = 10
R1 = A1/(A1+C1) = 10/20 = 0.5
P1 = A1/(A1+B1) = 10/27 = 0.37
A1 = (A1+D1)/(A1+B1+C1+D1) =
= 65/100 = 0.65
System 2:
selektiert: A2+B2 = 49
relevant: A2 = 16
R2 = A2/(A2+C2) = 16/20 = 0.8
P2 = A2/(A2+B2) = 16/49 = 0.33
A2 = (A2+D2)/(A2+B2+C2+D2) =
= 63/100 = 0.63
VO: IR & IE © 2006 Harald Trost
Recall und Precision:
Zusammenhang
0.9
0.8
0.7
0.6
Recall
0.5
0.4
0.3
Precision
0.2
0.1
0
20
40
60
80
Dokumente
• Die Kurven von Precision und Recall (vs. die Anzahl der selektierten
Dokumente) zeigt eine inverse Beziehung zwischen den beiden
Werten
• Die beiden Extremfälle sind P=1, R=0 (bei 0%) und R=1 bei 100%
• Der Schnittpunkt von Precision und Recall kann als
zusammenfassendes Evaluierungsmaß verwendet werden.
VO: IR & IE © 2006 Harald Trost
7
F-measure
• Rijsbergen (1979)
– Fα= P*R/((1- α)*P + α *R)
– Großes α: Recall ist wichtiger
– Kleines α: Precision ist wichtiger
• Meistens verwendet mit α=0.5 → gewichtetes
harmonisches Mittel von P und R
– F0.5= 2*P*R/(P + R)
• Der Maximalwert des F0.5-measure (oder kurz nur
F-measure) ist ein guter Indikator für den besten
Kompromiss für P und R.
• Das F-measure ist eine Approximation des
Schnittpunkts von Precision und Recall.
VO: IR & IE © 2006 Harald Trost
Problem: Ermitteln des Recall
• Für Dokumentensammlungen nicht-trivialer
Größe wird es schnell unmöglich, jedes
Dokument auf Relevanz zu überprüfen.
• Bei 1.000.000 Dokumenten und einem Aufwand
von 15sek/Dokument würde die Überprüfung ca.
4200 Stunden benötigen.
• Will man mehrere Systeme miteinander
vergleichen, so bietet sogenanntes Pooling eine
Möglichkeit, das Problem zu umgehen.
VO: IR & IE © 2006 Harald Trost
8
Pooling
• Entwickelt von Spärck-Jones & van Rijsbergen (1975)
• Der Pool wird aus den von n Systemen jeweils N ersten
selektierten Dokumenten (TREC: N = 100)
• Die von den einzelnen Systemen selektierten
Dokumentmengen überlappen: Der Pool ist daher
deutlich kleiner als das theoretische Maximum von N*n
Systeme → üblicherweise etwa 1/3 der Maximalgröße
• Manuelle Beurteilung jedes Dokuments in diesem Pool.
• Dokumente außerhalb des Pools werden automatisch
als irrelevant betrachtet.
• Pooling funktioniert am besten beim Vergleich deutlich
unterschiedlicher Ansätze
VO: IR & IE © 2006 Harald Trost
9