Doris AltenkrUger Winfried Buttner Wissensbasierte Systeme Artificial Intelligence Kiinstliche Intelligenz herausgegeben von Wolfgang Bibel und Walther von Hahn Kunstliche Intelligenz steht bier fUr das Bernuhen urn ein VerstAndnis und urn die technische Realisierung intelligenten Verhaltens. Die Bucher dieser Reihe sollen Wissen aus den Gebieten der Wissensverarbeitung, Wissensreprasentation, Expertensysterne, Wissenskornrnunikation (Sprache, Bild, Klang, etc.), Spezialrnascbinen und -sprachen sowie Modelle biologischer Systerne und kognitive Modellierung vermitteln. Bisher sind erschienen: Automated Theorem Proving von Wolfgang Bibel Die Wissensreprasentationssprache OPS 5 von Reinhard Krickhahn und Bernd Radig LISP von Rudiger Esser und Elisabeth Feldrnar Logische Grundlagen der Kiinstlichen Intelligenz von Michael R. Genesereth und Nils J. Nilsson Wissensbasierte Echtzeitplanung von Jurgen Dom Modulare Regelprogrammierung von Siegfried Bocionek Automatisierung von Terminierungsbeweisen von Christoph Walther Logische und Funktionale Programmierung von Ulrich Furbach Parallelism in Logic von Franz KurfeB Relative Complexities of First Order Calculi von Elrnar Eder Schlie6en bei unsicherem Wissen in der Kiinstlichen Intelligenz von der Gruppe Lea Sornbe Doris Altenktiiger Winfried Buttner Wissens basierte Systeme Architektur, Entwicklung, Echtzeitanwendungen - Eine praxisgerechte Einfiihrung I I Vleweg Die Deutsche Bibliothek -CIP-Einheitsaufuahme Altenkriiger, Doris: Wissensbasierte Systeme : Architektur, Entwicklung, Echtzeitanwendungen ; eine praxisgerechte Einfiihrung / Doris AItenkriiger; Winfried Buttner. -Braunschweig; Wiesbaden: Vieweg,1992 (KUnstliche Intelligenz) ISBN-13: 978-3-528-05244-7 e-ISBN-13: 978-3-322-86811-4 DOl: 10.1007/978-3-322-86811-4 NE: Buttner, Winfried: AIle Rechte vorbehalten • © Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, BraunschweigIWiesbaden, 1992 Der Verlag Vieweg ist ein Unternehmen der Verlagsgruppe Bertelsmann International. Das Werk einschlieBlich aller seiner Teile ist urheberrechtlich geschutzt. Jede Verwertung auBerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmungen des Verlags unzulassig und strafbar. Das gilt insbesondere fur VervielfaItigungen, Ubersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Gedruckt auf saurefreiem Papier ISSN 0940-0699 ISBN-13: 978-3-528-05244-7 Inhaltsverzeichnis v Inhaltsverzeichnis 1 Wissensbasierte Systeme 1 1.1 Von Datenverarbeitung zu Wissensverarbeitung 1 1. 2 Struktur Wissensbasierter Systeme 3 1.3 Perspektive Wissensbasierter Systeme 5 2 Wissensbasis: Reprasentation von Wissen 6 2.1 Prozedurale Wissensreprasentation 18 2.1.1 Produktionsregeln 21 2.1.2 Scripts 27 2.2 Logische Wissensreprasentation 30 2.2.1 Aussagenlogik 30 2.2.2 Pradikatenlogik 35 2.3 Objektorientierte Wissensreprasentation 43 2.3.1 Semantische Netze 48 2.3.2 Partitionierte Semantische Netze 53 2.3.3 Conceptual Dependency Graphs 56 2.3.4 Frames 59 2.4 Reprasentation vagen Wissens 67 2.4.1 Nichtmonotone Logik 70 2.4.2 Unscharfe Logik 75 2.5 Reprasentation unsicheren Wissens 82 2.5.1 Bayes'sche Wahrscheinlichkeitstheorie 82 2.5.2 Sicherheitsfaktoren 84 2.5.3 Dempster-Shafer-Theorie 86 2.5.4 INFERNO 89 2.5.5 Endorsements 91 2.6 Reprasentation zeitlichen Wissens 94 VI Inhaltsverzeichnis 3 Inferenzmaschine: Verarbeitung von Wissen 98 3.1 Pridikatenlogische Inferenzmechanismen 98 3.1.1 Unifikation 101 3.1.2 Resolution 103 3.2 Methoden zur Ablaufsteuerung 109 3.2.1 Blackboard 109 3.2.2 Vorwiirts- und Riickwiirtsverkettung 110 3.2.3 Mustergesteuerter Ablauf 114 3.2.4 Aktive Werte 117 3.2.5 Evidenzwerte 117 3.3 Suchstrategien 119 3.3.1 Unwiderrufliche Suchstrategien 121 3.3.2 Riicksetzen 123 3.3.3 Graphen-Suchstrategien 126 3.3.4 Tiefen- und Breitensuche 129 3.3.5 Heuristische Suchstrategien 131 3.3.6 Bidirektionale Suche 134 3.3.7 Weitere Suchstrategien 135 3.4 Schluf3folgerungsverfahren 136 3.4.1 Monotones und Nichtmonotones SchluBfolgern 136 3.4.2 Vererbung 136 3.4.3 Deduktion, Induktion, Abduktion 136 3.4.4 Weitere SchluBfolgerungsverfahren 139 Inhaltsverzeichnis VII 4 Entwicklungswerkzeuge 140 4.1 NEXPERT OBJECT 140 4.1.1 Objekte und Klassen 141 4.1.2 Regeln 145 4.1.3 Inferenzmaschine 147 4.1.4 Mustererkennung 149 4.1.5 Interpretationen 150 4.1.6 Links 151 4.1.7 Editoren 152 4.1.8 Browser 154 4.2 Personal Consultant Plus 155 4.2.1 Frames 155 4.2.2 Parameter 157 4.2.3 Regeln 158 4.2.4 Vererbung 159 4.2.5 Systemfunktionen 159 4.2.6 Vages Wissen 160 4.2.7 Verkettung 164 4.2.8 Meta-Ebene 165 5 Anwender-Schnittstelle 166 5.1 Dialogkomponente 171 5.1.1 Anwenderfreundlichkeit 172 5.1.2 Hilfesysteme 180 5.1.3 Anwendermodellierung 194 5.1.4 Anwenderkonventionen 200 5.1.5 Anwenderkompetenz 201 5.1.6 Anwenderintentionen 205 5.2 Erklarungskomponente 217 VIII Inhaltsverzeichnis 6 Wissensakquisition 220 6.1 Grundmodelle 221 6.1.1 Indirekte Wissensakquisition 221 6.1.2 Direkte Wissensakquisition 222 6.1.3 Automatische Wissensakquisition 223 6.2 Phasen 225 6.2.1 Identifikation 226 6.2.2 KonzeptionaIisierung 226 6.2.3 F ormaIisierung 227 6.2.4 Interpretationsmodell 228 6.3 Techniken 229 6.3.1 Brainstorming 230 6.3.2 Intensiv-Interview 230 6.3.3 Konstruktgitter-Verfahren 230 6.3.4 Strukturiertes Interview 231 6.3.5 SkaIierung 231 6.3.6 Gruppendiskussion 231 6.3.7 Review 232 6.3.8 Protokollanalyse 232 6.3.9 Vorwarts-/Riickwartssimulation 232 7 Echtzeit-Anwendungen 233 7.1 Definierte Antwortzeiten 237 7.1.1 Kopplung Expertensystem-ProzeBrechner 239 7.1.2 Approximatives SchlieBen 241 7.1.3 Behandlung von Zeitvorgaben 246 7.2 Leistungssteigerung 247 7.2.1 Parallelisierung auf Programmiersprachen-Ebene 250 7.2.2 Ansatzpunkte zur Parallelisierung von LISP 253 7.2.3 Multi LISP 256 7.2.4 Geschwindigkeitszuwachs durch Parallelisierung 259 Literaturverzeichnis 261 Sachwortverzeichnis 272 1 Wissensbasierte Systeme 1 1 Wissensbasierte Systeme Wissensbasierte Systeme bilden ein Teilgebiet der Kiinstlichen Intelligenz (KI) und umfassen schwerpunktmaBig Expertensysteme, aber z.B. auch Natiirlichsprachliche und Bildverstehende Systeme. Wissensbasierte Systeme verfiigen iiber komplexe Formalismen zur Reprasentation und umfangreiche Techniken zur Verarbeitung von Wissen. 1.1 Von Datenverarbeitung zu Wissensverarbeitung Systeme der klassischen Datenverarbeitung (DV) bestehen vorrangig aus prozeduralen Programmen und numerischen Daten. In der Wissensverarbeitung herrschen dagegen deklarative Beschreibungen und symbolische Daten vor. Die Daten herkommlicher DV- Systeme sind in starren Strukturen abgelegt und ihre Verarbeitung erfolgt nach einem fest vorgegebenen Ablauf, d.h. schematischen Berechnungsverfahren, den sog. Algorithmen. Der Software-Entwickler eines DV-Programms hat seine Kenntnisse iiber DV-Prozesse, die eigentliche Aufgabe und die von spateren Nutzern geforderten Randbedingungen mit diesen Algorithmen implementiert. Der Vorteil der festen Strukturen ist ein schneller VerarbeitungsprozeB der Daten, auf die diese Strukturen angewandt werden. Diese Art der Programmierung ist jedoch sehr aufwendig und fiihrt zu starren Verarbeitungsstrukturen. Der Wunsch nach einer Abbildung des Wissens in flexibleren Strukturen, die sich der jeweiligen Situation anpassen, ist naheliegend. Die Integration von Wissen bei der DV-Programmentwicklung ist ein seit langem von Software-Entwicklern betriebenes Handwerk. Diesen manuellen ProzeB weitgehend zu automatisieren ist eine wichtige Aufgabe der Wissensverarbeitung. Eine Unterstiitzung der Software-Entwicklung durch CASE-Werkzeuge (Computer Aided Software Engineering Tools) ist heute Stand der Technik. Eine noch starkere VerIagerung des Software-Entwicklungsprozesses auf die Maschine wird kiinftig Gegenstand der Wissensverarbeitung sein. 2 1 Wissensbasierte Systeme Wissen (Fakten & Regeln) Abb. 1.1 Datenverarbeitung versus Wissensverarbeitung In der klassischen DV-Welt wird zwischen Daten und Programm klar getrennt. Sowohl die Programmentwicklung als auch die Erstellung problemadaquater Daten ist Aufgabe des Software-Entwicklers. In der KI-Welt gibt es diese Unterscheidung nicht: Fur den Wissensingenieur liegt bei der Entwicklung Wissensbasierter Systeme der Schwerpunkt auf der Umsetzung des anwendungsspezifischen Wissens in eine geeignete Reprasentationsform, meist bestehend aus Fakten und Regeln. Die eigentliche Verarbeitung und Anwendung des Wissens obliegt der Inferenzmaschine und ist damit bereits vorgegeben. Der Wissensingenieur hat dabei lediglich die Aufgabe, ein Entwicklungswerkzeug auszuwahlen, das sowohl bzgl. des Reprasentationsformalismus als auch bzgl. der Inferenzmaschine der Anwendung gerecht wird.