Grundlagen

[Klaus]

1. Einführung in die künstliche Intelligenz

Zu Beginn dieses Kapitels soll der Versuch unternommen werden, den Begriff künstliche Intelligenz (KI) zu definieren. Weiters werden die Anforderungen besprochen, welche die KI an einen Wissensspeicher stellt. Der Hauptteil dieses Kapitels stellt Speichermethoden vor, die diese Anforderungen erfüllen. Speziell wird dabei auf logikorientierte und prozedurale Methoden eingegangen, Frames, Semantischen Netze und Constraints werden vorgestellt. Am Schluß dieses Kapitels wird auf die Notwendigkeit eingegangen, unsicheres Wissen in Wissensspeichern der KI abzubilden und entsprechende Techniken der Implementierung vorgestellt.

1.1 Definition und Ziele der KI

Wie auch bei der Definition von Wissensverarbeitung gibt es auch für die künstliche Intelligenz keine einheitliche Definition in der Literatur. Um dennoch eine Vorstellung über die Thematik der KI zu erlangen, wird in diesem Abschnitt zunächst der Turing-Test als Einstieg in die Thematik vorgestellt. Anschließend wird augehend von Definitionen durch renommierte Buchautoren eine Deutung des Begriffes künstlicher Intelligenz hergeleitet. Weiters werden die Anwendungsgebiete angeführt, die erst durch die Verwendung von künstlicher Intelligenz für den Computer erschossen wurden.

Der Turing-Test

Eine der ersten Arbeiten, die sich mit maschineller Intelligenz beschäftigt, ist ,,Computing machinery and intelligence'' von dem englischen Mathematiker Alan Turing, 1950. In dieser Arbeit beleuchtet Turing die Frage, ob Maschinen je in der Lage sein werden zu denken. Dabei geht er im Speziellen nicht darauf ein, worum es sich bei Intelligenz oder Denken handelt, sondern schlägt einen empirischen Test, den Turing-Test, vor. [Luger1997]

Der Test läuft nach folgendem Konzept ab. Ein menschlicher Richter steht in Verbindung mit einem Computer und einem Menschen. Damit der Test fair und unvoreingenommen gegenüber dem Computer ablaufen kann, werden beide Dialoge ausschließlich über Terminals geführt. Der Richter hat nun die Aufgabe herauszufinden, welcher der beiden Kommunikationspartner der Mensch und welcher der Computer ist. Über die Aufgabe des Richters sind sowohl der Computer als auch der Mensch informiert. Der Computer muß somit versuchen, sich wie ein Mensch zu verhalten. Am Ende des Tests muß der Richter auf Grund der geführten Dialoge entscheiden, welcher der beiden Partner der Computer war. Kann der Richter schlußendlich keine Entscheidung treffen, oder entscheidet er sich falsch, so kann die Maschine nach Turing als intelligent aufgefaßt werden. [Luger1997]

Defintionen von künstlicher Intelligenz

Ausgehend von der Auslegung von künstlicher Intelligenz von Alan Turing sollen an dieser Stelle Definitionen aus der Literatur vorgestellt und interpretiert werden.

,,Artificial Intelligence is the study of ideas which enable computers to do things, that make people seem intelligent. [...] The central goals of Artificial Intelligence are to make computers more useful and to understand the principles which make intelligence possible.'' [Winston1993]

In dieser Definition geht es einerseits um das Studium der Natur von Wissen und der Mechanismen intelligenten Verhaltens und andererseits um die Erweiterung der Anwendbarkeit von Computern zur Vereinfachung bisheriger Vorgangsweisen sowie zum Einsatz für neue, anspruchsvollere Aufgaben.

,,Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better. [...]'' [Rich1986]

Nach dieser Definition ist künstliche Intelligenz keine Eigenschaft, sondern ein Forschungsgebiet. Ausgehend von den beiden obigen Definitionen und deren Deutungen kann man zwei Grundrichtungen in der KI Forschung unterscheiden [Puppe1991][Gottlob1990]:

1. Die Erforschung und möglichst exakte Simulation von natürlichem intelligenten Verhalten. Dazu ist es notwendig, das Verhalten von Menschen möglichst genau zu beobachten und zu verstehen. In dieser Richtung gibt es starke Überschneidungen mit der Psychologie und der Neurologie.

2. Die Entwicklung von Systemen, deren intelligentes Verhalten auf Methoden beruht, die unterschiedlich zu den von Menschen benutzten Methoden sind. Diese Vorgehenswiese kommt in der Ingenieurswissenschaft häufig vor, z.B. fliegen Flugzeuge nach den selben aerodynamischen Prinzipien wie Vögel, ohne jedoch mit den Flügeln zu schlagen.

Bei den Anwendungsgebieten der KI handelt es sich naturgemäß um besonders komplexe Themengebiete, die mit den Methoden der ,,herkömmlichen'' Informatik nicht bewältigt werden konnten [Gottlob1990].

Game Playing:
Brettspiele wie Dame oder Schach gehörten zu den ersten Anwendungen der künstlichen Intelligenz.3.1

Sprachverstehen:
Sprachverstehende Systeme sollen es dem Benutzer ermöglichen, in seiner natürlichen Sprache mit dem Computer zu kommunizieren.

Wahrnehmung:
Die Forschung auf dem Gebiet der Wahrnehmung beschäftigt sich mit dem Problem menschliche Sinne am Computer nachzubilden, dazu gehören sehen (Bilderkennung) und hören (Spracherkennung).

Theorembeweisen:
Die Aufgabe der Theorembeweiser ist, die automatisierte Herleitung und Verifikation von mathematischen und logischen Formeln und Sätzen.

Robotik:
In der Robotik geht es um die Entwicklung von Steuerungen für Roboter, dazu müssen diese z.B. in der Lage sein, ihre Umgebung wahrzunehmen.

Expertensysteme:
In Expertensystemen ist das Spezialwissen und die Schlußfolgerungsfähigkeit qualifizierter Fachleute auf einem eng begrenzten Anwendungsgebiet im Computer nachgebildet. Die so entstandenen Systeme sollen Fachleute bei ihren Entscheidungen unterstützen. [Puppe1991]

Automatisches Programmieren:
Darunter versteht man das automatisierte Erstellen von Programmen, ausgehend von einer formalen Spezifikation.

Maschinelles Lernen:
Die Forschung zu maschinellen Lernen beschäftigt sich mit der Entwicklung von Computersystemen, die in der Lage sind, durch die Benutzung von Eingabeinformationen neues Wissen zu konstruieren und vorhandenes Wissen zu verbessern. [Herrmann1997]


1.2 Wissensrepräsentation

Grundvoraussetzung für intelligentes Verhalten von Computer-Systemen ist, daß sie Wissen über ihre Umwelt besitzen. Dieses Wissen muß in einer für den Computer lesbaren Form gespeichert sein, wie dies bereits in Abschnitt 2.3.1 erläutert wurde. ,,Intelligente Systeme verhalten sich als würden sie Wissen über ihre Umgebung besitzen und die von ihnen verursachten Veränderungen vorhersehen.''3.2 Dabei ist zu beachten, daß das Computersystem selbst Teil der Umwelt ist und dadurch auch Wissen über sich besitzen muß, um bestimmte Aufgaben zu erfüllen.

Praktisch kann man eine Wissensrepräsentation als die Abbildung eines Ausschnitts der realen Welt bezeichnen. Diese Abbildung muß in einer Art und Weise geschehen, daß die darin enthaltenen Informationen automatisiert verarbeiten werden können. Das Wissen kann implizit im Programmcode, somit in der Abfolge der Befehle gespeichert sein, oder explizit an bestimmten Stellen des Systems. [Gottlob1990]
3.2.1 Implizites Wissen

Implizites Wissen steht im Code eines Programmes; z.B. bei der Berechnung einer bestimmten mathematischen Funktion, wie der Multiplikation zweier Matrizen. Der Algorithmus wird nicht abgearbeitet, weil das System eine Methode gesucht hat um zwei Matrizen zu multiplizieren, sondern weil der Programmierer wußte, daß in weiterer Folge das Produkt benötigt wird und hat deshalb den entsprechenden Algorithmus und den Aufruf der entsprechenden Funktion implementiert. Das Wissen, daß dieser Algorithmus an einer bestimmten Stelle aufgerufen werden muß, ist also dirlekt im Programmcode enthalten. [Gottlob1990]

/* Anweisungen vor der Matrizenmultiplikation */
...
for i := 1 to n do /* äußere Schleife */
for j := 1 to m do /* innere Schleife */
... /* Multiplikationsanweisungen */
endfor;
endfor;
...
/* Anweisungen nach der Matrizenmultiplikation */

Auch ein Funktionsaufruf ändert nichts daran. Das Wissen ist in einem Unterprogramm versteckt, aber die Information, wann ein bestimmtes Unterprogramm aufgerufen werden soll, ist fix im Programm enthalten.

/* Anweisungen vor der Matrizenmultiplikation */
...
Produkt := Matrix_Mult(A, B);
...
/* Anweisungen nach der Matrizenmultiplikation */

3.2.2 Explizites Wissen

Wird Wissen explizit gespeichert, so sind dem System seine Problemlösungsmöglichkeiten für bestimmte Aufgaben bekannt, z.B. die verschiedenen Möglichkeiten die Inverse einer Matrix zu berechnen. Sie sind an einer bestimmten Stelle im System explizit vermerkt, und werden je nach Bedarf entsprechend angewandt. Es wird zwischen deklarativem und prozeduralem Wissen unterschieden [Gottlob1990]:

Deklarativ: Es wird beschrieben, in welchem Verhältnis die betrachteten Einheiten in der realen Welt zueinander stehen. In obigen Beispiel kann die ursprüngliche Matrix ($M$) und die invertierte Matrix ($M^{-1}$) in Beziehung mit der Einheitsmatrix ($E$) gesetzt werden:


\begin{displaymath}M*M^{-1}=E \end{displaymath}

Eine getrennte, aktive Komponente muß dann dieses Wissen verwenden, um die Lösung zu berechnen. Der Vorteil liegt in der besseren Verständlichkeit und Lesbarkeit diese Methode. Der Aufwand, um eine konkrete Lösung zu berechnen, ist aber entscheidend größer.

Prozedural: Es wird Schritt für Schritt angegeben, wie die Aufgabe gelöst werden muß. Der Unterschied zu implizitem Wissen ist jedoch, daß der Aufruf nicht implizit im Code vermerkt ist, sondern das System selbst erkennt, daß es zur Lösung des Problems dieses Wissen benötigt. Die explizite prozedurale Art Wissen zu speichern ist nicht so leicht lesbar, aber effizienter in der Abarbeitung.


3.2.3 Wissensbasierte Systeme

Abbildung 1.1: Grundsätzlicher Aufbau von konventionellen Programmen und Wissensbasierten Systemen.
\includegraphics {bilder/ki/wissensbasiert.eps}

Systeme, die Wissen explizit speichern, werden auch wissensbasierte Systeme genannt. Der Unterschied zu herkömmlichen, konventionellen Programmen ist in Abbildung 3.1 veranschaulicht. Konventionelle Programme, die Wissen implizit speichern, erschweren es, Wissen nachträglich zu verändern. Dazu wäre ein Eingriff in den Algorithmus notwendig. Bei wissensbasierten Systemen existiert eine klare Schnittstelle zwischen anwendungsspezifischen Wissen und der allgemeinen Problemlösungsstrategie. Die Komponente der allgemeinen Problemlösungsstrategie wird auch Inferenzmaschine genannt. Der Vorteil dieses Konzepts ist, daß man eine Problemlösungsstrategie für mehrere Anwendungsgebiete verwenden kann. Es muß nur die entsprechende Wissensbasis ausgetauscht werden.

Somit ist es Softwareherstellern möglich, ,,leere'' Wissensbasierte Systeme anzubieten, die durch eine anwendungsspezifische Wissensbasis an die eigenen Anforderungen angepaßt werden können. Ein Beispiel für ein solches System ist die Expertensystemshell D33.3, welche aus einer grafischen Benutzeroberfläche und einer Problemlösungskomponente besteht. Durch Verwendung von unterschiedlichen Wissensbasen kann das System einfach an verschiedene Anwendungsgebiete angepaßt werden. Mit D3 wurden z.B. ein Expertensystem zur Pflanzenbestimmung, aber auch ein Service -System für Druckmaschinen entwickelt [Ernst1996].

1.2.4 Anforderungen an die Wissensrepräsentationen

In der künstlichen Intelligenz muß eine Wissensrepräsentation hohen Ansprüchen gerecht werden. Sie muß es ermöglichen, Wissen in möglichst einfacher, übersichtlicher Form schnell und effektiv zu verarbeiten. Dabei sind nicht nur Kriterien zu berücksichtigen, die für das automatisierte Verarbeiten von Wissen notwendig sind, es müssen auch die Interessen des Knowledge Engineers3.4, das ist die Person, die die Wissensrepräsentation erstellt und wartet, beachtet werden. Daraus lassen sich fünf Anforderungen ableiten, die für eine Wissensrepräsentation wesentlich sind [Gottlob1990]:

Verarbeitbarkeit:
Es muß dem Softwaresystem möglich sein, aus bestehendem Wissen durch logisches Verknüpfen, auf neues Wissen zu schließen. Die Wissensrepräsentation sollte das auf effiziente Weise unterstützen.

Expertensysteme versuchen z.B. aus bereits bekannten Fakten und aus Verknüpfungen von Fakten, den Regeln, auf neue Fakten zu schließen, die dann wieder als bekanntes Wissen betrachtet werden. Auf Expertensysteme wird später, im Abschnitt 6, genauer eingegangen.

Flexibilität:
Ein bestimmter Repräsentationsansatz soll einerseits geeignet sein, Wissen aus möglichst vielen Anwendungsbereichen (Domains) wie z.B. der Medizin oder der Geologie, darzustellen. Anderseits sollen unabhängig vom Anwendungsgebiet unterschiedliche Aufgabenstellungen, wie z.B. Diagnostik, Konstruktion und bzw. oder Simulation, effizient verwirklicht werden können.

So ist es das Ziel der Diagnose, ein bekanntes Muster, wie z.B. ein Krankheitsbild oder einen Fehler, wieder zuerkennen. Dabei wird die Lösung aus einer vorgegebenen Menge von Alternativen ausgewählt. Im Gegensatz dazu wird bei der Konstruktion die Lösung aus kleinen Bausteinen zusammengesetzt. Es gibt jedoch zuviele mögliche Kombinationen, um aus einer Menge vorgegebener Alternativen auszuwählen. So kann z.B. bei der automatisierten Programmierung nicht aus der Menge aller möglichen Programme ausgewählt werden. Die Simulation unterscheidet sich von der Diagnose und der Konstruktion dadurch, daß kein vorgegebenes Ziel erreicht werden soll, sondern nur die Auswirkungen von Handlungen und Entscheidungen simuliert werden sollen.[Puppe1991]

Modularität:
Die Wissensbasis eines intelligenten Systems soll möglichst einfach veränderbar und erweiterbar sein. Am einfachsten ist das zu erreichen, wenn die Wissensbasis modular aufgebaut ist. Das bedeutet, spezielle Bereiche des Wissens, wie etwa Wissen über die Lösung eines bestimmten Teilproblems, sollen möglichst unabhängig vom Rest der Wissensbasis hinzugefügt oder verändert werden können.

Da bei deklarativem Wissen Informationen über die Zusammenhänge zwischen einzelnen Wissenselementen, wann und wo sie eingesetzt werden, nicht Bestandteil des Wissens selbst ist, kommt die deklarative Art Wissen zu speichern der Forderung nach Modularität entgegen.

Eine der Modularität verwandte Forderung ist die Trennung zwischen dem gespeicherten Wissen (der Wissensbasis) und dem für die Verarbeitung und Schlußfolgerung zuständigen Teil des Systems (der Inferenzmaschine).

Verständlichkeit:
Der Inhalt der Wissensbasis muß gegenüber dem Knowledge Engineer und dem Benutzer gleichermaßen leicht verständlich darstellbar sein. Das heißt allerdings nicht, daß die Darstellung für beide zwangsläufig in derselben Form erfolgen muß, da sie im Umgang mit der Wissensbasis unterschiedliche Ziele verfolgen; z.B. muß es für einen Benutzer nachvollziehbar sein, wie ein System zu einer bestimmten Entscheidung gekommen ist. Dem Knowledge Engineer dagegen ist es wichtig, einen Überblick über das gesamte gespeicherte Wissen zu besitzen, um Lücken oder Widersprüche in der Wissensbasis des Systems aufzudecken.

Darstellbarkeit unsicheren Wissens:
In vielen Fällen kann die Wirklichkeit nicht durch Fakten beschrieben werden, die hundertprozentig korrekt sind, sondern nur mit Fakten, die mit einer bestimmten Wahrscheinlichkeit zutreffen. Intelligentes Verhalten besteht nun darin, aus einer Situation das Beste zu machen, in der das richtige Verhalten nicht eindeutig vorgeschrieben ist. Daher müssen intelligente Systeme in der Lage sein, mehrdeutige Aussagen zu verarbeiten. Diese Unsicherheiten können auf mehrere Arten entstehen [Gottlob1990]:

* Inhärente Unsicherheit der Information
* Unvollständigkeit der Information
* Unsicherheit von Schlußfolgerungen
* Zusammenfassung von Informationen, die aus mehreren, eventuell einander widersprechenden Quellen stammen

Bei vielen Anwendungen kann jedoch auf einer Repräsentation unsicheren Wissens verzichtet werden, sodaß dadurch die Wissensrepräsentation und die Verarbeitung vereinfacht wird. Auf die Quellen von Unsicherheit und deren Repräsentation in Wissensspeichern wird in Abschnitt 3.8 näher eingegangen.

1.3 Logikorientierte Methode der
Wissensrepräsentation

Aufbauend auf den Theorien der formalen Logik stellt die Prädikatenlogik erster Stufe mit Identität3.5 und Funktionssymbolen, kurz PIF, das bekannteste Kalkül zur Darstellung von logischen Sachverhalten dar. Ein Beispiel für eine Formel dieser Repräsentation ist [Gottlob1990]:
$\displaystyle {\forall X((person(X) \wedge \neg(X=eva) \wedge \neg (X=adam)) \Rightarrow} \hspace{3cm}$
$\displaystyle \Rightarrow \exists Y (person(Y) \wedge mutter\_von(X)=Y).$ (3.1)

Diese PIF-Formel sagt aus, daß jede Person ausgenommen Adam und Eva (mindestens) eine Mutter hat.

Eine Formel in der PIF-Logik setzt sich aus folgenden Grundzeichen zusammen: [Gottlob1990]

* Konstantensymbole, die hier mit Kleinbuchstaben beginnende Zeichenfolgen oder Ziffern dargestellt werden; z.B.: $adam, eva, 10$.

* Variablensymbole, hier durch mit Großbuchstaben beginnende Zeichenfolgen dargestellt; z.B.: $X, Y$.

* Funktionssymbole, zur Darstellung n-ärer Funktionen3.6, hier durch Kleinbuchstaben beginnenden Zeichenfolgen dargestellt; z.B. das einstellige Funktionssymbol $mutter\_von$.

* Prädikatensymbole, zur Darstellung n-ärer Prädikate3.7, hier durch mit Kleinbuchstaben beginnende Zeichenfolgen dargestellt; z.B.: $person$.

* Junktoren: $\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$

* Quantoren: $\forall, \exists$

* Das Gleichheitszeichen =

* Klammern und Kommas als Hilfssymbole; für die Darstellung von Argumenten von Funktionen und Prädikaten und zur Festlegung der Bindungsbereiche von Junktoren und Quantoren.

Die PIF ist zwar eine sehr ausdrucksstarke Logik, doch leider eignet sie sich nicht zur Implementierung. Erstens ist die PIF unentscheidbar, d.h. für eine beliebige Aussage kann nicht entschieden werden, ob sie aus den Fakten folgt oder nicht; z.B. kann aus der Formel $(raum(dunkel) \Rightarrow tageszeit(nacht) \vee jalousie(geschlossen))$ kein weiteres Faktum gewonnen werden, wenn das Faktum $raum(dunkel)$ bekannt ist. Zweitens nehmen Formelmanipulationen in der PIF sehr viel Rechenzeit in Anspruch. Aus diesem Grund werden meist nur stark reduzierte Teilsysteme der PIF in der Praxis verwendet. Diese Teilsysteme werden aber oft um Möglichkeiten erweitert, die in der ursprünglichen PIF nicht vorhanden waren, z.B. um die Möglichkeit eine Implikation mit einer Wahrscheinlichkeitsaussage zu versehen, wie in Kapitel 3.8 besprochen wird. [Gottlob1990]


1.3.1 Einfache Fakten Regel Systeme

Bei Einfachen Fakten Regel Systemen, kurz EFRS, handelt es sich um ein PIF Teilsystem, das sich besonders gut zur Implementierung eignet. Die folgende Definition ist entnommen aus [Gottlob1990].

,,Ein EFRS S ist eine endliche Menge von Regeln und Fakten. Die Menge aller Regeln von $S$ wird mit $R(S)$ bezeichnet und die Menge aller Fakten von $S$ mit $F(S)$. Es gilt somit $S=R(S) \cup F(S)$.'' [Gottlob1990]

Fakten haben die Form $\psi(c_1, \ldots, c_n)$ mit einem Prädikatensymbol $\psi$ und Konstantensymbolen $c_1, \ldots ,c_n$. Beispiele für Fakten: mensch(hans), vater (hans, maria), gerade(2), teiler(2,4). Die Prädikatensymbole $mensch$, $gerade$ sind einstellig; die Prädikatensymbole $vater$, $teiler$ sind zweistellig.

Regeln sind Implikationen der folgenden Form:
$\displaystyle Q(\psi_1(t^1_1, \ldots ,t^1_{\alpha_1})$ $\textstyle \wedge$ $\displaystyle \psi_2(t^2_1, \ldots ,t^2_{\alpha_2})$
$\textstyle \wedge$ $\displaystyle \ldots \psi_n(t^n_1, \ldots ,t^n_{\alpha_n})) \Rightarrow \psi_0(t^0_1, \ldots ,t^0_{\alpha_0})$ (3.2)

wobei die $\psi_i$ Prädikatensymbole darstellen, die $t^i_j$ entweder Variablensymbole oder Konstantensymbole sind und $Q$ ein Quantorpräfix ist. Der Quantorpräfix enthält für genau jedes in der Formel vorkommende Variablensymbol $X$ einen Allquantor der Form ,,$\forall X$''. Zusätzlich muß jede Variable die rechts vom Implikationszeichen vorkommt auch auf der linken Seite vorkommen. Zur Vermeidung von überflüssigen Klammerzeichen bindet der Junktor ,,$\wedge$'' stärker als ,,$\Rightarrow$''.

Wenn ein Fakt $F$ aus einem EFRS logisch folgt, dann schreiben wir $S \models F$. Die Menge aller Fakten die aus einem EFRS $S$ logisch folgen, bezeichnen wir als $Cons(S)$. [Gottlob1990]

Ein Beispiel für ein Einfaches Fakten Regel System ist:
$\displaystyle S_1$ $\textstyle =$ $\displaystyle \{ \forall X(mensch(X) \Rightarrow sterblich(X)),$
$\displaystyle \forall X\,\forall Y(kind(X,Y) \wedge mensch(X) \Rightarrow mensch(Y)),$
$\displaystyle mensch(hans),$
$\displaystyle kind(hans, ernst)$
$\displaystyle kind(ernst, olga)\}.$ (3.3)

Aus dem Faktum $mensch\,(hans)$ und der Regel $kind\,(hans, enst)\; \wedge$ $mensch$ $(hans)$ wird gefolgert, daß $mensch(ernst)$ ein neues Faktum ist. Der analoge Schluß führt zu $mensch(olga)$. Aus der Regel $\forall X(mensch(X) \Rightarrow sterblich(X))$ folgt somit, daß $hans$, $ernst$ und $olga$ sterblich sind, da alle Menschen sind. Alle Fakten, die aus dem EFRS $S_1$ logisch folgern, erhält man mit $Cons(S_1)$:
$\displaystyle Cons(S_1)$ $\textstyle =$ $\displaystyle \{mensch(hans), kind(hans, ernst), kind(ernst, olga),$
$\displaystyle mensch(ernst), mensch(olga), sterblich(hans),$
$\displaystyle sterblich(ernst), sterblich(olga)\}.$ (3.4)

In einem weiteren Beispiel soll die Mitarbeiterstruktur eines Betriebes mit Hilfe eines EFRS beschrieben werden. Abbildung 3.2 zeigt die Mitarbeiterhierarchie im Betrieb. [Gottlob1990]

Abbildung 3.2: Die Mitarbeiterhirarchie soll durch ein einfaches Fakten Regelsystem repräsentiert werden.
\includegraphics [width=14cm]{bilder/ki/mitarbeiter.eps}

$angestellter(X)$: $X$ ist ein Angestellter der Firma
$vorgesetzter(X,Y)$: $X$ ist der unmittelbare Vorgesetzte von $Y$
$gleiche\_ebene(X,Y)$: $X$ und $Y$ sind Kollegen auf der gleichen Ebene in der Mitarbeiterhierarchie
<>

Bei der Umsetzung der in der Abbildung beschriebenen Struktur soll das Prädikat $gleiche\_ebene$ nicht durch eine Faktenmenge, sondern durch Regeln definiert werden.
$\displaystyle S_2$ $\textstyle =$ $\displaystyle \{angestellter(muller),$
$\displaystyle angestellter(maier),$
$\displaystyle angestellter(stallburger),$
$\displaystyle angestellter(massenbach),$
$\displaystyle angestellter(tunlich),$
$\displaystyle angestellter(zettel),$
$\displaystyle angestellter(frohlich),$
$\displaystyle angestellter(irrsiegler),$
$\displaystyle angestellter(pagenstecher),$

$\displaystyle vorgesetzter(muller, maier),$
$\displaystyle vorgesetzter(muller, tunlich),$
$\displaystyle vorgesetzter(maier, stallberger),$
$\displaystyle vorgesetzter(maier, massenbach),$
$\displaystyle vorgesetzter(tunlich, zettel),$
$\displaystyle vorgesetzter(tunlich, frohlich),$
$\displaystyle vorgesetzter(tunlich, irrsigler),$
$\displaystyle vorgesetzter(irrsiegler, pagenstecher),$

$\displaystyle \forall X(angestellter(X) \Rightarrow gleiche\_ebene(X,X)),$
$\displaystyle \forall X \,\forall Y \,\forall X_1 \,\forall Y_1 (gleiche\_ebene(X,Y) \wedge vorgesetzter(X, X_1)$
$\displaystyle \hspace{2,48cm} \wedge vorgesetzter(Y, Y_1) \Rightarrow gleiche\_ebene(X_1,Y_1))\}$ (3.5)

Für $Cons(S_2)$ erhält man nun alle Fakten, die in $S_2$ vorkommen und zusätzlich Fakten der Form $gleiche\_ebene(\alpha, \beta)$, wobei $\alpha$ und $\beta$ Angestellte der gleichen Hierarchieebene sind, z.B. $gleiche\_ebene(stallburger, zettel)$ oder gleiche_ebene (zettel, irrsiegler).

Um zum Faktum $gleiche\_ebene(stallburger, zettel)$ zu gelangen, beginnt man bei der Schlußfolgerung der letzten Regel: $gleiche\_ebene(X_1,Y_1)$. Somit lautet die Voraussetzung, daß das Faktum aus den bereits bekannten Fakten folgt: gleiche_ebene(X,Y) $\wedge$ vorgesetzter(X, stallburger) $\wedge$ vorgesetzter(Y, zettel). In den bekannten Fakten wird nun nach einem $X$ gesucht, welches das Prädikat $vorgesetzter(X, stallburger)$ erfüllt. Das ist für $X=mair$ der Fall. Äquivalent wird mit $Y$ verfahren, sodaß $Y=tunlich$ folgt. Die einzige offene Voraussetzung ist nun $gleiche\_ebene(mair,tunlich)$. Um diese Forderung zu prüfen wird rekursiv wieder die letzte Regel betrachtet. Nach der Abarbeitung kommt man zu der Vorderung $gleiche\_ebene(muller, muller)$, welche durch die vorletzte Regel $angestellter(muller) \Rightarrow gleiche\_ebene(muller,muller)$ erfüllt ist. Somit kann man schreiben: $S_2 \models gleiche\_ebene(stallburger, zettel)$.

Die Regeln in einem EFRS entsprechen Hornklauseln, das sind Klauseln bei denen nur auf ein Faktum geschlossen wird, d.h. es steht nur ein Prädikatensymbol nach dem Implikationszeichen. Somit stellt z.B. die PIF-Formel (3.1) keine Hornklausel dar. Sie besitzt nach dem Implikationszeichen die zwei Prädikate $person$ und $mutter\_von$. Hornklauseln werden auch in logischen Programmiersprachen z.B. PROLOG verwendet. [Böhringer1988]

1.3.2 Logische Programmiersprachen

Klassische Programmiersprachen sind hauptsächlich auf zwei Schwerpunkte ausgerichtet, um wissenschaftlich-technischen Aufgaben zu lösen und um Daten und Textbestände zu manipulieren. Mit ihrer Hilfe ist es schwer komplexe Wissensbasierte Systeme zu entwickeln. Aus diesem Grund werden solche Systeme vorwiegend in logischen Programmiersprachen, wie Lisp oder Prolog, implementiert. [Gottlob1990]

LISP

LISP wurde in den 50er Jahren von John McCarthy entwickelt und ist die zweitälteste noch in Verwendung stehende Programmiersprache. Nur Fortran ist um ein Jahr älter. LISP steht für List Programming. Zielsetzung bei der Entwicklung der Sprache war es, ein System zur Symbolmanipulation zur Verfügung zu haben. Symbolmanipulation wurde als Schlüssel für die Entwicklung intelligenter Programme aufgefaßt.

LISP ist eine funktionale Programmiersprache und verwendet Listen als Datenstruktur. Die Verarbeitung eines Programmes erfolgt durch Verarbeitung von Listen. Für LISP sind Daten und Programme äquivalent, d.h. sie werden in der gleichen Datenstruktur, in Listen, kodiert. Dieser Ansatz verhalf LISP zu einer dominierenden Stellung überall dort, wo anspruchsvolle Symbolverarbeitungsaufgaben gelöst werden mußten, für welche die Sprachmittel bisher bekannter Sprachen nicht ausreichten.

LISP selbst stellt jedoch direkt keine Methoden zur Verfügung, um Fakten logisch zu verknüpfen und so auf neue Fakten zu schließen. Die für ein Wissensbasiertes System notwendigen Komponenten, die Wissensbasis und die Inferenzmaschine, sind somit erst aus LISP-Konstrukten zu erstellen. [Schnupp1986]

Prolog

Prolog ist eine deklarative Programmiersprache und steht für ,,Programmieren in Logik''. Das bedeutet, daß in Prolog, im Gegensatz zu den herkömmlichen prozeduralen Programmiersprachen wie Fortran, Pascal oder C nicht mehr algorithmisch der Lösungsweg angegeben wird, sondern nur mehr die Bedingungen, die die Lösung des Problems erfüllen sollen. Funktionale Sprachen wie LISP sind ebenfalls deklarativ. Während aber funktionale Programmiersprachen auf Funktionen und Funktionsapplikationen beruhen, basieren logische Programmiersprachen auf Relationen und Regelanwendung. [Gottlob1990]

Prolog ist eine deskriptive Programmiersprache, d.h. die Lösung eines Problems wird durch Regeln und Fakten beschrieben. Prozedurale Programmiersprachen sind hingegen imperativ. Die Lösung eines Problems muß in Form von Befehlsfolgen ausprogrammiert werden. Die in der nachfolgenden Gleichung formulierte Aussage

\begin{displaymath}Algorithmus = Logik + Kontrolle\end{displaymath}

betont den Unterschied zwischen dem Was (der Logik) und dem Wie (der Kontrolle) in der Programmierung, d.h. in der Implementierung eines Algorithmus. Ein Algorithmus besteht also aus einer logischen Komponente, die das Wissen zur Problemlösung enthält und einer Steuerungskomponente, die bestimmt, wie das Wissen verwendet wird, um damit Probleme zu lösen. Mit dieser Grundidee stellt Prolog eine Sprache dar, in der sich Wissensbasierte Systeme, wie sie in Abschnitt 3.2.3 beschrieben wurden, einfach entwickeln lassen. [Gottlob1990]

1.4 Prozedurale Methode als Wissensrepräsentation

Beim prozeduralem Ansatz wird Wissen in Form einer Abfolge von Anweisungen, den Prozeduren, gespeichert. Im Unterschied zu nicht wissensbasierten Programmen muß der Aufruf einer Prozedur aber explizit der Kontrolle des Programmes unterliegen. Das bedeutet, das Programm weiß über seine Problemlösungsmöglichkeiten bescheid und wendet diese entsprechende der vorliegenden Problemstellungen an. [Gottlob1990]

Beispiel: Es soll der Sachverhalt dargestellt werden, daß alle Personen sterblich sind, daß alle Hunde sterblich sind, daß alle Katzen sterblich sind, und daß Helena und Sokrates Personen sind.

Die logische Repräsentation sieht folgendermaßen aus:

\begin{eqnarray*} & & \forall X (person(X) \Rightarrow sterblich(X)). \\ & & ... ...erblich(X)). \\ & & person(sokrates). \\ & & person(helena). \end{eqnarray*}



Eine prozedurale Repräsentation könnte so aussehen:

boolean function person(x)
if x=sokrates then return true
else
if x=helena then return true
else return false

boolean function sterblich(x)
if person(x) then true
else
if hund(x) then true
else
if katze(x) then true
else return false

Versucht man mit dem Aufruf $sterblich(Sokrates)$ zu überprüfen ob Sokrates sterblich ist, so wird zuerst überprüft ob Sokrates eine Person ist. Wäre Sokrates keine Person, würde überprüft ob Sokrates ein Hund ist. In dieser Kette wird solange fortgeschritten, bis auf die Spezies getroffen wird, der Sokrates angehört oder keine weiteren Abfragen mehr folgen. Geht man davon aus, daß die meisten Objekte Personen sind, die auf Sterblichkeit überprüft werden, ist diese Vorgehenswiese effizient. Schon beim ersten Schritt wird überprüft, ob das Objekt der Spezies Person angehört. Somit ist es bei prozeduraler Wissensspeicherung möglich, durch geschickte Wahl der Abfolge der Einzelschritte, die Abarbeitung für häufig auftretende Vorgänge effizient zu gestalten. Da jedoch alle Lösungsmöglichkeiten explizit berücksichtigt werden müssen, ist es schwer, komplexe Wissensbasen zu erstellen.

Ein weiterer Nachteil ist die geringe Flexibilität. So kann das System die Frage ,,Sind alle Personen sterblich?'' nicht entscheiden. Eine solche Entscheidung wäre bei einer logikbasierten Repräsentation mit geeignetem Inferenzverfahren möglich. Zudem macht eine Erweiterung der bestehenden Wissensbasis um den Satz

\begin{displaymath}\forall X (tier(X) \Rightarrow sterblich(X)). \end{displaymath}

einen Eingriff in eine bereits bestehende Prozedur nötig. Dies schränkt die Modularität sehr stark ein. [Gottlob1990]


1.5 Frames

Die Wissensrepräsentation mit Hilfe von Frames stellt eine objektorientierte Wissensrepräsentation dar. Dabei werden Objekte der realen Welt durch Frames dargestellt. Die Eigenschaften des Objekts werden in den Frames in sogenannten Slots gespeichert. Der Tatsache, daß es in der realen Welt mehrere unterschiedliche Objekte eines Objekttyps gibt, wird mit Hilfe von generischen Frames und deren Instanzen Rechnung getragen. Ein generischer Frame hält für jedes Attribut mit dem ein Objekt beschrieben wird, einen Slot bereit. In einer Instanz des generischen Frames wird nun jedem Slot, entsprechend für das Attribut für das er steht, ein Wert zugeordnet. Abbildung 3.3 zeigt den generischen Frame des Objekttyps Elefant und eine Instanz, die den speziellen Elefanten Bimbo beschreibt. Die Bedeutung des Slots AKO wird später beschrieben, wenn auf die Technik der Vererbung eingegangen wird. [Winston1993]

Abbildung 1.3: Der Generische Frame des Objekttyps Elefent und eine Beispielinstanz Bimbo. Im ,,Is A'' Slot der Instanz ist gespeichert, daß es sich bei Bimbo um einen Elefanten handelt.
\includegraphics {bilder/ki/frameelefant.eps}

Die Beziehung zwischen einem generischen Frame und einer Instanz wird mit Hilfe des ,,Is A''-Slot hergestellt. Im Beispiel ist im ,,Is A''-Slot gespeichert, daß es sich bei Bimbo um einen Elefanten handelt. In den übrigen Slots sind die Werte zu den Attributen gespeichert.

In einem generischen Frame wird zu einem Slot nicht nur das Attribut gespeichert, für das der Slot steht, sondern auch zusätzliche Informationen und Programme. Dazu gehören: [Puppe1991]

* Defaultwerte, die beim Lesezugriff zurückgegeben werden, wenn kein Wert explizit zugeordnet wurde. Im Beispiel mit dem Elefanten wäre das für den Slot Farbe der Wert grau.
* Bedingungen, die der Wert erfüllen muß, z.B. männlich oder weiblich im Slot Geschlecht.
* Prozeduren die beim Schreib-, Lese- oder Löschzugriff auf den Slotwert ausgeführt werden. Dadurch wird erreicht, daß Wissen nicht nur passiv gespeichert wird. Es wird möglich bei jedem Zugriff auf Slots Schlüsse zu ziehen und andere Frames zu modifizieren. Somit ist es möglich, die Wissensbasis auf einfache Art konsistent zu halten.

Vererbung

Die Stärke des Framekonzepts ist die Vererbung. Ein generischer Frame kann Slots an einen anderen generischen Frame vererben. Diese Beziehung wird mit Hilfe des AKO-Slots dargestellt. AKO steht für ,,A Kind Of''. Im erbenden Frame ist im AKO-Slot vermerkt, von welchem Frame er Slots erbt. Abbildung 3.4 zeigt eine Framestruktur, in der Informationen zu einem Ereignis gespeichert werden. Es gibt zwei mögliche Ereignisse, Unglücke und Feiern. Die Ereignisse teilen sich wieder in Erdbeben und Überschwemmungen, bzw. in Hochzeiten und Geburtstage. Jedes Ereignis findet an einem bestimmten Ort zu einer bestimmten Zeit statt. Darum werden diese Slots weitervererbt an Unglücke und Feiern. Weiters hat jede Feier einen Gastgeber und Gäste. Diese und die Slots die vom Ereignis geerbt wurden, werden weiter an die verschiedenen Feiern vererbt. Eine Instanz einer Geburtstagsfeier könnte also wie in Abbildung 3.5 aussehen. [Winston1993]

Abbildung 1.4: Beispiel für eine Frame Struktur für zwei unterschiedliche Arten von Ereignissen. Die Vererbung erfolgt über zwei Ebenen: Unglück und Feier erben vom Frame Ereignis; Erdbeben und Überschwemmung erben vom Frame Unglück und somit auch vom Frame Ereignis.
\includegraphics {bilder/ki/frameereignis.eps}

Abbildung 1.5: Beispiel für eine Instanz Geburtstag, die duch Vererbung erzeugt wurde.
\includegraphics {bilder/ki/framegeburtstag.eps}

1.6 Semantische Netze

Semantische Netze sind nicht als eigenständige Wissensrepräsentation aufzufassen, sie dienen vielmehr dazu, die Zusammenhänge in den bisher besprochenen Repräsentationen übersichtlich darzustellen [Puppe1991]. So wurde z.B. in Abbildung 3.2 die Aufgabenstellung der Implementierung einer Mitarbeiterhierarchie graphisch als semantisches Netz dargestellt, bevor die logische Repräsentation erarbeitet wurde, oder in Abbildung 3.4 wurde die Framehierarchie zur besseren Verständlichkeit als semantisches Netz dargestellt, ohne dies explizit zu erwähnen.

Abbildung 1.6: Ein Beispiel für eine Repräsentation durch ein semantisches Netz; Mit Hilfe des semantischen Netzes wird die räumliche Beziehung der geometrischen Objekte untereinander ausgedrückt.
\includegraphics [height=5cm]{bilder/ki/SemantischesNetz.eps}

Semantische Netze stellen gerichtete Graphen dar, die aus Nodes, Links und Link Labels bestehen. Diese Begriffe sind folgendermaßen definiert [Winston1993]:

Node,
beschreibt ein Objekt der realen Welt.
Link,
stellt die Beziehung zwischen zwei Nodes dar.
Link Labels,
beschreibt die Art der Beziehung, die mit einem Link ausgedrückt wird.

Abbildung 1.6 stellt ein Beispiel für ein semantisches Netz dar. Es drückt die räumlichen Beziehungen der geometrischen Objekte untereinander aus.

Anhand semantischer Netze werden in Kapitel 4 und 5 Algorithmen erklärt, die in der Wissensverarbeitung häufig angewandt werden. Dazu gehören vor allem Algorithmen zur Suche in Graphen und zur Behandlung von Spielbäumen.

1.7 Constraints

Mit der Hilfe von Constraints können Relationen, d.h. Beziehungen zwischen Variablen, dargestellt werden. Dabei eignen sich Constraints besonders zur Darstellung von Randbedingungen, die die Lösung des Problems auf jeden Fall erfüllen muß. Ein Beispiel dafür ist der Wunsch eines Lehrers bei der Stundenplanerstellung, daß er einen bestimmten Tag in der Woche frei haben möchte. Durch jedes neue Constraint wird der Lösungsraum zusätzlich eingeschränkt [Puppe1991].

Während Constraints ungerichtete Zusammenhänge zwischen Variablen ausdrücken, die nach jeder Variable hin aufgelöst werden können, z.B. $U=I*R$, repräsentieren Regeln gerichtete Zusammenhänge, z.B. $A \Rightarrow B$. Ein Constraint kann häufig als mathematische Gleichung betrachtet werden, ein Constraint-System als Gleichungssystem. Unter Constraint-Propagierung versteht man dann die Berechnung der Lösung des Gleichungssystems. Es lassen sich aber nicht nur mathematische Gleichungen beschreiben, sondern auch Ungleichungen und nichtnumerische Zusammenhänge. Constraints eignen sich deshalb zur quantitativen und qualitativen Modellierung von mathematischen und physikalischen Systemen [Puppe1991].

Es existieren die unterschiedlichsten Möglichkeiten Constraints zu realisieren, z.B. läßt sich die Beziehung zwischen Körpergröße und Idealgewicht folgendermaßen darstellen:

* Tabelle, z.B. mit Hilfe einer Gewichtstabelle
* Funktion, z.B. Normalgewicht = Körpergröße - 100
* Prädikate: $\mbox{Übergewicht} = \frac{\mbox{tatsächliches Gewicht}}{\mbox{Normalgewicht}}<0,8 $

Als Eingabe für den Propagierungs-Algorithmus dient ein Constraint-System, sowie eine Variablenbelegung, soweit diese bekannt ist. Als Ausgabe erhält man eine Belegung der bisher unbekannten Variablen. Wenn alle Variablen einen eindeutigen Wert annehmen, liegt eine eindeutige Lösung vor. Es ist aber auch möglich, daß für eine Variable eine Wertemenge von möglichen Lösungen zurückgegeben wird, oder eine Variable unter den gegebenen Bedingungen keinen gültigen Wert annehmen kann. Die Aufgabe des Propagierungs-Algorithmus ist es also, den Wertebereich einer Variablen solange einzuschränken, bis keine weiteren Einschränkungen mehr möglich sind. Es hängt von der Komplexität dieses Algorithmus ab, welche Ausdrücke in Constraints verarbeitet werden können.

* Nur Feste Werte: $X=5$
* Wertemenge: $ X \in \{3,5,6,8,10\}$
* Symbolische Ausdrücke: $X=2*Y$

Veranschaulichung der Arbeitsweise anhand eines Beispiels

Mit Hilfe des nachfolgenden Beispiels, ,,Der Hilferuf eines Studenten an seinen Vater'' [Puppe1991], soll die Arbeitsweise des Propagierungs-Algorithmus erläutert werden.

\begin{figure} % latex2html id marker 1163\begin{tt} \begin{center} \begin{... ...More Money''.] {Aufgabenstellung des Problems ,,Send More Money''.}\end{figure}

Es soll jedem Buchstaben eine Ziffer zugewiesen werden, so daß obige Addition korrekt ist. Es dürfen keine Ziffern doppelt zugeordnet werden. Die höchstwertige Ziffer jeder Zahl muß ungleich Null sein. Wieviel Geld benötigt der Student also von seinem Vater?

Der erste und vielleicht schwerste Schritt bei der Lösung des Problems ist die geeignete Formulierung. Die gegebene Darstellung stellt eine Gleichung in acht Variablen dar. Statt dessen teilt man nun die Gleichung entsprechend der Spalten und erhält somit fünf Gleichungen. Eine mögliche Formulierung der Constraints wäre eine Mischung aus Funktionen und Prädikaten, z.B. für die letzte Spalte ,,wenn $(D+E<10)$ dann $(D+E=Y)$, sonst $(D+E=10+Y)$''. Diese Formulierung ist aber sehr umständlich, da für die folgenden Spalten immer mehr Fallunterscheidungen nötig werden. Eine weitaus bessere Beschreibung zeigen die Gleichungen (3.6) bis (3.10) , bei der die Überträge der Gleichung als neue Variablen $U_1,\ldots ,U_4$ dargestellt werden. Da die führenden Stellen ($M,S$) ungleich Null sein müssen, ergeben sich die unten gezeigten Wertebereiche.


$\textstyle C_1:$ $\displaystyle D+E=Y+10*U_1$ (3.6)
$\textstyle C_2:$ $\displaystyle N+R+U_1=E+10*U_2$ (3.7)
$\textstyle C_3:$ $\displaystyle E+O+U_2=N+10*U_3$ (3.8)
$\textstyle C_4:$ $\displaystyle S+M+U_3=O+10*U_4$ (3.9)
$\textstyle C_5:$ $\displaystyle M=U_4$ (3.10)

$\displaystyle D,E,N,O,R,Y \in \{0,1,2,3,4,5,6,7,8,9\}$
$\displaystyle M,S, \in \{1,2,3,4,5,6,7,8,9\}$
$\displaystyle U_1,U_2,U_3,U_4 \in \{0,1\}$

Aus $C_5$ folgt, daß $M$ und $U_4$ die selbe Zahl darstellen, und ist deshalb durch die Schnittmenge der beiden Wertebereiche mit $M=1$ eindeutig bestimmt. Dadurch kann die Ziffer 1 aus der Wertebereichen der einzelnen Variablen gestrichen werden, nicht aber aus dem Wertebereichen der Überträge. In der weiteren Folge wird nicht mehr angegeben, daß eine eindeutig zugeordnete Zahl aus den Wertebereichen gestrichen wird. Constraint $C_4$ reduziert sich nun auf $S+U_3=O+9$. Damit können keine weiteren Werte eindeutig bestimmt werden. Es wird also eine Annahme nötig, die auf ihre Richtigkeit überprüft wird. Da $U_3$ die kleinste Wertemenge besitzt, wird eine Annahme für diese Variable getroffen.

Annahme: $U_3=1$. $C_4$ vereinfacht sich zu $S=O+8$. Daraus ergibt sich, daß $S\in \{8,9\}$ ist und $O=0$, da wegen $M=1$ die Ziffer aus dem Wertebereich gestrichen wurde. Damit vereinfacht sich $C_3$ zu $E+U_2=N+10$, was für keine gültige Wertebelegung erfüllte sein kann, da $E<10$ sein muß. Die Annahme $U_3=1$ war also falsch, und muß ebenso wie alle daraus abgeleiteten Variablen zurückgesetzt werden.

Damit folgt die neue Annahme $U_3=0$. $C_4$ vereinfacht sich zu $S=O+9$ und ist nur mit $S=9$ und $O=0$ erfüllbar. Für $C_3$ ergibt sich nun $E+U_2=N$. Die Annahme $U_2=0$ führt zum Widerspruch $E=N$, also muß $U_2=1$ sein. Daraus folgt $E+1=N$. Direkt läßt sich mit $C_3$ keine weitere Variable bestimmen. Daher ersetzt man in $C_2$ $N$ durch $E+1$. Diesen Schritt macht das symbolische Propagieren möglich. Für $C_2$ ergibt sich $R+U_1=9$. Da die Ziffer 9 nicht mehr im Wertebereich der Variablen $R$ ist, folgt $R=8$ und $U_1=1$. Für $C_1$ gilt nun $D+E=Y+10$. Da jede der Variablen $D$, $E$, $N$, $Y$ noch sechs Werte annehmen kann, scheint eine Fallunterscheidung wenig sinnvoll. Auch hilft uns das symbolische propagieren nicht weiter. Dagegen hilft die Propagierung der Wertemengen. Die aktuellen Wertemengen sind $D$, $E$, $N$, $Y\in\{2,3,4,5,6,7\}$. Durch die Gleichung $E+1=N$ folgt, daß für $N$ der Wert 2 und für $E$ der Wert 7 herausfällt. Aus $D+E=Y+10$ folgt die Ungleichung $D+E>11$. Dadurch werden die Wertemengen weiter eingeschränkt: $E\in\{5,6\}$ und $D\in\{6,7\}$. Da für $E$ nur mehr zwei Werte zur Verfügung stehen, kann wieder eine Annahme getroffen werden. Aus $E=6$ folgt $D=7$ und $N=7$ und stellt einen Widerspruch dar. Daher muß $E=5$ sein. Damit ergeben sich für die restlichen Variablen die Werte: $N=6$, $D=7$ und $Y=2$. Die eindeutige Lösung des Problems ist in Abbildung 3.8 dargestellt.

\begin{figure} % latex2html id marker 1184\begin{tt} \begin{center} \begin{... ...oney''.] {Eindeutige L\uml osung des Problems ,,Send More Money''.}\end{figure}

Komplexität von Constraintsystemen

Die im Beispiel angegebene Lösung kann nur von einem sehr leistungsfähigen Constraintsystem gefunden werden. Entsprechend der Fähigkeiten des Constraint-Propagierungs-Algorithmus lassen sich die Constraint-Systeme wie folgt einteilen [Puppe1991]:

* Einfache Constraintsysteme, die nur feste Werte propagieren können; diese würden für obiges Beispiel keine Lösung finden, da nach dem ersten Schritt für jede Variable mehr als ein Wert in Frage kommt.
* Ein weitgehend einfaches Constraintsystem, das zusätzlich auch Fallunterscheidungen beherrscht, würde erst nach sehr viel willkürlichem raten eine Lösung finden. Wäre die Wertemenge der Variablen unendlich, z.B. die reellen Zahlen, wäre die Fallunterscheidung prinzipiell unmöglich.
* Ein Constraintsystem, das auch in der Lage ist Wertemengen zu propagieren, würde den Suchraum weitgehend einschränken, müßte jedoch auch noch viel raten.
* Bei komplexen Problemen erweist sich die symbolische Propagierung als leistungsstarke Technik. Sie ist jedoch sehr aufwendig zu implementieren, da es vom System algebraische Umformungen verlangt.
* Wenn ein System über alle oben angeführten Techniken verfügt, benötigt es noch gute Heuristiken, um zu entscheiden, wann welche Technik angewandt werden soll. So eignet sich z.B. eine Fallunterscheidung nur, wenn der Wertebereich der Variable möglichst kein ist und sich die einzelnen Fälle nicht weiter verzweigen.

Aus den oben angeführten Punkten ist ersichtlich, daß die Komplexität des Propagierungs-Algorithmus das Aufgabengebiet bestimmt, in dem das Constraint-System sinnvoll eingesetzt werden kann.


1.8 Unsicheres Wissen

In den bisher besprochenen Repräsentationen wurde Wissen immer in Form von eindeutigen Fakten, Regeln, Bedingungen oder Abbildungen gespeichert. Oft ist es jedoch nicht möglich, eindeutige Aussagen über die reale Welt zu treffen oder einen strikten Zusammenhang zwischen Bedingung und Schlußfolgerung herzustellen. Vielmehr können Aussagen und Schlußfolgerungen nur mit einer bestimmten Unsicherheit getroffen werden. Eine Möglichkeit diese Unsicherheit darzustellen ist, anzugeben mit welcher Wahrscheinlichkeit die Aussagen und Schlußfolgerungen zutreffen. Quellen für die Unsicherheit von Information können sein [Gottlob1990]:

Inhärente Unsicherheit der Information,
z.B. die Information eines Temperatursensors mit der Toleranz von $\pm1^\circ$C.
Unvollständigkeit der Information
, es werden z.B. fehlende Informationen durch Annahmen ersetzt, sind alle Schlußfolgerungen, die auf dieser Annahme basieren, unsicher.
Unsicherheit von Schlußfolgerungen:
Es kann kein strikter Zusammenhang zwischen Bedingung und Schlußfolgerung hergestellt werden, z.B. ,,Wenn der Patient mehr als $38^\circ$C Fieber hat, dann ist er mit der Wahrscheinlichkeit von 0,7 an Grippe erkrankt.''
Zusammenfassung von Informationen aus mehreren Quellen,
widersprechen sich z.B. die Aussagen von zwei Experten, so erhöht dies die Unsicherheit dieser Aussagen.

Unsicherheiten können nummerisch oder symbolisch dargestellt werden. Bei der symbolischen Repräsentation wird der Grad der Unsicherheit durch Elemente aus einer vorgegebenen Menge von Symbolen ausgedrückt, z.B. durch Begriffe wie ,,meistens'', ,,beinahe'', ,,immer'', usw. Bei dieser Methode ist es aber schwierig die Fortpflanzung der Unsicherheit beim Schlußfolgern zu berücksichtigen.

Bei der nummerischen Repräsentation wird die Unsicherheit durch die Zuordnung von einem oder mehreren Zahlenwerten, z.B. der Wahrscheinlichkeit, ausgedrückt. Für die Darstellung der Fortpflanzung der Unsicherheit gibt es mathematische Formalismen. Jedoch ist es oft nicht möglich, einer Aussage oder Schlußfolgerung einen exakten Wahrscheinlichkeitswert zuzuordnen. Im nachfolgenden werden drei Verfahren zur nummerischen Repräsentation von Unsicherheit vorgestellt.

Theorem von Bayes

In der klassischen Wahrscheinlichkeitsrechnung ist die Wahrscheinlichkeit als
\begin{displaymath} p(X)=\frac{\mbox{Anzahl der günstigen Ereignisse}}{\mbox{Anzahl der möglichen Ereignisse}} \end{displaymath} (3.11)

definiert. Diese Definition erweist sich für die Darstellung von Unsicherheiten als nicht geeignet. Daher wird die Wahrscheinlichkeit als der Grad des Vertrauens einer Person in eine Hypothese definiert. Eine Hypothese bezeichnet eine Annahme über einen Sachverhalt. Die Wahrscheinlichkeiten sind Werte im Intervall [0,1]. Folgende Schreibweisen werden im weiteren verwendet [Gottlob1990]:














$p(X)$ ... Wahrscheinlichkeit, daß X wahr ist
$p(X_1,X_2,...,X_n)$ ... Wahrscheinlichkeit, daß $X_1,X_2,...,X_n$ alle wahr sind
$p(X_1,X_2,...,X_n\vert Y_1,Y_2,...Y_n)$ ... Wahrscheinlichkeit, daß $X_1,X_2,...,X_n$ alle wahr sind, unter der Voraussetzung, daß $Y_1,Y_2,...,Y_n$ wahr sind (bedingte Wahrscheinlichkeit)
<>

Allgemeines Theorem von Bayes

Gegeben sei eine Menge von Hypothesen $H=\{h_1,h_2,...,h_n\}$ und eine Menge von Ereignissen $E=\{e_1,e_2,...,e_m\}$. Das allgemeine Bayes'sche Theorem baut auf folgenden Voraussetzungen auf [Gottlob1990]:














Die Hypothesen in der Menge H schließen sich gegenseitig aus:

\begin{displaymath}p(h_i,h_j)=0 \mbox{ für } i\neq j \end{displaymath}

Die Menge H ist erschöpfend:
\begin{displaymath}\sum_{i=1}^{n}p(h_i)=1 \end{displaymath} (3.12)

Jedes Teilergebnis $e_i$ ist bedingt unabhängig von jeder Hypothese:
\begin{displaymath} p(e_1,e_2,...,e_m\vert h_i)=\prod^m_{j=1} p(e_j\vert h_i) \end{displaymath} (3.13)

Das allgemeine Bayes'sche Theorem besagt, daß die a-posteriori Wahrscheinlichkeit $p(h_i\vert e_1,e_2,...,e_m)$ einer Hypothese $h_i$ als Funktion der bedingten Wahrscheinlichkeiten $p(e_1,e_2,...,e_m\vert h_i)$ sowie der a-priori Wahrscheinlichkeiten $p(h_i)$ berechnet werden kann [Gottlob1990]:


\begin{displaymath} p(h_i\vert e_1,e_2,...,e_m)=\frac{p(e_1,e_2,...,e_m \vert ... ..._i)}{\sum\limits_{k=1}^{n}p(e_1,e_2,...,e_m \vert h_k)p(h_k)} \end{displaymath} (3.14)

Der Spezialfall für ein Ereignis $E$ und eine Hypothese $H$ sieht folgendermaßen aus:


\begin{displaymath}p(H\vert E)=\frac{p(E\vert H)p(H)}{p(E)} \end{displaymath} (3.15)

Die Anwendung des Satzes soll nun durch ein Beispiel veranschaulicht werden. Im Beispiel tritt das Ereignis $E$ ,,Die Reifen eines Autos quietschen.'' mit der Wahrscheinlichkeit $p(E)=0,05$ auf; die Hypothese $H$ ,,Die Bremsen des Autos sind schlecht eingestellt.'' mit der Wahrscheinlichkeit $p(H)=0.02$.

Nehmen wir weiters an, daß schlecht eingestellte Bremsen oft, aber nicht immer, ein Quietschen der Räder verursachen. Die bedingte Wahrscheinlichkeit dafür ist $p(E\vert H)=0,7$. Wenn man nun ein Quietschen der Reifen beobachtet, so kann man mit Hilfe des Bayes'schen Theorem die Wahrscheinlichkeit berechnen, daß die Bremsen schlecht eingestellt sind.


\begin{displaymath}p(H\vert E)=\frac{0,7*0,02}{0,05}=0,28\end{displaymath}

Durch die Beobachtung des Ereignisses $E$ hat sich die Wahrscheinlichkeit der Hypothese $H$ von 0,02 auf 0,28 erhöht. Die Berechnung von $p(H\vert E)$ ausgehend von $p(H)$ kann als Neubewertung der Hypothese $H$ beim Eintreten des Ereignisses $E$ aufgefaßt werden. Darin liegt die Stärke dieses Theorems. Mit ihm läßt sich die Fortpflanzung der Unsicherheit berechnen. Der Nachteil ist jedoch, daß zu jedem Ereignis und zu jeder Hypothese die Wahrscheinlichkeit und die entsprechenden bedingten Wahrscheinlichkeiten gespeichert werden müssen. Dies erfordert eine große Datenmenge, die schwer zu beschaffen ist und auch oft nicht mit mathematischer Exaktheit beschafft werden kann. [Gottlob1990]


Certainty Factors

In der Praxis werden daher aus oben genannten Gründen Unsicherheiten anstelle von Wahrscheinlichkeiten durch sogenannte Certainty Factors ausgedrückt. Jeder Regel wird ein fester Certainty Factor zugeordnet. Den Fakten, die eine Regel erfüllen muß, sind dynamische Certainty Faktoren zugeordnet. Bei der Abarbeitung einer Regel wird aus den festen und dynamischen Faktoren der Certainty Factor der Schlußfolgerung berechnet. Somit erhält man neue, bewertete Fakten. Der Vorteil der Certainty Factors liegt darin, daß für jede Regel und für jedes Faktum nur ein Wert gespeichert werden muß. Es werden keine bedingten Wahrscheinlichkeiten gespeichert. Daher sind sie einfacher zu handhaben und leichter zu implementieren. Die Implementierung von Certainty Factors wird im Abschnitt 6.8 anhand von Expertensystemen genauer ausgeführt. [Gottlob1990]

Fuzzy Logik

Der Grundgedanke der Fuzzy Logik ist es, eine Theorie der unscharfen Mengen zu entwickeln. Durch die unmittelbare Verknüpfung zwischen Mengenlehre und Logik ist damit auch die Theorie der unscharfen Logik verknüpft. An dieser Stelle soll nur erwähnt werden, wie in der Fuzzy Logik unsicheres Wissen gespeichert wird. Näher wird auf dieses Thema in Kapitel 7 eingegengen. [Rojas1993]

In der klassischen Mengenlehre gilt für ein Objekt, daß es entweder Element oder kein Element der Menge ist. In der Fuzzy Logik besitzt eine Menge keine so scharfen Grenzen. Damit ist es möglich, daß ein Element nur ,,zu einem bestimmten Grad'' einer Menge angehört. Der Grad der Zugehörigkeit wird durch einen Wert aus dem Intervall [0,1] angegeben. Dieses Konzept erweist sich als vorteilhaft, wenn man Zuordnungen aus dem natürlichen Sprachgebrauch darstellen will.

Ein Beispiel dafür ist die Aussage: ,,Die Person X ist groß.''. Befragt man mehrere Personen wo für sie die Grenze liegt, ab wann eine Person als groß gilt, so wird man keinen eindeutigen Grenzwert erhalten. Für manche beginnt groß schon bei 1,75m, für andere erst bei 1,85m. In der Fuzzy Logik kann diese unscharfe Grenze mit der Mitgleidsgradfunktion ausgedrückt werden. Abbildung 3.9 zeigt einen solchen Verlauf für die Zugehörigkeit zur Menge der großen Personen. Die Mitgliedsgradfunktion ordnet z.B. eine Person die 1,85m groß ist, mit dem Grad 0,8 zur Menge der großen Personen zu.

Abbildung: Beispiel für die Definition einer Fuzzy Menge. Gezeigt wird die Zuordnung zur Menge der großen Personen mit Hilfe der Mitgliedsgradfunktion.
\includegraphics{bilder/ki/koerpergroesse.eps}
Gerald Reif
2000-02-01

TU Graz

[Max]

Danke, Klaus, für diesen hochinteressanten Text.

[Martin]

Hallo

danke für den sehr ausfühlichen Bericht. Ich komme aus der kommerziellen Informatik und beschäftige mich mit Repositories und Softwarentwicklungsmethoden.
Meines Wissens ist aber die Bedeutung von KI heute nicht mehr so groß, wie sie es mal war.
Ich kann mich nur erinnern an ein System Mycel (oder so ähnlich) welches in der Medizin benutzt werden sollte um damit Pilzerkrankungen zu bestimmen.
Das Problem, was die Expertensystem hatten waren immer die Randbereiche, also dann, wenn sie eigentlich "sagen" müßten, hier bin ich nicht zuständig. Hatte sich jemand ein Bein gebrochen, so versuchte das Programm diese Krankheit immer durch Pilze zu erklären, was natürlich Unsinn ist.
Ich habe lange nichts mehr von diesen System gehört, kannst du etwas sagen über kommerzielle Programm und ob sie heute im Einsatz sind und wo ?

Würde mich interessieren.

Thanx

Martin

[Klaus]

Die KI wie sie mal vor Jahren diskutiert wurde gibt es heute nicht mehr. Es wird da zwischen weicher(soft) KI und harter KI unterschieden. Die harte KI ist meiner Überzeugung nach eine Aufgabe der kommenden Quantencomputer, echte parallele, drei-dimensionale Informationsverarbeitung. Das ist meine persönliche Meinung, hinzu kommt noch die Entwicklung wie sie Moore vorhergesagt hat, also über die Speicherdichte, nach Ray Kurzweil und Elizer Yudkowski dürfte die Transistordichte in 15-20 Jahren erreicht sein, um die Kapazitäten des menschlichen Gehirns zu erreichen.
technische Singularität

Die softe KI findet sich heute in einer Fülle von Problemlösungen wieder, ich denke hier nur an Thinking Machines, rechnergestützte Informationssysteme, Spieletheorie, Chaostheorie und Entropieforschung.

In der Medizin hatte ich mal mit der Mumps Software zu tun, die ähnliches geleistet hat, ist weiterentwickelt worden und die Namen haben sich zigfach geändert.
Ne Aufstellung darüber kann ich dir als PN schicken. :D

bei TED oder auf meinem Blog ist ein Videovortag von Kurzweil über die technische Singularität, anschaubar.

[Martin]

Hi.

spannendes Thema. Habe mal etwa in Wiki gestöbert, komme aber doch bald an meine Grenzen.
Trotzdem danke für die Denkanstöse, wenn ich nicht mehr weiter weiß, melde ich mich.

Martin