Information Retrieval

Kernidee, Einsatz und Entwicklung

Information Retrieval (IR), auch Informationsrückgewinnung oder Informationserschließung, bezeichnet das computergestützte Wiederauffinden bereits vorhandener Informationen, meist aus Datenbanken. Im Mittelpunkt steht die Suche nach komplexen Inhalten wie Texten, Bildern, Filmen oder Musik und nicht nur nach einzelnen Wörtern. IR gehört zur Informationswissenschaft, Informatik und Computerlinguistik. Das Erkennen neuer Strukturen gehört dagegen zur Knowledge Discovery in Databases, zu Data-Mining oder Text Mining. Dokumentenretrieval konzentriert sich besonders auf Textdokumente.

IR-Techniken werden unter anderem in Internet- und Bildsuchmaschinen, digitalen Bibliotheken, Antwortsystemen und Spamfiltern eingesetzt. Zwei Schwierigkeiten prägen die Suche: Unsicherheit entsteht, wenn Inhalte unzureichend beschrieben sind oder Homographe wie „Bank“ und Synonyme wie „Bank“ und „Geldinstitut“ nicht berücksichtigt werden. Vagheit bedeutet, dass Nutzer ihren Informationswunsch nicht präzise in Suchbegriffe übersetzen können.

Ein IR-System wandelt gespeicherte Dokumente in verarbeitbare Dokumentenrepräsentationen um. Nutzer formulieren aus ihrem Informationsbedürfnis eine Anfrage. Das System vergleicht sie mit den Repräsentationen und liefert eine Trefferliste. Danach bewerten Nutzer die Dokumente und können deren Erschließung ergänzen, die Anfrage verfeinern oder aufgrund neuer Erkenntnisse ihr Informationsbedürfnis ändern. Relevance Feedback kann solche Bewertungen zur automatischen Reformulierung der Anfrage verwenden.

Der Ausdruck „Information Retrieval“ wurde 1950 erstmals von Calvin N. Mooers verwendet. Vannevar Bush entwarf 1945 im Essay „As We May Think“ den Wissensspeicher Memex, in dem Dokumente gespeichert und über Links gesucht werden sollten. Die Sputnikschocks verdeutlichten später, dass eine große Informationsmenge nicht automatisch zu Informiertheit führt. Hans Peter Luhn entwickelte in den 1950er Jahren textstatistische Verfahren für automatisches Zusammenfassen, Indexieren und individuelle Informationsprofile. Eugene Garfield arbeitete an Zitierindices und gründete 1960 das Institute for Scientific Information. In Deutschland entstanden bei Siemens GOLEM und PASSAT. Seit den 1960er Jahren gilt die Informationswissenschaft als etabliert. Frühe kommerzielle Systeme waren unter anderem CIRC ab 1962, Orbit ab 1967, DIALOG ab 1972, MEDLINE ab 1974 und das aus OBAR hervorgegangene LexisNexis. Mit dem Internet wurde IR zum Massenphänomen; WAIS ermöglichte ab 1991 verteiltes Retrieval, bevor Websuchmaschinen diese Rolle übernahmen.

Informationsbedarf, Dokumentation und Suchdienste

Informationsbedarf ist der objektiv betrachtete Bedarf an handlungsrelevantem Wissen. Ein konkreter Informationsbedarf verlangt eine Faktenantwort, etwa „Paris“ auf die Frage nach der Hauptstadt Frankreichs. Ein problemorientierter Bedarf erfordert mehrere Dokumente, wird meist nie vollständig gedeckt und kann sich während der Recherche verändern. Das Informationsbedürfnis ist dagegen die subjektive Ausprägung dieses Bedarfs bei einem bestimmten Nutzer.

Eine Suchanfrage muss natürlichsprachliche Vorstellungen in eine Form übersetzen, die das jeweilige System verarbeiten kann. Wortorientierte Systeme arbeiten mit den eingegebenen Ausdrücken; begrifforientierte Systeme können Mehrdeutigkeiten erkennen, etwa Java als Insel, Kaffee oder Programmiersprache. Suchsprachen unterscheiden sich je nach Datenbank. Für Johnny Depp im Film „Chocolat“ nennt der Artikel beispielsweise HEADLINE:(„Johnny Depp“ w/5 „Chocolat“) bei LexisNexis, (Johnny ADJ Depp AND Chocolat) ti bei DIALOG und “Chocolat” “Johnny Depp” bei Google.

Das Ausgangsdokument, die Dokumentarische Bezugseinheit (DBE) und die Dokumentationseinheit (DE) sind zu unterscheiden. Nach der Prüfung der Dokumentationswürdigkeit wird festgelegt, ob beispielsweise ein ganzes Werk, ein Kapitel oder eine Seite die DBE bildet. Diese wird formal beschrieben und inhaltlich verdichtet. Das Ergebnis ist die DE, ein Datenbank-Stellvertreter mit informationellem Mehrwert, etwa Angaben zu Autor und Jahr. Anhand der DE entscheidet der Nutzer, ob er die DBE anfordern möchte. Information Indexing und Information Retrieval müssen deshalb aufeinander abgestimmt sein.

Kognitive Modelle berücksichtigen unter anderem Vorkenntnisse, Sprachkenntnisse und sozioökonomischen Hintergrund der Nutzer. Bei Pulldiensten sucht der Nutzer aktiv. Pushdienste oder Alerts speichern ein Informationsprofil beziehungsweise eine erfolgreiche Anfrage und melden neu eingetroffene relevante Dokumente. Marcia J. Bates bezeichnet fortlaufendes Suchen in mehreren Datenbanken und das wiederholte Ändern der Anfrage als Berrypicking. Zeit, Ort, Sprache, Gesetze und Finanzierung können dabei Informationsbarrieren bilden.

Qualität der Ergebnisse

Relevanz beschreibt, ob ein Dokument objektiv zur formulierten Suchanfrage und zum Informationsbedarf passt. Pertinenz berücksichtigt dagegen das subjektive Informationsbedürfnis. Ein relevantes Dokument kann unpassend für den einzelnen Nutzer sein, wenn dieser den Inhalt schon kennt, den Autor ablehnt oder die Sprache nicht lesen möchte. Nützlich wird Wissen, wenn der Nutzer daraus neues handlungsrelevantes Wissen erzeugt und praktisch umsetzt. Erfolgreiches IR soll das richtige Wissen zum richtigen Zeitpunkt, am richtigen Ort, im richtigen Umfang, in der richtigen Form und Qualität liefern.

Recall misst die Vollständigkeit einer Trefferliste, Precision ihre Genauigkeit:

• Recall = a/(a+c)
• Precision = a/(a+b)
• a = gefundene relevante Treffer
• b = gefundene nicht relevante DE, also Ballast
• c = relevante, aber nicht gefundene DE, also Verlust

Da unbekannt sein kann, welche relevanten Einheiten nicht gefunden wurden, ist c nicht unmittelbar messbar. Häufig lässt sich der Recall nur auf Kosten der Precision steigern und umgekehrt. Bei einer Faktenfrage sind laut Artikel beide Werte gleich eins. Ein ideales System fände alle relevanten und keine nicht relevanten Dokumente.

Der binäre Relevanzansatz ordnet ein Dokument entweder als relevant oder als nicht relevant ein. Realistischer sind oft abgestufte „Relevanzregionen“. Probabilistisch wird für ein Dokument D und eine Anfrage Q die Wahrscheinlichkeit P(D ∈ R⁺(Q)) bestimmt, wobei R⁺(Q) die Menge relevanter Dokumente bezeichnet.

Bei großen Dokumentenmengen können Relevanzverteilungen auftreten. Eine binäre Verteilung erlaubt kein Relevanzranking. Für die invers-logistische Verteilung nennt der Artikel f(x) = e^(-C)(x−1)^b mit dem Rangplatz x, der Eulerschen Zahl e, einer Konstanten c und b ≈ 3; diese Angabe ist im Artikel ausdrücklich als nicht hinreichend belegt und hinsichtlich der Herleitung von 3 als klärungsbedürftig markiert. Die informetrische Verteilung lautet f(x) = C/x^a, wobei a zwischen 1 und 2 liegt. Bei C = 1 besitzt das zweitplatzierte Dokument den Wert 0,5 für a = 1 beziehungsweise 0,25 für a = 2.

Dokumentarten und sprachliche Erschließung

Ob ein Objekt als Dokument gilt, wird anhand von vier Kriterien beurteilt: Materialität einschließlich digitalen Vorhandenseins, Intentionalität beziehungsweise Bedeutung, Erarbeitung und Wahrnehmung. Dokumente können textuell oder nicht textuell sowie digital oder nicht digital sein. Ein digitales Dokument mit mehr als zwei Medienformen, beispielsweise Video, Audio und Bildern, heißt Multimedia. Nicht digitale Objekte benötigen in einer Datenbank einen digitalen Stellvertreter, etwa ein Foto.

Formal publizierte Textdokumente haben einen geregelten und geprüften Veröffentlichungsprozess durchlaufen. „Graue Literatur“ ist zwar geprüft, aber nicht veröffentlicht. Bei formalen Publikationen werden Arbeit, Ausdruck beziehungsweise konkrete Realisierung, Manifestation und einzelnes Item unterschieden; normalerweise bezieht sich die DBE auf die Manifestation. Informell publizierte Texte, besonders Internetdokumente, sind veröffentlicht, aber nicht formal geprüft. Wikis bilden als publizierte und kooperativ geprüfte Texte eine Zwischenstufe. Briefe, Rechnungen, interne Berichte sowie Dokumente in Intranet oder Extranet zählen zu den nicht publizierten Texten.

Nicht textuelle Dokumente umfassen einerseits digitale oder digitalisierbare Filme, Bilder und Musik. Andererseits gibt es nicht digitalisierbare Gegenstände oder Sachverhalte wie chemische Stoffe und Reaktionen, Patienten und Symptome oder Museumsobjekte. In Datenbanken werden sie durch eine DE und häufig zusätzlich durch Bilder, Videos oder Audiodateien vertreten.

IR unterscheidet strukturierte, schwach strukturierte und unstrukturierte Texte. Schwach strukturierte Texte besitzen formale Merkmale wie Kapitelnummern, Titel, Zwischenüberschriften, Abbildungen oder Seitenzahlen und stehen im Mittelpunkt der Informationswissenschaft. Formale Struktur beseitigt jedoch keine Bedeutungsmehrdeutigkeit. Deshalb können menschliche Indexer Sinnzusammenhänge teilweise besser erfassen.

Terminologische Kontrolle verwendet kontrolliertes Vokabular aus Klassifikationen, Schlagwörtern, Thesauri oder Ontologien. Rechercheure und Indexer können dadurch dieselben Benennungen verwenden und Probleme durch Synonyme und Homonyme verringern. Nachteile sind verzögerte Anpassung an den Sprachwandel, Bedienungsprobleme und die hohen Kosten intellektueller Indexierung. Systeme können kontrollierte und natürliche Sprache unterschiedlich kombinieren, etwa indem eine natürlichsprachliche Anfrage im Hintergrund um Ober- und Unterbegriffe erweitert wird.

Die informationslinguistische Textbearbeitung beziehungsweise Natural Language Processing (NLP) erkennt zunächst Schriftsystem und Sprache und trennt Text, Layout und Navigation. Danach folgen n-Gramm- oder Wortanalyse, Stoppwortmarkierung, Fehlerkorrektur, Eigennamenerkennung, Grund- oder Stammformenbildung, Zerlegung von Komposita, Behandlung von Homonymen und Synonymen, Untersuchung semantischer Ähnlichkeit, Übersetzung und Anaphoraauflösung.

Retrievalmodelle und Rangbildung

Retrievalmodelle legen fest, wie Dokumente und Anfragen dargestellt, verglichen und sortiert werden. Mehrere Modelle können miteinander kombiniert werden. Das Boolesche Modell arbeitet mit UND, ODER und NICHT. In seiner ursprünglichen binären Form ermöglicht es kein Relevanzranking; eine erweiterte Form verwendet Gewichtungen und angepasste Operatoren.

Textstatistische Modelle bewerten vorkommende Terme. Die Within-document Frequency lautet WDF = Anzahl des vorkommenden Terms / Anzahl aller Wörter und wächst mit der Häufigkeit eines Wortes im Dokument. Die Inverse Dokumenthäufigkeit lautet IDF = gesamte Anzahl der Dokumente in der Datenbank / Anzahl der Dokumente mit dem Term. Je mehr Dokumente einen Term enthalten, desto kleiner ist sein IDF. Im Vektorraummodell spannen n Wörter einen n-dimensionalen Raum auf; Ähnlichkeit wird über die Winkel zwischen Vektoren berechnet. Das probabilistische Modell berechnet die Wahrscheinlichkeit, dass ein Dokument zu einer Anfrage passt, und ähnelt ohne Zusatzinformationen dem IDF.

Linktopologische Modelle nutzen Verknüpfungen zwischen Webseiten. Beim Kleinberg-Algorithmus sind Hubs Seiten mit ausgehenden und Authorities Seiten mit eingehenden Links. Gute Hubs verweisen auf gute Authorities, die wiederum von guten Hubs verlinkt werden. Der PageRank von Sergey Brin und Lawrence Page beschreibt die Wahrscheinlichkeit, mit der ein zufällig surfender Nutzer eine Seite erreicht.

Clustermodelle fassen ähnliche oder zusammengehörige Dokumente in gemeinsamen Pools zusammen und können dadurch die Suche beschleunigen. Auch Synonyme sollen berücksichtigt werden. Schwierigkeiten entstehen, weil Cluster stabil und vollständig sein müssen, sehr groß oder bis auf Einzeldokumente klein werden können und Überschneidungen schwer kontrollierbar sind. Nutzer-Nutzungsmodelle verwenden Nutzungshäufigkeit und Hintergrundinformationen wie den Standort als Rangkriterien. Rückkopplungsschleifen passen Anfragen automatisch oder mithilfe wiederholter Relevanzbewertungen an.

IR-Modelle lassen sich außerdem nach ihrem mathematischen Fundament als algebraisch, mengentheoretisch oder probabilistisch klassifizieren. Algebraische Modelle arbeiten etwa mit Vektoren, Matrizen oder Tupeln, mengentheoretische mit Mengenoperationen und probabilistische mit Wahrscheinlichkeiten, besonders dem Satz von Bayes. Eine zweite Dimension betrifft Terminterdependenzen: Modelle ohne Interdependenzen behandeln Terme als unabhängig. Immanente Interdependenzen werden aus der Kookkurrenz, also dem gemeinsamen Auftreten von Termen im Dokumentenbestand, abgeleitet. Transzendente Interdependenzen werden ausdrücklich modelliert, ihre konkrete Ausprägung muss aber von außerhalb des Modells, beispielsweise durch Menschen, vorgegeben werden.

Systemarchitektur, Websuche und Crawler

Ein Retrievalsystem besitzt Schnittstellen zu Dokumenten und Nutzern. Auf Dokumentseite werden Inhalte gefunden, auf Aktualisierungen geprüft, in ein Feldschema eingeordnet, intellektuell oder automatisch erschlossen und doppelt gespeichert: in einer Dokumentendatei und in einer invertierten Datei. Die invertierte Datei ist ein Register, in dem Wörter oder Phrasen samt Positionen und Strukturinformationen sortiert stehen. Ein Phrasenindex eignet sich beispielsweise besser für Autorenfelder als ein Wortindex. Strukturmerkmale können das Ranking beeinflussen. Die Ablage in normaler und umgekehrter Reihenfolge unterstützt eine offene Linkstrukturierung. Auf Nutzerseite folgen Anfrage, Trefferliste, Anzeige der DE und lokale Weiterverarbeitung.

ASCII entstand 1963 als 7-Bit-Code für 128 Zeichen und wurde später auf 8 Bit beziehungsweise 256 Zeichen erweitert. Unicode umfasst 4 Byte beziehungsweise 32 Bit und soll alle weltweit verwendeten Zeichen abbilden. ISO 8859 regelt zusätzlich sprachspezifische Varianten wie das deutsche „ß“.

Neue Dokumente werden durch Indexer oder automatisch durch Robots beziehungsweise Crawler aufgenommen. Ein Crawler beginnt mit einer „seed list“, verfolgt deren Links, prüft URLs und erkennt Spiegel sowie Dubletten. Best-First-Crawler priorisieren bestimmte Seiten: Der PageRank-Crawler nutzt Zahl und Popularität eingehender Links, Fish Search sucht in Bereichen mit vielen relevanten Seiten, und Shark Search berücksichtigt zusätzlich Informationen wie Ankertexte. Seitenbetreiber können ihre Seiten für Crawler sperren.

Deep-Web-Crawler müssen Suchmasken, Trefferlisten und Dokumentanzeigen verstehen; dies funktioniert nur bei kostenlosen Datenbanken. Um möglichst alle Inhalte zu erfassen, können sie beispielsweise sämtliche Jahrgänge einzeln abfragen oder bei Stichwortfeldern adaptive Strategien verwenden. Für Aktualisierungen sind regelmäßige, zufällige oder priorisierte Besuche möglich. Prioritäten können sich nach Änderungshäufigkeit oder Nutzung richten. Hinzu kommen Spam-, Spiegel- und Dublettenerkennung.

FIFO-Crawler arbeiten Links in einer Warteschlange ab. Der Breadth-First-Crawler folgt allen Links einer Seite und anschließend den Links der gefundenen Seiten. Der Depth-First-Crawler trifft nach dem ersten Schritt eine Auswahl, welchen Links er weiter folgt. Thematische Crawler konzentrieren sich auf ein Fachgebiet, verfolgen aber Links durch irrelevante Seiten hindurch, um später wieder relevante Inhalte zu finden. Distiller bestimmen mithilfe von Taxonomien und Musterdokumenten günstige Startpunkte; Classifier beurteilen Seiten auf Relevanz. Taxonomien, Musterdokumente und Begriffsordnungen müssen regelmäßig gepflegt werden.

Das Oberflächenweb ist allgemein und kostenlos erreichbar. Im Deep Web liegen unter anderem Datenbanken, deren Suchoberflächen sichtbar, deren Inhalte aber meist kostenpflichtig sind. Algorithmische Suchmaschinen verwenden grundsätzlich jede Webseite, intellektuell erstellte Webkataloge meist nur die Einstiegsseite als DBE, und Metasuchmaschinen beziehen Ergebnisse aus mehreren anderen Suchmaschinen.