Post on 06-Apr-2016
transcript
Evaluierung von Information Retrieval Systemen
Teil 2: TREC – Million Query Track
Karin Haenelt
14.12.2014 / 4.12.2011
Inhalt: TREC Million Query Track
Ziele und Aufgaben Auswahl des Corpus und der Queries Teilnehmende Systeme Beurteilungsverfahren Beurteilungsmethoden
UMass NEU
2© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Million Query Track
erste Durchführung: TREC 2007
Ziele des Tracks1. Erforschung des ad-hoc-Retrieval in einer sehr großen
Dokumentkollektion2. Untersuchungen der Systemevaluierung,
Frage: was ist besser: viele oberflächliche Beurteilungen oder wenige gründliche Beurteilungen?
3
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Million Query Track
Aufgaben der Teilnehmenden1. Systemlauf von 10000 Anfragen gegen eine 426 GB
Testkollektion2. Beurteilung von Dokumenten bezüglich der Relevanz für
bestimmte Anfragen
kollaboratives online-Verfahren: alle Teilnehmenden beurteilen eine Teilmenge der Dokumente
4
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Inhalt: TREC Million Query Track
Ziele und Aufgaben Auswahl des Corpus und der Queries Teilnehmende Systeme Beurteilungsverfahren Beurteilungsmethoden
UMass NEU
5© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TestaufbauAuswahl des Corpus: GOV2-Collection
Sammlung des Webseiten der .gov-Domäne aus dem Jahr 2004
gesammelt von Web-Crawlern HTML, text, extrahierte Texte aus PDF, Word und Postscript 25 Millionen Dokumente, 426 GB
verteilt durch Universität Glasgow auf Platte gegen Beteiligung an Unkosten der Zusammenstellung und
der Versendung
6
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TestaufbauAuswahl der Queries
Sammlung von Anfragen an eine große Internetsuchmaschine Auswahl von 10.000 Anfragen mit mindestens einem relevanten
Dokument in GOV2-Corpus ermittelt aus log files der Suchmaschine
Anfragen, die zu einem Click auf ein Dokument aus GOV2-Corpus führten
Clicks bieten keine Garantie, aber gewisse Wahrscheinlichkeit der Relevanz
keine Qualitätskontrolle der Queries (Tippfehler, sprachliche Fehler, …)
Erstellung einer Textdatei mit den Anfragen Beispiel:32: barack obama internships
7
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TestaufbauAuswahl der Queries
Short Queries (TREC-Standard): Originalanfragen an die Suchmaschine
Long Queries (TREC-Standard): aus short queries während des Beurteilungsprozesses von Menschen entwickelt
8
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Einsendungen der Teilnehmenden
Durchlauf der Fragen Rückgabe der 1.000 höchstplatzierten Ausgaben für jede der
10.000 Queries
9
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Inhalt: TREC Million Query Track
Ziele und Aufgaben Auswahl des Corpus und der Queries Teilnehmende Systeme Beurteilungsverfahren Beurteilungsmethoden
UMass NEU
10© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeARSC multisearch system / University of Alaska Fairbanks
Grid Information Retrieval und multisearch-Ansatz: Verteilung einer Anfrage auf mehrere Hosts mit jeweils eigenen Suchmaschinen
Ziel: Schätzung der Anzahl von Hosts, die für 10.000 Anfragen in der vorgegebenen Zeit befragt werden können
frühere Leistung für ähnliche Anfragen (TREC-Bewertung); qrel: (topic, document, relevance score)
20% der Hosts, die ein relevantes Dokument zu einer Query liefern, enthalten 78% aller relevanten Dokumente
80% der Hosts, die für alle Queries ein relevantes Dokument liefern, enthalten 10 oder weniger relevante Dokumente für eine Query
nur die Hosts mit den meisten relevanten Dokumenten in früheren TRECs durchsucht
Zusammenführung der Ergebnisse (in Entwicklung) Index- und Suchtechniken aus Lucene verwendet
11
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeExegy Inc.
Firma: Entwickler von Ultra-Hochleistungs-Hardware (11-50 Mitarbeitende)
Suche mit Spezialsuchmaschine: Exegy Text Miner (XTM): hybrides System: hardware-software co-design-Architektur
Suche über unindizierte Texte (brute force string search) relevante Ergebnisse für die meisten Queries durchschnittliche Precision 0.3106 (nach UMass-Messung) und
0.0529 (nach NEU-Messung) vollständige Suche über gesamtes unindiziertes Corpus für
10.000 Fragen in weniger als 2,5 Stunden
12
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeIBM Haifa
Weiterentwicklung der Ranking-Funktion von Lucene zu üblichen Formeln der TREC-Teilnehmenden: bessere Dokumentlängennormalisierung bessere Term-Gewichts-Maße
Query-Parsing Stoppwortentfernung Synonym-Expansion Phrasen-Expansion
deutlich bessere Ergebnisse als mit früheren Lucene-Formeln ähnliche Ergebnisse wie mit eigener Suchmaschine Juru
13
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeUniversität Amsterdam / Universität Twente
Ziel: Vergleich früherer Terabyte Tracks mit Million Query Track: Einfluss flacher Pooling-Methoden auf gemessene Effektivität der
Retrievalmethoden Einfluss größerer Themenmenge
Retrieval nach folgenden Methoden Volltext-Index (mit Vektorraum-Modell und Sprachmodell) Titel-Index (mit Sprachmodell) Anker-Text-Index (Text eines Hyperlinks) (mit Sprachmodell)
14
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeUniversität Amsterdam / Universität Twente
Bewertung der Ergebnisse nach Standard-TREC-Verfahren Bewertung der Ergebnisse nach MQ-Bewertungen (nicht-
gesichtete Texte gelten als nicht relevant) Vergleich:
MQ-Evaluierung ähnliche Ergebnisse wie nach Standard-TREC-Methode
MQ-Evaluierung zeigt stärkere Korrelation mit precision auf den vorderen Rängen
15
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
TeilnehmendeUniversity of Melbourne
Vier Retrieval-Varianten1. topic-only (Originalanfragen) Ähnlichkeitsmaß basierend
auf einem Sprachmodell mit Dirichlet-Glättung2. Anfrage an öffentliche Suchmaschine, Auswahl von
Termen aus den 5 höchtplatzierten Dokumenten und Erweiterung der Anfrage um diese Terme
3. impact-based ranking (Anzahl der Zitierungen)4. Zusammenfassung von 1 und 3
16
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Teilnehmende
Heilongjiang Institute of Technology, China: verwendet Lemur Northeastern University: verschiedene Lemur-Standardformeln
(tf-idf bm25, tdf-idf log, kl abs, kl dir, inquery, cos, okapi) und Kombination der Ausgabe (Metasuche) mit dem hedge Algorithmus
RMIT: Zettair Dirichlet smoothed language model SabIR Standard SMART ltu.Lnu University of Massachusetts Amherst verwendet Indri-Retrieval-
System
17
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Inhalt: TREC Million Query Track
Ziele und Aufgaben Auswahl des Corpus und der Queries Teilnehmende Systeme Beurteilungsverfahren Beurteilungsmethoden
UMass NEU
18© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Relevanzbeurteilungen Ziel
Ziel: Erstellung einer kleinen Anzahl von Beurteilungen für eine
große Anzahl von Themen Ergebnis
1700 vom 10.000 queries beurteilt frühere TRECs: 50 queries
Bewertende NIST Gutachter Teilnehmende
19
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
RelevanzbeurteilungenBeurteilungsverfahren
Bewertungssystem erstellt von University of Massachusetts auf der Basis des Drupal-Content Management Systems1. Bewertungssystem schlägt 10 zufällig ausgewählte queries
vor2. Bewertende wählen eine dieser 10 queries zur Beurteilung3. Bewertende erstellen eine TREC-long query (<desc>
Beschreibung, <narr> narrative Angabe der Relevanzkriterien)
4. Bewertungssystem präsentiert ein Dokument und fragt, ob es für die query relvant ist (highly relevant, relevant, not relevant)
5. Wiederholung von 4. bis zu 40 Dokumenten
20
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Inhalt: TREC Million Query Track
Ziele und Aufgaben Auswahl des Corpus und der Queries Teilnehmende Systeme Beurteilungsverfahren Beurteilungsmethoden
UMass NEU
21© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeStandardevaluierungsverfahren der TREC
Aufbau von Datenbanken mit großen Mengen von Relevanzbeurteilungen Teilnehmende schicken Ergebnisse der Retrievalläufe auf
einem Corpus ein N höchstplatzierte Dokumente aus jedem System kommen
in einen Pool und werden von Menschen auf Relevanz untersucht
22© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeStandardevaluierungsverfahren der TREC
Pooling&Beurteilungs-Verfahren ungeeignet für riesige Datenmengen
im besten Fall uneffizient im schlechtesten Fall nicht machbar
sehr dynamische Kollektionen (Beispiel: Internet) und ständige Evaluierung neuer Algorithmen(Testdaten verschwinden, verlieren an Relevanz, erscheinen neu)
spezifische Aufgaben (sehr hoher Aufwand für Einzelfall)
23© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeMinimal Test Collection (MTC)
Ben Carterette, James Allan, and Ramesh K. Sitaraman. Minimal test collections for retrieval evaluation. In: Proceedings of SIGIR, pages 268-275, 2006. http://ir.cis.udel.edu/~carteret/papers/sigir06.pdf
James Allan, Ben Carterette, Javed A. Aslam, Virgil Pavlu, Blagovest Dachev, Evangelos Kanoulas (2007). Million Query Track 2007 Overview. Proceedings of TREC 2007. http://maroo.cs.umass.edu/pub/web/getpdf.php?id=800
auch UMass-Verfahren genannt (University of Massachusetts Amherst)
24
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeMinimal Test Collection (MTC)
Ziel Erforschung
eines minimalen Beurteilungsaufwandes für eine möglichst hohe Konfidenz des
Evaluierungsergebnisses Aufbau einer minimalen Testkollektion zum Vergleich von IR-
Systemen
25© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeMinimal Test Collection (MTC)
Ansatz: Verbindung von Evaluierung und Konstruktion von Testkollektionen
26
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
BeurteilungsmethodeMinimal Test Collection (MTC)
Methode: neue Sicht auf durchschnittliche Präzision Schätzung des Grades der Konfidenz durch Definition einer
Verteilung über mögliche Dokumentbeurteilungen ermöglicht Evaluierung von Retrievalsystemen mit
minimaler Menge an Beurteilungen führt zu einem Algorithmus zum Aufbau einer
Testkollektion Studie mit dieser Methode: Bestimmung der Rangfolge einer
Menge von Systemen möglich mit kleiner Gruppe von Beurteilenden in weniger als drei Stunden mit 95% Konfidenz
27
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeGrundgedanken
1. Neuartige Sicht auf durchschnittliche Präzision (AP – average precision): Betrachtung im Sinne eines Bernouilli Experiments
2. AP ist normalverteilt über mögliche Mengen von Relevanzbeurteilungen
3. [2.] ermöglicht die Schätzung der Konfidenz einer AP4. Grad der Konfidenz dient als Abbruchkriterium für den
Algorithmus5. [4.] ermöglicht Verbindung von Evaluierung und Konstruktion
einer Testkollektion
28
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeGrundgedanken 1
1. Neue Sicht auf durchschnittliche Präzision (AP – average precision):
Betrachtung des Beitrags einzelner Dokumente zur durchschnittlichen Präzision (AP average precision) als quadratische Gleichung über Bernoulli Experimente Xi für die Relevanz eines Dokuments i
29
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeGrundgedanken 2
2. Betrachtung der Differenz der durchschnittlichen PräzisionΔ AP zwischen zwei Systemen s1 und s2
Δ AP ist über alle möglichen Relevanzzuordnungen zu allen unbeurteilten Dokumente normalverteilt
Normalverteilung ermöglicht Angabe einer Konfidenz für das beim jeweiligen Fortschritt der Beurteilung erreichte Ergebnis
30
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 14.12.2014
Minimal Test Collection (MTC) MethodeGrundgedanken 3
3. Grad der Beurteilungssicherheit dient als Abbruchkriterium für den Algorithmus
4. → Verbindung von Evaluation und Konstruktion der Testkollektion
31
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeErgebnisse
32
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeErgebnisse
33
(Carterette, Allan, Sitamaran, 2006)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Minimal Test Collection (MTC) MethodeEvaluierungssystem
ordnet Dokumente iterativ nach ihrem Informationsbeitrag zu einer Differenz der durchschnittlichen Präzision
präsentiert das höchstgeordnete Dokument zur Beurteilung Neugewichtung und Neuordnung der Dokumente nach einer
Beurteilung
34© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Auswahl von Dokumente für die BeurteilungStatistical evaluation (statMAP) Methode
beurteilt eine Zufallsmenge von Dokumenten von einer geordneten Liste
erzeugt eine Schätzung der Durchschnittspräzision, R-Präzision und Präzision an Standard-Messpunkten
nicht-zufällig beurteilte Dokumente können in den Schätzprozess einbezogen werden
35
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Ergebnisse TREC 2007
Vergleich der Ergebnisse TREC-Standardmethode über Terabyte-Corpus MTC über MillionQueries-Corpus statMap über MillionQueries-Corpus
Übereinstimmung in der relativen Ordnung der Systeme statMap vermutlich bessere Schätzung der mean average
precision (MAP) MTC vermutlich ein korrektes Ranking der Systeme MTC bessere Konfidenz
36
(Allan, Carterette, Aslam, Pavlu, Dachev, Kanoulas, 2007)
© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011
Literatur
James Allan, Ben Carterette, Javed A. Aslam, Virgil Pavlu, Blagovest Dachev, Evangelos Kanoulas (2007). Million Query Track 2007 Overview. Proceedings of TREC 2007. http://maroo.cs.umass.edu/pub/web/getpdf.php?id=800
Ben Carterette, James Allan, and Ramesh K. Sitaraman. Minimal test collections for retrieval evaluation. In: Proceedings of SIGIR, pages 268-275, 2006. http://ir.cis.udel.edu/~carteret/papers/sigir06.pdf
Eliah Ninyo, Keren Kenzi (o.J.). Minimal Test Collections for Retrieval Evaluation. B. Carterette et al. http://cs.haifa.ac.il/courses/infor/students/Minimal Test Collections for Retrieval Evaluation-Eli+Keren.ppt
Versionen: 2.1: 4.12.2011, 2.0: 5.12.2010, 1.0: 27.11.2009
37© Karin Haenelt, Evaluierung von IR-Systemen 4.12.2011