Ausarbeitung zum Thema

Textuelles Fallbasiertes Schließen

Textual Case Base Reasoning

Einführung

Mit Hilfe des Textuellen Fallbasierten Schließens möchte man aus einer Doc Collection Antwort auf eine Nachfrage gewinnen, dh. man möchte spezielle Informationen aus einer Sammlung von textuellen Informationen gewinnen und eine Fallsammlung erzeugen, die die Beantwortung weiterer Anfragen verbessert. Anwendung findet dies in help desks und hotlines, die innerhalb eines festgelegten Zeitraumes (sofort oder in mehreren Tagen) Antworten anbieten.

In industriellen und medizinischen Fachgebieten besteht ein großer Bedarf an solchen Anwendungen, da dort viele wichtige Informationen in elektronischer Textform vorliegen. Als Beispiel seien folgende aufgezählt.

• Arztberichte
• Dokumentationen/Manuals zu Technischen Geräten
• FrequentlyAskedQuestions-Sammlungen
• informale Beschreibungen spezieller Funktionen

Die zugrundeliegenden Dokumente weisen eine Vielzahl unterschiedlicher Eigenschaften auf.

• Struktur
  So sind diese Dokumente voll-, semi- oder nicht strukturiert. Beispielsweise weist ein FAQ-Dokument die Semistruktur 'Frage-Antwort' auf.
• Sprache
  Sie enthalten natürlichen Text verschiedener Sprachen oder enthalten Fachwörter, bzw. bestehen gänzlich aus Fachsprache.
• Eindeutigkeit
  Beim Lesen der Wörter zeigen sich mitunter zwei Probleme.
  Ambiguity-problem (Doppelsinn), d.h. ein Wort kann mehrere Bedeutungen haben;
  Paraphrase-problem (Umschreibung), d.h. ein Sachverhalt kann durch unterschiedliche Wörter ausgedrückt werden;
  Das erste Problem wirkt sich auf die Relevanz eines Dokumentes aus, zweiteres auf den Vergleich von Dokumenten mit Anfragen und anderen Dokumenten.
• Fachwissen
  Im Dokument können weitere Informationen enthalten sein, die jedoch nicht direkt in textueller Form gegeben sind, wie zum Beispiel zusätzliche Strukturinformationen, Diagramme, Informationen 'zwischen den Zeilen', etc.

Für ein gutes Antwort-System bedarf es sinnvoller Strategien, die sich dieser Probleme annehmen. Weiterhin braucht man Konzepte, wie Ähnlichkeiten (similarity) zwischen Dokumenten oder Anfragen ermittelt und bewertet werden, wie zusätzliches Wissen erworben (knowledge acquisition) werden kann und wie man sich an vorgegebene Domänen anpasst (domain adaption). Entscheidend dafür ist die interne Repräsentation der Daten und die Benutzung weiterer Hilfskonstrukte wie Indexterme.

Grundlagen

Ein Vorläufer des CBR ist das IR-Modell. Jedoch ist textual CBR gegenüber dem IR-Modell erweitert, ja mitunter konträr dazu. Diverse Vorteile des CBR sorgten dafür, dass auf einigen Gebieten in den letzten Jahren IR- durch CBR-Systeme ersetzt wurden. Die Entscheidung zum Einsatz eines Systems hängt dabei von verschiedenen Faktoren ab. Hauptsächlich abzuwägen ist zwischen der allgemeinen Anwendbarkeit und der Ausnutzung speziellen Domänenwissens. Ebenso muss zwischen 'statischem' Vergleich, wie er bei IR-Modellen benutzt wird, und CBR-typischer dynamischer Bewertung, die durch Lernen aus bisherigen Problemlösungen entsteht, unterschieden werden.

IR-model

Die Information Retrieval Technik wurde 1979 von Rijsbergen und 1983 Salton & McGill eingeführt und ist die traditionell am häufigsten benutzte Methode zur Informationsgewinnung. Der bekannteste Einsatz ist die Anwendung als WWW-Suchmaschine. Jedoch ist der Name falsch gewählt, wie Rijsbergen bemerkte, da es sich nicht um Informationsgewinnung handelte, sondern nur um eine Suche nach Dokumenten, die in irgendeinem Bezug zur Anfrage stehen.

Es gibt drei Arten von IR-Modellen.

• Vector Space Model
• Prohabilistic Model
• Inference Network Model

Im Vector Space Model (Salton et al. 1975) werden Dokumente intern durch einen sehr langen Vektor

Doc_i = [d_i1, d_i2, ..., d_in]

repräsentiert. Dazu werden im Vorfeld n Indexterme festgelegt. Beim Hinzufügen eines neuen Dokumentes zur DocCollection zählt man die Häufigkeit eines jeden dieser Terme in diesem Dokument und berechnet daraus das Gewicht d_ik des Terms k im Dokument i. d_ik ist eine natürliche Zahl und wird im Vektor Doc_i festgehalten. Das heißt, die interne Dokumentenpräsentation ist ein Gewichtsvektor, dessen Einträge aus gezählten Häufigkeiten berechnet werden. Die Ähnlichkeit der Vektoren (per Kosinus-Messung) bestimmt die Ähnlichkeit der zugrundeliegenden Dokumente. D.h. Zwei Dokumente sind sich per Definition 'ähnlich', wenn sie viele gemeinsame Worte enthalten.

Analog benutzt das Prohabilistic Model (Fuhr 1989) einen Vektor Doc_i, jedoch befinden sich die Werte der Gewichte d_ik in der Menge {0, 1}, wobei das Gewicht 1 genau dann angenommen wird, wenn der Term k im Dokument i vorkommt. Aus dem Vektor berechnet sich (nach Bayes' Theory) die Wahrscheinlichkeit für die Relevanz des Dokuments bzgl. einer Anfrage.

Das Inference Network Model (Turtle/Croft1990,Turtle1991) verfolgt einen anderen Ansatz. Hier werden Dokumente als Knoten eines Graphen dargestellt, dem weitere Knoten angehören, die IndexTerme und QueryTerme darstellen. Die gerichteten Kanten des Graphen sind durch Wahrscheinlichkeiten gewichtet entsprechend den Beziehungen, die in der Doc-Collection beobachtet wurden. Neue Anfragen werden dann bzgl. der Abhängigkeiten im Doc-Collection-Graph untersucht.

Die Vorteile des IR-Systems liegen auf der Hand. Es ist (fast) unabhängig von der zugrundeliegenden Domäne, also ein domänunabhängiges System, und kann deshalb sehr einfach in eine andere Domäne portiert werden. Notwendig sind lediglich eine DocCollection und eine Menge von Indextermen. Die langjährige Anwendung des IR-Systems bringt eine Menge wertvoller Beiträge mit sich, die das Schätzen und Vergleichen erheblich erleichtern. Weiterhin ist es möglich, IR in sehr großen DocCollections einzusetzen. Hingegen fehlt es aufgrund der bisher noch in den Kinderschuhen steckenden Anwendung von CBR an Erfahrung über das Verhalten von CBR auf großen Sammlungen.

Jedoch birgt IR auch Nachteile in sich. Eine wesentliche Voraussetzung für IR und damit auch eine Einschränkung ist die Unabhängigkeit der Indexterme. Für genaue Berechnungen im Prohabilistic Model ist die stochastische Unabhängigkeit der Indexterme notwendig. Ebenso führen im Vector Space Model synonyme Terme zu orthogonalen Vektoren, welche dann keine Ähnlichkeit aufweisen. Ein weiterer Nachteil ist, das man Statistik statt Wissen nutzt. Dabei gelten sehr seltene und sehr häufige IndexTerme als nutzlos, was im allgemeinen sinnvoll ist, jedoch nicht stimmen muss. Ebenso beruht das Gewicht der IndexTerme und damit die Ähnlichkeitsmessung allein auf der Häufigkeit der IndexTerme im Dokument. Weiterhin ist IR sehr statisch. Bezüglich eines Dokumentes sind das Ähnlichkeitsmaß und die Menge relevanter Indexvokabeln fest bestimmt. Damit ergeben sich auch Probleme beim Integrieren neuen Wissens, wie neue relevante Indexterme oder neue Beziehungen zwischen Indextermen. Das Ambiguity- und Paraphrase-Problem sind ungelöst. Informationen in nicht-textueller Form werden ignoriert. Die Fallerstellung (case authoring), die unter anderem den Aufbau von Entscheidungsbäumen und die Fall-Codierung beinhaltet, ist sehr aufwendig. Dies sind eine Menge von Nachteilen, die den sinnvollen Einsatz von IR mitunter verhindern.

n-grams

Ein alternativer Ansatz zum IR sind n-grams. Dabei werden Dokumente intern durch eine Menge kurzer Wortsequenzen dargestellt. Die Sequenzen erhält man, indem man mittels eines Fensters geringer Größe durch den Text scrollt und alle vollständigen Sequenzen notiert.

Bsp: 3-gram-set

The new printer does not work.
{the, new, pri, rin, int, nte, ter, doe, oes, not, wor, ork}

Der große Vorteil ist, dass man keine IndexTerme benötigt. Ebenso ist die interne Repräsentation leicht erzeugt und vor allem robust gegenüber grammatikalischen Variationen und Rechtschreibfehlern, da ein falscher Buchstabe im obigen Beispiel in höchstens drei Sequenzen vorkommt, ein Wort der Länge n jedoch durch n-2 Sequenzen vertreten wird. Allerdings ist es auch hier analog zum IR nicht möglich, weiteres Wissen wie domänspezifische Thesauri oder glossaries zu integrieren.

textual CBR

Im Gegensatz zu den vorgestellten Systemen ist im CBR neues Wissen integriebar, ja der Wissenserwerb bzw. knowledge aquisition ist sogar notwendig. Im CBR beschränkt man sich jedoch auf eine Domäne, verliert also durch die Spezialisierung die allgemeine Anwendbarkeit und damit die Übertragbarkeit, passt sich jedoch dafür optimal an die Domäne an. Dazu entwickelt man einen (abstrakten) knowledge container, der während des Wissenserwerbs erzeugt wird und alle essentiellen Eigenschaften der Domäne enthält. Insbesondere sind die in der Domäne typischen entities und ihre relationships beschrieben, die erheblichen Einfluss auf das Ähnlichkeitsmaß haben.

Komponenten des Textuellen Fallbasierten Schließens

knowledge container

Das Wissen einer Domäne unterteilt man entsprechend seinem Gebrauch

• als Basis in Fallsammlung
• zur Definition eines Index-Vokabulars
• zur Konstruktion eines Ähnlichkeitsmaßes
• zur Spezifikation angepassten Wissens

Natürlich gibt es immer genügend Dokumente, die zum Aufbau einer Fallbasis genutzt werden können. Da die Dokumente direkt als Fall aufgenommen werden und nicht erst bearbeitet werden müssen, erspart man sich so den Case-Authoring-Process. Der letzte Punkt ist unwichtig, da eine solche Anpassung nur selten passiert [Anmerkung des Autors: Dieser Punkt war in den Quellen sehr kurz und wenig genau umschrieben und ist hier nur informativ erwähnt]. Die wichtigsten Bestandteile des knowledge containers sind also die Beschreibung des Ähnlichkeitsmaßes und der Indexterme.

Da CBR an eine spezielle Domäne gebunden ist, kann auch domänspezifisches Wissen in das Ähnlichkeitsmaß einfließen. Damit erhalten wir ein angepaßtes Ähnlichkeitsmaß, welches auch semantische Bezüge enthält, insbesondere finden domänspezifischer Thesaurus, Domän-Ontologie, Objektnamen etc. Beachtung. Dies läßt eine genauere Bewertung zu, als bei der Verwendung statischer Termgewichte.

Ebenso wird spezifisches Wissen zur Definition der Indexterme verwendet. Man benutzt ein term-dictionary, welches unabhängig von Statistiken ist und domänspezifische Idendifikatoren enthält (keywords, terms, expressions, ...). Es enthält nicht nur Einzelwörter, sondern auch inhaltlich zusammenhängende Wortkombinationen, wie z.B. mehrteilige Modulnamen. Auch das Erkennen von technischen Attribut-Value-Pairs ist ein Informationsgewinn gegenüber der Bewertung als Einzelwörter.

The CPU 999 is constructed to work with 12 Volt.

Weiterhin kann das Wissen über die Struktur von Dokumenten und damit zusätzliche Informationen genutzt werden (FAQ: Frage-Antwort). Ebenso vorteilhaft entfällt das Ambiguity Problem in spezifischer Domäne, da es innerhalb einer Domäne kaum Bezeichner mit Doppelsinn gibt.

knowledge acquisition

Enthält der Index nur Fachterme, so ist dies für einen genauen Vergleich nicht ausreichend. Darum werden Dokumente mit natürlicher Sprache nach Text und Satzbau analysiert und für den Index-Aufbau verwendet. Das Verfahren nennt sich Natural Language Processing (NLP).

Es gibt einfache (Shallow NLP) und komplizierte (Sophisticated NLP) Verfahren. Letztere haben jedoch einige Nachteile. Meist haben sie eine schlechte Performance, arbeiten nur mit kleinen Wörterbüchern und können nur korrekte Satzstrukturen behandeln. Ebenso ist ihr Datenformat nicht für den Vergleich geeignet und das Paraphrase-Problem ist nicht gelöst.

In der Praxis hat sich das Shallow NLP-Verfahren durchgesetzt. Eine öffentlich zugängliche Implementation für englische und neuerdings auch deutsche Sprache findet man auf http://www.ims.uni-stuttgart.de/tools/DecisionTreeTagger.html. Dieses tool führt eine part-of-speech tagging aus, wobei jedem Wort ein Tag mit seiner Satzfunktion (Wortstamm, Verb, Substantiv, ...) und weiteren Informationen zugeordnet wird. 'Ein Tag pro Wort' stellt eine einfache interne Präsentation des Textes dar. Das Verfahren ist effizient und robust. Damit fließen in den Index Strukturinformationen ein. Der Indexaufbau in den Projekten der Autoren lief wie folgt ab:

1. Zunächst wird das Tagging der Doc-Collection mit dem vorgestellten Tool ausgeführt.
2. Anschließend werden die Texte normalisiert, d.h. einzelne Wörter werden durch ihren Wortstamm ersetzt (abstrahiert von grammatikalischen Versionen).
3. Nun werden Wörter gleichen Wortstamms gruppiert und bilden so die ersten Indexterme.
4. Im folgenden werden diese Terme automatisch klassifiziert.
   - nutzlos sind Satzzeichen, Hilfs-, Modalverben, Präpositionen, Pronomen, ...
   - nützlich sind Adverben, Adjektive, Vollverben, Substantive
   - sonst potentiell nützlich
5. Treten (potentiell) Nützliche Terme zu selten/häufig auf, werden diese selektiert.
6. Letztlich werden v.a. die potentiell Nützlichen manuell bewertet, da zB. Wörter mit Rechtschreibfehlern, aber auch seltene domänspezifische Wörter noch nicht zugeordnet sind.

Man beachte, dass nur der letzte Schritt manuell durchgeführt wird, jedoch mit einer vergleichsweise geringen Menge an Worten.

Um das Paraphrase-Problem zu lösen, benutzt man den Thesaurus, der synonyme Wörter erkennt und somit verschiedene Beschreibungen des gleichen Sachverhaltes einander zuordnet. Auch hierfür gibt es öffentliches Tool names WordNet: http://www.cogsci.princeton.edu/~wn, welches auf solider Linguistik basiert. Man erhält Informationen über ähnliche Wörter, Synonyme und Antonyme. Jedoch funktioniert es nicht für Fachbegriffe und ist auch nur in Englisch verfügbar und nicht in deutsch, wodurch man selber solch ein Tool entwickeln musste. Dabei hat man einfließen lassen, das in deutschen Texten häufig zusammengesetzte Wörter enthalten sind, sich die Ähnlichkeitsmessung also auch auf Teilwörter beziehen muss.

Ergebnisse

Die Autoren haben einige Anwendungen programmiert. Dazu zählen

• CBR-Answers (SIMATEC Knowledge Manager)
• FALLQ project
• Experience Book

Anhand des erstgenannten Projektes wurden die Auswirkungen der Strategien auf die Precicion (Wieviel Prozent der Antwortdokumente sind relevant ?) und Recall (Wieviel Prozent aller relevanter Seiten wurde in der Antwort aufgelistet ?) gemessen, indem dem System FAQ-Fragen und zufällig grammatikalische Variationen davon gestellt wurden.

• Wenn Information Extraction (attribute-value-pairs) nicht ausgeführt wird, verändert sich die Kurve nur schwach. (1->2)
• Wird die Domänstruktur nicht beachtet, um ähnliche Dokumente andere Gebiete zu filtern, erhalten wir den gleichen Recall mit schlechtere Precision. (1->3)
• Der Einfluß der Dokumentstruktur wurde untersucht, aber nicht eingezeichnet.
• Wird die Ähnlichkeit von Indextermen nicht beachtet und statt dessen nur exakte matchings gezählt, so fällt die Performance weiter. (3->4)
• Der Verzicht auf domainspezifische Terme hat bedeutende Auswirkung. (4->5)

Referenzen

Case-Based Reasoning Technology
-Mario Lenz, Brigitte Bartsch-Spörl, Hans-Dieter Burkhard, Stefan Wess

6th German Workshop on CBR
-Lothar Gierl, Mario Lenz (1998)