KI in Interaktiven Systemen - Lernende Wörterbücher und lehrende Käfer

KI in Interaktiven Systemen - Lernende

Worterbiieher und lehrende Kafer

Eaimund Klein

13.07.2000

Zusammenfassung

Dieser Vortrag wurde im Rahmen des Seminars Entwicklung Interaktiver Systeme im Sommersemester 2000 gehal- ten. Er stellt zwei junge Konzepte dar, die in interaktiven Systemen vollig neue Moglichkeiten unter Nutzung von kiinstlicher Intelligenz eroffnen: Adaptive Systeme und Agenten, wobei letztere vor allem im Bereich der Presentation betrachtet werden. In Abschnitt 2 werden allgemeine Aspekte und mogliche Einsatzbereiche fur adaptive Systeme dargestellt, und in Abschnitt 3 werden diese Ideen am Beispiel eines adaptiven Spell Checkers, des Laempel Systems von Klaus Truemper (UT Dallas)^[1] illustriert. In Abschnitt 4 wende ich mich den Ein- satzmoglichkeiten von Agenten, einem auch innerhalb der gesamten KI recht j ungen Konzept, in interaktiven Systemen zu, bevor in Ab­schnitt 4.5 verschiedene Prasentationsagenten und ihr Einsatzbereich vorgestellt werden; in Abschnitt 5 wird ein solcher Agent, STEVE von der University of Southern California (USC), detaillierter erlautert.

1 Einleitung

Der Einsatz von Kiinstlicher Intelligenz in Benutzungsschnittstellen steht der- zeit gerade an seinem Anfang und befindet sich noch groBtenteils im Bereich der Forschung. Es zeichnet sich allerdings ab, dass intelligente Benutzungsschnitt­stellen in nicht allzu ferner Zukunft stark an Bedeutung gewinnen werden. Die in diesem Vortrag vorgestellten Konzepte verfolgen verschiedene Ziele, u.a. ein System auf den Benutzer automatisch abzustimmen, ihm unnotige Detailar- beit abzunehmen und ihm das Gefiihl zu nehmen, mit einer moglicherweise iiberlegenen Maschine zu interagieren. Hierfiir konnen vielfaltige KI-Methoden eingesetzt werden: Von der parametrisierten Suche liber Plansysteme bis hin zu den noch recht j ungen Agenten ist alles in Benutzungsschnittstellen verwendbar.

2 Adaptive Systeme

Schon langer bekannt sind sogenannte adaptierbare Systeme, die der Nutzer auf seine individuellen Bediirfnisse abstimmen kann. Adaptive Systeme hingegen passen sich automatisch an den Benutzer an. So schreibt Langley ([Lan97]):

An adaptive user interface is an interactive software system that im­proves its ability to interact with a user based on partial experience with that user.

Uber die Anpassung an den Benutzer hinaus sind Systeme denkbar, die sich an Ausgabegerate (z.B. unterschiedliche DisplaygroBen) oder Ressourcen (z. B. langsame Netziibertragung) anpassen konnen.

2.1 Anpassung an den Benutzer

Die Idee bei nutzeradaptiven Systemen besteht darin, dass das System den Nut- zer bei seiner Arbeit „beobachtet“ und liber ihn ein „Benutzermodell“ anlegt. Eine derartige Vorgehensweise ist natiirlich nur sinnvoll, wenn der Nutzer liber einen wesentlich langeren Zeitraum mit dem System arbeitet, als das Erler- nen des Nutzerverhaltens beansprucht. Ebenso sollte aus Griinden des Daten- schutzes der Nutzer darliber informiert werden, dass seine Praferenzen in einer wie auch immer gearteten History-Liste gespeichert werden. Ein einfaches Bei- spiel fur dieses Verfahren sind Listen, in denen eine bestimmte Anzahl zuletzt gewahlter Eintrage als Standauswahl zur Verfiigung gestellt wird.

Eine (Komplexitats-)Stufe hoher sind solche Systeme anzusiedeln, die nicht nur Wissen liber den Nutzer sammeln, sondern daraus auf Basis gewisser Infe- renzregeln neues Wissen ableiten, so dass aus einem Informationssystem schlieB- lich ein Beratungssystem wird. Beim Einsatz solcher Systeme muss jedoch si- chergestellt werden, dass der Nutzer immer die gesamte Kontrolle behalten kann, insbesondere natiirlich die Kontrolle iiber sein Benutzermodell. Gerade bei schwerwiegenden Entscheidungen, wobei der Begriff „schwerwiegend“ an- wendungsabhangig ist, sollte sich das System darauf beschranken (lassen), dem Nutzer lediglich Vorschlage zu unterbreiten.

Fiir nutzer adaptive Systeme bieten sich u.a. zwei Anwendungsfelder an: Lehr- bzw. Lernprogramme konnen mithilfe der hier vorgestellten Konzepte z.B. anhand der vom Benutzer korrekt beantworteten Fragen erraten, in welchen Be- reichen er sich besser und in welchen schlechter auskennt und die Fragenauswahl darauf abstimmen; in Hypertext-/Hypermediasystemen ist es denkbar, die ge- lieferten Informationen auf den Benutzer abzustimmen. Zum letzteren gibt es bereits statistische Untersuchungen im Bereich des WWW, die darlegen, welche Benutzergruppe welche Arten von Informationen bevorzugt [Pre99].

2.2 Anpassung an vorhandene Ressourcen

Die Anpassung an Ressourcen ist dort interessant, wo Verarbeitungsgeschwin- digkeit oder verfiigbare Zeit unbekannte Parameter sind. Um eine solche Anpas­sung zu erreichen, werden sog. Anytime-Algorithm,en entwickelt; solche Algorith- men sind jederzeit unterbrechbar. Eine abgeschwachte (und sicherlich haufiger anzutreffende) Form stellen sog. diskrete Anytime-Algorithm,en dar, die zu be- stimmten Zeitpunkten abgebrochen werden konnen. Im Bereich der Computer- grafik gibt es bereits eine Vielzahl derartiger Algorithmen, die unter dem Be­griff progressive refinement (schrittweise Verfeinerung) zusammengefasst wer­den ([Pre99]).

Den Standard stellen heutzutage jedoch zumeist ressourcenadaptierte Sy­steme dar, die wesentlich mehr Wissen iiber das Endsystem auf Entwickler- seite voraussetzen, als dies bei ressourcenadaptiven Systemen der Fall ware.

Anwendungsbereiche fur ressourcenadaptive Systeme finden sich z.B. iiberall dort, wo harte RealTime-Constraints einzuhalten sind und im Internet, wo eine wohl in dieser Form sonst nirgends in der Informatik anzutreffende He- terogenitat an Ressourcen (Betriebssysteme, Bandbreiten,...) vorhanden ist. Insbesondere fur das WWW ware es wiinschenswert, wenn der Clientbrowser mehr Einfluss auf den Informationsfluss seitens des Servers hatte - z.B. beim Ubertragen von Multimediadaten zu spezifizieren, wie detailgetreu diese sein sollen (Grobkornigkeit von Bildern oder erlaubtes Storrauschen bei Audiodatei- en). Gerade dieser Bereich enthalt viele interdisziplinare Aspekte, vor allem im Bereich der „Cognitive Sciences11, wenn es darum geht, zu untersuchen, welche Informationen dem Benutzer unter gegebenen Umstanden geniigen.

2.3 Anpassung an Ausgabegerate

Mil der fortschreitenden Mikrotechnologie klafft eine immer groBere Liicke zwi- schen den Displays portabler PCs, z.B. Notebooks auf der Basis von Windows CE, und denen lokal stationierter Rechner, wo heutzutage 17”- und wohl bald schon 19”- oder 21”-Monitore den Standard darstellen. Allgemein gilt: Je klei­ner das Display, desto wichtiger wird die Darstellung von Interfaceelementen in textueller Form, da diese weniger Platz beansprucht als z.B. Icons, die eine bestimmte GroBe nicht unterschreiten diirfen, um iiberhaupt noch erkennbar zu sein. Es ist also praktisch unmoglich, eine einheitlich aussehende Benutzer- schnittstelle fur alle diese Systeme zu entwickeln.

Dennoch ist es heutzutage moglich, Fensterinhalte zumindest soweit zu ver- einheitlichen, dass egal auf welchem System die gleichen Elemente unter- oder nebeneinander plaziert werden. Ein Beispiel hierfiir stellt das AWT- bzw. Swing- Package von Java dar: Der Entwickler hat zwar die Moglichkeit, Elemente ent- sprechend der Bildschirmpixel anzuordnen, aber wesentlich einfacher ist die Be­nin zung eines (vordefinierten) Layout-Managers, der nur die Spezifikation von Grafikdetails wie z.B. Page und GroBe der Elemente im Verhaltnis zueinander erlaubt. Im wesentlichen werden die Darstellungselemente und insbesondere die Page derselben also nur auf syntaktischer Ebene definiert, was die Nutzung dieses Interfaces auf ganzlich unterschiedlichen Plattformen und insbesondere BildschirmgroBen erlaubt.

3 Das Laempel-System: Ein adaptiver Spell Checker

3.1 Ubersicht

Obwohl das Laempel-System von Klaus Truemper (UT Dallas) nicht die op- tische Gestaltung einer Benutzerschnittstelle beeinflusst, stellt es durchaus ein gutes Beispiel fur die Anpassung eines Systems an den Benutzer dar: Es pro- tokolliert das Nutzerverhalten in Bezug auf Fehler, die in einem Textdokument auftauchen, und verbessert dadurch die automatische Rechtschreibpriifung. Sei­ne Vorteile gegeniiber bekannteren Spellcheckern wie I spell oder der Recht- schreibpriifung von Microsoft Word liegen vor allem darin, dass es mit einer wesentlich hoheren Wahrscheinlichkeit

1. korrekte Ersetzungen fur als inkorrekt erkannte Worter findet und
2. unbekannte, aber korrekte Worter auch als solche erkennt.

Das System besteht im Wesentlichen aus sechs verschiedenen Bestandtei- len: einem general dictionary, der in etwa 200.000 englische Worter umfasst und vom Nutzer nicht verandert werden kann, einem user dictionary, der beim ersten Systemstart leer ist und alle vom Nutzer Jemals verwendeten (korrek- ten) Worter umfasst, einem excluded words dictionary, der ebenfalls im Auslie- ferungszustand leer ist und alle aufgetretenen inkorrekten Worter enthalt, einem user history file, das eine Art „Fehlerprofil“ des Nutzers darstellt, und zwei lo- gischen Modulen, die die eigentliche Funktionalitat des Systems umfassen.

Mithilfe dieser Komponenten erreicht das System folgende Features:

- inkorrekte Worter werden mit an Sicherheit grenzender Wahrscheinlich- keit als solche erkannt - in diversen Tests iibersah das System nie ein inkorrektes Wort
- fur jedes inkorrekte Wort schlagt es eine sehr wahrscheinlich richtige Er- setzung vor
- es erkennt unbekannte, aber korrekte Worter mit einer hohen Wahrschein- lichkeit als korrekt an
- jedes bereits einmal vom Nutzer als inkorrekt markierte Wort wird immer als inkorrekt markiert
- das Spell Checking vollzieht sich ziigig und belastet den Nutzer kaum

Bis auf den ersten und letzten Punkt sind diese Features stark nutzer- domanenabhangig und erfordern ausgekliigelte Lernmethoden.

Das Laempel-System ist inzwischen in der Version 3.0 erhaltlich. Die Erlauterungen in diesem Abschnitt stiitzen sich in erster Linie auf den Arti- kel [ZT99].

3.2 Bekannte Methoden

Bisherigen Systemen zur Fehlererkennung liegen ein Basisworterbuch und oft- mals auch schon ein Benutzerworterbuch zugrunde; diese Ideen sind also nicht wirklich neu, das Neue ist eher die Herangehensweise: Verbreitet ist z.B. das sog. n-grarn checking, bei dem nicht komplette Worter, sondern Substrings der Langen 1, 2 oder max. 3 mithilfe von Statistiken liber die verwendete Sprache ausgewertet werden; dies geschieht meist in Verbindung mit sehr ausgekliigelten Such- und Hashingfunktionen fur einen schnellen Zugriff auf die Worterbiicher. Fur diese Vorgehensweise liegen bereits viele ausgefeilte Methoden vor; dennoch muss sich das Laempel-System hier keinesfalls vor den anderen Spell Checkern verstecken.

Die Fehlerkorrektur beschrankt sich in den meisten Systemen auf Einzel- wortbearbeitung, da etwa 80% der in Textdokumenten auftretenden Fehler Rechtschreib- bzw. Tippfehler sind. Die eingesetzten Techniken sind ausgefeil- tes Pattern Matching in Verbindung mit statistischen Daten iiber die jeweilige Sprache.

3.3 Die Arbeitsweise des Laempel-Systems

Das Laempel-System durchlauft fur jedes im Dokument auftretende Wort den in Abbildung 1 dargestellten Entscheidungsbaum:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Entscheidungsbaum des Laempel-Systems

1. 1st das Wort im excluded words dictionary enthalten, ist es als falsch be- kannt. Das System benachrichtigt den Nutzer, bittet ihn um einen korrek- ten Ersatz und durchlauft den Baum fur das neue Wort.

2. Ist das Wort nicht im excluded words, aber im user dictionary, erkennt das System es an und bringt den entsprechenden word usage index (Ab- schnitt 3.4) auf den neuesten Stand.

3. Falls weder 1. noch 2. zutreffen, sucht das System nach dem Wort im general dictionary; wird es fiindig, speichert es das Wort mit Syntaxinfor- mationen im user dictionary (s.a. Abschnitt 3.4).

4. Ist auch dies nicht der Fall, versucht das System, mithilfe des logischen Mo- duls und der eingebauten Konstruktionsregeln fur Wortkonstruktion das zu untersuchende Wort aus einem Stammwort im general dictionary zu konstruieren. Die vordefinierten Konstruktionsregeln umfassen sehr einfa- che Basiswortbildungsregeln der englischen Sprache wie z.B. die Bildung von Komparativ bzw. Superlativ und sind so gewahlt, dass das System nicht aus Versehen ein inkorrektes Wort durch diese Konstruktion als an dieser Stelle korrekt erkennen kann.

Gelingt die Konstruktion des Wortes, so speichert das System selbiges mit den Konstruktions- (und Syntax-)informationen im user dictionary.

5. Gelingt die Konstruktion des Wortes nicht, wird es als unbekannt markiert, und das System iiberpruft anhand des user history files, ob der Nutzer viel- leicht einen fiir ihn charakteristischen Tippfehler begangen hat. Kommt das System zu dem Schluss, dass der Nutzer sehr wahrscheinlich einen haufiger auftretenden Fehler gemacht hat, sortiert es die zu dem/den iden- tifizierten Fehler(n) passenden Kandidatenworter und gewichtet sie nach einer bestimmten Formel (s.a. Abschnitt 3.5). Es wahlt die drei wahr- scheinlichsten aus und gibt diese an den Nutzer weiter. Dieser kann nun:

- einen der Vorschlage akzeptieren; in diesem Fall speichert das System diesen Vorschlag mit den Syntaxinformationen im user dictionary.
- ein viertes Wort eingeben; in diesem Fall priift das System fur das neue Wort die Punkte 1.-5. und gibt eine Warnung, falls das neue Wort unbekannt ist.
- das urspriingliche Wort als korrekt deklarieren; in diesem Fall er- folgt keine weitere Fehleranalyse durch das System, sondern das Wort wird mit den entsprechenden Daten direkt in den user dictionary ubernommen.

6. Ist das Wort nicht auf einen Fehler des Nutzers zuriickzufiihren, wird es als korrekt angenommen, und das System bittet den Nutzer um eine Bestatigung. Bestatigt der Nutzer das Wort, speichert das System dieses mit den iiblichen Informationen im user dictionary. Ist es jedoch falsch, so muss der Nutzer selbst einen Ersatz angeben. Fur dieses neue Wort durchlauft das System den Baum erneut. Falls das Wort ebenfalls nicht konstruierbar ist (d.h. 1.-4. gelten nicht), so warnt das System den Benut- zer, der diese Warnung nun ignorieren oder ein neues Ersatzwort eingeben kann.

3.4 Der user dictionary

Im user dictionary wird jedes vom System bisher gelesene und korrekte Wort mit einigen Zusatzinformationen gespeichert. Hierbei bedeutet „korrekt“, dass das Wort entweder aus einem Stammwort im user dictionary konstruierbar ist oder vom Nutzer als korrekt deklariert wurde. Die Baumstruktur des dictionary's, der im Normalfall etwa 20.000 Worter umfasst ([ZT99]), erlaubt einen sehr schnellen Zugriff auf die Eintrage. Die Zusatzinformationen umfassen:

- u.U. die Konstruktionsinformationen
- die Syntaxklassifikation (wird das Wort als Adjektiv, Substantiv,... be- nutzt?)
- statistische Informationen iiber bisherige Syntaxklassifikationen
- den Word Usage Index

Fur den Word Usage Index q gilt stets: -1000<=q<=1000. Einem neuen Wort wird der initiale Index 0 zugewiesen. Ist der Index eines Worts kleiner oder gleich 0, so ist dieses nicht in den letzten [q[ -f- 1 Dateien aufgetreten; ist er hingegen positiv, so trat das entsprechende Wort mit einer gewissen Haufigkeit in den zuletzt untersuchten Dokumenten auf. Fur die genaue Formel s. [ZT99].

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Vergleich von Ispell und Laempel-System

3.5 Fehlererkennung und -korrektur

Die Fehlererkennung und Fehlerkorrektur basiert auf den Daten im user histo­ry file. Stofit das System auf ein unbekanntes Wort, priift es dieses File auf friiher vom Nutzer gemachte Fehler und wie hoch die Wahrscheinlichkeit ist, dass einer dieser Fehler bei dem unbekannten Wort vorliegt. Ebenso wahlt es Kandidatenworter aus, die nach folgender Formel gewichtet werden:

w = (1 + a)q + 1001

Die Elemente in der Gleichung sind:

- q: der Word Usage Index.

- 1: die Wahrscheinlichkeit, dass der User genau den Fehler gemacht hat, der das Kandidatenwort in das gerade untersuchte Wort uberfiihrt.

- a: ein dynamisch in Abhangigkeit von der Erfahrung des Programms mit dem Nutzer veranderter Skalar, der sicherstellen soil, dass das am hochsten gewichtete Kandidatenwort auch die korrekte Ersetzung ist.

3.6 Abschliefiende Bemerkungen

Man kann den Lernvorgang des Systems beschleunigen (um ihm z.B. Spezi- alvokabular wie DT^X beizubringen), indem man einen kompletten Text als korrekt deklariert. Jedes Wort, das nicht unter einen der in Abschnitt 3.3 be- schriebenen Falle 1.-4. fallt, wird vom System als korrekt in den user dictionary iibernommen.

Das System bewies in Vergleichstests mit Ispell seine Starke in der Fehlerer­kennung vor allem darin, unbekannte, aber korrekte Worter auch als korrekt zu erkennen. Ispell erkannte solche Worter in 19% aller Falle an, Laempel in 82%. Ebenso entdeckte es insgesamt 4% mehr Rechtschreib- bzw. Tippfehler. Die Fahigkeiten beider Systeme in puncto Fehlerkorrektur wurden mit Testdoku- menten, die etwa 15.500 Worter umfassten, getestet; von diesen 15.500 Wortern waren 54 falsch buchstabierte Alltagsworter. Um ein faires Vergleichsergebnis zu erzielen, startete das Laempel-System mit leeren Userfiles (dictionary und history). Hierbei wurden die in Tabelle 1 dargestellten Beobachtungen gemacht.

Diese Ergebnisse zeigen deutlich, dass der in Abschnitt 3.5 geschilderte Ge- wichtungsalgorithmus sehr gut funktioniert, obwohl er auf einer augenscheinlich recht simplen Formel beruht. Auch die hohe Rate in der korrekten Anerkennung unbekannter Worter spricht durchaus fur das Laempel-System. Die hier darge­stellten Methoden verbessern die Rechtschreibpriifung erheblich und erleichtern es vor allem dem Nutzer, echte Fehler schneller zu korrigieren - je langer ei- ne Auswahlliste ist, desto uniibersichtlicher ist sie. Es lasst sich also annehmen,

[...]

^[1] siehe http://www.utdallas.edu/"klaus