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" wW 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 wW eine "mögliche Welt". Mit

(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 (w,y) gilt. Bezeichnet

(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:

(w,y->x)= ((w,y), x)

Die Wahrscheinlichkeit p(y->x) wird nun folgendermaßen definiert:

p

(y->x)

=

wW

p

(w)

(w,y->x)

=

wW

p

(w)

((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)

=

tT

p

(t)

((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 dT und eine Anfrage qT kann folgendermaßen berechnet werden:

• Zunächst wird für jeden Term tT\d der Term t'd 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.

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 N

)

wobei n_i die Anzahl der Dokumente in der Sammlung angibt, in denen der Term t_i vorkommt, und N die Gesamtzahl der Dokumente. (In diesem IDF-Maß ist

ni 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.)

Abbildung 76: Imaging

Als Ähnlichkeitsmaß wählen Crestani und van Rijsbergen das EMIM-Maß:

EMIM

(ti,tj)

=

(ti,tj ){0,1} 2

p

(ti,tj)

log

p(ti ,tj) p(t i)·p(tj )

Dabei sind p(t_i) bzw. p(t_j) die Wahrscheinlichkeitsverteilungen für die Gültigkeit des Terms t_i bzw. des Terms t_j , also seines Auftretens in einem Dokument. p(t_i,t_j) ist die Wahrscheinlichkeitsverteilung des gemeinsamen Auftretens von t_i und t_j . In der Summe wird also über die vier Auftretensmöglichkeiten - keiner der Terme, nur t_i , nur t_j und beide Terme - summiert.

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.