% Studienarbeit von Ulrike Steffens
%
% Universitaet Hamburg
% Fachbereich Informatik
% Arbeitsbereich DBIS
%
% Kapitel: INQUERY: Ein probabilistisches Information Retrieval System
% 2.4.96

\chapter{INQUERY: Ein probabilistisches Information Retrieval System}
\index{INQUERY}
\label{inq}
Um dem wachsenden Interesse Rechnung zu tragen, das dem Information Retrieval 
aufgrund immer gr"o"serer verf"ugbarer Datenmengen und variierender
Formen der Information entgegengebracht wird, wurde im Information Retrieval 
Laboratory der Universit"at von Massachusetts das System INQUERY entwickelt. 
Dieses dient der Forschung auf dem Gebiet des Information Retrieval mit 
verschiedenen Arten von Text\-re\-pr"a\-sen\-ta\-tio\-nen, Suchmodellen, 
Lernverfahren und Schnittstellen \cite{cch92}.

INQUERY folgt dem probabilistischen Modell der Inferenznetze\index{Inferenznetz} 
(vgl. Abschnitt
\ref{inferenz}), was den Vorteil hat, da"s verschiedene Indizierungs- und
Anfragekonzepte in diesem System verkn"upft werden k"onnen.

\section{Architektur von INQUERY}
\label{inqarch}
Die Aufgaben eines Information Retrieval Systems sind die 
rech\-ner\-ad\-"a\-qua\-te
Darstellung\index{Repr"asentation} der Dokumente der Textsammlung und des 
Informationsbedarfs des
Benutzers sowie die Auswertung der Anfrage hinsichtlich der 
Text\-repr"asentationen. Die Architektur von INQUERY erf"ullt diese Aufgaben
folgenderma"sen (vgl. Abb. \ref{arch}). 

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsfxsize=7cm \epsfysize=7cm
\epsffile{/usr/users/stud/steffens/Studienarbeit/Latex/Bilder/arch.epsf}
\end{center}
\caption[Die Architektur des Information Retrieval Systems INQUERY]{Die Architektur des Information Retrieval Systems INQUERY [CCH91]}
\label{arch}
\end{figure}

Eine Textsammlung durchl"auft zun"achst ein Parser\index{Parser Subsystem} 
Subsystem, das die 
Dokumente f"ur das Information Retrieval aufbereitet und dabei 
Transaktionen\index{Transaktionen}
({\em transactions\index{transactions}}) erstellt. Diese enthalten 
Informationen "uber in den
Dokumenten enthaltene Terme\index{Term}, die f"ur die Generierung einer
 invertierten\index{invertierte Datei} Datei ({\em inverted\index{inverted file}
file}) verwendet werden. Die 
invertierte Datei ist die Grundlage, 
auf der das Retrieval Subsystem\index{Retrieval Subsystem} die Anfragen 
verarbeitet, die es nach einer
dem Parsing\index{Parsing} "ahnlichen Verarbeitung von der 
Benutzerschnittstelle\index{Benutzerschnittstelle} erh"alt. Als Ergebnis 
liefert das Retrieval Subsystem die
von ihm ermittelte Dokumentenrangfolge\index{Rangfolge} an die 
Benutzerschnittstelle zur"uck.
Der Benutzer kann mit Hilfe einer Ansichtsdatenbank\index{Ansichtsdatenbank} 
({\em viewing\index{viewing database} database}), die
ebenfalls vom Parser Subsystem bereitgestellt wird, die ihm relevant 
erscheinenden Dokumente einsehen.


\subsection{Parser Subsystem}
\index{Parser Subsystem}
\label{parsing}
Um eine Textsammlung f"ur das Information Retrieval nutzbar zu machen, m"ussen
zun"achst die enthaltenen Dokumente auf entsprechende 
Repr"asentationen\index{Repr"asentation}
abgebildet werden (vgl. Kapitel \ref{ir}). Dieser Vorgang wird als 
Parsing\index{Parsing}
bezeichnet. Da INQUERY dem Modell der Inferenznetze\index{Inferenznetz} 
folgt (vgl. Abschnitt 
\ref{probabModelle}), kann das
Parsing auch als Aufbau der Kanten zwischen den Dokumenten- und den 
Konzeptknoten des Inhaltsnetzes\index{Inhaltsnetz} angesehen werden 
\cite{cch92}. Das Parsing ist in vier 
Phasen aufgeteilt: Die Anordnungsanalyse\index{Anordnungsanalyse} 
({\em layout\index{layout analysis} analysis}), die 
lexikalische\index{lexikalische Analyse} Analyse, die 
syntaktische\index{syntaktische Analyse} Analyse und
die Begriffserkennung\index{Begriffserkennung} ({\em 
concept\index{concept identification} identification}). W"ahrend dieser 
Phasen werden Transaktionen\index{Transaktion} generiert, die jeweils einen 
Term, das dazugeh"orige
Dokument sowie die Stellen im Dokument, an denen der Term vorkommt, 
beinhalten \cite{bcc94}.
Die Programmodule der einzelnen Parsingphasen f"uhren die Transaktionen einem
Transaktionsmanager\index{Transaktionsmanager} zu, der sie f"ur die 
sp"atere Datei-Inversion\index{Datei-Inversion} ({\em
file\index{file inversion} inversion}) abspeichert \cite{cch92}.

\subsubsection{Anordnungsanalyse}
\index{Anordnungsanalyse}
W"ahrend der Anordnungsanalyse werden Anfang und Ende der Dokumente erkannt. 
Der Text wird von Informationen unterschieden, die f"ur 
den Zweck des Information Retrieval irrelevant sind, wie z.B. 
von Formatierungsinformationen, Katalogisierungsinformationen
oder "ahnlichem. Optional k"onnen w"ahrend der Anordnungsanalyse die 
Begrenzungen besonderer Felder\index{Feld} (vgl. Kapitel \ref{ir}), wie z.B. 
Titel, Haupttext usw., erkannt werden \cite{bcc94}.

Die Programme zur Anordnungsanalyse in INQUERY arbeiten standardm"a"sig 
mit einer Untermenge der Trennzeichen\index{Trennzeichen} 
({\em tags\index{tag}}) der {\em Standardized\index{Standardized General
Mark-up Language} 
General Mark-up Language (SGML)}. Da die Module zur 
Anordnungsanalyse
mit Hilfe des Parsergenerators {\em yacc\index{yacc}} \cite{asu88} erstellt 
wurden, ist es unproblematisch, 
diese durch Module, die andere Dokumentenformate verarbeiten, zu ersetzen 
oder zu erg"anzen.

\subsubsection{Lexikalische Analyse}
\index{lexikalische Analyse}
Die Module f"ur die lexikalische Analyse erkennen Wortbegrenzungen und 
generieren Transaktionen\index{Transaktion} f"ur die 
Indizierung\index{Indizierung} der W"orter. Stoppw"orter\index{Stoppw"orter}
(vgl. Kapitel \ref{ir}) k"onnen optional erkannt werden. Zu diesem Zweck
steht den Modulen der lexikalischen Analyse eine Stoppliste\index{Stoppliste} 
zur Verf"ugung, die
vom Benutzer spezifiziert wird. Wird ein Stoppwort erkannt, so wird dieses
nicht indiziert. Es verbleibt jedoch im Text, damit es in den weiteren 
Analysephasen zur Verf"ugung steht. Die 
Stammformreduktion\index{Stammformreduktion} (vgl. Kapitel 
\ref{ir}) ist ebenfalls optional
\cite{bcc94}. 

Die Module, die die lexikalische Analyse
in INQUERY durchf"uhren, liegen im {\em lex}-Format\index{lex} vor. 
{\em lex} ist ein standardisiertes
UNIX-Werkzeug, das aus regul"aren\index{regul"are Grammatik} Grammatiken 
endliche\index{endlicher Automat} Automaten generiert \cite{les79}. 
Dadurch wird die Erstellung von
Programmen erm"oglicht, die beliebige Formate von Textsammlungen lexikalisch
analysieren k"onnen.

\subsubsection{Syntaktische Analyse} 
\index{syntaktische Analyse}
Die syntaktische Analyse dient zur "Uberpr"ufung der Konsistenz der 
Textsammlung. Ist diese nicht gegeben, so sorgen die Programme der
syntaktischen Analyse f"ur Fehlererholung\index{Fehlererholung}. In INQUERY 
stehen verschiedene 
Programme zur syntaktischen Analyse zur Verf"ugung, die mit 
{\em yacc\index{yacc}} erstellt 
wurden und sich die {\em SGML}\index{Standardized Mark-up Language}-Trennzeichen
in der Textsammlung zunutze machen
\cite{cch92}.

\subsubsection{Begriffserkennung}
\index{Begriffserkennung}
INQUERY erm"oglicht es, die Textsammlung mit
verschiedenen Begriffserkennern\index{Begriffserkenner} 
(vgl. Kapitel \ref{ir}) zu bearbeiten. 
 Hat ein Begriffserkenner
ein bestimmtes Muster identifiziert, so f"ugt er dem Dokument einen 
Meta-Indexterm\index{Meta-Indexterm}
hinzu und generiert eine entsprechende Transaktion\index{Transaktion}. 
Wird beispielsweise ein Firmenname erkannt, so wird f"ur die entsprechende
Stelle im
Dokument und f"ur den Metaterm \#COMPANY eine Transaktion generiert.
Die Begriffserkenner in INQUERY liegen im 
{\em lex}- oder {\em flex}-Format\index{lex}\index{flex} vor.

\subsection{Generierung der invertierten Datei}
\index{invertierte Datei}
Jede Transaktion\index{Transaktion}, die w"ahrend des Parsing\index{Parsing} 
generiert wird, stellt eine
Kante zwischen einem Dokumenten- und einem Konzeptknoten des 
Inhaltsnetzes\index{Inhaltsnetz} dar. Die Gesamtmenge dieser Transaktionen 
entspricht dem
Inhaltsnetz der Textsammlung. Der Wert eines internen Knoten in einem 
Inferenznetz\index{Inferenznetz}
errechnet sich "uber eine Funktion der Werte seiner Vaterknoten. Die
Geschwindigkeit, mit der w"ahrend des Information Retrieval der Wert eines
Knotens berechnet wird, ist daher abh"angig davon, wie schnell auf
Information "uber diesen Knoten und vor allen Dingen "uber die ihn verbindenden
Kanten zugegriffen werden kann. INQUERY stellt diese Information
f"ur die Konzeptknoten des Inhaltsnetzes als invertierte Datei zur
Verf"ugung. Die w"ahrend des Parsings erkannten Terme und Konzepte,
wie z.B. die Meta-Indexterme der Begriffserkennung, bilden die 
Schl"usselwerte der invertierten Datei. Jedem Term oder Konzept sind seine 
Vorkommensh"aufigkeit\index{Vorkommensh"aufigkeit}
in der gesamten Textsammlung, die Anzahl der Dokumente, in denen er vorkommt,
und die Transaktionen, in denen er erscheint, zugeordnet \cite{cch92}.
Die invertierte Datei bildet eine wichtige Basis  
f"ur die Verarbeitung und die Auswertung der Anfragen \cite{par95}.

\subsection{Verarbeitung der Anfragen}
\index{Anfrage}\index{Anfrageverarbeitung}
\label{queryProcessing}
Vor dem eigentlichen Anfrageproze"s mu"s zun"achst spezifiziert werden, auf
welche der vorhandenen INQUERY Datenbanken zugegriffen werden soll. Ein
gleichzeitiger Zugriff auf mehrere Datenbanken ist in der vorliegenenden Version
des Systems nicht m"oglich. 

INQUERY l"a"st Anfragen in nat"urlicher Sprache, aber auch in einer 
strukturierten Anfragesprache\index{Anfragesprache} (siehe Anhang 
\ref{queryLanguage}) zu.
Anfragen in nat"urlicher Sprache werden zun"achst von 
Textbearbeitungsmodulen\index{Textbearbeitungsmodul}
({\em text\index{text processing module} processing modules}) interpretiert, 
um zu gew"ahrleisten, da"s
die lexikalische\index{lexikalische Analyse} Analyse und die 
Begriffserkennung\index{Begriffserkennung} hier genauso ablaufen
wie im Parser\index{Parser Subsystem} Subsystem. Die Resultate der 
Textbearbeitung werden in 
strukturierte Anfragen umgewandelt, indem auf die Terme\index{Term} der 
Anfrage der
{\em \#sum}-Operator\index{Anfrageoperator} angewendet wird. 
Anhang \ref{queryLanguage} und die Gleichungen
\ref{Formel1} - \ref{Formel6} in Abschnitt \ref{retrievalEngine} beschreiben 
{\em \#sum} sowie die anderen
Operatoren der strukturierten Anfragesprache von INQUERY. Durch die Operatoren
der Anfragesprache ist es den Textbearbeitungsmodulen oder dem Benutzer 
m"oglich, zus"atzlich zu den blo"sen Termen strukturelle Information in die
Anfrage einzubinden. Unter anderem kann so nach ganzen Phrasen, wie z.B.
{\em ''House of Representatives''}, oder nach mehreren Termen in gewissem
Abstand zueinander gesucht werden \cite{bcc94}. Die Operatoren der
Anfragesprache werden in das Anfragenetz integriert (vgl. Abbildung
\ref{Anfragenetz}).

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsfxsize=7cm \epsfysize=7cm
\epsffile{/usr/users/stud/steffens/Studienarbeit/Latex/Bilder/anfrage.epsf}
\end{center}
\caption[Ein Teil eines INQUERY Anfragenetzes]{Ein Teil eines INQUERY Anfragenetzes [HKW94]}
\label{Anfragenetz}
\end{figure}
Wie die Dokumente der Textsammlung k"onnen
auch die Anfragetexte auf Stoppw"orter\index{Stoppwort} untersucht und auf 
ihre Wortst"amme\index{Wortstamm} reduziert werden (vgl. 
Abschnitt \ref{parsing}).

Die Vorg"ange w"ahrend der Anfragebearbeitung m"ussen zumindest denen im
Parser Subsystem entsprechen, da sonst die Gefahr besteht, da"s
Information Retrieval Prozesse nicht mehr die gew"unschten Ergebnisse
liefern k"onnen (vgl. Kapitel \ref{ir}).
Zus"atzlich zu den Modulen, die diese Anforderung erf"ullen, 
enth"alt INQUERY weitere
Prozessoren zur Bearbeitung des Anfragetextes. Einer davon erkennt 
Wortgruppen\index{Wortgruppen},
die entweder durch Bindestriche verbunden oder durch  Gro"sschreibung 
gekennzeichnet sind. Bindestriche werden w"ahrend des Parsings grunds"atzlich 
entfernt. In den Dokumenten werden aus Ausdr"ucken, wie {\em Iran-Contra}, 
einzelne
Terme, wie {\em Iran Contra}. Um dennoch sinnvoll nach dem Gesamtbegriff suchen
zu k"onnen, wird bei der Anfrageverarbeitung der Bindestrich entfernt und 
die einzelnen
W"orter werden mit dem Nachbarschaftsoperator\index{Nachbarschaftsoperator}
 {\em \#1} verbunden. In der 
Anfrage wird aus {\em Iran-Contra} also {\em \#1( Iran Contra )}. Dadurch 
wird erzwungen,
da"s die beiden W"orter im Dokument unmittelbar nebeneinander stehen m"ussen,
um die Anfrage zu erf"ullen. Entsprechendes geschieht mit Gruppen von W"ortern
in Gro"sschreibung. So wird {\em House of Representatives} in einer Anfrage
\mbox{zu {\em \#2( House Representatives )}} \cite{bcc94}.

Ein weiterer Textprozessor in INQUERY entfernt Ausdr"ucke, die sich auf
den Information Retrieval Proze"s und nicht auf den Inhalt der
gesuchten Dokumente beziehen, wie beispielsweise {\em ''A relevant document must
contain ...''} oder {\em ''I would like to know something about\nolinebreak ...''}. Ob solche
Ausdr"ucke entfernt werden k"onnen, h"angt jedoch von dem Fachgebiet ab,
f"ur das Information Retrieval betrieben wird. Daher m"ussen die Regeln dieses
Textprozessors an den Benutzungskontext angepa"st werden \cite{bcc94}.

Die Textprozessoren f"ur die Anfrageverarbeitung in INQUERY liegen im {\em
flex}-Format\index{flex} vor. Eine zus"atzliche Bearbeitung der Anfragen 
mit weiteren
Textprozessoren vor der Bearbeitung
durch INQUERY ist m"oglich. Die Anfragekonzepte des Systems lassen sich
hierdurch erg"anzen \cite{bcc94}.



\subsection{Retrieval Subsystem}
\index{Retrieval Subsystem}
\label{retrievalEngine}
Das Anfragenetz\index{Anfragenetz} dient als Eingabe f"ur
das Retrieval Subsystem, das es mit dem Inhaltsnetz\index{Inhaltsnetz} der 
Textsammlung verbindet.
Im eigentlichen Information Retrieval Vorgang wird das vollst"andige 
Inferenznetz\index{Inferenznetz} wie folgt ausgewertet.

	
Zun"achst wird bestimmt, mit welcher Wahrscheinlichkeit ein
Konzeptknoten $Q$ des Anfragenetzes den 
Informationsbedarf\index{Informationsbedarf} erf"ullt, unter der Annahme, 
da"s alle Dokumente der
Textsammlung betrachtet werden. Dieser Wert $bel(Q)$ wird auch als 
Erf"ullungsgrad\index{Erf"ullungsgrad} ({\em belief\index{belief} value}) 
des Knotens bezeichnet und ist vom Typ des
Knotens abh"angig. Er kann durch die
folgenden Formeln unter Einsetzung der Bewertungen $p_i$ und Gewichtungen $w_i$ 
der jeweiligen $n$ Vorg"angerknoten ermittelt werden. Der Erf"ullungsgrad
eines Negationsknotens $bel_{not}(Q)$ ist dabei nur von einem Vaterknoten
abh"angig.
\begin{eqnarray}
\label{Formel1}
bel_{not}(Q) = 1 - p
\end{eqnarray}
\begin{eqnarray}
bel_{or}(Q) = 1 - (1 - p_1) \cdot \ldots \cdot (1 - p_n)
\end{eqnarray}
\begin{eqnarray}
bel_{and}(Q) = p_1 \cdot p_2 \cdot \ldots \cdot p_n
\end{eqnarray}
\begin{eqnarray}
bel_{max}(Q) = max(p_1, p_2,\hspace{0.2cm}\ldots\hspace{0.2cm}, p_n)
\end{eqnarray}
\begin{eqnarray}
bel_{sum}(Q) = \frac{p_1 + p_2 + \ldots + p_n}{n}
\end{eqnarray}
\begin{eqnarray}
\label{Formel6}
bel_{wsum}(Q) = \frac{({w_1}p_1 + {w_2}p_2 + \ldots + {w_n}p_n) \cdot w_q}
{w_1 + w_2 + \ldots + w_n}
\end{eqnarray}
Nun werden der Reihe nach alle Dokumentenknoten $d_i$ des Inhaltsnetzes 
betrachtet.
Die Bewertung eines jeden Knotens $d_m$ wird "uber das Netz weitergegeben und der
Knoten wird markiert. Dadurch wird die bedingte Wahrscheinlichkeit $P(I|d_m)$
des Ereignisses berechnet, da"s das Dokument $d_m$ den Informationsbedarf $I$ des
Benutzers deckt \cite{hkw94}. Die Details der Auswertung
mit Hilfe von Inferenznetzen beschreibt \cite{tcr91}.

\section{Schnittstellen von INQUERY}
\index{Schnittstelle}
\label{schnitt}
INQUERY kann im Stapelbetrieb\index{Stapelbetrieb} ausgef"uhrt werden. 
Auch eine 
Benutzerschnittstelle\index{interaktive Benutzerschnittstelle}
 zur direkten Interaktion mit dem System ist vorhanden.
Eine Schnittstelle\index{Schnittstelle f"ur Anwendungsprogrammierung} f"ur 
Anwendungsprogrammierung ({\em application\index{application programmer's 
interface} programmer's interface, API}) unterst"utzt die Entwicklung 
eigener Benutzerschnittstellen sowie die Integration von INQUERY in eigene
Anwendungen.

\subsection{INQUERY im Stapelbetrieb}
\index{Stapelbetrieb}
INQUERYs Stapelprogramm erh"alt seine Argumente in Form von Da\-tei\-nam\-en und
boole\-schen Attributen aus der Kommandozeile. Hieraus 
erzeugt es eine Dokumentenrangliste\index{Rangfolge}, die
von einem Auswertungsprogramm verarbeitet werden kann. Dieses 
Auswertungsprogramm erzeugt R"ucklauf- und 
Genauigkeitstabellen\index{R"ucklauf}\index{Genauigkeit}, die "uber die
Wirksamkeit\index{Wirksamkeit} des Systems Auskunft geben 
(vgl. Abschnitt \ref{precisionRecall}).
Die Stapelverarbeitung erleichtert die mehrfache Ausf"uhrung von Anfragen, so da"s
hier die Auswirkungen von "Anderungen am System betrachtet werden k"onnen
\cite{cch92}.
\subsection{Benutzerschnittstelle}
\index{interaktive Schnittstelle}
Die Benutzerschnittstelle von INQUERY erm"oglicht die direkte Eingabe
sowohl von nat"urlichsprachlichen als auch von strukturierten Anfragen. Die Ergebnisse
der Anfragen werden dem Benutzer in der vom System ermittelten 
Rangfolge\index{Rangfolge}
angezeigt. Die Dokumente erscheinen dabei in Kurzform, k"onnen jedoch 
durch eine entsprechende Auswahl des Benutzers auch vollst"andig auf den
Bildschirm gebracht werden. Der Benutzer hat die M"oglichkeit, die f"ur
seinen Informationsbedarf relevanten Dokumente zu markieren. Das System
ist in der Lage, die urspr"ungliche Anfrage aufgrund dieser Markierungen
zu ver"andern. Es unterst"utzt somit das Konzept der 
Relevanzr"uckkopplung\index{Relevanzr"uckkopplung}
(vgl. Kapitel \ref{ir}). Die Ergebnisse des Information Retrieval Prozesses
k"onnen in einer Datei abgespeichert werden \cite{inq95}.
\subsection{Schnittstelle f"ur Anwendungsprogrammierung}
\index{Schnittstelle f"ur Anwendungsprogrammierung}
\label{API}
Die Schnittstelle f"ur Anwendungsprogrammierung erm"oglicht die Implementation
einer eigenen Benutzerschnittstelle zum System INQUERY
sowie deren Integration in eigene Anwendungen. Hierzu
stellt sie einen Satz von Funktionen zur Verf"ugung, die in der Programmiersprache
C\index{Programmiersprache C} \cite{ker77} geschrieben wurden. Diese 
k"onnen von jedem C-Programm oder jedem
anderen Programm, das C-Funktionen einbinden kann, aufgerufen
werden. 

Die Funktionen sind in zwei Bibliotheken\index{Funktionsbibliotheken}
 zusammengefa"st. Die
erste Bibliothek enth"alt die Funktionen f"ur lokale Anwendungen, die zweite
die Funktionen f"ur Netzwerkanwendungen. Dadurch ist Information Retrieval
auf lokalen, aber auch auf entfernten INQUERY-Datenbanken m"oglich. Hierbei ist 
jedoch nur eine der beiden Anwendungsarten zur Zeit zul"assig. 

Die Benutzung von C-eigenen Datentypen wird in INQUERY-Funktionen vermieden,
um eine Portabilit"at\index{Portabilit"at} des Systems zu erreichen. 
Die Annahmen, die INQUERY
zum jeweiligen, im System definierten Datentyp trifft, sind in einer speziellen 
C-Header-Datei festgelegt.

Die Funktionen zur Anwendungsprogrammierung werden funktionalen Gruppen
\index{Funktionsgruppen} zugeordnet. Diese Gruppen umfassen \cite{api94}:
\begin{itemize}
\item den Zugang zu INQUERY-Datenbanken
\item das Parsing von Anfragen
\item die Auswertung von Anfragen
\item die Relevanzr"uckkopplung
\item den Zugang zu Dokumenten und Informationen "uber die Textsammlung
\item die Indizierung
\item Fehlerbehandlung
\item sonstige Funktionen
\end{itemize}
Mit Hilfe der Funktionsgruppen f"ur den Datenbankzugang, f"ur das Parsing und
die Auswertung von Anfragen sowie f"ur den Zugang zu Dokumenten k"onnen
einfache Anwendungen des Information Retrieval auf Standard-Textsammlungen realisiert werden. Diese lassen sich unter Benutzung der "ubrigen Funktionsgruppen erweitern.
