Information Search and Retrieval
Vorlesungsblock 05: Query Reformulation, AI in Information Retrieval
Gerald Eigenstuhler
Alexander Hubmann
Daniel Wischounig
Inhalt
Das Ziel einer Query Reformulation ist die schrittweise Verfeinerung einer zunächts einfachen Query.
Dadurch soll die Menge der relevanten Dokumente optimiert werden.
In Abbildung 1 ist die Rolle des Relevance Feedback im Information Retrieval Prozess dargestellt.
|
Abbildung 1: Übersicht über den Information Retrieval Prozess
Bei der Query Reformulation kann zwischen Search Term Expansion und Search Term Reweighting unterschieden werden.
Da User oft Probleme bei der Erstelling von Queries haben (z.B. durch mangelnde Kenntnisse über Knowledge Domain, Suchsystem oder die Dokument-Collection), ist eine Query Reformulation oft sinnvoll.
Die Query Reformulation kann manuell geschehen, d.h. der Benutzer ändert die in seiner Suchanfrage verwendeten Terme selbst ab.
Genauso kann sie aber auch automatisch ablaufen, entweder mit oder ohne Benutzerinteraktion (Automatic Query Reforumulation with User Feedback / without User Feedback).
Das Verhalten von Benutzern bei der Suche nach Informationen kann durch Abbildung 2 beschrieben werden.
|
Abbildung 2: Verhalten der Benutzer
Bei der manuellen Query Reformulation ändert der Benutzer während des Suchprozesses die Search Query aktiv selbst, d.h. er verwendet die aus den bisherigen Suchergebnissen gezogenen Erkenntnisse zur Erweiterung bzw. Abänderung der Suchbegriffe.
Der Vorteil dabei ist natürlich, dass der Benutzer aktiv und bewusst die Search Query anhand der gefundenen Resultate anpassen kann.
Gerade für Poweruser ist dies eine gute Möglichkeit.
Nicht versierte Benutzer können dabei natürlich mit der Anpassung der Query überfordert sein.
Desweiteren sind gute Kenntnisse über die verwendete Query Language erforderlich, außerdem muss der Benutzer über entsprechende Domain Knowledge verfügen (Synonyme passend zur Domäne, ...).
Um diesen Nachteile abzuhelfen, können automatische Query-Anpassungen durchgeführt werden.
Wie bereits erwähnt, kann prinzipiell zwischen Query Expansion und Term Reweighting unterschieden werden.
Abhängig davon, welche Quellen zur Änderung der Query herangezogen werden, können folgende Lösungen zur Query Reformulation verwendet werden:
- basierend auf Feedback durch den Benutzer
- basierend auf Informationen aus den aktuellen Suchergebnissen (Local set of Documents)
- basierend auf Informationen aus dem gesamten Dokumentenbestand (Document collection)
User Relevance Feedback
Die Methode des User Relvance Feedback basiert auf Feedback durch den Benutzer, sie ist die populärste Technik zur Query Reformulation.
Der Ausgangspunkt für diese Methode ist eine initiale Search Query des Benutzers.
Mit dieser Query wird eine erste Suche durchgeführt, der Benutzer bewertet danach die relevantesten 10 bis 20 Dokumente dieser initialen Suche als "relevant" oder "nichtrelevant".
Danach kann durch eine Veränderung der Gewichte der Terme bzw. durch eine Erweiterung der Query durch neue Suchbegriffe eine schrittweise Verbesserung erzielt werden.
In Experimenten zeigt sich dabei eine gute Verbesserung der Relevanz der Suchergebnisse.
Ein Hauptvorteil der User Relevance Feedback Methode gegenüber anderen Query Reformulation Methoden ist sicherlich, dass der Benutzer vom Prozess der tatsächlichen Query Reformulation abgeschirmt wird.
Die einzige Aufgabe des Users ist die Bewertung der Suchergebnisse.
Ein weiterer Vorteil ist die Aufteilung des Suchprozesses in überschaubare Teile:
- initiale Suche
- Bewertung durch den Benutzer
- schrittweise Verbesserung der Ergebnisse
Desweiteren gibt es bei dieser Technik genau definierte Methoden zur Ermittlung der Terme bzw. deren Gewichte.
Bekannte Ausprägungen von User Relevance Feedback sind:
- Query Expansion und Term Reweighting for Vector Space Model
- Term Reweighting for Probabilistic Model
Vector Space Model
Die Bestimmung der Relevanz von Dokumenten geschieht über die Ähnlichkeit von Query und Dokument, welche als  bezeichnet wird.
Es wird dabei davon ausgegangen, dass sich die durch relevante Dokumente definierten Vektoren ähnlich sind (die Dokumente ähneln einander). Auch kann angenommen werden, dass sich die Vektoren von nicht-relevanten Dokumenten von denen der relevanten Dokumente unterscheiden.
Die Grundidee des User Relevance Feedback ist damit, die Query so zu verändern, dass sie sich den Vektoren der relevanten Dokumenten annähert.
Eine allgemeine Darstellung des durch dieses Verfahren aufgespannten Vektorraumes ist in Abbildung 3 dargestellt.
|
Abbildung 3: Vector Space Model
Die Ähnlichkeit kann auf mehrere Arten definiert werden, z.B. über den Winkel.
Die Definition dieses Zusammenhangs ist in Abbildung 4 ersichtlich.
|
Abbildung 4: Definition der Ähnlichkeit über den Winkel zwischen Query und Dokument
Die Gewichte der einzelnen Index-Terme werden dabei aus der normalisierten Term Frequenz  und der inversen Dokumenten Frequenz  bestimmt, wie in Abbildung 5 dargestellt.
|
Abbildung 5: Bestimmung der Gewichte der einzelnen Index-Terme
Wenn alle relevanten Dokumente bekannt sind, ergibt sich die optimale Query wie in Abbildung 6 dargestellt.
|
Abbildung 6: Optimale Query im Vector Space Modell
Dabei bezeichnet
 das Set aller relevanten Dokumente alle Dokumente der Kollektion
Das Problem dabei ist, dass die relevanten Dokumente nicht a priori bekannt sind!
Die Abhilfe dafür sind Methoden, die ausgehend von einer initialen Query eine inkrementelle Annäherung durchführen.
Beispiele für solche Methoden sind in Abbildung 7 ersichtlich.
|
Abbildung 7: Inkrementelle Annäherung an die optimale Query
Dabei bezeichnet
 das Set aller durch den Benutzer bestimmten relevanten Dokumente das Set aller durch den Benutzer bestimmten nicht relevanten Dokumente Konstanten das höchts-gerankte, nicht relevante Dokument
Wenn gleich 1 sind, entspricht dies der originalen Richio Formel. Wenn  , spricht man von einer positiven Feedback Strategie.
Der großen Vorteile dieser Methoden sind ihre Einfachheit und ihre guten Resultate. Die Einfachheit kommt aus der Berechnung der neuen Gewichtsterme direkt aus dem Set der gefundenen Dokumente.
Probabilistic Model
Die Relevanz von Dokumenten geschieht in diesem Modell durch folgenden Zusammenhang, wie in Abbildung 8 dargestellt.
|
Abbildung 8: Bestimmung der Relevanz
Dabei bezeichnet
 die Gewichte der Index- und Query-Terme die Wahrscheinlichkeit, dass  in einem zufällig ausgewählten Dokument aus  vorkommt die Wahrscheinlichkeit, dass nicht in einem zufällig ausgewählten Dokument aus vorkommt (d.h. die Wahrscheinlichkeit, dass in einem nicht-relevanten Dokument vorkommt)
Die Startwerte für diese beiden Wahrscheinlichkeiten werden durch den Zusammenhang aus Abbildung 9 bestimmt.
|
Abbildung 9: Bestimmung der Startwerte
Die weiteren Werte (inkrementelle Änderung) dieser Wahrscheinlichkeiten werden durch die Formel aus Abbildung 10 bestimmt.
|
Abbildung 10: Bestimmung der Wahrscheinlichkeiten
Bei kleinen Werte von  und  sind folgende Zusammenhänge vorzuziehen, wie in Abbildung 11 dargestellt.
|
Abbildung 11: Bestimmung der Wahrscheinlichkeiten bei kleinen Werten
Die Wahrscheinlichkeiten können allerdings auch durch Interaktion des Benutzers angepasst werden.
Dabei ergibt sich folgender Zusammenhang (Abbildung 12):
|
Abbildung 12: Bestimmung der Wahrscheinlichkeiten, Benutzer Feedback
Dabei bezeichnet
 das Set aller durch den Benutzer als relevant klassifizierten Dokumente das Set aller durch den Benutzer als relevant klassifizierten Dokumente, die enthalten die Anzahl aller Dokumente der Kollektion die Anzahl der Dokumente, die enthalten
Auch hier kann eine Anpassung an kleine Werte durchgeführt werden.
Dadurch ändern sich die Zusammenhänge zu (Abbildung 13):
|
Abbildung 13: Bestimmung der Wahrscheinlichkeiten, Benutzer Feedback, kleine Werte
Der Vorteil dieser Methode ist, dass das Benutzer-Feedback direkt im IR-Modell wirkt.
Ein Nachteil dieser Technik ist, dass sich die Gewichte der Dokumentterme sich bei Feedback nicht auswirken.
Die Gewichte der vorherigen Query gehen ebenfalls nicht in eine neue Query ein.
Außerdem werden keine neuen Query Terms abgeleitet, sondern nur vorhandene Terme neu gewichtet.
Allgemein beeinflusst Relevance Feedback Recall und Precision positiv, was zu mehr und besser gerankten Dokumenten führt.
Bei der Bestimmung dieser Kenngrößen müssen allerdings bestimmte Vorraussetzungen erfüllt werden.
Wenn die im Query-Verbesserungs-Schritt als relevant eingestuften Dokumente in die Berechnung mit einbezogen werden, kommt es zu einer Verfälschung.
Um diese Verfälschung zu vermeiden, werden die im Vorangegangenen bewerteten Dokumenten nicht mehr berücksichtigt.
Dadurch ergeben sich zwar tendenziell niedrigere Recall-Precision-Kurven, was jedoch für Vergleiche kein Problem darstellt.
Artificial Inteligence in Information Retrieval
Künstliche Intelligenz spielt in den Letzten Jahren in der Informatik eine immer größere Rolle. Selbst in den Medien wird of diskutiert, über die Auswirkungen von künstlichen Intelligenz-Ansätzen zur Lösung verschiedener Problem im Bezug auf die Menschlichkeit oder die Ersetzbarkeit der Menschen. In vielen Bereichen ist dies durch mehr oder weniger intelligente Systeme z.B. Roboter schon geschehen. Genau bei hier setzt auch die Domäne von Information Retrieval an, es wird nach Systemen gesucht:
- die handeln wie Menschen
- denken wie Menschen
- sinnvoll handeln, anders als Menschen
- sinnvoll denken, anders als Menschen
Die folgenden Kapitel fallen unter den Aspekt der Künstlichen Intelligenz und wissensbasierten Ansätze:
Fuzzy Logic, Fuzzy Set Theory
Fuzzy Logic ist eine Logic die nicht nur einen Richtig und einen Falsch Zustand kennt sondern auch Zustände dazwischen. Diese Aufweichung der Zustandsgrenzen nennt man auch Unschärfe.
Bei der abstrakten Darstellung von Dokumenten und Suchanfragen durch die Menge von Schlüsselwörtern erhält man Beschreibungen die nur bedingt mit den realen Inhalten verknüpft sind. Daher sind die erhaltenen Dokumente zu einer Anfrage nur ungenau.
Als Einleitung um die Bedeutung von Fuzzy Logik zu veranschaulichen kann folgendes Beispiel angegeben werden. Es wird von verschiedenen Personen die Raumtemperatur definiert. Wobei die technische Definition von 19° Celsius bis 24° Celsius als Raumtemperatur gilt. In Abbildung 14 ist einerseits eine disktrete Logik zu sehen bei der es nur die strikten Grenzen gibt, andererseits zeigt die Abbilung eine Grafik beider die Raumtemperatur sich um 20° Celsius bewegt. Diese wird mit unscharfen Kanten begrenzt da zum Beispiel für mache Personen 19° Celsius absolut nicht als Raumtemperatur gilt für andere aber schon. Der Zugehörigkeitsgrad in diesen Skizzen beschreibt mit welcher Genauigkeit, ähnlich zur Wahrscheinlichkeit, der jeweilige Temperaturwert als Raumtemperaturwert gezählt wird.
 |
Abbildung 14: Raumtemperatur als Beispiel zu Erläuterung der Fuzzy Logik.
Die Idee angewandt auf Information Retrieval bzw. die Dokumenten Domäne ist eine Zugehörigkeitsfunktion zu finden für die jeweiligen Dokumente zu einer gegebenen Anfrage. Es ist sinnvoll diese Funktion Werte im Interval [0,1] annehmen zu lassen wobei 0 bedeutet dass keinerlei Zugehörigkeit existiert und 1 bedeutet vollständige Zugehörigkeit. Wobei die Werte zwischen 0 und 1 als Randwerte oder grenzwertig (marginal) bezeichnet werden. Diese Möglichkeit oder Kennzeichnung existiert in konventioneller Boolscher Logik nicht, dort gibt es nur abrupte Grenzen.
Definition: Eine Fuzzy Teilmenge  eines 'Universums'  ist bestimmt durch die Zugehörigkeitsfunktion  die zu jedem Element  aus eine Zahl  im Interval  zuordnet.
Wie auch bei anderen Mengensystemen werden auch hier die drei Mengenoperationen: Komplement, Vereinigungs- und Schnittmenge definiert:
Definition: Die Menge ist das sogenannte Universum, und  sind zwei Fuzzy Teilmengen von und  ist das Komplement von bezogen auf . Wenn ein Element von ist gelten folgende Annahmen:
 |
Abbildung 16: Verschiedene Fuzzy Zugehörigkeitsfunktionen.
Ein zusätzlicher Ansatz um die Suchen zu optimieren ist es einen Thesaurus anzupassen um Term Beziehungen herzustellen. Die Grundidee ist es die Menge der Index Terme in einer Anfrage zu erweitern um dann Dokumente die die ursprünglichen Suchterme garnicht enthalten ebenfalls zu finden. Diese erweiterten Suchbegriffe werden dem Thesaurus entnommen der durch die Term-Term Korrelations Matrix bestimmt wird, deren Zeilen und Spalten den Index Termen der Dokumente zugeordnet sind.
In dieser Matrix ist der normalisierte Korrelations Faktor  zwischen zwei Termen  und  folgend definiert:
Wobei  die Anzahl der Dokumente bestimmt, die den Term  enthalten,  die Anzahl der Dokumente ist die den Term enthalten und  die Anzahl der Dokumente ist die beide Terme enthalten. Diese Korrelations-Metrik wurde schon weitgehend bei den Clustering Algorithmen erläutert. Im Folgenden kann die Term Korrelations Matrix dazu verwendet werden jedem Index Term eine Fuzzy Menge zuzuordnen. In dieser Fuzzy Menge erhält jedes Dokument  einen Zugehörigkeitsgrad der als Algebraische Summe aller Terme im jeweiligen Dokumet berechnet wird. Der Einfachheit der Berechnung wird statt der Summe das negative Produkt der Komplemente genommen.
Ein Dokument gehört dann zu der Fuzzy Menge des Termes wenn seine Terme in Verbindung zu stehen. Wenn auch nur ein Term des Dokumentes stark zu dem Index Term gebunden ist, was durch den Korrelationsfaktor ausgedrückt wird (nahe an 1), dann ist auch  nahe an 1 und der Index ist somit ein guter Fuzzy Index für das Dokument. Im anderen Fall, wenn alle Index Terme des Dokumentes nur schlecht mit verbunden werden können ist ein schlechter Fuzzy Index für dieses Dokument, ist dann nahe bei 0.
In der Anwendung bei der Suche wird vom Benutzer eine Anfrage verlangt. Diese wird unter Benützung der gewöhnlichen Boolschen Logik angegeben. Diese wird dann in die Disjunktive Normalform konvertiert um sie für dieAufweichung der Grenzen durch die Fuzzy Logik vorzubereiten. Das Verfahren ist nun ähnlich, bzw. nahezu identisch dem der Boolschen Logik.
Allgemein geschrieben:  wobei  jeder Komponent der disjunktiven Normalform darstellt.
Beispiel:
Anhand des folgenden Beispieles wird der Sachverhalt genauer dargelegt. Die Anfrage  soll aufgelöst werden. Die Anfrage wird für die Endgültige Auflösung auf die Form  gebracht. Um eine Anfrage aufzulösen bedient man sich erst der Vereinfachung zur disjunktiven Normalform, die mit dem Gewichtungsvektor und dem Anfrage Tupel angschrieben wird:
 , 
 |
Abbildung 17: Grafische Darstellung der Anfrage
Um nun die einzelnen Komponenten zu finden geht man wie folgt für alle Komponenten vor. Die Fuzzy Menge  von Dokumenten für den Index Term  wird aus den Dokumenten erzeugt die einen entsprechenden Zugehörigkeitsgrad ( ) der Index Terme aufweisen der einen bestimmten Schwellwert überschreitet. Weiters ist  das Komplement von die mit der Negation der Index Terme verknüpft ist. Auf die selbe Weise können die Fuzzy Mengen  und  definiert werden.
Die Menge  ist die Fuzzy Menge der Anfrage und Antwort die die Vereinigung der einzelnen Komponenten Mengen darstellt. Die Zugehörigkeit  eines Dokumentes der Antwort Menge kann wie folgt berechnet werden.
Logic-based Reasoning
Neurnale Netzwerke
In einem \emph{Information Retrieval System} werden Dokument
Vektoren mit Query Vektoren verglichen um ein Ranking für die
Suchergebnisse zu erhalten. Das bedeutet dass Dokumente und
Anfragen angepasst und gewichtet werden um das Ranking
durchzuführen.
Aus anderen Kontexten ist bekannt, dass \emph{neuronale Netzwerke}
gut geeignet sind für Mustervergleiche, was daher veranlasst diese
auch in dieser Domäne einzuführen.
\subsection{Grundprinzipien}
Neuronale Netzwerke sind Abbildungen des menschlichen Gehirns, wo
Milliarden von \emph{Neuronen} auf einfachste Weise miteinander
ein Netzwerk bilden. Die Mächtigkeit wird durch die große Anzahl
der Neuronen erklärt.
Die Funktion eines solchen Netzwerkes ist denkbar einfach, dass
jedes einzelne Neuron als Basisknoten mit mehreren Ein- und
Ausgängen gesehen wird. Die Vernetzung erfolgt mit gewichteten
Verbindungen, die in jedem Neuron dann einen Ausgangswert bewirken
wenn ein wiederum gewichteter und veränderbarer Schwellwert
überschritten wird. Jeder Ausgang ist wieder Eingang eines anderen
Neurons, wodurch ein gigantisches Netzwerk entsteht.
Als einfache Skizze eines Neuronalen Netzwerks für die Domäne der
\emph{Information Retrieval Systeme} kann ein drei schichtiger
vereinfachter Graf angesehen werden (Abbildung
\ref{fig_neuronal}).
Die erste Schicht stellt die Menge der \emph{Query Terms} dar, die
zweite stellt die \emph{Document Terms} dar und die dritte die
Dokumente selbst.
Abbildungsverzeichnis
Abbildung 1: Übersicht über den Information Retrieval Prozess
Abbildung 2: Verhalten der Benutzer
Abbildung 3: Vector Space Model
Abbildung 4: Definition der Ähnlichkeit über den Winkel zwischen Query und Dokument
Abbildung 5: Bestimmung der Gewichte der einzelnen Index-Terme
Abbildung 6: Optimale Query im Vector Space Modell
Abbildung 7: Inkrementelle Annäherung an die optimale Query
Abbildung 8: Bestimmung der Relevanz
Abbildung 9: Bestimmung der Startwerte
Abbildung 10: Bestimmung der Wahrscheinlichkeiten
Abbildung 11: Bestimmung der Wahrscheinlichkeiten bei kleinen Werten
Abbildung 12: Bestimmung der Wahrscheinlichkeiten, Benutzer Feedback
Abbildung 13: Bestimmung der Wahrscheinlichkeiten, Benutzer Feedback, kleine Werte
Abbildung 14: Raumtemperatur als Beispiel zu Erläuterung der Fuzzy Logik.
Abbildung 15: Die Mengenoperationen: Komplement, Vereinigung, Schnitt.
Abbildung 16: Verschiedene Fuzzy Zugehörigkeitsfunktionen.
Abbildung 17: Grafische Darstellung der Anfrage.
|
