Vorlesung Wissensbasierte Systeme - web.fhnw.ch fileFHNW Vorlesung Wissensbasierte Systeme Dr. T. Nouri kbs-deutsch99.doc KI-Wissenbasierte systeme 18.5.2004FH-NW/So 2/31 Inhaltsverzeichnis

FHNW Vorlesung Wissensbasierte Systeme

Dr. T. Nouri kbs-deutsch99.doc KI-Wissenbasierte systeme 18.5.2004FH-NW/So 1/31

Vorlesung Wissensbasierte Systeme

Eine Übersicht

FHNW-SO



Inhaltsverzeichnis 1 Einführung ............................................................................................................ 4

1.1 Definition und Motivation...................................................................................... 4

1.2 Charakterisierung von Wissensbasiertes Systems ...................................................... 5

1.3 Geschichte........................................................................................................ 5

1.4 Problemlösungstypen von Wissensbasiertes Systems ................................................. 7

1.5 Architektur von Wissensbasiertes Systems .............................................................. 8

1.6 Begriffe ............................................................................................................ 9

1.6.1 Knowledge ................................................................................................... 9

1.6.2 Heuristics .................................................................................................. 10

1.6.3 Facts........................................................................................................ 10

1.6.4 Inference Procedures (Schlussfolgerungsmechanismen) ...................................... 11

2 Wissensrepräsentation und Ableitungsstrategien................................................... 12

2.1 Anforderungen an die Wissensrepräsentation ......................................................... 12

2.2 Methoden zur Wissenspräsentation ...................................................................... 12

2.2.1 Logikorientierte Methode .............................................................................. 12

2.2.2 Prozedurale Methoden.................................................................................. 14

2.2.3 Objektorientierte Methoden........................................................................... 14

2.3 Regeln............................................................................................................ 16

2.3.1 Überblick................................................................................................... 16

2.3.2 Vorwärtsverkettung (forward reasoning oder forward chaining) ............................ 17

2.3.3 Rückwärtsverkettung (backward reasoning oder backward chaining) ..................... 17

2.3.4 Tiefensuche und Breitensuche ....................................................................... 18

2.3.5 Certainty Factors ........................................................................................ 19

2.4 Vergleich konventionelle Programme — Expertensysteme ......................................... 19

3 Entwicklung von Wissensbasiertes Systems .......................................................... 20

3.1 Entwicklungsphasen .......................................................................................... 20

3.2 Rapid Prototyping — modellbasierte Wissensaquisition.............................................. 21

3.2.1 Rapid Prototyping........................................................................................ 21

3.2.2 Modellbasierte Wissensaquisition .................................................................... 23



4 Wissenserwerb ................................................................................................... 24

4.1 Aufgaben der Wissensakquisition ......................................................................... 24

4.2 Arten des Wissenserwerbs.................................................................................. 24

4.3 Erhebung von Expertenwissen ............................................................................. 25

5 Anhang............................................................................................................... 27

5.1 Expertensystemwerkzeuge ................................................................................. 27

5.1.1 ART .......................................................................................................... 27

5.1.2 KEE .......................................................................................................... 27

5.1.3 BABYLON................................................................................................... 28

5.1.4 Knowledge Craft ......................................................................................... 28

5.1.5 Twaice...................................................................................................... 28

5.1.6 D3............................................................................................................ 28

5.2 Nexpert Object ................................................................................................ 29

5.2.1 Allgemeines................................................................................................ 29

5.2.2 Wissensrepräsentation ................................................................................. 29

5.2.3 Agenda ..................................................................................................... 30

5.3 Literaturverzeichnis........................................................................................... 31



1 Einführung

1.1 Definition und Motivation

Die Entwicklung von Wissensbasiertes Systems begann vor rund 25 Jahren. Die Expertensysteme waren von Anfang an stark auf die Lösung praktischer Aufgaben ausgerichtet.

Versuch einer Definition: Expertensysteme versuchen, Gedankengänge und Erfahrungen von Experten bestimmter Fachgebiete auf eine Menge von formalisierten, maschinenverarbeitbaren Operationen abzubilden, um Aspekte einer Problemlösungskompetenz zu reproduzieren und Anwendern zur Verfügung zu stellen.

Um ein Expertensystem zu bauen, muss das Expertenwissen formalisiert, im Rechner repräsentiert und gemäss einer Problemlösungsstrategie manipuliert werden.

Mit Expertenwissen ist Wissen gemeint, das eine Fachperson in ihrem jeweiligen Gebiet durch langjährige Erfahrung sammelt. Es ist kein allgemeines Weltwissen. Es ist auch nicht in erster Linie in Büchern kodiertes Fachwissen. Es ist Erfahrungswissen, das normalerweise nicht schriftlich fixiert ist, sondern nur in den Köpfen der Fachleute existiert.

Allgemeines Weltwissen oder Hintergrundwissen lässt sich sehr viel schwerer darstellen und verarbeiten (grosse Menge). Von der Formalisierung des Expertenwissens verspricht man sich:

• die Explizierung und Überprüfbarkeit von Fachwissen

• die Unterstützung und Ergänzung menschlicher Fachtätigkeit

• die Begünstigung einer Wissensevolution

• Vorteile bei der fachlichen Ausbildung

• die Möglichkeit einer Konservierung von Fachwissen

• technische Hilfsmittel für die Wissensverarbeitung und -nutzung

Eine schwierige Aufgabe ist die Modellierung von Wissen, welches Experten benutzen. Diese Schwierigkeiten werden bei der Entwicklung von Wissensbasiertes Systems häufig grob unterschätzt.



1.2 Charakterisierung von Wissensbasiertes Systems

• Simulation menschlicher Experten

• Trennung zwischen Expertenwissen und Problemlösungsstrategien

Daten

Algorithmen

Daten

Problemlösungs-strategien

Wissen

konventionelle Programme Expertensysteme

Abbildung 1: Vergleich von konventioneller Programmierung und Wissensbasiertes Systems

• Eignung für "diffuse" Bereiche

• selbständige Wissensinterpretation

• notwendige Eigenschaften:

− Transparenz

− Flexibilität

− Benutzerfreundlichkeit

− Kompetenz

1.3 Geschichte

60er Jahre:

Entwicklung von universellen Problemlösern

70er Jahre:

Wechsel von einer rechenintensiven Strategie zu einem wissensbasierten Ansatz



Erste Expertensysteme:

• DENDRAL

− Strukturanalyse organischer-chemischer Substanzen

− Erweiterungen: Congen, Meta-Dendral (Lernkomponente)

• MACSYMA

− Lösung mathematischer Probleme mit symbolischen Methoden

• MYCIN

− Diagnose und Therapie von bakteriellen Infektionskrankheiten des Blutes

− zu gegebenen Patientendaten fordert Mycin bei Bedarf Labortests und analysiert die Ergebnisse der Tests mit Hilfe von Regeln (Produktionssysteme)

− klare Trennung zwischen Wissensrepräsentation und Problemlösungsstrategie

− Erklärungskomponente

− Wissen vage und ungenau (Sicherheitsfaktoren)

− die Leistungsfähigkeit von Mycin war mit der von Experten auf diesem Gebiet vergleichbar, es war besser als Studenten und Allgemeinmediziner

− MYCIN kam nicht zum praktischen Einsatz

− aus Mycin entstand das Expertensystemshell Emycin

Weitere klassische Expertensysteme:

• CASNET

− Diagnose und Therapie einer Augenerkrankung

• INTERNIST

− Diagnose von ca. 75% der Krankheiten in der Inneren Medizin (grosse Wissensbasis)

• PROSPECTOR

− geologisches System zur Interpretation von Messdaten aus Probebohrungen (Finden bestimmter wertvoller Mineralien)

• XCON (R1)

− Konfiguration von VAX-Computern der Firma Digital Equipment



1.4 Problemlösungstypen von Wissensbasiertes Systems

Wir unterscheiden drei Haupttypen:

1. Klassifikation: (Auswahl, Selektion, Diagnose)

Die Lösung wird aus einer Menge vorgegebener Alternativen ausgewählt. Hierzu gehören auch:

• Interpretation: Ableitung von Objekt - oder Situationsbeschreibungen aus beobachtbaren Daten, z.B.: Sensordaten (Prospector)

• Diagnose: Ableitung von Systemfehlern (Krankheiten) aus Beobachtungen; Generierung von Vorschlägen zur Beseitigung der Fehlzustände

• Überwachung: (Steuerung) Vergleich von Beobachtungen mit Sollwerten; Gewährleistung der Einhaltung kritischer Systemparameter und Beseitigung der Abweichungen von vorgegebenen Normalzuständen

• Beratung: (Analyse) Analyse komplexen und umfangreichen Datenmaterials (Finanz- und Bankwesen); Auskunftserteilung bzw. Unterstützung bei der Anwendung komplexer Systeme oder Vorschriften

• Instruktion: (Training) Anleitung und Unterweisung auf einem bestimmten Spezialgebiet bzw. in der Bewältigung komplizierter Situationen

2. Konstruktion: Entwicklung von Strukturen, die bestimmte Funktionen realisiere Hierzu gehören:

• Konfigurierung: (Design) Zusammenfügen von Objekten unter Berücksichtigung besonderer Anforderungen

• Planung: Entwurf einer Folge von Aktionen zum Erreichen eines Zieles

3. Simulation: (Vorhersage) Aus dem Ausgangszustand werden Folgezustände hergeleitet. Es soll kein vorgegebenes Ziel erreicht werden, sondern nur die Auswirkungen von Handlungen oder Ereignissen simuliert werden.



1.5 Architektur von Wissensbasiertes Systems

Die Trennung zwischen dem Expertenwissen und den Problemlösungsstrategien führt zu den zwei Hauptmodulen (siehe Abb.: 2):

• Steuersystem (Shell, Kern)

• Wissensbasis

Steuersystem

• Problemlösungskomponente

• Benutzerschnittstelle:

− Interviewerkomponente

− Erklärungskomponente

− Wissenserwerbskomponente

Wissensbasis

• bereichsbezogenes Wissen: kommt vom Experten; besteht aus:

− Faktenwissen

− Ableitungswissen (Regeln)

− Kontrollwissen (Meta-Regeln)

• fallspezifisches Wissen: kommt vom Benutzer; Faktenwissen

• Zwischen- und Endergebnisse: kommt von der Problemlösungskomponente; Faktenwissen



Benutzer Experte

fallspezifischesWissen

bereichsbezogenesExpertenwissen

Zwischenergebnisseund Problemlösungen

Problemlösungskomponente

Interviewer-komponente

Erklärungs-komponente

Wissenserwerbs-komponente

Abbildung 2: Architektur eines Expertensystems

1.6 Begriffe

1.6.1 Knowledge

Was ist "Wissen"?

Wissen ist komplexer als Information, letztere ist komplexer als Daten. Den Weg von Daten zur Information beschreibt HARSH wie in Abbildung 3 dargestellt.

Data InformationProcessing

Abbildung 3: Transformation von Daten in Information

In analoger Weise kann das Entstehen von Wissen aus Informationen verstanden werden. Aus vielen Informationen, die mittels Assoziationen miteinander verknüpft sind, entsteht schliesslich Wissen.

Ein Beispiel soll diesen abstrakten Prozess verdeutlichen:

Aus vorliegenden Daten über landwirtschaftliche Betriebe können beispielsweise durch Berechnung von Kennzahlen, etwa Gewinn pro ha oder kg Milch pro Milchkuh und Laktation (Milchabsonderung), Informationen gewonnen werden. Ein landwirtschaftlicher Berater kann durch Sammeln (oder "sich merken") und Verknüpfen der Informationen nach einiger Zeit "Wissen" ableiten. Er weiss somit, dass z.B. eine Milchleistung von 9.000 kg pro Milchkuh und Laktation eine exzellente Leistung darstellt. Er weiss weiterhin, dass es zu einer solchen Milchleistung einer Reihe von begünstigenden Faktoren bedarf, etwa eines fähigen Melkers, ausgezeichneter Hygiene etc.



Das im Beispiel aus zusammengesetzten und assoziierten Informationen (Chunks) entstandene Wissen ist bereits verarbeitet und liegt für den Berater abrufbereit vor, d.h. es kann ohne weiteres zur Lösung von Problemen herangezogen werden. Man spricht hier von "compiled knowledge". Dieses Verarbeiten oder "Kompilieren" von Wissen ist der Prozess des "chunking".

Um kompiliertes Wissen tatsächlich nutzenbringend zur Problemlösung anwenden zu können, bedarf es freilich etwas mehr: nämlich Erfahrung. Kompiliertes, auf Erfahrungen beruhendes Wissen wird als "Heuristics" bezeichnet.

1.6.2 Heuristics

"Heuristics" sind Erfahrungswerte oder "rules of thumb", die den Suchraum für Problemlösungen auf ein überschaubares Mass beschneiden. Demzufolge können "heuristics" oder Daumenregeln zu fehlerhaften Ergebnissen führen, erhöhen aber hingegen die Wahrscheinlichkeit, das korrekte Ergebnis schneller zu finden.

Zusammen machen "heuristics" und "compiled knowledge" die Kompetenz eines Experten aus. Diese beiden Komponenten sind es auch, die in ein Expertensystem einfliessen. Da "heuristics" auch Entscheidungen unter unsicherer bzw. unvollständiger Information ermöglichen, gilt dies auch für Expertensysteme.

1.6.3 Facts

Die Fakten in einem Expertensystem repräsentieren die dem Modell enthaltenen Information.

Generell kann das, was als Intelligenz betrachtet wird (und das trifft auch für Expertensysteme zu) in zwei Komponenten geteilt

1. Eine Sammlung von Fakten

2. Ein Instrument, um diese Fakten für Problemlösungen nutzbar zu machen (weiter unten als Schlussfolgerungsmechanismus beschrieben).

Fakten sind, im Sinne von Wissensbasiertes Systems, in bestimmter Weise beschriebene Sachverhalte.

Eine verbreitete Methode, Fakten darzustellen, ist der Objekt-Attribut-Wert-Ansatz (oder object-attribute-value-triplets, im folgenden OAV-triplets genannt). Objekte sind physikalische Einheiten wie eine Kuh, ein Stall, ein landwirtschaftlicher Betrieb. Attribute sind generelle, mit einem Objekt assoziierte Eigenschaften wie die Grösse, die Farbe oder der Zinssatz. Werte schliesslich sind die Ausprägungen der Attribute. Der Wert beschreibt das Attribut eines Objekts in einer spezifischen Situation. Objekt und Attribut sind konstant oder fix, der Wert ist variabel. Ein Beispiel mag dies verdeutlichen:



Die Kuh Lisa hat eine Milchleistung von 6000 kg/Jahr. Dieser Satz beinhaltet ein OAV-triplet, wie in Übersicht 1 dargestellt.

Objekt Attribut Wert

Kuh Lisa Milchleistung 6000 kg/Jahr

Kuh Helga Milchleistung 7000 kg/Jahr

Kuh Anna Milchleistung 4000 kg/Jahr

Kuh Lisa Rasse Schwarzbunt

Kuh Anna Rasse Fleckvieh Übersicht 1: Objekt-Attribut-Wert-Triplet

Alle diese angeführten OAV-triplets sind Fakten oder Informationen, die in einem Expertensystem repräsentiert sein können.

1.6.4 Inference Procedures (Schlussfolgerungsmechanismen)

Im Zusammenhang mit AI und Wissensbasiertes Systems sind zwei "inference procedures" oder Schlussfolgerungsstrategien gebräuchlich: Modus ponens und Modus tollens.

Viele der heute eingesetzten Expertensysteme basieren ausschliesslich auf Modus ponens. Aus diesem Grund wird der Modus tollens nicht weiter erläutert.

Die Strategie des Modus ponens bedeutet, dass, vorausgesetzt A ist wahr - und eine wahre Regel sagt: "Wenn A, dann B" - gefolgert werden kann, auch B wahr ist.

Beispiel:

Regel: Wenn eine Kuh ein Kalb hat, dann gibt sie Milch.

Falls nun wahr ist, dass eine (bestimmte) Kuh ein Kalb hat, wissen wir der Regel folgend, dass sie auch Milch gibt.



2 Wissensrepräsentation und Ableitungsstrategien

2.1 Anforderungen an die Wissensrepräsentation

• Verarbeitbarkeit

• Flexibilität

• Modularität

• Verständlichkeit

• Darstellbarkeit unsicheren Wissens

2.2 Methoden zur Wissenspräsentation

Es gibt eine Vielzahl von Methoden um Wissensarten im Rechner zu modellieren. Drei davon, welche im Bereich der Wissensrepräsentationsformalismen durchgesetzt haben, sind folgende:

• Logikorientierte Methode

• Prozedurale Methode

• Objektorientierte Methode

2.2.1 Logikorientierte Methode

Der bekannteste Kalkül zur Darstellung von logischen Sachverhalten ist die Prädikatenlogik erster Stufe mit Gleichheit (Identität) und Funktionssymbolen (PIF).

Zur Bildung von Formeln benutzt man:

• Atome: n - stellige Prädikate, deren Argumente Terme (Konstanten oder n - stellige Funktionen) sind; z.B.: klein(Fritz), liebt(Adam,Eva), lang(Nase-von(Felix))

• Logische Operatoren: ¬ ∧ ∨ → ↔( ), ( ), ( ), ,nicht und oder

• Variablen und Quantoren: ∀ ∃( ), (min. )alleElemente einElement

Betrachten wir zum Beispiel die folgende PIF Formel:

∀ ∧ ¬ = ∧ ¬ = →X person X X adam X eva(( ( ) ( ) ( ))

∃ ∧ =Y person Y mutter von X Y( ( ) _ ( ) ))

Die Formel kann folgendermassen interpretiert werden:

Jede Person ausser Adam und Eva hat mindestens eine Mutter.



Die Prädikatenlogik erster Stufe ist zwar sehr ausdrucksstark, eignet sich aber nicht zur Implementation.

− nicht entscheidbar

− schon einfache Formelmanipulationen nehmen sehr viel Rechenzeit in Anspruch

− es gibt Wissen, das nicht darstellbar ist z.B.: Dieser Wagen rostet (ziemlich) schnell.

Offenbar hat "schnell" nicht den Status eines Prädikats, das auf Konstanten angewandt wird. Es modifiziert die Bedeutung eines anderen Prädikats ("rostet"). Bei "ziemlich" ist die Sache noch komplizierter.

Aus diesen Gründen werden meist stark reduzierte Teilsysteme der Prädikatenlogik verwendet. Diese Teilsysteme sind allerdings oft um Ausdrucksmittel erweitert, die in der Prädikatenlogik nicht vorhanden sind (z.B. Wahrscheinlichkeitswerte, Sicherheits-faktoren).

• Durch Hinzunahme von speziellen, anwendungsbezogenen Axiomen zur Prädikatenlogik erster Stufe erhält man Spezialtheorien für bestimmte Anwendungen.

2.2.1.1 Einfache Fakten - Regel - Systeme (EFRS)

Wir betrachten hier eine einfache Menge von Formeln, die wie folgt definiert wird:

Ein EFRS S ist eine endliche Menge von Regeln und Fakten:

S = R(S) ∪ F (S)

R(S) - Menge der Regeln von S

F(S) - Menge der Fakten von S

Fakten haben die Form F (S) =F S c cn( ) ( ,..., )= ψ 1

mit einem Prädikatensymbol ψ

und Konstantensymbolen c cn1 ,...,

Beispiele für Fakten:

mensch(hans),vater(hans,maria),gerade(2), teiler(2,4), kater(tom).

Die Prädikatensymbole mensch, gerade und kater sind einstellig; die Prädikatensymbole vater und teiler sind zweistellig

Regeln sind Implikationen der folgenden Form: Q= Quantorenpräfix

R S Q t t t t t t t tmm

mm( ) {( ( ,... ) ( ,..., ) ... ( ,..., ) ( ,..., ))}= ∧ ∧ ∧ →ψ ψ ψ ψα α α α1 1

11

12 1

22

21 0 1

00

0

Die Elemente eines EFRS sind eingeschränkte Hornklauseln, wie sie die Programmier-sprache PROLOG verwendet. Mit Hilfe der Unifikation und der Rückwärtsverkettung gibt es hier einen einfachen, effizienten Mechanismus zur Ableitung neuer Aussagen. Vieles Wissen lässt sich leicht als Hornklausel darstellen (Regelform). Allerdings enthält PROLOG auch viele nichtlogische Elemente (z.B.: Cut, Ein- und Ausgabe).



2.2.2 Prozedurale Methoden

Beim prozeduralen Ansatz wird Wissen in Form von Prozeduren dargestellt, die jeweils bestimmte Aufgaben erfüllen. Im Unterschied zu nicht wissensbasierten Programmen muss der Aufruf einer Prozedur aber der expliziten Kontrolle des Programms unterliegen. Das heisst, das Programm besitzt Wissen über die Problemlösungsmöglichkeiten und wendet diese entsprechend der Aufgabenstellung an.

Beispiel:

∀ →X person X sterblich Xperson sokratesperson helena

( ( ) ( )).( ).( ).

Alle Personen sind sterblich und Sokrates und Helena sind Personen.

Die Modularität der Prozeduralen Methode ist gegenüber der Logischen Methode eingeschränkt. Beim Erweitern des Wissens um einen Satz macht bereits eine Veränderung der bestehenden Prozedur nötig.

2.2.3 Objektorientierte Methoden

Frame Based- oder auch "Object Oriented Systems" stellen sowohl an den Programm-Entwickler, den Wissensingenieur, als auch an die Hardware die höchsten Ansprüche der drei diskutierten Methoden.

Die Werkzeuge (Tools), die sich bei der Entwicklung von Wissensbasiertes Systems auf die Darstellung von Wissen mit Frames/Objects stützen, werden als "Hybrid Tools" bezeichnet. Ihnen gehört ohne Zweifel die Zukunft, denn sie erlauben die eleganteste und flexibelste Wiedergabe von Wissen in computerverständlicher Form. Die Methode dieser Art von Wissensdarstellung an sich ist einfach, wenn auch abstrakt, wird aber mit zunehmender Komplexität des Sachproblems komplizierter.

Das Frame-Konzept wurde in den siebziger Jahren von MINSKY entwickelt:

Objekt

Attribut A

Attribut B

Attribut C

Attribut D

Satz von Werten

Regeln zur Bestimmung der Werte

Weglasswerte

zugeordneter Wert eines anderen Objektes (Parent)

S

L

O

T

S

Abbildung 4: Ein Frame: Beschreibung eines Objekts mit verschiedenen Slots und einiger möglicher Typen von assoziierten Informationen



Ein Frame kann im weitesten Sinne mit einem Aktenordner oder einer Karteikarte verglichen werden. Er hat einen Namen und enthält Informationen und evtl. Verweise über das benannte Objekt. Abbildung 6 zeigt einen typischen Frame. Slots können, wie Attribute eines OVA-triplets, Werte speichern, sie können vorbesetzte Werte enthalten (default values), Zeiger zu anderen Objekten, Sätze von Regeln (wie etwa bei regelbasierten Systemen zu finden) oder auch Prozeduren sein. Die Slots stellen gewissermassen Schnittstellen zu anderen Frames dar.

Diese Art der Wissensdarstellung setzt voraus, dass ein Satz von Objekten (Childs) eine Unterklasse eines anderen Objektes (Parent) ist.

2.2.3.1 Vor- und Nachteile

Frames erlauben eine mannigfaltigere Präsentation von Wissen als etwa die OAV-triplets in den regelbasierten Systemen, die hier lediglich eine Untergruppe darstellen (Rules können auch in Frames implementiert werden). Dies ist aber erheblich komplexer und somit schwieriger zu entwickeln sind.

Ebenso wie bei den regelbasierten Systemen muss der Wissensingenieur ein gründliches Verständnis von dem zu beschreibenden System haben und des weiteren über ausreichende Kenntnisse in LISP und/oder PROLOG (bzw. anderen AI-Sprachen) verfügen.

Wegen der Flexibilität dieser Art der Wissensrepräsentation werden Frame Based Systems allerdings trotz der damit verbundenen Schwierigkeiten in der Zukunft eine bedeutende Rolle spielen.



2.3 Regeln

2.3.1 Überblick

Regeln sind die am weitesten verbreitete Wissensrepräsentation in Wissensbasiertes Systems. Sie dienen zur Repräsentation natürlichsprachlicher wenn — dann — Sätze.

Eine Regel besteht aus einer Vorbedingung und einer Aktion (Implikation). Die Vor-bedingung beschreibt eine Situation, in der die Aktion ausgeführt werden soll. Es gibt zwei Typen von Aktionen:

• Implikationen oder Deduktionen: mit denen der Wahrheitsgehalt einer Feststellung hergeleitet wird

Wenn A, dann gilt B.

• Handlungen: mit denen ein Zustand verändert wird

Wenn A, dann führe B aus.

Im Gegensatz zur konventionellen Programmierung legt der Experte mit einer Regel nur fest, was in einem beschriebenen Zusammenhang getan wird, während die Reihenfolge der Regelausführung dem Regelinterpreter überlassen bleibt.

Ein wichtiger Unterschied besteht zwischen Regelsystemen mit Implikationen und solchen mit Handlungen, da letztere i. a. nicht kommutativ sind.

Regelbasiertes System:

• Datenbasis: gültige Fakten

• Regelmenge: zur Herleitung neuer Fakten

• Regelinterpreter: zur Steuerung des Herleitungsprozesses

Die meisten Expertensysteme benutzen diese Strategie in ihrem Begründungsprozess. Wenn die Zahl der möglichen Ergebnisse eines Expertensystemlaufes (die Zahl der möglichen Werte eines Multi-Value-Attributes) begrenzt und nicht zu hoch ist, dann ist die Rückwärtsverkettung sehr effizient.

Rückwärtsverkettende Systeme werden oft auch "Goal-Directed-Systems" genannt. Im Gegensatz dazu steht die "Vorwärtsverkettung", die für den Fall, dass die Zahl der möglichen Ergebnisse gross ist, bessere Dienste leistet.



2.3.2 Vorwärtsverkettung (forward reasoning oder forward chaining)

In vorwärtsverkettenden Wissensbasiertes Systems werden, beginnend von der ersten Regel, alle Inhalte anhand der vorhandenen Informationen auf ihren Wahrheitsgehalt überprüft, bis die erste Prämisse passiert, also wahr ist. Diese Schlussfolgerung wird dann zu einer Faktenliste hinzugefügt (in der alle bisher gefundenen, wahren Schlussfolgerungen stehen), und das System beginnt von neuem mit der Überprüfung der Regeln von Regel 1 an. Solche Systeme werden oft auch als "Data-Driven-Systems" bezeichnet.

Wichtige Konfliktlösungsstrategien:

• Auswahl nach der Reihenfolge, z.B. die erste anwendbare Regel

• Auswahl nach der syntaktischen Struktur der Regel

• Datenordnung

• Auswahl mittels Zusatzwissen

Beispiele:

• Ops5

• Med2

2.3.3 Rückwärtsverkettung (backward reasoning oder backward chaining)

Der Regelinterpreter geht von einem vorgegebenen Ziel aus und überprüft alle Regeln, deren Aktionen das Ziel enthalten. Wenn die Gültigkeit der Aussagen ihrer Vorbedingungen unbekannt sind, werden rekursiv Teilziele zur Bestimmung der Wahrheitswerte dieser Aussagen generiert, die entweder mit anderen Regeln abgeleitet oder vom Benutzer erfragt werden.

Bei der Abarbeitung der Teilziele sind Tiefensuche (bei PROLOG), Breitensuche oder gemischte Verfahren möglich.

Beispiele:

• Emycin

• Prolog



2.3.4 Tiefensuche und Breitensuche

Neben Rückwärts- und Vorwärtsverkettung wird bei Wissensbasiertes Systems zusätzlich nach der Richtung der Suche im Suchraum unterschieden.

Es bestehen zwei Möglichkeiten:

Die Suche geht zuerst in die Tiefe (Depth First Search) oder die Suche geht zuerst in die Breite (Breadth First Search). In den meisten Fällen findet die erstgenannte Technik Anwendung.

Diese Technik "gräbt" sich tiefer und tiefer in die Details eines Problems ein. Dabei ist die Art der Verkettung dafür verantwortlich, dass die Fragen, die von dem Expertensystem an den Benutzer gestellt werden, in einer sinnvollen Reihenfolge präsentiert werden. So würde beispielsweise ein Expertensystem zur Erfolgsanalyse eines landwirtschaftlichen Betriebes möglicherweise mit den Pflanzenbau betreffenden Fragen beginnen, immer detailliertere Antworten erwartend und erst nachdem alle notwendigen Informationen vorliegen, zur Tierproduktion übergehen.

Ein Expertensystem, welches die Technik der "Breadth First Search" anwendet, würde möglicherweise Fragen aus pflanzlicher und tierischer Produktion gemischt stellen, die Fragen würden nach einem Zufallsprinzip gestellt aussehen. Dem Benutzer mag dies eher suspekt vorkommen.

Abbildung 5: Suchstratiegien von Schlussfolgerungsmechanismen



Weitere Inferenzstrategien sind wie folgt ersichtlich. Aus Zeit- und Komplexitäts-Gründen wird in dieser Vorlesung nicht speziell darauf eingegangen.

• Ableitung

• Beweisbaum

• Matching

2.3.5 Certainty Factors

Certainty Factors und verwandte Methoden sind weitverbreitete Techniken zur Erfassung und Verarbeitung von unsicherer Information in Wissensbasiertes Systems.

CF = RegelCF * PrämisseCF /100

Kombinierte CF

CF(X,Y) = X + Y (100-X)/100 X,Y > 0

CF(X,Y) = X + Y (1- min(|X|,|Y|)) eine von X,Y < 0

CF(X,Y) = -CF(-X,-Y) X,Y < 0

Unter CF verstehen wir eine Zahl, die einem Teilausdruck einer Regel zugeordnet wird und die Sicherheit dieses Ausdrucks repräsentiert. Diese Certainty Factors werden während der Abarbeitung der Regel errechnet. Einer Regel selbst ist ein fester Certainty Factor zugeordnet. Dieser wird mit dem dynamischen Certainty Factor der Prämisse zum dynamischen Certainty Factor der Konklusion verknüpft.

2.4 Vergleich konventionelle Programme — Expertensysteme

Vergleich zwischen Data Processing und Knowledge Engineering

Konventionelle Programme Data Processing

Expertensysteme Knowledge Engineering

Wiedergabe und Gebrauch von Daten Wiedergabe und Gebrauch von Wissen

Verwendung von Algorithmen Verwendung von Heuristik

Sich wiederholende Prozesse Schlussfolgernde Prozesse

Manipulation grosser Datenbanken Manipulation grosser Wissensbanken

Sequentiell, Stapelverarbeitung Stark interaktiv, dialogorientiert

Erklärungen während des Programmablaufs schwierig zu erhalten

Erklärungen während des Programmablaufs (relativ) unproblematisch



3 Entwicklung von Wissensbasiertes Systems

• Knowledge Engineering (KE) ist der gesamte Prozess der Erstellung, Integration und Wartung eines Expertensystems.

• Die Aufgaben und Probleme beim Knowledge Engineering sind im wesentlichen die gleichen wie bei der normalen Softwareentwicklung (SE), erweitert um das besondere Problem der Wissensaquisition (WA):

KE = SE + WA

• Eine KE—Entwicklungsmethodik ist mindestens so notwendig und sinnvoll wie die bekannten SE—Entwicklungsmethoden; sie sollte die Wissensaquisition und insbesondere die Wissenspflege explizit unterstützen.

• Es gibt zwei Klassen von KE—Entwicklungsmethodiken:

− 1. Rapid Prototyping

− 2. modellbasierte Wissensaquisition (modellbasierter Ansatz)

3.1 Entwicklungsphasen

1. Problemidentifikation (Problemanalyse):

Die zu lösenden Probleme müssen abgegrenzt und beschrieben werden.

• Identifikation der am Projekt mitwirkenden Personen und deren Rollen

• Identifizierung des Problems

• Ressourcen bestimmen und einschätzen

• Identifikation der Ziele

2. Prüfung der Angemessenheit und Realisierbarkeit (Bedarfsanalyse)

• praktischer Nutzen

• Existiert eine konventionelle algorithmische Lösung?

• Komplexität des Problembereichs muss hinreichend gross sein, um den Aufwand für die Entwicklung eines Expertensystems zu rechtfertigen

• Expertensysteme haben bisher recht enge Grenzen hinsichtlich dessen, was machbar ist. Bestimmen/Erkennen der Grenzen des Expertensystems und Prüfen der Realisierbarkeit.



3. Wissenserhebung und -analyse (Konzeptualisierung): Sehr zeitaufwendiger Schritt; in dem Ausmass von Erhebung und Analyse vor Beginn der Implementation liegt ein entscheidender Unterschied zwischen dem modellbasierten und dem Rapid—Prototyping—Ansatz.

4. Implementierung:

• Gibt es geeignete Entwicklungswerkzeuge?

• möglichst problemspezifische Shell

• die Wissensbasis kann in kleinen Schritten inkrementell implementiert werden

• Abspalten von Teilen, die sich klassisch entwickeln lassen (z.B. Nutzeroberfläche)

5. Systemtest: Prüft, ob das System korrekt und anwendungsreif ist. Bei Wissensbasiertes Systems schwieriger als bei traditionellen Softwaresystemen feststellbar.

6. Einsatz und Wartung:

• Schnittstellen zu anderer Soft- und Hardware

• Vorbereitung der Benutzer

• laufende Aktualisierung des im Expertensystem verwendeten Wissens (aufwendig und wichtig); häufige Fehlerursache für schnelle Veralterung (viele Projekte sind schliesslich hieran gescheitert)

7. Evaluation:

Hierunter versteht man die Bewertung des eingesetzten Systems hinsichtlich seiner Leistung und Nützlichkeit.

3.2 Rapid Prototyping — modellbasierte Wissensaquisition

3.2.1 Rapid Prototyping

• Konstruktion eines Prototyps

• Bewertung des Prototyps

• Weiterverwendung des Prototyps



ErhebungExperte v Knowledge Engineer

StrukturierungKnowledge Engineer

EntwicklungKnowledge Engineer d Prototyp

BewertungExperte, Nutzer -- Knowledge Engineer

Expertensystem

Abbildung 6: Rapid Prototyping

Bemerkung: Wissensanalyse und Wissensimplementierung werden vermischt.

Vorteile:

• Knowledge Engineer und Experte können sofort überprüfen, ob der Wissenstransfer richtig durchgeführt worden ist

• der Experte kann das Verhalten des Systems überprüfen

• der Experte kann den Knowledge Engineer direkt auf fehlendes oder ungenügendes Wissen in der Wissensbasis hinweisen

Nachteile:

• die Repräsentation der Expertise in der Wissensbasis wird durch die Imp lementierungs-formalismen bestimmt und entspricht nicht der Begriffswelt des Experten

• Systemarchitektur muss vor der abschliessenden Analyse der Wissensprotokolle festgelegt werden; spätere Änderungen sind teuer

• Planung ist unübersichtlich; selbst während der Implementierung ist nie recht klar, wieviel noch zu tun ist

• es ist ungewiss, ob die Struktur des kleinen Systems tatsächlich im Grossen standhält

• es wird keine explizite Entscheidung über das Wissensmodell getroffen; es ergibt sich im Verlauf der Entwicklung



3.2.2 Modellbasierte Wissensaquisition

• Modellierung der Expertise

• Wissenserhebung durch Modellvervollständigung

• Implementierung durch Operationalisierung des Modells

• Unterstützung der Wartungsphase

Vorteile:

• klare Trennung von Analyse und Implementierung (die eventuell sogar von verschiedenen Personen durchführbar sind)

• nach der Analysephase liegt eine relativ vollständige Beschreibung der Expertise auf einer implementierungsunabhängigen Darstellungsebene vor

• Modell näher an der Terminologie der Experten

• der Interpretationsprozess, d.h. der Aufbau des konzeptuellen Modells, wird transparent und lässt sich dokumentieren

• dem Knowledge Engineer können generische Modelle zur Verfügung gestellt werden, welche die Interpretation leiten und besonders in der Anfangsphase Unterstützung geben, wenn er mit einer grossen Masse von Wissen konfrontiert wird

• Fehler bei der Interpretation von Daten schlagen sich nicht in unnötiger Implemen-tierungsarbeit nieder

InitialerhebungExperte v Knowledge Engineer

StrukturierungKnowledge Engineer

Modellierung - AnreicherungKnowledge Engineer v Experte

OperationsanalisierungKnowledge Engineer

ExpertensystemEntwicklung

Abbildung 7: Modellbasierte Wissensaquisition

Nachteil:

• die Vorteile des Rapid—Prototyping—Ansatzes entfallen



4 Wissenserwerb Die Wissensakquisition (WA) ist die Erhebung von Wissen aus verschiedenen Wissensquellen, wie Experten (Heuristiken, Strategien, Erfahrungswerte), Büchern, Handbüchern oder Lexika, sowie die anschliessende Umsetzung dieses Wissens in eine operationale Wissensbasis.

WA beinhaltet auch die Wartung der Wissensbasis nach der Auslieferung an den Kunden.

4.1 Aufgaben der Wissensakquisition

• Erhebung: Erfassung und Fixierung von Wissen. Es entsteht eine Datensammlung.

• Aufbereitung: Identifizierung, Analyse und Strukturierung des erhobenen Wissens. Es entsteht ein (mentales) Modell.

• Operationalisierung: Umsetzung in Wissensrepräsentationsformen (Regeln, Objekte,…) Es entsteht eine Wissensbasis.

4.2 Arten des Wissenserwerbs

1. Indirekter Wissenserwerb: Ein Wissensingenieur (KE) befragt einen Experten und formuliert die Ergebnisse für das Expertensystem.

Dieses Verfahren ist aufwendig und naturgemäss fehleranfällig, da das Wissen auf dem Umweg über den KE akquiriert wird.

Der KE (Knowledge Engineer)

• erhebt Wissen eines Experten

• bereitet es auf

• bringt es in operationalisierter Form in die Wissensbasis ein.

Es gibt zahlreiche Techniken:

• Interview

• Textanalyse

• Fallbeschreibung

• Protokollanalyse

• Konstruktgitterverfahren

• mehrdimensionale Skalierung

usw.



2. Direkter Wissenserwerb: Der Experte formalisiert sein Wissen selbst. Dieses Vorgehen erfordert ein komfortables Wissenserwerbssystem, ist aber nur in gut verstandenen Anwendungsbereichen durchführbar (z.B. Diagnose).

Der Experte

• formalisiert sein Wissen selbst

• überträgt es mittels Wissenseditoren (möglichst mit Graphikunterstützung und Konsistenzprüfung) in die Wissensbasis

Beispiele:

• TEIRESIAS (für MYCIN)

• CLASSIKA (für D3)

• MOLE, OPAL

3. Automatischer Wissenserwerb: Das Expertensystem extrahiert sein Wissen selbständig aus Falldaten oder verfügbarer Literatur. Hierzu dient ein Lernprogramm, welches aus Fallbeispielen Teile der Wissensbasis extrahiert. Es gibt erste Ansätze, die bisher aber nicht praxisreif sind.

4.3 Erhebung von Expertenwissen

Die Wissenserhebung ist der erste Schritt beim Transfer des Expertenwissens in ein wissensbasiertes System. Die Techniken lassen sich in drei Kategorien einteilen:

1. Interviewtechniken, bei denen der KE durch explizites Fragen versucht, neues oder spezifischeres Wissen vom Experten zu erfragen. Der Experte versucht, durch Introspektion sein Bereichswissen an den Tag zu bringen und Zusammenhänge zu verdeutlichen.

Man unterscheidet:

• Unstrukturiertes Interview

• Strukturiertes Interview

• Fokussiertes Interview

2. Techniken, mit denen versucht wird, das Vorgehen des Experten bei konkreten Problemstellungen zu beobachten und sein Vorgehen beim Problemlösen zu analysieren.

Dadurch ist es möglich, auch Wissen hervorzuholen, das sich der Introspektion und der direkten Verbalisierung durch den Experten entzieht und das nur in der Auseinandersetzung mit konkreten Problemsituationen angewandt wird.

Man unterscheidet:

• Protokollanalyse

• Introspektion

• Dialoge mit Klienten



3. Indirekte Techniken, bei denen der KE nicht durch explizites Fragen, sondern durch neutralere Fragestellungen versucht, zähes, impizites und unbewusstes Wissen aus dem Experten hervorzuholen.

Man unterscheidet:

• multidimensionale Skalierung

• hierarchisches Clustering

• gewichtete Netze

• Konstruktgitterverfahren

• Strukturlegetechniken

• geschlossene Kurven

• Inferenzflussanalyse

• geordnete Bäume durch Aufzählung



5 Anhang

5.1 Expertensystemwerkzeuge

Einen Gesamtüberblick gibt:

5.1.1 ART

ART — Automated Reasoning Tool

• Lisp — Schnittstelle

• Fakten, Schemata, Regeln, Kontexte

• multiple Vererbung

• Vor- und Rückwärtsverkettung

• vages Wissen

• Blackboard- und Constraints-mechanismen

5.1.2 KEE

KEE — Knowledge Engineering Environment

• Lisp — Schnittstelle

• prozedurale Wissensrepräsentation

• objektorientierte Wissensdarstellung auf der Basis von Frames

• regelbasierte Inferenzmaschine

• gute graphische Oberfläche

• multiple Vererbungsmechanismen

• Vor- und Rückwärtsverkettung

• Erzeugung von Erklärungen

• Schlussfolgerungsstrategien können vom Benutzer beeinflusst werden



5.1.3 BABYLON

• GMD, St. Augustin

• läuft unter Lisp

• 4 Hauptmodule:

− Frame - Prozessor (multiple Vererbung)

− Regel - Prozessor (Vor- und Rückwärtsverkettung)

− Logik - Prozessor (Resolutionsmechanismen für Hornklauseln)

− Meta - Prozessor

• reichhaltige Testhilfen

5.1.4 Knowledge Craft

• baut auf Common Lisp auf

• verwaltet Objekte (Schemata) mit multipler Vererbung

• Regeln (Vor- und Rückwärtsverkettung)

5.1.5 Twaice

• Prolog und C implementiert

• läuft auf Unix - Rechnern und PCs

• Regeln (automatisch auf Konsistenz prüfbar)

• Erzeugung von Erklärungen in natürlicher Sprache

• Induktionskomponente für das automatische Lernen von Regeln aus Daten

• Verbindung mit einem Hypertextsystem

5.1.6 D3

• Keine Angaben



5.2 Nexpert Object

5.2.1 Allgemeines

• Hersteller: Firma NEURON DATA INC . mit Hauptsitz in Palo Alto Deutschland: Firma Nexus GmbH aus Dortmund

• Markteinführung 1985

• auf verschiedenen Hardwareplattformen lauffähig

• Problembereich wird nicht vorgegeben

• in C geschrieben

• Schnittstellen zu Datenbanken

• Protabilität der Wissensbasen auf alle Hardwareplattformen ist möglich

• Visualisierung des Wissens mit Netzwerken

• C - Programme können auf NEXPERT OBJECT zugreifen und aus NEXPERT OBJECT können externe Programme aufgerufen werden

5.2.2 Wissensrepräsentation

Geschieht in Form von Regeln und Objektstrukturen.

5.2.2.1 Objekte und Klassen

Ein Objekt stellt die Beschreibung eines konkreten Gegenstandes dar. Die Beschreibung erfolgt durch die Angabe von Eigenschaften und Werten für diese Eigenschaften.

Es können Hierarchien von Objekten auftreten.

Eine Klasse stellt eine Verallgemeinerung von gleichartigen Objekten dar. Durch die Angabe von Beziehungen zwischen Objekten und Klassen können Aussagen über alle zu einer Klasse gehörenden Objekte gemacht werden.

Auch hier können Subklassen auftreten.



5.2.2.2 Slots und Metaslots

Als Slots bezeichnet man die Verbindungen Objekt.Eigenschaft bzw. Klasse.Eigenschaft.

Dort werden die Werte abgelegt, welche die Eigenschaft des jeweiligen Objektes bzw. der jeweiligen Klasse hat.

Werte für Slots werden in der Regel erst dann ermittelt, wenn sie für die Wissensverarbeitung gebraucht werden. Zu Beginn setzt man UNKNOWN.

Metaslots erlauben eine funktionale Beschreibung von einzelnen Slots. Zum Beispiel:

• Methoden der Wertermittlung

• Aktionen bei Wertänderungen

• Vererbungsmethoden

• Inferenzprioritäten

5.2.2.3 Regeln

Sie haben folgenden Aufbau:

Wenn Operator Operator 1 Operator 2 (Bedingungen)

Dann Hypothese Aktionen Operator Operator 1 Operator 2

Zu Beginn einer Sitzung ist der Boolsche Wert einer Hypothese UNKNOWN.

Eine Hypothese kann dann die Werte

• TRUE: alle Bedingungen wahr

• FALSE: mindestens eine Bedingung falsch

• NOTKNOWN: wenn nicht alle benötigten Informationen beschaffbar sind

annehmen (3 - wertige Logik).

5.2.3 Agenda

Die Agenda ist der zentrale Kontrollmechanismus, der den Inferenzprozess steuert.

Sie stellt eine geordnete Liste von Hypothesen dar.

Entsprechend ihrer Rangordnung in dieser Liste wird eine Hypothese bearbeitet, indem die Bedingungen aller Regeln zu dieser Hypothese überprüft werden. Die Hypothese erhält einen der Werte TRUE, FALSE, NOTKNOWN. Danach wird sie von der Agenda entfernt.

Die Agenda wird im Verlauf des Inferenzprozesses dynamisch verändert.



Hypothesen können auf die Agenda gelangen durch:

• Suggerieren einer Hypothese Der Nutzer des Systems wählt eine Hypothese direkt und beauftragt die Inferenzkomponente, diese Hypothese auszuwerten.

• Vorgabe von bereits bekannten Werten Der Nutzer teilt dem System mit, dass er gewisse Datenwerte kennt. Kommen die zugehörigen Slots auf der linken Seite einer Regel vor, dann wird deren Hypothese indirekt ausgewählt.

• Backward chaining ausgehend von der gerade bearbeiteten Regel

• Forward chaining

− von einer bereits bewiesenen Hypothese

− von Daten, die durch eine Aktion verändert wurden

− von Daten, die vom Benutzer eingegeben wurden

• Semantic gates aus einer bereits überprüften Regel

• Kontext zu einer bereits untersuchten Hypothese

Strategien bestimmen:

• welche Hypothesen auf die Agenda gelangen und

• wie die Regeln zu ihrer Bearbeitung benutzt werden.

Die gültige Strategie kann vor und während der Wissensverarbeitung verändert werden.

Prioritäten lösen die dabei auftretenden Konflikte.

5.3 Literaturverzeichnis

[1] G. Gottlob, Th. Frühwirth, und W. Horn, editors. Expertensysteme. Springer, Wien New York, 1990.

[2] P. Jackson. Expertensysteme Eine Einführung. ADDISON-WESLEY, Bonn, 1987.

Documents

Vorlesung Wissensbasierte Systeme - web.fhnw.ch fileFHNW Vorlesung Wissensbasierte Systeme Dr. T. Nouri kbs-deutsch99.doc KI-Wissenbasierte systeme 18.5.2004FH-NW/So 2/31 Inhaltsverzeichnis