Information-Retrieval

Das Information Retrieval ist die computergestützte Suche nach komplexen Inhalten. Es wurde zur Suche von Textdokumenten entwickelt und seit den 70er Jahren des letzten Jahrhunderts entsprechend eingesetzt. Im Gegensatz zu den gängigen Verfahren in RDBMS und ORDBMS werden im Information-Retrieval-Verfahren nicht die Metadaten der Medien durchsucht, sondern stattdessen die Medien selbst. Die gesuchten Informationen liegen innerhalb des Mediums vor und müssen mit geeigneten Methoden extrahiert werden. Zusätzlich wird innerhalb des Information Retrieval Verfahrens oftmals ein Feedbacksystem eingesetzt. Das Feedbacksystem versetzt den Anwender in die Lage, die vom System vorgeschlagenen Suchergebnisse zu bewerten. Durch die Bewertung der Suchergebnisse kann das System wiederum lernen und die Ergebnisse anpassen.

Grundlagen

Die Anfragen in einer "normalen" (relationalen) Datenbank sind sehr exakt, sowohl in ihrer Formulierung als auch in den vom DBS zurückgelieferten Ergebnissen. Als Beispiel dient folgende SELECT-Anfrage:

SELECT Titel, Autor 
 FROM  Buecher
 WHERE Thema="Multimedia-Datenbanken";

Diese Art der Suche wird im Folgenden als Data-Retrieval bezeichnet. Sie spezifiziert sehr genau, welche Daten gebraucht werden. Es ist keine Interpretation nötig und die Auswahl der Datensätze für die Rückgabe verläuft danach, ob das formulierte Kriterium (WHERE) zutrifft oder nicht. Eine Suche in einem Information-Retrieval-System besitzt dagegen wesentlich mehr Unschärfe, da dessen Daten nicht so strikt strukturiert sind wie beispielsweise in relationalen Datenbanken. Eine Information-Retrieval-Anfrage könnte so aussehen:

"Zeige mir Titel und Autor von allen Büchern, die sich mit dem Thema "Multimedia-Datenbanken" beschäftigen."

Die relative Unstrukturiertheit von Information-Retrieval-Systemen hat den Grund, dass es sehr schwer ist, ihre Inhalte in einem Schema zu strukturieren, da sie meist implizit vorliegen, wie zum Beispiel das Thema eines Textes oder das Motiv eines Bildes. Während relationale Anfragen eine klar abgegrenzte Menge an gleichwertig "richtigen" Ergebnissen zurückliefern, ergeben IR-Anfragen eine Liste mit nach Relevanz zur Anfrage geordneten Ergebnissen. Die Sortierung nach Relevanz ergibt sich daraus, dass es in der Regel keine klare Unterscheidung gibt, ob ein Datensatz der Anfrage genau entspricht oder nicht, und dementsprechend eine Ähnlichkeitssuche durchgeführt werden muss, welche zwar auch identische, aber hauptsächlich ähnliche Ergebnisse liefert. Unter Umständen können sich auch unähnliche, also nicht der Suchanfrage entsprechende Einträge unter den Ergebnissen befinden, welche durch eine Anfrageiteration minimiert werden können (dazu siehe Anfrage-Modifikation durch Feedback). Da eine Ähnlichkeitssuche zu formulierten Kriterien meist eine zu große Zahl an Einträgen betrifft, kann die Ergebnisliste durch einen Relevanz-Schwellenwert oder eine Begrenzung der Listengröße eingeschränkt werden. Information-Retrieval-Verfahren arbeiten nach dem Query-By-Example-Prinzip. Dem System wird in der Suchanfrage ein Beispielmedium übergeben, welches als Vergleichsobjekt innerhalb der Suche dient. Dieses Beispielmedium wird auf bestimmte Charakteristika (engl. Features) hin analysiert und anhand dieser mit den Medien innerhalb der Datenbank verglichen. Ein Information-Retrieval-System ist jedoch nicht auf die Durchführung von Ähnlichkeitssuchen beschränkt. Es ist auch hier möglich, "normale" Datenbankanfragen zu stellen, bzw. beide Arten zu kombinieren.

Vorteile gegenüber der Suche nach von Metadaten

Das Information Retrieval Verfahren birgt gegenüber dem Suchen in Metadaten Vorteile. Metadaten zu Medien müssen von Benutzern aufwändig gepflegt und aktuell gehalten werden. Zudem sind die Metainformationen oftmals nicht korrekt oder auch unvollständig. Information Retrieval Verfahren arbeiten unabhängig von den Metadaten und unterliegen daher nicht diesen Problemen. Ihre Effektivität bestimmt sich lediglich durch die Qualität der verwendeten Algorithmen.

Information-Retrieval-Modelle

Es existieren verschiedene Modelle für die Strategie einer Ähnlichkeitssuche. Die drei bekanntesten werden hier erläutert:

Abbildung 1: Boolesches Modell

Boolesches Modell

Das boolesche Modell baut auf der Mengenlehre und der booleschen Algebra auf. Sein Prinzip ist es, dass Suchterme bezogen auf ein Dokument immer mit 0 oder 1 bzw. true oder false markiert werden. Es wird also einfach unterschieden, ob ein Term mit einem Dokument in Bezug steht oder nicht. Die Anfrageformulierung erfolgt beim booleschen Modell mit booleschen Junktoren wie "and", "or" oder "not". Der Nachteil dieses Modells ist, dass es sehr exakt und einfach ist, und deswegen keine Ähnlichkeitssuche zulässt, da bei ihm alle Dokumente ähnlich wie beim Daten-Retrieval in die Mengen "relevant" und "Nicht relevant" aufgeteilt werden und somit auch keine Sortierung nach Relevanz zulässt, da diese immer nur positiv oder negativ sein kann.

Abbildung 2: Fuzzy-Modell

Fuzzy Modell

Das Fuzzy-Modell kann als Erweiterung des booleschen Modells betrachtet werden. Auch hier werden Anfragen mit booleschen Junktoren formuliert und der Bezug von Termen zu Dokumenten wird ebenfalls über boolesche Werte realisiert. Der Unterschied ist der, dass die Zugehörigkeit der Terme zu Dokumenten auf Grundlage der Fuzzy-Logik nicht mehr nur positiv oder negativ sein, sondern auch Zwischenwerte einnehmen kann. Dadurch ergibt sich, dass ein Term zu einem bestimmten Grad zu einem Dokument zugehörig ist und somit eine Ähnlichkeitssuche mit Sortierung der Ergebnisse nach Relevanz möglich ist.

Abbildung 3: Dokumente als Vektoren (vgl. [Schmitt2006])

Vektorraum-Modell

Beim Vektorraum-Modell handelt es sich um das am weitesten verbreitete Modell. Es basiert darauf, dass alle Dokumente einen Vektor im n-dimensionalen Raum darstellen, wo bei n gleich der Anzahl an Suchtermen ist. Dementsprechend eignet sich der Einsatz dieses Modells nur dort, wo die Anzahl der Terme fix ist. Die Relevanz eines Terms für ein Dokument ergibt sich bei diesem Modell aus dem Wert des "Dokument-Vektors" in der Dimension des Terms. Die Ähnlichkeitsberechnung erfolgt durch die Berechnung der Distanz zwischen gesuchtem Term und Dokumenten.

Anfrage-Modifikation durch Feedback

Wie bereits im Abschnitt zu den Grundlagen des Information-Retrieval erklärt, kann es bei der Suche in IR-Systemen neben identischen und ähnlichen Elementen auch unähnliche und somit nicht relevante Ergebnisse geben, die die Qualität der Ergebnisliste verringern. Weiterhin kann es sein, dass der Nutzer nur vage Vorstellungen über die gewünschten Informationen hat und sich mit den ersten Ergebnissen einen Überblick und somit eine genauere Vorstellung verschafft, dass er die Anfrage schlecht formuliert hat und dies erst anhand der Ergebnisse bemerkt oder auf einer inhaltlich komplett unbekannten Datenbasis arbeitet und somit nicht weiss, wonach er überhaupt suchen kann.

Abbildung 4: Information-Retrieval-Ablauf (vgl. [Schmitt2006])

Eine Möglichkeit zur Lösung dieser Probleme ist neben dem Durchschauen der gesamten Datenbasis, was ab einer gewissen Größe dieser nicht mehr sinnvoll ist, oder der händischen Modifikation der Anfrage, die oft tiefergehende Kenntnisse erfordert, das so genannte Relevance Feedback. Dabei bewertet der Nutzer einzelne Elemente des Suchergebnisses nach ihrer Relevanz, und gibt dem System damit eine Grundlage zur automatischen Modifikation und Neuausführung der Anfrage. Mit jeder Iteration verbessert sich somit das Ergebnis. Die Art der Bewertung durch den Nutzer kann verschiedene Formen annehmen.

Neben dem simplen Markieren relevanter Elemente kann es auch die Möglichkeit geben, nicht-relevante Elemente entsprechend zu markieren, damit diese und ähnliche in der nächsten Iteration nicht mehr erscheinen.

Eine weitere Möglichkeit wäre es, den Nutzer eine Relevanz-Bewertung von Elementen oder sogar verschiedener Aspekte eines Elements in Stufen vornehmen zu lassen, was mehr Genauigkeit aber auch mehr Aufwand für den Nutzer mit sich bringt. Neben der manuellen Einstufung durch den Nutzer gibt es noch das Konzept der Pseudo-Relevanz. Dabei markiert das System selbst die "oben" stehenden Elemente der nach Relevanz sortierten Ergebnisliste als besonderes relevant und führt daraufhin eine Anfragemodifikation durch.

Weitere Möglichkeiten der Anfragemodifikation sind das Anlegen von Nutzerprofilen, um Anfragen anhand des bisherigen Verhaltens des jeweiligen Nutzers zu optimieren, die Modifikation von Dokumentenbeschreibungen, wo der Bezug von Suchtermen zu Dokumenten bzw. dessen Gewichtung anhand der bisher vorgenommenen Relevanz-Markierungen verändert wird oder die Modifikation des Suchalgorithmus.

siehe auch: Image-Retrieval, Multimedia-Retrieval, Audio-Retrieval

Quellen:

[MeyerWegener2003] Meyer-Wegener, Klaus: "Multimediale Datenbanken", Teubner Verlag, Wiesbaden 2003, 2., überarbeitete Auflage.
[Schmitt2006] Schmitt, Ingo: "Ähnlichkeitssuche in Multimedia-Datenbanken", Oldenbourg Wissenschaftsverlag GmbH, München 2006.

Kategorie: Datenbanken, Objektrelationale DB, Multimediadatenbanken, M