5.3.2: Bayes'sche Inferenznetze

Während beim Imaging die Dokumente nur als Mengen von Termen behandelt wurden, können bei stärker strukturierten Dokumenten logische Verfahren besser zum Tragen kommen. Allerdings wird sich auch hier zeigen, dass die Komplexität, die eine genauere Modellierung der Struktur eines Dokumentes mit sich bringt, der Anwendung für grosse Dokumentmengen immer wieder Grenzen setzt.

Ein bayes'sches Inferenznetz kann als ein gerichteter Graph definiert werden, dessen Knoten Aussagen und dessen Kanten Abhängigkeiten zwischen Aussagen darstellen. Die Knoten können Wahrscheinlichkeitswerte zwischen 0 und 1 annehmen. Diese Wahrscheinlichkeiten dienen als Ausgangswerte zur Berechnung neuer Wahrscheinlichkeiten in den Knoten, auf die die Kanten zeigen. Dazu besitzt jeder Knoten eine Funktion oder Tabelle, die aus der Wahrscheinlichkeit der Knoten, die auf ihn zeigen, eine neue Wahrscheinlichkeit berechnet. Im einfachsten Fall, wenn es zu einem Knoten nur einen anderen Knoten gibt, der auf ihn zeigt, kann das die einfache bedingte Wahrscheinlichkeit sein.

Zur Informationsverarbeitung geht man nun von einem Muster von Aktivierungen auf den Knoten des Netzes aus. Aufgrund dieses Aktivierungsmusters werden für alle Knoten mit den zugehörigen Funktionen neue Aktivierungswerte berechnet. Dies kann solange wiederholt werden, bis sich die so berechneten Muster nicht mehr oder nur noch minimal unterscheiden. In diesem Fall spricht man von Konvergenz des Netzes. Sie muss nicht in jedem Fall eintreten.

Zur Anwendung im Information Retrieval führen Turtle und Croft (1990 [->], 1991 [->]) ein zweigeteiltes Inferenznetz ein. Dabei beschränken sie sich auf einen azyklischen Graph, der in Schichten organisiert ist. Der eine Teil, das Dokumentennetz ( Document Network) besteht aus drei Schichten von Knoten,

• der Dokumentenschicht
• der Textrepräsentationsschicht und
• der Konzeptrepräsentationsschicht.

Abb. 74: Inferenznetz für das Information Retrieval nach Turtle und Croft 1990

Der zweite Teil des Netzes, das Anfragenetz ( Query Network) kann ebenfalls aus mehreren Schichten bestehen, wobei die erste Schicht mit der Konzeptrepräsentationsschicht verbunden ist und die letzte Schicht nur aus einem Knoten besteht, dessen Wahrscheinlichkeitswert als Wahrscheinlichkeit der mit dem Netz berechneten Inferenz interpretiert wird. Dieser Teil des Netzes ist nur von der jeweiligen Anfrage abhängig und nicht von den Dokumenten.

Um mit dem Netz eine Inferenz zu berechnen, werden die Werte der Dokumente, deren Relevanz zu einer Anfrage berechnet werden soll, auf den Wert 1 gesetzt, die Knoten der anderen Dokumente erhalten den Wert 0 . Da der Graph in Schichten organisiert ist, die Verbindungen im Netz also nur in eine Richtung verlaufen, muss hier nicht untersucht werden, ob das Inferenznetz konvergiert. Die Informationsverarbeitung beschränkt sich darauf, von Schicht zu Schicht neue Aktivierungen zu berechnen. Es kann also von vorneherein bestimmt werden, nach wievielen Iterationen die Aktivierung der Eingabeknoten in der letzten Schicht angekommen ist. Es werden also bei der Textrepräsentationsschicht beginnend sukkzessive für die Knoten jeder Schicht die Wahrscheinlichkeitswerte berechnet, bis schließlich im letzten Knoten des Infereznetzes die Relevanz abgelesen wird. Dieser Wert ist eine Funktion verschiedener Beiträge, die über verschiedene Pfade durch das Netz propagiert werden. Sie repräsentieren die verschiedenen Aspekte, die zur Beurteilung der Wichtigkeit eines Dokumentes beitragen.

5.3.2.1: Die Dokumentenschicht

5.3.2.2: Die Textrepräsentationsschicht

5.3.2.3: Die Konzeptrepräsentationsschicht

Abb. 75: Schema eines Inferrenznetzes mit Regeln und Bildfeaturedetektoren

Die drei Schichten des Dokumentennetzes stellen also eine zunehmende Abstrahierung der Dokumentinhalte von der jeweiligen Oberflächenform, in der sie in den Dokumenten vorliegen, dar. Neben der Definition der entsprechenden Knoten stellt insbesondere die Bestimmung der Übergangsfunktionen für die Knoten ein Problem dar. Sie müssen einerseits einfach genug sein, um auch für große Dokumentsammlungen berechnet werden zu können, andererseit stellt ihre Flexibilität ein wesentliches Merkmal der Method dar. Abbildung _75_ zeigt den Entwurf eines Inferenznetzes mit dem auch Bildinformationen verarbeitet werden sollen.

Das Anfragenetz ist in der Theorie von Turtle und Croft einfacher strukturiert. Zwischen den Konzepten und dem Bewertungsknoten sehen sie eine Schicht mit verschiedenen Anfragetypen vor, die verschiedene Konzepte zusammenfassen.

Dadurch, dass man die Verarbeitung der Information in einem Netz graphisch darstellt, lassen sich die verschiedenen Schritte gut nachvollziehen. Insbesondere die verschiedenen Wege auf denen Teile eines Dokuments zur Gesamtgewichtung beitragen können, sind gut sichtbar. Andererseits ist die vollständige Modellierung eines solchen komplexen Netzes sehr aufwändig. Es zeigt sich, dass hier i. A. Kompromisse gemacht werden müssen.

Aus dem theoretischen Modell leiten Turtle und Croft (1991) ein weiter vereinfachtes Modell her, das in dem Retrievalsystem INQUERY implementiert wurde. Dazu

• verzichten sie auf die Textrepräsentationsschicht,
• leiten die Konzepte unmittelbar aus den Termen, die in den Dokumenten vorkommen her,
• verzichten auf die Anfrageschicht im Anfragenetz
• verwenden anstelle der Wahrscheinlichkeiten allgemeinere Werte, die aus einem IDF Maß und anderen Häufigkeitsmaßen der Terme gewonnen werden und
• ersetzen die individuellen Funktionen in den Knoten durch eine allgemeine Funktion, die in allen Knoten gleich ist. Dabei gehen sie von einer Unabhängigkeitsannahme bei der Berechnung der Aktivierungswerte der Knoten aus.

Dadurch kann das System mit Hilfe einer invertierten Liste mit Wahrscheinlichkeitswerten implementiert werden und ist trotz des zunächst komplexen Ansatzes in der Lage, sehr große Dokumentsammlungen zu verwalten. Es reduziert sich allerdings auch im wesentlichen auf ein gewichtetes Vektorraummodell. Über diese Struktur hinaus soll auch die Integration von Abhängigkeiten zwischen Dokumenten und zwischen Termen möglich sein, wie das allerding realisiert wurde, ist aus dem Text von 1991 nicht ersichtlich.

Abb. 76: Inferenznetz, wie es zur Implementierung von INQUERY verwendt wurde (nach Turtle und Croft 1991)

Zur Berechnung der Ähnlichkeiten zwischen einer Anfrage und einem Dokument verwenden Turtle und Croft in ihrem Modell von 1991 [->] verschiedene Formeln für die Wahrscheinlichkeit eines einzelnen Knotens, die sich teilweise als eine probabilistische Form des Booleschen Retrieval interpretieren lassen. Seien w_i,1,...,w_i,r die Werte der Knoten, die eine Verbindung zu einem Knoten k haben, dann lassen sich einige der Formeln so schreiben:

w_or=1-(1-w_i,1)·...·(1-w_i,r)

w_and=w_i,1·...·w_i,r

w_s=(k₁w_i,1+k₂w_i,2+...k_rw_i,r)k_q/(k₁+...+k_r)

s(w_i,q)=(w_i·q)/(q·q)

d0

w_i,k=d+(h(i,k)/h(k))

s(w_i,q)=((d+w_i~)·q)/(q·q)
=d·q/(q·q)+w_i~·q/(q·q)

Anders ist das bei dem von der AND Verknüpfung abgeleiteten Ähnlichkeitsmaß:

s(w_i,q)=_qk=1w_i,k