Information Retrieval: Die große Suche nach Wissen

Wir leben in einer Informationsgesellschaft. Daten, Fakten und Wissen nehmen einen ungleich höheren Stellenwert ein als noch vor einem halben Jahrhundert. Gleichzeitig gib es dank des Internets immer mehr verfügbare Informationen. Doch diese müssen auch abgerufen werden – dabei helfen uns Suchmaschinen. Doch wie kommen diese wiederum an die Daten, die sie ausgeben? Die Erklärung ist die sogenannte Information Retrieval. Die Informationsbeschaffung – genauer: Informationsrückgewinnung – ist eine eigene Disziplin der Informatik und der Informationswissenschaften und vor allem für Suchmaschinen von großer Bedeutung. Anhandkomplexer Information-Retrieval-Systeme erkennen sie Intentionen, die hinter bestimmten Suchbegriffen stehen und machen relevante Daten zu Suchanfragen ausfindig.

Ziel der Information Retrieval (IR) ist es, maschinell gespeicherte Daten auffindbar zu machen. Anders als beim Data-Mining, mit dem man Strukturen aus Datensätzen extrahiert, befasst sich IR damit, bestimmte Informationen aus einer Datenmenge zu filtern. Das typische Anwendungsgebiet ist eine Internet-Suchmaschine. Information-Retrieval-Systeme lösen hier vor allem zwei Probleme:

• Vagheit: Die Anfragen der Nutzer sind oft ungenau, der eingegebene Suchbegriff lässt Interpretationsspielraum. Wer z. B. nach dem Begriff „Bank“ sucht, kann Informationen zum Bankwesen allgemein oder aber eine Wegbeschreibung zum nächsten Geldinstitut benötigen. Das Problem potenziert sich, wenn die Nutzer selbst noch nicht genau wissen, was für Informationen sie überhaupt finden möchten.
• Unsicherheit: Die Inhalte der gespeicherten Informationen sind dem System mitunter nicht bekannt genug. Dadurch werden falsche Ergebnisse geliefert. Dies passiert z. B. bei Homonymen, also Wörtern, die mehrere Bedeutungen haben. So könnte der Nutzer gar nicht nach einem Geldinstitut suchen, sondern nach einer Sitzgelegenheit für seinen Garten.

Hinzu kommt, dass das Information-Retrieval-System die Informationen auch bewerten sollte, um dem Nutzer eine Reihenfolge der Daten anzubieten. Das erste Ergebnis sollte also im Idealfall die beste Antwort auf die Frage des Nutzers liefern.

Die bekanntesten Suchmaschinen im Web basieren auf dem Booleschen Prinzip. Dabei handelt es sich um logische Verknüpfungen, mit denen Nutzer die Suche verfeinern und genauer bestimmen können. Mit UND, ODER oder NICHT (AND, OR, NOT) bzw. den entsprechenden Symbolen ∧, ∨ oder ¬ lässt sich eine Anfrage spezifizieren, wenn z. B. zwingend beide Begriffe im Ergebnis auftauchen oder Inhalte mit einem bestimmten Begriff ausgeblendet werden sollen. Nach diesem Prinzip funktionieren auch die Operatoren bei Google. Der Nachteil dieses Systems ist, dass es keinerlei Rangordnung der Ergebnisse vorsieht. Sinnvoll ist eine Ordnung nach Nützlichkeit, die Methode liefert aber eine zufällige Reihenfolge.

In einem mathematischen Zugang lassen sich Inhalte auch als Vektoren darstellen. Im Vektorraummodell werden Begriffe (terms) als Koordinatenachsen abgebildet. Sowohl Dokumente als auch Suchanfragen erhalten spezifische Werte in Bezug zu dem Begriff und sind deshalb als Punkte oder Vektoren innerhalb eines Vektorraums darstellbar. Anschließend werden beide Vektoren miteinander verglichen. Der Vektor (also der Inhalt), der dem der Suchanfrage am ähnlichsten ist, sollte in der Rangliste der Ergebnisse an erster Stelle auftauchen. Der Nachteil hierbei ist, dass sich ohne Boolesche Operatoren keine Begriffe ausschließen lassen.

Das probabilistische Modell greift auf die Wahrscheinlichkeitstheorie zurück. Jedem Inhalt wird ein Wahrscheinlichkeitswert zugeordnet. Die Ergebnisse werden abhängig von der Wahrscheinlichkeit, mit der sie zur Suchintention passen, sortiert. Wie hoch die Chancen stehen, dass ein bestimmter Inhalt dem Wunsch des Nutzers entspricht, ermittelt das Modell durch sogenanntes Relevance-Feedback. Dabei werden Nutzer z. B. dazu aufgefordert, die Ergebnisse manuell zu bewerten. Bei der nächsten gleichlautenden Anfrage zeigt das Modell eine andere (und vielleicht bessere) Ergebnisliste. Nachteil dieses Verfahrens ist, dass es von zwei Anforderungen ausgeht, die nicht mit Sicherheit gegeben sind: Zum einen setzt das Modell voraus, dass die Nutzer gewillt sind, an dem System durch sein Feedback mitzuarbeiten. Zum anderen geht die Theorie davon aus, dass Nutzer die Ergebnisse unabhängig voneinander betrachten, also jeden Inhalt so bewerten, als wäre es der erste, den sie bezüglich der Suchanfrage lesen. In der Praxis schätzen Suchende die Nützlichkeit einer Information aber immer basierend auf bereits gesichteten Inhalten ein.

Beim Information Retrieval kommen – unabhängig von den Modellen – verschiedene Methoden und Arbeitstechniken zum Einsatz. Deren Ziel ist es immer, dem Nutzer die Informationssuche zu vereinfachen und relevantere Ergebnisse zu liefern.

Mit der Kombination aus Vorkommenshäufigkeit von Begriffen und der inversen Dokumenthäufigkeit wird die Wichtigkeit eines Begriffs für eine Suchanfrage berechnet. Der Wert wird abgekürzt als tf-idf.

Durch die Verbindung der beiden Tests können Information-Retrieval-Systeme bessere Ergebnisse liefern, als wenn sie allein eingesetzt würden: Wäre nur die Term Frequency von Bedeutung, dann würde die Suchanfrage „Die Sendung mit der Maus“ diejenigen Dokumente hoch einschätzen, in denen die Wörter „die“, „mit“ und „der“ häufig vorkommen. Das ist aber offensichtlich wenig hilfreich. Wird hingegen die Inverse Document Frequency hinzugezogen, bekommen „Sendung“ und „Maus“ eine sehr viel größere Bedeutung für die Suche und werden als die eigentlichen Suchbegriffe erkannt.

Ein großes Problem der Informationsbeschaffung sind die Nutzer selbst: Durch zu ungenaue oder gar fehlerhafte Anfragen erhalten sie falsche oder unzureichende Informationen. Um dies zu vermeiden, haben Informationswissenschaftler die Query Modification eingeführt. Hierbei verändert das System selbstständig die eingegebene Suchanfrage. So werden z. B. Synonyme eingesetzt, die bessere Ergebnisse liefern. Dafür greift das System u. a. auf Thesauri und Nutzer-Feedback zurück. Um nicht auf die Mitarbeit des Nutzers angewiesen zu sein, kann man auch ein sogenanntes Pseudo-Feedback anwenden. Bei dieser Methode liest das System verwandte Begriffe aus den besten Suchergebnissen aus und schätzt diese als relevant für die entsprechende Suche ein. Anfragen können u. a. durch diese Techniken erweitert oder verbessert werden:

• Stoppworteliminierung: Als Stoppwörter bezeichnet man solche Ausdrücke, die nicht oder nur unwesentlich zum Inhalt des Textes beitragen. Es ist sinnvoll, Wörter wie „und“ oder alle Artikel nicht als repräsentativ für den Inhalt des Dokuments anzusehen.
• Mehrwortgruppenidentifizierung: Gruppierungen von Wörtern müssen als solche erkannt werden. Diese Identifizierung sorgt dafür, dass die Suchmaschine auch Teile von zusammengesetzten Wörtern als relevant ansieht.
• Grund- und Stammformreduzierung: Um effektiver suchen zu können, müssen Wörter auf ihre Wortstämme reduziert werden. Flexionsformen eines Wortes würden ansonsten nicht korrekt in den Suchergebnissen auftauchen.
• Thesaurus: Neben den im entsprechenden Dokument auftauchenden Begriffen sollte ein Information-Retrieval-System auch Synonyme des Wortes als relevant ansehen. Nur so lässt sich sicherstellen, dass Nutzer auch das finden, was sie wirklich suchen.

Beide Werte liegen dabei grundsätzlich zwischen 0 und 1, wobei 1 ein perfekter Wert wäre. Zudem schließen sich perfekte Ergebnisse bei beiden Quotienten in der Praxis aus. Wer die Vollständigkeit des Suchergebnisses erhöht, tut dies auf Kosten der Genauigkeit und umgekehrt. Als weiterer Wert kann zudem der Fallout (also die Ausfallquote) berechnet werden: Dieser Quotient gibt die Falsch-Positiv-Rate wieder; er wird bestimmt aus dem Verhältnis der gefundenen, irrelevanten Dokumente zu den irrelevanten Inhalten, die nicht gefunden wurden. Darstellen lassen sich Recall und Precision in einem Achsendiagramm, bei dem jeder der beiden Werte je eine Achse belegt.

Jede Internetsuchmaschine basiert auf Information Retrieval. Somit wären Google, Bing und Yahoo prominente Beispiele für die computergestützte Informationsbeschaffung. Um zu zeigen, wie IR in der Praxis funktioniert, ist es aber sinnvoller, ein einfacheres, eigenes Beispiel zu nehmen. Dabei gehen wir von einer Suchmatrix in einer (sehr kleinen) Bibliothek für Kinderbücher aus. In allen Büchern kommen Tiere vor, doch wir möchten nur solche Bücher finden, in denen Elefanten und Giraffen eine Rolle spielen, aber keine Krokodile. Eine Suchanfrage mit der Booleschen Methode würde demnach so aussehen: Elefant UND Giraffe NICHT Krokodil. Das Ergebnis der Suche kann immer nur 1 oder 0 sein: Kommt der Begriff vor oder kommt er nicht vor?

Das Ergebnis der Suche wäre also „Tim & Olli im Zoo“ und „Michael und der verrückte Zirkus“. Damit ist aber noch keine Gewichtung der Ergebnisse gegeben. In welchem Buch geht es mehr um Elefanten und Giraffen? Dafür kann das System die Term Frequency und die Inverse Document Frequency bestimmen:

„Tim & Olli im Zoo“ ist also wahrscheinlich besser für die Suche nach einem Text mit Giraffen und Elefanten geeignet als „Michael und der verrückte Zoo“ und sollte deshalb an erster Stelle der Suchergebnisse auftauchen. Die Methode, die wir hier angewandt haben, funktioniert nur, wenn die Suchbegriffe festgelegt sind (kontrollierte Indexierung). Dies kann z. B. in Fachdatenbanken der Fall sein, bei dem die Nutzer in der Verwendung der Suchmaske geschult sind. In unserem Beispiel wäre eine Query Modification sinnvoll: Außer „Elefant“ würden auch eine Suche nach „Dickhäuter“ sowie grammatische Varianten dieser Wörter positive Ergebnisse liefern.