Gewichtetes Information Retrieval

Das Gewichtete Information Retrieval, auch Gewichtetes Retrieval, ist eine Methode der Informationswissenschaft zur Informationsgewinnung mit Suchtermen, kurz Termen. Es ist aufgeteilt in termbasierte Methoden und in Boolesches Retrieval (engl. weighted boolean retrieval). Moderne Methoden verwenden dazu die Theorien von Robertson und Karen Spärck Jones.

Alle Suchmaschinen wie beispielsweise Google verwenden diese Methoden, um optimale Trefferlisten zu erstellen.

Gewichtetes Boolesches Retrieval

George Boole beschrieb mit „Laws of Thought“ (1854) die Theorie, dass Gedankenexperimente mit logischen Schlussfolgerungen stets binär sind, unterscheidbar in wahr oder falsch. Die Booleschen Systeme arbeiten entsprechend mit exakt eingestellten Termen. Die Operatoren AND, NOT und OR verbinden mehrere Suchterme, wobei keine Prioritäten nach Relevanz vorgesehen sind (engl. Relevance Ranking). Die möglichen Platzhalter $?$ für genau ein Zeichen oder $*$ für beliebig viele Zeichen werden manuell angegeben, sie haben keine Fehlertoleranz.

Im gewichteten Booleschen Retrieval werden die Terme durch die Benutzer gewichtet, die passende Werte festlegen, beispielsweise information retrieval mit einem Wert 0,75 und Journal of the American Society for Information Science mit 0,25.

<”Information Retrieval”; 0,75> AND <”Journal of the American Society for Information Science"; 0,25>.

Das termbasierte gewichtete Retrieval unterscheidet drei Arten von Termen: Sprachelemente, Eigennamen und Bedeutungseinheiten. Für jedes Dokument werden die relevanten Terme identifiziert, und für jeden Term wird ein Gewicht ermittelt, beispielsweise über die Häufigkeit im Dokument. Diese Verfeinerung erhöht die Qualität und die Güte der Ergebnisse.

Probabilistisches Information Retrieval

Sparck Jones entwickelte ein Modell mit probabilistischen Aussagen, das die Relevanz einer Suchanfrage über alle verfügbaren Dokumente ermittelt. Der Satz von Bayes zu den bedingten Wahrscheinlichkeiten erlaubt, diese Relevanz im Voraus zu berechnen. Dabei ist $P(L|D)$ die Wahrscheinlichkeit für ein Dokument $D$ und das Ereignis $L$ , dass $D$ vom Benutzer als relevant eingestuft wird. Das Ereignis $L$ hängt von der Suchanfrage $Q$ und von Einschätzungen der Benutzer ab.

Der einfachste Ansatz, ohne Einschätzungen, findet kaum Eingang in die Praxis. Es braucht eine Schleife nach der Suchanfrage, ob die gefundenen Dokumente tatsächlich relevant waren. Wenn das System dies selbst einschätzt, ist es ein “pseudo-relevance feedback”.^[1] Denn eine folgende Suchanfrage wird bessere Treffer liefern, wenn die Einschätzungen geschickt ausgewertet werden. Dies ist eine Schleife, die Relevanz durch die Benutzer oder das System geprüft. Es ist zielführend, die Dokumente abhängig von einander, also relativ zu bewerten und eine Relevanz zu berechnen.

Beispielsweise wird einem Benutzer das gleiche Dokument in zwei Situationen präsentiert. Wenn er bereits andere Dokumente hat, welche den Informationsbedarf abdecken, wird das präsentierte Dokument als minder relevant ansehen. Hat er nur irrelevante Dokumente, so mag das gleiche Dokument als äußerst relevant erscheinen.

Die Relevanz ist ein relatives Maß für die Bedeutung der Dokumente aus Benutzersicht.^[2] Jede Suchanfrage führt zu einer Liste von $N$ Dokumenten, davon sind $R$ relevant und $N-R$ nicht relevant. Das zweite Kriterium prüft, ob das Dokument dem Suchterm entspricht. Zu klassifizieren sind alle ${\boldsymbol {t}}$ Dokumente, welche diesen Term enthalten sowie jene ${\boldsymbol {s}}$ gesuchten, die zusätzlich relevant sind,^[3] das führt zur Liste der gesuchten Dokumente.^[4]

Term / Dokument	relevante Dokumente	nicht relevante Dokumente	Summe
Term enthalten	$s$	$t-s$	$t$
Term nicht enthalten	$R-s$	$N-t-R+s$	$N-t$
Summe	$R$	$N-R$	$N$

Die Relevanz $w$ der Dokumente kann berechnet werden über eine von Robertson und Sparck Jones aufgestellte Formel, die Croft, Metzler und Strohman im Jahr 2010 verbessert wurde:^[5]

{\begin{aligned}w:=\ &\log \left({\frac {s+0{,}5}{R-s+0{,}5}}\ /\ {\frac {t-s+0{,}5}{N-t-R+s+0{,}5}}\right)\\&{\text{mit }}\\&0\leqq s\leqq t\leqq N{\text{ und }}s\leqq R\leqq N.{\text{ Es gilt }}w\leqq 0.\end{aligned}}

Ein Zahlenbeispiel in Microsoft Excel liefert bei $N=10$ Dokumenten, wenn $R=5$ relevant sind und $t=5$ den Suchterm enthalten, für die Relevanz $w$ in Abhängigkeit von $s$ gefundenen, relevanten Dokumenten die folgenden Werte:

$s$ = relevant mit Suchterm	0	1	2	3	4	5
$w$ = Relevanz der $s$ Dokumente	−2,1	−1	−0,3	0,3	1	2,1

Die mit dieser Suche ermittelte Relevanz ${\boldsymbol {w}}$ kann allen ${\boldsymbol {s}}$ Dokumenten in den Metadaten zugeordnet werden, weil ${\boldsymbol {w}}$ die Erkenntnis aus dieser Suchanfrage gut zusammenfasst.^[1] Nach internen Algorithmen können die ${\boldsymbol {s}}$ Dokumente bei einer späteren Suchanfrage in einer optimierten Reihenfolge gezeigt werden, und jedes Dokument hat eine um $w$ verbesserte Relevanz.

Bewertung

Das gewichtete Information Retrieval legt den Grundstein für das Ranking von Dokumenten. Der nach Relevanz sortierte Output einer Suchanfrage ermöglicht eine schnelle und präzise Antwort auf das Informationsbedürfnis eines Benutzers. Die untersuchten Modelle weisen darauf hin, dass zur Gewichtung von Dokumenten ein grundlegendes Retrieval-System um die Gewichtung der Suchterme ergänzt werden muss. Das Ziel ist, die Vorteile des klassischen Retrieval-Systems mit denjenigen des gewichteten Information Retrieval zu ergänzen.^[1]

Boolesche Systeme

In der Praxis stößt man auf Schwierigkeiten mit der Benutzerfreundlichkeit Boolescher Systeme, denn der Endnutzer muss die Suchoperatoren korrekt anwenden und jeden Suchterm mit Gewichten versehen. Dies kann für Laien unintuitiv und hinderlich sein. Klassische Boolesche Systeme konnten sich bisher nicht durchsetzen. Die Erweiterung um die Gewichtung der einzelnen Suchterme erschwert die intuitive Bedienung weiter. Es ist davon auszugehen, dass gewichtete Boolesche Retrieval-Systeme außerhalb des professionellen Recherchewesens keinen Anklang finden.^[1]

Probabilistisches Modell

Das probabilistische Information Retrieval von Robertson Sparck Jones ist am besten dokumentiert und verstandenen.^[6] Es ermöglicht in modifizierter Version ein automatisiertes “Pseudo-Relevance-Feedback”, welches den Output einer Suchanfrage ohne Bewertung der einzelnen Dokumente durch einen Benutzer nach Relevanz sortieren kann. Diese Systeme sind noch nicht ausgereift und haben eine relativ hohe Fehlerquote, da dem Algorithmus keine als “nicht relevant” markierten Dokumente übergeben werden.^[1] Das klassische Dokumenten-Retrieval rückt in den Hintergrund und das Retrieval von Bildern, Videos und Musik nimmt an Bedeutung zu.

Nach Relevanz sortierte Suchergebnisse stellen einen Qualitätsfaktor dar. In Hinblick auf neue, multimediale Retrieval-Systeme ist eine ähnliche Entwicklung zu erwarten. Erst die Gewichtung bzw. Sortierung der Suchergebnisse im Information Retrieval, führte zu heutigen Standards im Umgang mit Suchmaschinen. Den Gewichtungsmethoden ist also eine große Bedeutung für die Entwicklung der Suchmaschinen zuzuschreiben.

Einzelnachweise

↑ ^a ^b ^c ^d ^e Stock, W.G. & Stock, M. (2013). Handbook of Information Science. Berlin: De Gruyter Saur.
↑ Robertson, S.E., Walker, S., & Beaulieu, M. (1999). Okapi at TREC-7. Automatic ad hoc, filtering, VLC and interactive track. In the 7th Text REtrieval Conference(TREC 7). Gaithersburg, MD: National Institute of Standards and Technology. (NIST Special Publication 500-242.)
↑ Sparck Jones, K., Walker, S., & Robertson, S. E. (2000a) A probabilistic model of information retrieval: development and comparative experiments Part 1. Information Processing and Management, 36, 779–808
↑ Sparck Jones, K., Walker, S., & Robertson, S. E. (2000b) A probabilistic model of information retrieval: development and comparative experiments Part 2. Information Processing and Management, 36, 809–840
↑ Croft, W.B., Metzler, D., & Strohman, T. (2010). Search Engines. Information Retrieval in Practise. Boston, MA: Addison-Wesley.
↑ Mittendorf, E., Mateev, B., Schäuble, P. (2000). Using the Co-Occurences of Words for Retrieval Weighting. Alphen an den Rijn: Kluwer Academic Publishers.

[1a-1] Stock, W.G. & Stock, M. (2013). Handbook of Information Science. Berlin: De Gruyter Saur.

[2] Robertson, S.E., Walker, S., & Beaulieu, M. (1999). Okapi at TREC-7. Automatic ad hoc, filtering, VLC and interactive track. In the 7th Text REtrieval Conference(TREC 7). Gaithersburg, MD: National Institute of Standards and Technology. (NIST Special Publication 500-242.)

[3] Sparck Jones, K., Walker, S., & Robertson, S. E. (2000a) A probabilistic model of information retrieval: development and comparative experiments Part 1. Information Processing and Management, 36, 779–808

[4] Sparck Jones, K., Walker, S., & Robertson, S. E. (2000b) A probabilistic model of information retrieval: development and comparative experiments Part 2. Information Processing and Management, 36, 809–840

[5] Croft, W.B., Metzler, D., & Strohman, T. (2010). Search Engines. Information Retrieval in Practise. Boston, MA: Addison-Wesley.

[6] Mittendorf, E., Mateev, B., Schäuble, P. (2000). Using the Co-Occurences of Words for Retrieval Weighting. Alphen an den Rijn: Kluwer Academic Publishers.

[1]

[2]

[3]

[4]

[5]

[6]