Modelle des Information Retrieval

Im Folgenden wird ein kurzer Überblick über die wichtigsten Information-Retrieval-Modelle gegeben. Dies sind das Boolesche Modell, das Vektorraummodell und das probabilistische Modell.
In der Darstellung wird vor allem auf deren Tauglichkeit für bzw. Verwendung in Suchmaschinen eingegangen. Für umfassende Darstellungen der besprochenen Modelle sei auf Korfhage (1997), Belkin u. Croft (1987) sowie Grossman u. Frieder (2000) verwiesen.

Boolesches Modell

Das Boolesche Modell ist das einzige der hier vorgestellten, welches nach der Methode des exact match, also der exakten Übereinstimmung zwischen Anfrage und Dokument, arbeitet. Suchbegriffe werden mit den Dokumenten bzw. deren Repräsentanten abgeglichen. Es werden nur Dokumente ausgegeben, die die Suchbegriffe exakt in der Form, in der sie eingegeben wurden, enthalten.
Zur Formulierung der Suchanfrage stehen im klassischen Modell die drei Operatoren AND, OR und NOT, in manchen Systemen auch das ausschließende Oder (XOR), zur Verfügung. Weiterhin besteht die Möglichkeit der Klammersetzung, um komplexe Suchanfragen formulieren zu können. Erweiterungen des Booleschen Modells sehen Abstandsoperatoren vor, mit denen die Treffermenge weiter eingeschränkt werden kann.
Neben dem kostengünstigen Aufbau boolescher Retrievalsysteme werden die bestehende Popularität solcher Systeme (und daher die Gewöhnung zumindest der regelmäßigen Nutzer an diese) sowie die Flexibilität als Vorteile dieses Systems angesehen (Chu, 100). Die Formulierung der Suchanfragen ist bei entsprechender Kenntnis der Operatoren und ihrer Anwendung nahezu unbeschränkt möglich. Boolesche Operatoren bieten damit eine effektive Möglichkeit, ein Informationsbedürfnis in einer Suchanfrage auszudrücken.
Die Recherche mit Hilfe der Booleschen Logik wird in den meisten kommerziell verfügbaren Systemen eingesetzt und hat sich entsprechend etabliert. Allerdings wird die Boolesche Suche oft und ausführlich kritisiert (vgl. u.a. Cooper 1988; Chu 2003, 100-102; eine Verteidigung des Booleschen Prinzips findet sich in Frants et al. 1999). Belkin u. Croft (1987, 113) fassen die Nachteile der Booleschen Systeme (bzw. aller Systeme, die ein exact match erfordern) unter fünf Punkten zusammen:
1. Viele relevante Dokumente werden nicht gefunden, weil ihre Repräsentationen die Anfrage nur teilweise erfüllen.
2. Es findet kein Ranking statt.
3. Die unterschiedliche Wertigkeit bestimmter Begriffe innerhalb der Anfrage oder innerhalb des Texts wird nicht berücksichtigt.
4. Die Formulierung der Anfragen ist kompliziert.
5. Die Repräsentation der Anfrage und die Repräsentation des Dokuments müssen im gleichen Vokabular vorliegen.
Der erste Punkt beschreibt das Problem, welches bei der Suche mit mehreren Begriffen auftritt. Werden diese mit AND verknüpft, so werden nur Dokumente gefunden, die alle eingegebenen Begriffe exakt in der eingegebenen Form enthalten. Dokumente, die beispielsweise alle bis auf einen der Begriffe enthalten, werden ausgeschlossen. Es findet also kein Vergleich der Ähnlichkeit zwischen Anfrage und Dokument statt, sondern nur ein Abgleich exakter Gemeinsamkeiten. In der Websuche ist dieses Problem allerdings dadurch nicht genauso gravierend wie in professionellen Datenbanken, da in Suchmaschinen in den meisten Fällen deutlich weniger Terme pro Anfrage eingegeben werden (für Datenbanken vgl. Spink u. Saracevic 1997; für Suchmaschinen Spink u. Jansen 2004).
Dadurch, dass im Booleschen Modell keine Unterscheidung der Relevanz der Dokumente stattfindet, kann auch beim Retrieval keine Grenze gesetzt werden, wie viele Dokumente ausgegeben werden sollen (Chu 2003, 102).
Auf das nicht vorhandene Ranking in rein Booleschen Systemen bzw. auf die Vorteile des Rankings allgemein wird in Kapitel 6 ausführlich eingegangen. Bereits hier ist jedoch schon anzumerken, dass ein Ranking überhaupt erst notwendig ist, wenn die Dokumentenmenge zu groß ist, um vom Nutzer gesichtet zu werden. Das Boolesche Modell geht davon aus, dass bereits durch die Anfrage die Treffermenge so weit eingeschränkt wird, dass nur wenige hoch relevante Treffer übrig bleiben.
Für komplexe Suchanfragen kann es sinnvoll sein, den Begriffen schon bei der Suche unterschiedliche Wertigkeiten zu geben. So kann bestimmt werden, dass ein Begriff beispielsweise auf jeden Fall in den ausgegebenen Dokumenten vorhanden sein muss, ein anderer aber nur vorkommen sollte, stattdessen aber auch ein anderer Begriff vorkommen kann. Solche Anfragen werden im klassischen Booleschen Retrieval nicht unterstützt. Für den durchschnittlichen Suchmaschinen-Nutzer dürften solche Anfragen auf jeden Fall zu kompliziert sein; als einzige Suchmaschine hat AltaVista eine Zeit lang in der erweiterten Suche eine entsprechende Möglichkeit angeboten (Chu 2003, 109), diese wurde jedoch schon bald wieder eingestellt.
Punkt vier beschreibt einen grundsätzlichen Nachteil des Booleschen Modells, nämlich seine mangelnde Verständlichkeit (s.a. Cooper 1988, 243). Da alle Anfragen zuerst in eine formale Sprache übersetzt werden müssen, sei das Modell für den Laien schwer verständlich und daher sei es für diesen nur schwer möglich, adäquate Suchanfragen zu formulieren. Insbesondere die Formulierung komplexer Suchanfragen, für die die Arbeit mit Klammern notwendig ist, um die Reihenfolge der Verarbeitungsschritte auszudrücken, bereitet enorme Probleme (s.a. Kapitel 2.6).
Der fünfte Punkt beschreibt das Problem des mangelnden Recalls aufgrund der nicht exakten Übereinstimmung zwischen den in der Suchanfrage verwendeten Begriffen und denen, die in der Repräsentation bzw. im Falle einer reinen Volltextindexierung im Dokument selbst verwendet werden. Dokumente werden nicht gefunden, weil ein im Dokument verwendeter Begriff beispielsweise ein Synonym des gesuchten Begriffs ist oder weil im Dokument nur die Pluralform anstatt der in der Suchanfrage verwendeten Singularform verwendet wird. Für Suchmaschinen ist diese Problematik relevant: Sie arbeiten mit einer Volltextindexierung und verwenden kein kontrolliertes Vokabular, welches die aufgezeigten Probleme mindern könnte. In der Regel geben sie auch nur strenge exact matches zurück, so dass eine Menge von eigentlich relevanten Dokumenten nicht ausgegeben wird. Allerdings geben Suchmaschinen aufgrund ihres immensen Datenbestands auf die meisten typischen Suchanfragen hin eine sehr große Menge an Dokumenten zurück, die vom Benutzer nicht alle gesichtet werden können. Wird eine zweiwertige Relevanzbewertung allein der „Top-Treffer" zu Grunde gelegt, erscheint es fraglich, ob sich der Anteil der relevanten Dokumente signifikant verändert, wenn Suchanfragen mit Singular- bzw. Pluralformen oder Suchanfragen mit Synonymen eines Begriffs ausgeführt werden. Entsprechende Untersuchungen liegen allerdings bisher nicht vor.
Für die Web-Suchmaschinen (und alle anderen Systeme, die Volltexte indizieren) ergibt sich das Problem des in Booleschen Anfragen nicht berücksichtigten Kontext der Suchbegriffe. Da Dokumente im Booleschen System als relevant eingestuft werden, sobald sie die Anfrage erfüllen, aber keine Unterscheidung nach dem Grad der Relevanz stattfindet, wird ein Dokument, welches die Suchbegriffe in direkter Umgebung enthält als ebenso relevant angesehen wie eines, in dem die Suchbegriffe weit voneinander entfernt stehen. Aufgrund der Volltexterschließung sowie der besonders großen Menge der vorhandenen Dokumente ist es für die Suchmaschinen unabdingbar, den Grad der Relevanz der gefundenen Dokumente zu messen und eine entsprechend gewichtete Trefferliste auszugeben. Die Grundlage des Matchings in Suchmaschinen bildet jedoch das Boolesche Modell. Nachdem eine Menge von der Booleschen Anfrage entsprechenden Dokumenten ermittelt wurde, wird diese Menge mittels eines Rankingverfahrens in eine nach Relevanz sortierte Listenform gebracht.
Nicht alle Internet-Suchmaschinen unterstützen allerdings die kompletten Booleschen Funktionen. Insbesondere Google bietet keine vollständige Unterstützung der Booleschen Operatoren, so dass die Formulierung mancher Anfragen schlicht unmöglich wird. Andere Anfragen können durch die Benutzung nicht regelkonformer Syntax gestellt werden (Notess 2000). Da Operatoren nur selten verwendet werden (Spink u. Jansen 2004, 184; Machill et al. 2003, 167f.), müssen die Suchmaschinen die eingegebenen Begriffe automatisch verknüpfen; alle bekannten Suchmaschinen tun dies mittlerweile mit der AND-Verknüpfung, obwohl aufgrund von Rankingverfahren, die das Vorkommen aller Begriffe in einem Dokument bevorzugen, auch an eine OR-Verknüpfung zu denken wäre. Diese wurde einige Jahre beispielsweise bei AltaVista eingesetzt.

Vektorraummodell

Als Grundproblem des Booleschen Modells (wie auch aller anderen Modelle, die das Konzept des Exact Match verfolgen) kann die notwendige genaue Übereinstimmung zwischen den in der Suchanfrage und in den Dokumenten verwendeten Begriffen angesehen werden. Einerseits werden von rein booleschen Verfahren viele irrelevante Dokumente gefunden, die zwar die Suchbegriffe enthalten, in denen diese jedoch nicht im Kontext zueinander stehen, andererseits werden relevante Dokumente nicht gefunden, weil sie nicht exakt die Begriffe in der Form enthalten, wie sie in der Suchanfrage eingegeben wurden.
Salton u. McGill (1987, 126) sehen die Stärken des klassischen Modells des exact match darin, dass es bei einer konsistenten Indexierung mittels eines einheitlichen Indexierungsvokabulars, welches sowohl dem Indexer als auch dem Rechercheur gut bekannt ist, gute Ergebnisse liefert. Dazu kommt, dass dieses Verfahren aufgrund der Arbeit mit einer invertierten Datei für kurze Antwortzeiten sorgt, da auf die Dokumentdatei erst zugegriffen werden muss, wenn die Ergebnisse angezeigt werden. Als Nachteil ist zu sehen, dass nur exakte Übereinstimmungen als Treffer gewertet werden, ähnliche Dokumente aufgrund der Nicht-Geordnetheit der invertierten Datei nicht nahe beieinander stehen und alle gefundenen Dokumente als gleich relevant eingestuft werden.
Das Vektorraummodell nach Salton (Salton, Wong u. Yang 1975; Salton u. McGill 1987) verspricht eine Lösung dieser Problematik, indem es nicht mehr nach exakten Übereinstimmungen zwischen Suchanfrage und Dokumenten sucht, sondern nach Ähnlichkeiten zwischen Dokument und Suchanfrage oder zwischen mehreren Dokumenten.

Abb. 5.1. Verktorraumpräsentation eines Dokumentraums (Salton u. McGill 1987, 129)

Der vieldimensionale Vektorraum wird durch die Terme aufgespannt, wobei jeder Term eine Dimension darstellt. Jedes Dokument wird repräsentiert durch einen Vektor, der alle enthaltenen Begriffe bzw. alle für die Indexierung verwendeten Deskriptoren enthält (s. Abb. 5.1). Durch die Berechnung des Cosinus des Winkels zwischen zwei Dokumenten bzw. zwischen einem Dokument und einer Suchanfrage lässt sich deren Ähnlichkeit berechnen. Je kleiner der Cosinus des Winkels, desto ähnlicher sind sich Anfrage und Dokument. So ist es möglich, eine nach dem Grad der Ähnlichkeit sortierte Trefferliste auszugeben. Dabei kann entweder ein Grenzwert festgelegt werden, der angibt, wie ähnlich sich die Dokumente mindestens sein sollen, oder aber es kann die Anzahl der Treffer, die vom System zurückgegeben werden soll, angegeben werden. Ein weiterer Vorteil ist, dass bei der Formulierung der Anfrage keine Eingabe von Operatoren erforderlich ist. Systeme, die das Vektorraummodell einsetzen, sind daher auch von Anfängern bedienbar.
Allerdings hat das Vektorraummodell auch einige Nachteile. So wird in diesem Modell angenommen, dass die eingegebenen Suchbegriffe völlig unabhängig voneinander sind (Chu 2003, 105). Es ist nicht möglich, Begriffe mit Operatoren zu verbinden, um beispielsweise Synonyme durch eine Oder-Verknüpfung zu erfassen. Um eine sinnvolle Anfrage zu stellen, sind relativ viele Suchbegriffe nötig (Chu 2003, 105). Während in Booleschen Systemen schon wenige mit AND verknüpfte Begriffe zu guten Ergebnissen führen können, scheitern Systeme, die das Vektorraummodell einsetzen, an solchen Anfragen. Noch gravierender stellt sich das Problem dar, wenn bestimmte Begriffe ausgeschlossen werden sollen. Im Booleschen Modell ist dafür der Operator AND NOT vorgesehen; im Vektorraummodell ist ein solcher Ausschluss von Suchbegriffen schlicht nicht möglich.
Für Suchmaschinen ist das Vektorraummodell insofern von Bedeutung, als dass es das Ranking nach der Relevanz der gefundenen Treffer eingeführt hat. Die grundlegende Annahme der Ähnlichkeit zwischen Dokument und Suchanfrage wird in Suchmaschinen übernommen, um dem Nutzer bei in der Regel enorm großen Treffermengen die besten Treffer auf den vorderen Rängen zu präsentieren. Auf Fragen des Rankings wird im nächsten Kapitel ausführlich eingegangen.
Als alleiniges Modell wird das Vektorraummodell in keiner Suchmaschine eingesetzt; teilweise bildet es allerdings eine Komponente eines umfangreicheren Systems (z.B. in Bharat u. Henzinger 2000). Alle bekannten Systeme verwenden bevorzugt Verfahren des exact match und setzen höchstens einfache linguistische Verfahren ein, um beispielsweise die Pluralformen der Suchbegriffe mit einzubeziehen (s. Kapitel 7.3).

Probabilistisches Modell

Das probabilistische Modell geht davon aus, dass aufgrund der Gegebenheiten der natürlichen Sprache nicht mit Sicherheit festgestellt werden kann, ob ein Dokument für eine Suchanfrage relevant ist oder nicht (Sparck Jones u. Willett 1997, 129). Vielmehr kann nur eine Wahrscheinlichkeit ermittelt werden, ob das Dokument für die Suchanfrage relevant ist. Im probabilistischen Modell wird die Relevanz auf der Grundlage der Ähnlichkeit zwischen der Anfrage und dem Dokument gesehen, wobei der Ähnlichkeitswert abhängig von der Häufigkeit der Suchbegriffe im Dokument ist. Je ähnlicher sich Anfrage und Dokument sind, desto höher ist die Wahrscheinlichkeit, dass das Dokument für die Suchanfrage relevant ist
Auch in diesem Modell wird eine gerankte Trefferliste ausgegeben, wobei ein Schwellenwert verwendet wird, der ausdrückt, wie hoch die Wahrscheinlichkeit der Relevanz mindestens sein muss, damit das Dokument in die Treffermenge mit aufgenommen wird. Die Dokumente werden absteigend nach ihrer angenommenen Relevanz gelistet.
Die Vorteile des Modells sind in seiner theoretischen Begründbarkeit auf zwei Ebenen zu sehen (Fuhr 2004, 211): Das Modell kann sowohl über die Retrievalmaße als auch entscheidungstheoretisch über die Kosten begründet werden.
Die theoretische Annahme, dass es eine gewisse Unsicherheit im Retrievalprozess gibt, die automatische Gewichtung, welche den Nutzer von der Gewichtung der Suchbegriffe entlastet, das Ranking sowie die natürlichsprachliche Eingabe der Suchanfrage ohne Operatoren werden als weitere Vorteile gesehen (Chu 2003, 107). Problematisch ist allerdings, dass in diesem Modell die Relevanz der Dokumente als voneinander unabhängig betrachtet wird. Im Rechercheprozess ist allerdings die neu erworbene Kenntnis bereits betrachteter Dokumente zu berücksichtigen: Ein Dokument ist für den Rechercheur nicht mehr relevant, wenn er bereits eines mit gleichem oder ähnlichem Inhalt gesehen hat.
In der Praxis hat sich das probabilistische Modell zumindest bislang nicht bewährt und es konnte keine Verbesserung der Retrievaleffektivität gegenüber anderen Modellen festgestellt werden (Chu 2003, 108). Die Anwendung erfolgt(e) nahezu ausschließlich in experimentellen Systemen. Auch wenn dieses Modell in der theoretischen Information-Retrieval-Diskussion von hoher Bedeutung ist, ist es im Anwendungskontext ohne Bedeutung und erscheint auch für den Anwendungskontext Suchmaschinen nicht sinnvoll. Eine Stärke könnte das Modell beim Relevance Feedback (Kap. 10.1) entfalten; allerdings dürften die dafür erforderlichen Dokumentbewertungen durch den Suchmaschinennutzer diesen bereits überfordern.

Tabelle 5.2. Eigenschaften der drei Information-Retrieval-Modelle (Chu 2003, 112)

Tabelle 5.2 zeigt nochmals zusammenfassend in der Übersicht, wie sich die drei besprochenen Information-Retrieval-Modelle voneinander unterscheiden und durch welche Eigenarten sie sich auszeichnen.
Die Analyse der populären Suchmaschinen auf der Basis von wissenschaftlichen Veröffentlichungen und patentierten Technologien (u.a. Brin u. Page 1998; Bharat u. Henzinger 2000) zeigt zwar, dass die Suchmaschinen durchaus Verfahren einsetzen, die Eigenarten verschiedener Information-Retrieval-Modelle kombinieren. Allerdings liegt der Schwerpunkt auf dem Exact Matching des Booleschen Modells, wobei dieses durch Verfahren des Relevance Ranking ergänzt bzw. verbessert wird.
In den folgenden Kapiteln sollen die Verfahren des Relevance Ranking, die bei Suchmaschinen Einsatz finden, ausführlich vorgestellt werden. Im nächsten Kapitel sollen hierfür zuerst die Grundlagen und allgemeinen Probleme des Rankings besprochen werden, bevor die einzelnen Rankingverfahren und -fakto¬ren ausführlich diskutiert werden.