KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 1
Wissensbasierte Systeme/Expertensysteme
Teil 2
BiTS, Sommersemester 2004Dr. Stefan Kooths
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 2
Gliederung
1. Einführung und Einordnung2. Entscheidungsunterstützung(ssysteme)3. Künstliche Intelligenz und Expertensysteme im
Überblick4. Wissensrepräsentation und Inferenz5. Entwicklung von Expertensystemen6. Wissensmanagement7. Zusammenfassung und Ausblick
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 3
4. Wissensrepräsentation und Inferenz
• Formale Logik (Aussagen-/Prädikatenlogik) und logisches Schließen
• Produktionssysteme und regelbasierte Inferenz• Strukturen und Strategien der
Zustandsraumsuche• Simulation und modellbasiertes Schließen• Frames und Skripte• Fallbasiertes Schließen• Umgang mit Unsicherheit• Erklärungen und Metawissen
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 4
Formale Logik
• AussagenlogikSprache für Aussagen über die WeltSchlussfolgern durch rein formale Rechenoperationenüber 2000 Jahre alt
• Aussagenkleinstes Element der Sprache (Atome)Symbole: Großbuchstaben aus dem hinteren Teil des Alphabets (P,Q,R, ...)zweiwertig: wahr oder falsch (Grundsatz vomausgeschlossenen Dritten)
• Sätze (auch: Formeln)Atome oder Verknüpfung von AtomenVerknüpfung durch Junktoren (∧, ∨, ¬, ⇒, =)Gruppierung zur Auswertungssteuerung: () und []Interpretation: Auswertung über Wahrheitstafeln
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 5
Definition: Sätze der Aussagenlogik
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 6
Semantik der Aussagenlogik
• rein logisch-formal• Zuweisung von Wahrheitswerten für Atome• Anwendung logischer Regeln und Gesetze• Auswertung über Wahrheitstafeln• Übung: Elementare Wahrheitstafeln
NegationKonjunktionDisjunktionImplikationÄquivalenz
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 8
Schlussregeln: Modus ponens und Modus tollens
• Modus ponensEs gelte:P ⇒ Q “Wenn es regnet, wird die Straße nass.”P “Es regnet.”
Dann lässt sich schließen:Q “Die Straße ist nass.”
• Modus tollensEs gelteP ⇒ Q “Wenn es regnet, wird die Straße nass.”¬Q “Die Straße ist nicht nass.”
Dann lässt sich schließen:¬ P “Es regnet nicht.”
• http://www.modus-tollens.com
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 9
Extensionalität
• Wahrheitswerte sind nicht zwingend sinnvoll• Beispiel 1 (Kommutativität)
P: “Das Unternehmen wurde zahlungsunfähig.”Q: “Alle Mitarbeiter wurden entlassen.”P ∧ Q = Q ∧ P?
• Beispiel 2 (logische Implikation)P: “Eine Bilanz enthält Stromgrößen.”Q: “Die Eigenkapitalrendite ist unabhängig vom Gewinn.”P ⇒ Q?
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 10
Prädikatenlogik
• Aufspalten der atomaren Sätze der Aussagenlogik• Prädikate bezeichnen Beziehungen/Eigenschaften• Schlussregeln zur Bearbeitung
prädikatenlogischer Ausdrücke• Variablen für allgemeine Aussagen über Klassen
von Elementen• Beispiele
“Die Rendite der BMW-Aktie ist hoch”wird repräsentiert alsrendite(bmw_aktie,hoch)
Verwendung von VariablenMenge aller Wertpapiere X mit hoher Renditerendite(X,hoch)
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 11
Prädikatenlogische Symbole 1
• AlphabetGroß- und KleinbuchstabenZiffern 0,1,...,9Unterstrich
• Konstantekonkrete Objekte der realen Weltbeginnen mit Kleinbuchstaben (bmw3er)true/false als Wahrheitssymbole
• Variableallgemeine Klassen von Objekten oder Eigenschaftenbeginnen mit Großbuchstaben (Auto)gelten nur lokal
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 12
Prädikatenlogische Symbole 2
• FunktionenAbbildung von einem oder mehreren Elementen einerMenge (Domäne der Funktion) auf eindeutiges Element einer anderen Menge (Bereich der Funktion)beginnen mit KleinbuchstabenStelligkeit = Anzahl der DomänenelementeAuswertung: Ersetzung einer Funktion durch deren WertBeispiele– preis(bmw3er)– summe(X,Y)
• TermeKonstantenausdrückeVariableFunktionsausdrücke
Funktionsausdruck
Funktionssymbol der Stelligkeit n, der n Terme folgen, die in rundenKlammern eingeschlossen sind und durch Kommas getrennt werden.
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 13
Prädikatenlogische Symbole 3
• PrädikateBeziehung zwischen null oder mehreren Objekten derrealen Weltbeginnen mit KleinbuchstabenStelligkeit (identifiziert Prädikat!)Beispiele– schneller(porsche,golf)– gewinnabfuehrung(bmwkonzern,mini)
• atomarer Satz (Atome)Prädikat der Stelligkeit n,dem n in Klammern eingeschlossene und durch Kommasgetrennte Terme folgenendet mit einem PunktWahrheitswerte true/false sind auch atomare Sätze
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 14
Prädikatenlogische Sätze
• bestehen aus Atomen• Verknüfpung durch Junktoren (∧, ∨, ¬, ⇒, =)• Variablenquantoren
Existenzquantor ∃ (“es gibt mind. ein/eine”)Beispiel: ∃ Y schneller(Y,bmw3er).Allquantor ∀ (“für alle gilt, dass”)Beispiel: ∀ X (hinterradantrieb(X) ∧ bmw(X)).
wohlgeformteAusdrücke
kannrekursiv getestet
werden(vgl. Luger,S. 80/81)
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 15
Beispiele (Verwandtschaftsbeziehungen)
mutter(eva,abel).mutter(eva,kain).vater(adam,abel).vater(adam,kain).∀X ∀Y vater(X,Y) ∨ mutter(X,Y) ⇒ elternteil(X,Y).∀X ∀Y ∀Z elternteil(X,Y) ∧ elternteil(X,Z) ⇒ geschwister(Y,Z).
mutter(daimlerchrysler,mercedes).mutter (daimlerchrysler,chrysler).∀X ∀Y ∀Z mutter(X,Y) ∧ mutter(X,Z) ⇒ schwestern(Y,Z).
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 16
Semantik der Prädikatenlogik
• Bedeutung wohlgeformter Ausdrücke im Hinblickauf Objekte, Eigenschaften und Beziehungen derrealen Welt (= Diskursdomäne)
• formale Grundlage für die Wahrheitswertbestimmung
• abhängig von der Abbildung von Termen und Prädikaten auf Objekte/Relationen der realen Welt
• Variablen als “Dummies”• CWA = Closed World Assumption• unendlich große Domäne: Quantifizierung (∀,∃)
führt zu Unentscheidbarkeit der Prädikatenlogik
Mielke: “Aber ich mag doch alle Menschen.”∀ X (mensch(X) ∧ mag(mielke,X)).
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 17
Interpretation in Bezug auf eine Domaine D
Variablen sind reine Platzhalter und können beliebig ersetzt werden, ohne dass sich die Bedeutung eines Ausdrucks ändern würde
∀X (mensch(X) ∧ mag(mielke,X)). ⇔
∀Lebewesen (mensch(Lebewesen) ∧ mag(mielke,Lebewesen)).
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 18
Prädikatenlogik erster und höherer Stufe
• Prädikatenlogik erster Stufe:Quantifizierung nur für Objekte, nicht für Prädikate oderFunktionenimplementiert in (deklarativer)Programmiersprache PROLOG
• Prädikatenlogik höherer StufeQuantifizierung auch für Prädikate/FunktionenBsp.: ∀ (Mag) Mag(dieter,herthabsc).
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 21
Beispiel (Bausteinwelt)
beachte: Reihenfolge der Aktionen wird implizit kodiert, daRegeln von links nach rechts abgearbeitet werden
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 22
Prädikatenlogisches Schlussfolgern
• Ziel: ausgehend von einer Menge wahrerAussagen auf neue korrekte Ausdrücke schließen
• korrekt = konsistent mit allen vorherigenInterpretationen der ursprünglichen Menge von Aussagen
• Eine Interpretation, die einen Satz wahr macht, heißt Interpretation, die den Satz erfüllt.
• Eine Interpretation, die jedes Element einerMenge von Ausdrücken S erfüllt, heißtInterpretation, die die Menge S erfüllt.
• Ein Ausdruck P folgt logisch aus einer Mengeprädikatenlogischer Ausdrücke S, wenn jedeInterpretation, die S erfüllt, auch P erfüllt.
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 23
Klassisches Beispiel/Abgrenzung
• Menge S∀ X mensch(X) ⇒ sterblich(X).mensch(sokrates).
• Ausdruck Psterblich(sokrates).
• logisch folgern heißt nicht,dass P aus S abgeleitet wird oderdass P aus S ableitbar wäre
• sondern,dass P für jede Interpretation wahr ist, die S erfüllt.
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 24
Schlussregeln
• Mittel, um mechanisch aus bestehenden Sätzenneue prädikatenlogische Sätze zu erzeugen(um nicht alle Interpretationen ausprobieren zumüssen)
• Modus ponens (Modus der Behauptung, s.o.)• Modus tollens (Modus der Widerlegung, s.o.)• Und-Eliminierung:
aus (P ∧ Q) wahr folgt, dass P wahr und Q wahr ist
• Universelle InstantiierungErsetzen einer Allvariablen durch Term aus der Domäneergibt einen wahren Satzwenn a aus Domäne von X, dann kann man aus demwahren Satz ∀X p(X) schließen, dass p(a) wahr ist
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 25
Unifikation
• Einsatz von SchlussregelnWann sind zwei Ausdrücke gleich?Wie lassen sich zwei Ausdrücke gleich machen?
• Aussagenlogiktrivial (syntaktische Identität)
• Prädikatenlogiknicht trivial, wegen Variablen bzw. QuantorenUnifikation: Substitutionsalgorithmus, um zweiquantifizierte Ausdrücke zur Übereinstimmung zu bringenZwischenziel: Quantifizierung nur über AllquantorExistenzquantor: Skolemisierung– Konstanten: aus ∃Y mutter(Y,mini) wird mutter(bmw,mini)– Funktionen: aus ∀X ∃Y mutter(X,Y) wird ∀X mutter(X,f(X))
vgl.Sokrates-Beispiel
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 26
Substitutionsinstanzen/Unifikationen
• Variable kann durch beliebigen Term ersetztwerden (auch durch andere Variablen oderFunktionsausdrücke)
• Notation für Ersetzungen (Bindungen)mutter(daimlerchrysler,X)X wird ersetzt/gebunden durch mercedes: {mercedes/X}mercedes ist Substitutionsinstanz für X
• weitere Beispiele:Unifikation des Ausdrucks foo(X,a,goo(Y)).
foo(fred,a,goo(Z)) {fred/X, Z/Y}foo(W,a,goo(hans)) {W/X,hans/Y}foo(Z,a,goo(moo(Z)) {Z/X,moo(Z)/Y}
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 27
Substitutionsalgorithmus
• Konstanten sind Grundinstanzen (dürfen nicht ersetztwerden)
• eine Variable darf nicht gleichzeitig durch zweiverschiedene Konstanten ersetzt werden
• eine Variable X darf nicht durch Term ersetzt werden, derwiederum X enthält (sonst unendlicher Regress) Occur-Check
• Konsistenz: einheitliche Bindung in allen Ausdrücken, in denen Variable vorkommt (Bsp.: Sokrates)
• Konzept der VerknüpfungX/Y, V/X, a/V ist äquivalent mit a/Y
• möglichst allegemeine Vereinheitlichung (mgu)statt: peter/X und peter/Y in p(X) und p(Y) lieber: Z/X, Z/Y
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 28
Unifikation durch syntaktischen Mustervergleich
• effektive Vernachlässigung (!) derprädikatenlogischen Unterscheidung zwischenPrädikatssymbolen, Funktionssymbolen und Argumenten
• Satz als Liste mit Prädikats-/Funktionssymbol alserstem Element
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 29
Pseudocode für rekursive Funktion unify
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 30
Beispiel
• Frage: Wann sind die folgenden Ausdrückegleich?
eltern(X,vater(X),mutter(bill)eltern(bill,vater(bill),Y)
• in Listenschreibweise(eltern X (vater X) (mutter bill))(eltern bill (vater bill) Y)
• Funktionsaufruf:unify((eltern X (vater X) (mutter bill)), (eltern bill (vater bill) Y))
KOOTHS – BiTS: Wissensbasierte Systeme/Expertensysteme | Teil 2 31
Anwendung: Finanzberater
• Entscheidungsalternativen (Anlageform)SparguthabenAktienKombination aus beiden
• Kriterienbei inadäquatem Sparguthaben zunächst Sparguthaben erhöhen(unabhängig vom Einkommen)bei adäquatem Sparguthaben und adäquatem EinkommenAktienanlage in Betracht ziehenbei geringem Einkommen und adäquatem SparguthabenAufteilung auf beide Anlageformen
• Berechnung adäquater Größen (abh. Familienmitglieder)Sparguthaben: mind. 5000 pro AFMJahreseinkommen: regelmäßig und mind. 15.000 + 4000 pro AFM