Eine Einführung in Programmiermethoden und Sprachen der KI 8. und letzter Teil

In diesem letzten Teil der Serie über künstliche Intelligenz, möchte ich Sie mit dem Konzept des Rahmens vertraut machen. Wie ich bereits in einer der ersten Folgen dieser Serie betont habe, erkennt man Intelligenz auch daran, daß aus unvollständigen Informationen richtige Schlüsse gezogen werden, bzw. für die jeweilige Situation nützliche Aktionen eingeleitet w erden. Gerade aber wenn die Wissensbasis unvollständig ist, bekommt ein Verfahren besondere Bedeutung, das als analoges Schließen bekannt ist.

Analoges Schließen bedeutet ganz einfach, daß das Programm die Kenntnis aus benachbarten Wissensgebieten benutzt um in der konkreten Situation Informationsmangel zu kompensieren. Besonders im Bereich des Lernens ist analoges Schließen von elementarer Bedeutung. Kein Wunder also, wenn die KI-Forscher nach Mechanismen gesucht haben, die analoges Schließen auch dem Computer ermöglichen sollen.

Rahmen dienen der Organisation von Wissen

Um dem Computer Analogieschlüsse zu ermöglichen, muß das zu vergleichende Wissen in einer geeigneten Form gespeichert werden. Hierzu sind die Rahmen (engl.: frames) besonders geeignet. Ein Rahmen ist nichts anderes als eine vereinheitlichte Property Liste. Und zwar besteht die Propertyliste aus dem Rahmen, Schlitz (engl.: slot) und Merkmalen (engl.: facettes). Hat man nun zwei Rahmen mit ähnlichen Eigenschaften, so können Informationen aus dem einen Rahmen in die entsprechenden Merkmale des anderen Rahmens vererbt werden. Wir wollen diese Eigenschaften von Rahmen am Beispiel des Programmes FRAME.LSP erarbeiten, welches ich in Anlehnung an [-] für XLISP geschrieben habe (Listing 1). Eine vollständige Implementation einer Übungssprache (PFL: Paedago-gical Frame Language) ist bei [-] gegeben. Über die Einordnung von Rahmen in den KI-Bereich kann man bei [-] nach-lesen. Kümmern wir uns also zunächst einmal um die Propertyliste, die alles beherrschende Datenstruktur unseres Programms.

Die Propertyliste

In Lisp gibt es eine Liste, in der man Eigenschaften eines Objektes ablegen kann, eben die Propertyliste. Diese ist nicht zu verwechseln mit Assoziationslisten, die man in beliebiger Anzahl erzeugen (und an Symbole binden) kann. Der Zugriff auf die Propertyliste des (X)Lisp Interpreters erfolgt über die Funktionen SETF und GET. Die Syntax dieser beiden Funktionen lautet:

(getXsym Xeig ) Holt den Wert der Eigenschaft eig des Symbols sym von der Propertyliste.

Das Symbol. Die Eigenschaft des Symbols, welche einen Wert hat.

(setf )

Diese Funktion gibt den Wert wert an die in der Zugriffsform zugr enthaltene Eigenschaft eig des Symbols sym der Propertyliste.

Die Zugriffsform. Sie muß, wenn evaluiert, den Wert der Eigenschaft des Symbols auf der Propertyliste erzeugen. In unserem Fall also (get <eig»

Der Wert, den die in der Zugriffsform enthaltene Eigen schalt eig des Symbols sym auf der Propertyliste erhalten soll.

An einem Beispiel wird der Sachverhalt leicht klar. Das Symbol KLOTZ mit der Eigenschaft FARBE soll den Wert ROT erhalten:

(setf (get ’klotz ’farbe) ’rot)

Dies ist die Zugriffsform. Sie reproduziert später wieder den Wert der Eigenschaft FARBE des Symbols KLOTZ aus der Propertyliste.

Anschließend kann mit der Zugriffsform der Wert wieder aus der Propertyliste geholt werden:

(get ’klotz ’farbe)
ROT1
In XLISP gibt es noch zwei spezielle Zugriffsfunktionen für die Propertyliste: REMPROP und PUTPROP. Die erste entfernt eine Eigenschaft aus der Propertyliste eines Symbols, die zweite ist äquivalent zur Funktion SETF. Wir benutzen aus Kompatibilitätsgründen aber die Funktion SETF.

Wie wir bereits gelesen haben, ist ein Rahmen nichts anderes als eine normierte Propertyliste mit den Elementen RAHMEN, SCHLITZ, MERKMAL Abb. 1 zeigt den Aufbau eines Rahmens in der Propertyliste. Natürlich ist die Anzahl der Rahmen in der Propertyliste, bzw. die Anzahl der Schlitze im Rahmen oder die Anzahl der Merkmale eines Schlitzes nur durch den verfügbaren Speicherplatz des Computers beschränkt.

Nehmen wir einmal an, wir wollten unser Wissen über Computer in Rahmen fassen. Dann könnte der Rahmen für den ATARI ST Computer vielleicht so aussehen, wie Abb. 2 es zeigt. Der Name des Rahmens ist ATARI, der erste Schlitz in diesem Rahmen ist die Typenbezeichnung MODELL mit dem Merkmal WERT 1040ST. Der zweite Schlitz des gleichen Rahmens ist SPEICHER. Standardmäßig wird er 1040ST mit 1Mb Speicher ausgeliefert. Der Besitzer obigen Gerätes hat aber sein Gerät auf 2Mb aufgerüstet. Dies ist erkennbar an den beiden Merkmalen STANDARD 1MB und WERT 2MB. Auch für den Schlitz MONITOR sind zwei Merkmale vorhanden STANDARD SW und WERT COLOR, woraus zu entnehmen ist, daß dieser Computer entgegen dem Standard mit einem Colormonitor ausgerüstet ist. Nun bleibt nur noch die Frage, wie man solch einen Rahmen einrichtet, bzw. die Informationen aus dem Rahmen abruft und weiterverarbeitet? Und wie funktioniert analoges Schließen mit den Rahmen?

Informationen holen

Es ist am leichtesten, aus der Propertyliste Informationen eines bestehenden Rahmens zu holen. Deshalb zunächst also die Zugriffsoperationen. Nehmen wir an, daß die Propertyliste den Rahmen aus Abb.2 enthält. Wir erhalten den kompletten Rahmen, wenn wir den Befehl (get ’atari 'rahmen) eingeben. Man erhält dann das Resultat aus Abb.3.

Wollen wir nicht den ganzen Rahmen, sondern nur ein Merkmal eines bestimmten Schlitzes eines bestimmten Rahmens, dann müssen wir uns eben durch die gegebene Rahmenliste Vorarbeiten. Inzwischen sind wir ja schon zu geübten XLisp(l)ern geworden, sodaß wir ohne Mühe in der obigen Liste eine sogenannte Assoziationsliste erken nen [(-)]. Der car dieser Liste ist der Schlüssel, der cadr ist der zugehörige Wert. Diesen erhalten wir mit der Funktion assoc. Abb. 3 zeigt einige Zugriffe auf Elemente des Rahmens mit Hilfe der Funktion assoc.

Die assoc-wurschtelei läßt sich natürlich durch Definition ei ner Funktion umgehen, die den Namen des Rahmens, Schlitzes und Merkmals als Parameter übernimmt und die Li ste mit dem Merkmalswert zurückgibt. Diese Funktion erhält den sinnvollen Namen rhol und findet sich zu Beginn des Listingl. Die Funktion rhol-rahmen gibt den ganzen Rahmen zurück. Falls der gewünschte Rahmen allerdings nicht vorhanden ist, wird er mit Hilfe der setf Funktion neu erzeugt.

Das Erzeugen eines Rahmens in der Propertyliste

Diese Funktion ist erheblich komplizierter zu realisieren und bedarf daher einiger Vor arbeit. Zunächst einmal muß getestet werden, ob der Rahmen exisitert. Wenn dies nicht der Fall ist, wird der Rahmen mit der obigen Funktion 2 rhol-rahmen erzeugt. Andernfalls wird der Rahmen mit der selben Funktion als Assoziationsliste geholt und auf das Vorliegen eines entsprechen den Merkmals getestet. Es ver steht sich, daß derselbe Wert nicht zweimal abgespeichert wird. Liegt der Wert des Merkmals also bereits vor, dann wird nicht noch einmal gespeichert, sondern einfach NIL zurückgegeben. Besondere Beachtung sollte hierbei die Art und Weise der Erweiterung finden, wenn ein Schlitz, bzw. ein Merkmal noch nicht vorliegen. Abb. 4 zeigt die Vorgehensweise, die wir uns nun etwas näher unter die Lupe nehmen. Zu Beginn soll z.B. der Rahmen (ATARI (MODELL (WERT 1040ST))) auf der Propertyliste vorliegen und es soll der Schlitz SPEICHER mit dem Merkmal (WERT 2MB) hinzugefügt werden. Dazu rufen wir die Funktion (rpack ’atari 'Speicher 'wert ’2mb) auf. Der interessanteste Teil der Funktion läuft bereits bei der Initialisierung mit dem LET-Konstrukt ab. Hier wird wertliste als gebundene Variable erzeugt, mit einem Wert, der sich durch Aufruf der Funktion (folge-pfad '(Speicher wert) ’(atari (modell (wert 1040st)))) ergibt (siehe Listing 1). Diese Funktion testet, ob die Liste mit dem Pfad (d.h. '(Speicher wert)) bereits leer ist. Dann wird die Argumentliste liste zurückgegeben. Sonst ruft sich die Funktion selbst auf, allerdings mit dem Rest des Pfades und dem Ergebnis der Funktion (erweitern 'Speicher '(atari (modell (wert 1040st))). In dieser Funktion erfolgt dann der eigentliche Teil der Erweiterung des Rahmens. Die erste Klausel der Disjunktion trifft zu, wenn der Schlüssel (SPEICHER) bereits in der Assoziationsliste des Rahmens enthalten ist. Dann braucht natürlich nicht erweitert zu werden, und die Funktion gibt die Assoziationsliste mit dem Schlüssel und dem Wert zurück, um dann im nach sten Schritt von folge-pfad als Ergebnis zurückgegeben zu werden. Falls nun aber wie in unserem Beispiel der Schlüssel SPEICHER noch nicht in der Assoziationsliste des Rahmens enthalten ist, tritt die zweite Klausel der Disjunktion in der Funktion erweitern in Kraft. Diese ersetzt den CDR des letzten Listenknotens durch die Liste die die Liste des Schlüssels ersetzt (mittlerer Teil der Abb. 4). Damit wurde an die Liste etwas angefügt, die ursprüngliche Liste also verändert. An diesem Beispiel sollte klar geworden sein, daß LISP Knoten nichts anderes als Knoten eines binären Baumes sind, deren erster Teil ein Zeiger auf ein Datenelement ist und dessen zweiter Teil ein Zeiger auf den nächsten LISP Knoten. Als Funktionswert wird dann die Liste mit dem Schlüssel (d. h. dem Schlitz SPEICHER) zurückgegeben. Diese wird dann beim Rücksprung aus der tieferen Rekursionstufe an die lokal gebundene wert-liste übergeben. Für Anfänger verblüffend ist dabei wahrscheinlich, daß trotz Verwendung einer lokal gebundenen Variablen (der Liste wert-liste) ein globaler Effekt erzielt wird. Der untere Teil der Abb.4 illustriert diesen Effekt. In der Funktion 2 rpack wird nämlich (wenn der Wert 2MB nicht in der Wertliste ist, wie bei uns der Fall!) der CDR des letzten Elementes der Werteliste durch die Liste mit dem Wert 2MB ersetzt. Da aber der CAR des LISP-Knotens von 2 wert liste auf einen global gebundenen LISP-Knoten zeigt, wird beim Anfügen eines Elementes an die Liste von wert-liste gleichzeitig ein globaler Effekt erreicht und der CDR des letzten Elementes des Rahmens hinzugefügt.

Dämonen als stille Helfer

Jeder Programmierer kennt die Situation: Man fragt einen Da tensatz ab und stellt fest, daß die abgefragte Information nicht vorhanden ist. Da wünscht man sich schon manchmal ein paar Dämonen, die ohne viel Aufsehen die passenden Werte besorgen, damit die anfragende Routine nicht abstürzt oder falsche Ergebnisse produziert. Solche Dämonen aber kann man in einem Rahmen leicht implementieren. Schauen wir uns zu diesem Zweck einmal die Datenbank über Automobile in Listing 1 an. Dort sehen wir, daß die Informatioen über die verschiedenen Autotypen nicht bei allen Typen vollständig sind. Über VW weiß die Daten bank z.B. nur, daß der meistgekauft Typ der GOLF ist, weshalb er als Standard eingesetzt wur de. Die Anfrage (rhol ’vw 'typ 'wert) würde also NIL ergeben, da das gesuchte Merkmal im Schlitz typ nicht vorhanden ist. Dagegen liefert die Anfrage 2 (rhol-w-s ’vw typ) er wartungsgemäß (GOLF), da nach mißlungener Abfrage nach dem Wert, die Abfrage nach dem Merkmal Standard im gleichen Schlitz erfolgt. Ein Dämon kann aber noch mehr. Wenn wir das Alter eines Autos nicht kennen, dann könnten wir einen WENN-NOETIG Dä mon aktivieren, der ein springt, wenn weder ein Stan dard noch ein Wert vorliegen. Nehmen wir einmal an, wir wollten für eine Gebrauchtwagendatenbank den Vorbesitzer eines Wagens in den Rahmen mit aufnehmen. Dazu verpassen wir z.B. dem Rahmen OPEL den WENN-NOETIG Dämon Frage für den Schlitz Vorbesitzer:

(rpack ’opel ’vorbesitzer ’wenn-noetig Trage)
(FRAGE)
Fragen wir nun nach dem Vorbesitzer des Opel:
(rhol-w-s-d ’opel ’vorbesitzer)

Da weder ein Wert für den Vorbesitzerschlitz, noch ein Standard bekannt ist, wird der Dämon aktiv (wir haben rhol-w-s-d aufgerufen!) und läßt die Funktion Frage ablaufen, die eine Eingabe für den Wert verlangt und diesen im Schlitz abspeichert. Abb. 5 zeigt das Protokoll der Abfrage.

Noch eindrucksvoller ist allerdings die Vererbung von Eigenschaften. Um einen Dämon zu implementieren müßten wir nun alle Automobile mit dem entsprechenden wenn-noetig Dämon versehen. Viel einfacher wäre es, könnte man für alle Autos gleichzeitig einen entsprechenden Dämon vereinbaren. Das ist möglich, wenn man einen Schlitz Ist vereinbart, der die Art des Rah mens definiert. Also z.B. (rpack ’lancia ’ist 'wert ’auto). Weiterhin führen wir umgekehrt einen Rahmen Auto, der ebenfalls einen Schlitz Ist enthält und in dem als Merkmal Wert alle Autos der Datenbank aufgeführt sind (siehe Li sting 1). Die Funktionen rhol-i, rhol-n und rhol-z holen sich über den Schlitz Ist Informationen der verwandten Rahmen und vererben diese Informationen weiter. Die vererbten Informationen können Werte aber auch Dämonen sein. Abb. 6 zeigt die Abfrage unter Benutzung der Vererbung.

Vererbung von Informationen

Die drei Funktionen rhol-i, rhol-n und rhol-z übernehmen die Vererbung von Informationen. Alle Vererbung geschieht dabei über den 2 Ist Schlitz. Schauen wir uns dazu einmal Abb.6 genauer an. Die erste Abfrage lautet (rhol-w-s-d ’vw ’alter). Da kein Schlitz ALTER in der Assoziationsliste des Rahmens enthalten ist, liefert weder die Frage nach dem Merkmal WERT, noch die Frage nach dem Merkmal STANDARD noch die Anfrage nach dem Merkmal WENN-NOETIG (Dämon) einen Wert.

Die nächste Anfrage ist (rhol-i ’vw ’alter). Diesmal wird die Informationsvererbung über den Ist-Schlitz des Rahmens verwendet. Dazu werden mit Hilfe der Funktion rhol-klas-sen alle durch den Ist1-Schlitz miteinander verbundenen Rahmen aufgefunden. Die Hilfsfunktion 2 rhol-il schaut nun in jedem Rahmen der Liste Klassen nach, ob der gefragte Schlitz (in unserem Beispiel ALTER) mit dem Merkmal WERT vorhanden ist. Wenn ein Rahmen mit diesem Merkmal gefunden wurde, wird der Merkmalswert zurückgegeben. Aus diesem Grunde ist die Antwort in Abb. 6 auch (1), da im Rahmen LANCIA im Schlitz ALTER im Merkmal WERT der Wert 1 gefunden wurde.

Das Ergebnis der Abfrage (rhol-n ’vw ’alter) ist das glei che, weil in der ersten Klausel der Hilfsfunktion rhol-nl ebenfalls alle Elemente der Liste Klassen auf das Vorliegen des Merkmals WERT getestet werden.

Anders reagiert das Programm lediglich auf die Anfrage (rhol-z ’vw ’alter). Nunmehr werden nämlich alle Elemente der Liste Klassen zunächst auf das Vorliegen der Merkmale WERT, STANDARD und WENN-NOETIG (Dämon) untersucht, bevor das nächste Element der Klassen untersucht wird. Und als Dämon findet rhol-z in der Assoziationsliste des Rahmens AUTO (steht an erster Stelle der Liste Klassen) das Merkmal WENN-NOETIG mit dem Merkmal FRAGE. Der Dämon WENN-NOETIG wird also aktiv und fragt nach dem Alter. Abb. 7 zeigt die Art der Vererbung, wie sie durch rhol-i, rhol-n1 und rhol-z verwendet wird. Man erkennt, daß die Buchstaben mnemonische Bedeutung haben. Die Reihenfolge der Abarbeitung ist allerdings willkürlich gewählt (Wo bliebe sonst die mnemonische Wirkung?).

XLISP’s Geisterstunde (Dämonenaktivierung)

Wie aktiviert man nun einen Dämon? Das ist in der Tat ein Paradestück für die Leistungsfähigkeit von LISP. Schließlich muß der Interpreter nun je nach Dämon ein anderes LISP Programm aktivieren, daß irgendwo als Liste vorliegt. Den Code für die Dämonenaktivierung finden wir in den Funktionen rhol-w-s-d und 2 rhol-n2. In beiden findet man die Funktion mapcan als Motor der Aktivierung. Die Funktion mapcan hat folgende Syntax:

(mapcan [...])
Es bedeuten:
: Eine gültige LISP Funktionsdefinition.
<liste?>: Für jedes Argument der Funktion eine Liste mit Argumentwerten.

Die Funktion wendet nun auf jedes Element der Listen an. Die zurück gegebenen Werte werden zu einer Liste zusammengefaßt. Leider ist mapcan in der XLISP Dokumentation nicht beschrieben, funktioniert aber trotzdem. Die obige Definition stimmt mit der Definition von mapcar in der XLISP Dokumentation überein. Trotzdem arbeiten beide Funktionen leicht unterschiedlich. Während mapcar die Ergebnisse in eine Liste packt, zieht mapcan die Ergebnisse in einer Liste mittels nconc zusammen. Das setzt natürlich voraus, daß das Ergebnis der Funktion eine Liste ergibt, da sonst nicht zusammengezogen werden kann.

Beispiel:
(mapcar ’equal ’ (12 3) ’ (2 2 2)) (NIL TNIL)

(mapcar '(lambda (a b) (list (equal a b))) ’(1 2 3) ’(2 2 2)) ((NIL) (T) (NIL))

(mapcan '(lambda (a b) (list (equalab))) ’(1 2 3) ’(2 2 2)) (NIL T NIL)

Mapcar und mapcan erlau ben also die Anwendung der gleichen Funktion auf mehrere Parameter hintereinander. Im Falle unserer Dämonen, holt sich die Funktion rhoi-w-s-d also zunächst mit (rhol rahmen schlitz ’wenn-noetig) Liste aller als Dämon agierender Funktionsnamen und wen det dann die Schablone im mapcan Aufruf sukzessiv an.

Vererbung in Analogieschlüssen

Wie Eingangs erwähnt, ist analoges Schließen ein typisches Merkmal von Intelligenz. Aus 2 stammt das folgende Beispiel. Wenn Jemand sagt, Fred ist wie ein Bär, dann überträgt der Zuhörer Eigenschaften des Bärs auf den ihm unbekannten Fred. Ein Anlogieschluß ist also nichts anderes als das Übertragen (Vererben) von Informationen. Und da wir im letzten Abschnitt mehrere Methoden zur Informationsvererbung kennengelernt haben, soll das oben genannte Beispiel in unserer Rahmensprache nachvollzogen werden. Im letzten Teil des Listing 1 finden Sie die Rahmen für Fred und Ted. Abb. zeigt, wie die Größe und Gang art von Fred aus der Analogie zu Ted vererbt wird.

Schlußwort

Diese Serie ist am Ende angelangt. Es gäbe natürlich noch vieles zu berichten, vor allem, weil der Fortschritt im Bereich der Informatik so ungeheuer schnell voranschreitet. So habe ich beispielsweise gerade vor ein paar Monaten von den ersten Neuronenchips erfahren, die in den USA verkauft werden. Parallel verarbeitende Rechnerarchitekturen werden in Zukunft sicherlich eine bedeutende Rolle spielen. Kurz und gut, wir stehen vor der Schwelle vieler neuer Verfahren und Methoden und vieles (wenn auch sicher nicht alles) was heute kaum vorstellbar ist, wird sich mit neuen, von der herkömmlichen v. Neumann Architektur abweichenden Konzepten erreichen lassen.

Ich bedanke mich bei Ihnen, lieber Leser, daß Sie mir bis hierher gefolgt sind. Als kleines Dankeschön füge ich der PL) demnächst eine Shell für XLISP und TOY-Prolog bei, so daß der Benutzer sehr bequem einen Entwicklungszyklus mit Hilfe eines Editors aus der PD durchführen kann.

Literatur

[1] Finin.T.ImplementingPFL.Part 1 & 2. AI Expert, Novembers De-cember 1986. CL Publications, Palo Alto, CA.

[2] Lenat, D.B. Software für künstliche Intelligenz. Spektrum der Wissenschaft. Sonderheft Computersoftware 1985.

[3] Samow, K. Elemente der künstlichen Intelligenz. 1. Teil: Atome und Listen, ST-Computer, 3/ 87, p.37ff.

[4] Winston, P.H. & B.K.P. Horn. I.ISP. 2nd Edition. Addison Wesley Publishing Company. Reading, Massachusetts. 1984.

Dies war der letzte Teil der Serie 'Künstliche Intelligenz’. Falls Sie Interesse an dem Thema KI haben, dann schreiben Sie uns was Sie aus dem Bereich der KI interessieren würde. Wir versuchen darauf einzugehen und je nach Nachfrage weitere, auch praxisbezogene Artikel zu veröffentlichen. Natürlich sind auch Sie aufgefordert, eigene Beiträge zu liefern. Zu Schriften bitte direkt an:

MERLIN-Computer GmbH
KI Industriestr. 26
6236 Eschborn Listings

Rahmenimplementation nach Winston und Horn