Titelblatt des Buchs
Reginald Ferber Information Retrieval
Suchmodelle und Data-Mining-Verfahren für Textsammlungen und das Web

Position im Angebot Information Retrieval -> Erweiterte Retrieval-Ansätze -> Logikbasierte Modelle des Information Retrieval
Stichwörter dieser Seite probabilistische Inferenz, mögliche Welt, possible world, Aussage, Rangfolge, Ähnlichkeitsfunktion, Vektorraummodell, Indikatorfunktion, charakteristische Funktion, Imaging, IDF, Ähnlichkeitsmaß
Navigation Zurück ]    [ Inhalt ]    [ Stichwörter ]    [ Feedback ]    [ Home ]

3.3.1: Imaging

Um die Konsistenzprobleme anzugehen, die sich bei einer strengen logischen Interpretation ergeben, kann man eine probabilistische Inferenz einführen. Sie schätzt die Wahrscheinlichkeit p(d->q) ab, dass eine Folgerung gilt - hier: dass die Anfrage q aus dem Dokument d gefolgert werden kann. Dazu kann man zunächst jedes Dokument als eine "mögliche Welt" (possible world) betrachten, also als eine Menge von Aussagen mit zugehörigen Wahrheitswerten. Das Prinzip der unsicheren oder probabilistischen Inferenz ist nun folgendes: Es seien zwei Aussagen x und y gegeben. Als Maß der Unsicherheit der Aussage y->x ("aus y folgt x ") bezüglich einer gegebenen Datenbasis kann der Umfang der kleinsten Informationsmenge gewählt werden, die zu der Datenbasis hinzugefügt werden muss, damit die Aussage y->x gültig ist.

Aus dieser eher vagen Beschreibung leitet van Rijsbergen schrittweise konkreter werdend einen Algorithmus ab, mit dem Dokumente in eine Rangfolge bezüglich einer Anfrage gebracht werden können. Dazu benötigt man eine Ähnlichkeitsfunktion zwischen den "möglichen Welten" wMathematisches Zeichen: Element vonW und eine Wahrscheinlichkeitsfunktion p auf dem Grundraum W .

Im Laufe dieser Ableitung wird sich zeigen, dass sich das System dabei im Wesentlichen auf ein gewichtetes Vektorraummodell reduziert, bei dem aus dem Korpus gewonnene Ähnlichkeiten zwischen Termen bei der Gewichtung berücksichtigt werden.

Seien nun wieder x und y zwei Aussagen und wMathematisches Zeichen: Element vonW eine "mögliche Welt". Mit
Griechischer Buchstabe sigma(w,y)
wird die Welt bezeichnet, die am ähnlichsten zu w ist und in der y gilt. Man sagt dann, dass y->x gilt, wenn x in Griechischer Buchstabe sigma(w,y) gilt. Bezeichnet
Griechischer Buchstabe tau (w,x) = {
1 falls x in w gilt
0 sonst
die Indikatorfunktion (charakteristische Funktion) dafür, dass eine Aussage in einer Welt gilt, dann folgt:
Griechischer Buchstabe tau(w,y->x)=Griechischer Buchstabe tau (Griechischer Buchstabe sigma(w,y), x)
Die Wahrscheinlichkeit p(y->x) wird nun folgendermaßen definiert:
p (y->x) =
Mathematisches Zeichen: Summe
wMathematisches Zeichen: Element vonW
p (w) Griechischer Buchstabe tau (w,y->x) =
Mathematisches Zeichen: Summe
wMathematisches Zeichen: Element vonW
p (w) Griechischer Buchstabe tau (Griechischer Buchstabe sigma(w,y), x)
Das heißt, um die globale Wahrscheinlichkeit des Schlusses y->x zu bestimmen, wird zu jeder Welt w die ähnlichste Welt gesucht, in der die Aussage y gilt, und nachgesehen, ob dort auch x gilt. Ist das der Fall, wird die Wahrscheinlichkeit der Welt w zur globalen Wahrscheinlichkeit addiert. Der Übergang zur ähnlichsten Welt, in der y gültig ist, wird Imaging genannt. Durch Imaging und den Mittelungsprozess soll die Informationsmenge geschätzt werden, die im Mittel fehlt, damit y->x gültig ist.

Man kann die Imaging-Technik auf Dokumente als "mögliche Welten" anwenden. Dabei ergibt sich aber das Problem, dass auch die Aussage y ein Dokument ist. Nimmt man an, dass ein Dokument in einem anderen Dokument nur dann "gültig" ist, wenn es eine Teilmenge davon ist, könnten beim Imaging nur solche Dokumente verwendet werden, bei denen das eine im anderen enthalten ist. Solche Dokumente sind aber vermutlich selten.

Crestani und van Rijsbergen (1995) [->] wählen deshalb eine Menge T von Termen als "mögliche Welten". Die Wahrscheinlichkeit der Inferenz von einem Dokument d auf eine Anfrage q ergibt sich dann als
p (d->q) =
Mathematisches Zeichen: Summe
tMathematisches Zeichen: Element vonT
p (t) Griechischer Buchstabe tau (Griechischer Buchstabe sigma(t,d), q)
Inhaltlich kann ein Term im einfachsten Fall als durch die Menge der Dokumente repräsentiert angesehen werden, in denen er auftritt. Das heißt, ein Dokument bzw. eine Anfrage ist in einem Term "gültig", wenn der Term darin auftaucht. Hat man zusätzlich eine Ähnlichkeitsfunktion zwischen Termen, so wird beim Imaging die Wahrscheinlichkeit eines Terms, der nicht in einem Dokument auftaucht, auf den nächstgelegenen Term aus dem Dokument übertragen.

Die globale Wahrscheinlichkeit p(d->q) für ein Dokument dMathematisches Zeichen: TeilmengeT und eine Anfrage qMathematisches Zeichen: TeilmengeT kann folgendermaßen berechnet werden:

  • Zunächst wird für jeden Term tMathematisches Zeichen: Element vonT\d der Term t'Mathematisches Zeichen: Element vond bestimmt, der t am ähnlichsten ist.
  • Dann wird die Wahrscheinlichkeit p(t) auf die von t' addiert.
  • Schließlich werden diese Summen über alle Terme aus der Anfrage q aufaddiert.
Diese Summe wird als Wahrscheinlichkeit interpretiert, dass sich die Anfrage q aus dem Dokument d folgern lässt. Die Dokumente werden in der Rangfolge, die sich aus diesen Werten ergibt, ausgegeben.

Entscheidend für diese Bewertung sind die Wahrscheinlichkeiten der Terme und das Ähnlichkeitsmaß zwischen den Termen. Da sie lediglich an einer Rangordnung der Dokumente interessiert sind, wählen Crestani und van Rijsbergen (1995) [->] anstelle einer Wahrscheinlichkeit das IDF-Maß
IDF(ti)=- log(
ni
Leere Abbildung mit der der Bruchstrich erzeugt wird
N
)
wobei ni die Anzahl der Dokumente in der Sammlung angibt, in denen der Term ti vorkommt, und N die Gesamtzahl der Dokumente. (In diesem IDF-Maß ist
ni
Leere Abbildung mit der der Bruchstrich erzeugt wird
N
<=1
, damit ist der Logarithmus negativ, das IDF-Maß also positiv. Qualitativ verhält es sich wie die anderen in Abschnitt 1.3.6.3 besprochenen IDF-Maße: Für seltene Terme ist es groß, für häufige klein.)

Pfeil als Kennzeichnung einer Unterueberschrift Abbildung 76: Imaging

Als Ähnlichkeitsmaß wählen Crestani und van Rijsbergen das EMIM-Maß:
EMIM (ti,tj) =
Mathematisches Zeichen: Summe
(ti,tj )Mathematisches Zeichen: Element von{0,1} 2
p (ti,tj) log
p(ti ,tj)
Leere Abbildung mit der der Bruchstrich erzeugt wird
p(t i)·p(tj )
Dabei sind p(ti) bzw. p(tj) die Wahrscheinlichkeitsverteilungen für die Gültigkeit des Terms ti bzw. des Terms tj , also seines Auftretens in einem Dokument. p(ti,tj) ist die Wahrscheinlichkeitsverteilung des gemeinsamen Auftretens von ti und tj . In der Summe wird also über die vier Auftretensmöglichkeiten - keiner der Terme, nur ti , nur tj und beide Terme - summiert.

Pfeil als Kennzeichnung einer Unterueberschrift Abbildung 77: Probleme des Imaging

Mit den Daten aus der Cranfield Collection wurden Versuche gemacht, wobei zwei Läufe verglichen wurden, einer mit Imaging und einer, in dem lediglich die IDF-Werte als Gewichtungen verwendet wurden. Die Ergebnisse zeigen leicht bessere Ergebnisse für Imaging. Der Unterschied ist aber statistisch nicht signifikant.

Navigation Zurück ]    [ Inhalt ]    [ Stichwörter ]    [ Feedback ]    [ Home ]
Position im Angebot Information Retrieval -> Erweiterte Retrieval-Ansätze -> Logikbasierte Modelle des Information Retrieval
Dieser Abschnitt und seine Unterabschnitte
Inhalt Stichwörter in der Reihenfolge ihres AuftretensStichwörter alphabetisch sortiert
3.3.1Imaging
Abb. 76 Imaging
Abb. 77 Probleme des Imaging
probabilistische Inferenz, mögliche Welt, possible world, Aussage, Rangfolge, Ähnlichkeitsfunktion, Vektorraummodell, Indikatorfunktion, charakteristische Funktion, Imaging, IDF, Ähnlichkeitsmaß Ähnlichkeitsfunktion, Ähnlichkeitsmaß, Aussage, charakteristische Funktion, IDF, Imaging, Indikatorfunktion, mögliche Welt, possible world, probabilistische Inferenz, Rangfolge, Vektorraummodell

Diese Seiten sind urheberrechtlich geschützt. Die Verantwortung für die Inhalte und die Rechte der Online-Version liegen beim Autor Reginald Ferber, Münster (Westf). Die Rechte der gedruckten Version beim dpunkt.verlag, Heidelberg. Die Weiterverwendung von Texten oder Abbildungen - auch auszugsweise - ist ohne die schriftliche Zustimmung des Autors Reginald Ferber bzw. des dpunkt.verlags nicht gestattet.

Es wird darauf hingewiesen, dass die verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken-, oder patentrechtlichem Schutz unterliegen. Alle Angaben und Programme wurden mit großer Sorgfalt kontrolliert. Trotzdem kann keinerlei Haftung für Schäden irgendwelcher Art übernommen werden, die sich im Zusammenhang mit der Nutzung dieser Seiten ergeben.

Diese HTML-Datei wurde am 27-10-2003 erzeugt.