Transcript
Einführung in die KI Prof. Dr. sc. Hans-Dieter Burkhard Vorlesung Winter-Semester 2009/10
Nichtmonotones Schließen
Umgang mit unvollständigem Wissen • • • • • •
Nicht-Monotones Schließen Negation, „Nicht-Wissen“ Unvollständigkeit Abgeschlossenheits-Annahmen Default-Schließen Revision/Truth Maintenance Systeme (TMS)
Verwandte Gebiete: • Modellierung als unsicheres Wissen – Wahrscheinlichkeiten für Annahmen – Modale Logik
• Modellierung als unscharfes Wissen H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
2
1
Unvollständigkeit des Wissens Entscheiden/Handeln trotz unvollständiger Information. Entscheiden/Handeln trotz inkonsistenter Information.
(beschränkte) Rationalität: Mit angemessenem Aufwand erfolgversprechende Entscheidungen treffen
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
3
Unvollständigkeit von Information Natürliche Sprache: – Mitteilung unvollständiger Information. – Beschränkung auf Wesentliches bzw. Allgemeines. – Vertrauen bzgl. Mitteilung von Ausnahmen.
Ökonomie von Beschreibungen
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
4
2
Quantifizierungsproblem Typische Eigenschaften „(alle) Vögel fliegen“ Vogel(X) ⇒ fliegt(X) ∀X ( Vogel(X) ⇒ fliegt(X) )
Ökonomie von Beschreibungen
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
5
Klassische Logik Monotonie: Fl und Abl sind monoton: X ⊆ Y ⇒ Fl (X) ⊆ Fl (Y) X ⊆ Y ⇒ Abl (X) ⊆ Abl (Y) Ableitungen: Mehr Axiome ⇒ mehr Sätze. Folgerungen: F folgt aus X gdw. jedes Modell von X ist Modell von F . Mehr Axiome ⇒ weniger Modelle ⇒ mehr Folgerungen. Spezifisches Verfahren. Formal einfach. Vorteil oder Nachteil? H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
6
3
Klassische Logik
• Ausnahmen explizit aufzählen (aufwändig). H0(x) ∧ ¬ Ausnahme(x) → H00(x) Ausnahme(x) = A1(x) ∧ A2(x) ∧ A3(x) ∧ . . . • Inkonsistenz nicht darstellbar. Th( H ∧ ¬ H) = ausd
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
Nicht-Monotonie
7
Eigentlich Alltags-Verfahren: Einfach bzgl. Aufwand. Formal kompliziert.
Natürliches Vorgehen ist nicht-monoton Umgang mit unvollständige Ausgangsinformation: • „solange nichts weiter bekannt“ : H0(x) → H00(x) • „weil nichts weiter bekannt“ : H0(x) → H00(x) bei „Zusatz-Information“ Ai(x) dann Revision: H0(x)∧Ai(x) → ¬H00(x) Umgang mit inkonsistenter Ausgangsinformation: • Entscheidung für eine Variante (konsistente Teilmenge): { H1,¬ H1, H2,H3,...,Hn} oder { H1,¬ H1, H2,H3,...,Hn} H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
8
4
Nicht-Monotonie: Frame-Problem Beschreibung von Ereignissen und veränderlichen Welten. Beispiel: Situationen-Kalkül (McCarthy,Hayes). • Situationen beschrieben durch gültige Fakten: Holds(In(Anton,Hörsaal), Situation085) Holds(Color(Hörsaal, weiss), Situation085)
• Ereignisse verändern Situationen: Sitation086 = Result(Go(Anton,Mensa),Situation085)
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
9
Nicht-Monotonie: Frame-Problem • Axiome beschreiben Veränderungen durch Ereignisse: Holds( In(a,l), Result(Go(a,l),s) ) Frame-Axiome beschreiben unveränderte Fakten: Holds( Color(x,c), s )
→ Holds( Color(x,c), Result(Go(a,l),s) ) Praktisch nichthandhabbar Alternativ: allgemeines Axiom für „Persistenz-Default“ Ereignisse verändern Eigenschaften normalerweise nicht. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
10
5
Nicht-Monotonie: Default-Annahmen Default: „Normaler Ablauf“ für – Übliche/Normale Eigenschaft • Regelsysteme, – Fehlerfreie Funktion (Diagnose) • Frame-Systeme, – Hintergrundwissen • ... Spezielle Behandlung für Ausnahmen: Priorität für Ausnahmeregel Überschreiben von Default-Werten Verträge sind gültig. Verträge mit Minderjährigen sind ungültig. Verträge mit Minderjährigen sind gültig, wenn sie im Beisein eines Vormundes geschlossen werden. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
11
Nicht-Monotonie: Default-Annahmen Default: Übliche/Normale Eigenschaft Inkonsistenzen entstehen durch Widersprüche zwischen – Default und Ausnahme-Fall vogel(X) → fliegt(X) vogel(X) & pinguin(X) → ¬ fliegt(X) – unterschiedlichen Defaults Quäker sind Pazifisten. Republikaner sind keine Pazifisten. Nixon ist Quäker und Republikaner. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
12
6
Unbekannte Aussagen Falls Gültigkeit der Aussage H nicht bekannt ist: Zwei Varianten Annahme: Aussage H gilt oder Annahme: Aussage H gilt nicht (¬ H gilt)
Problem: Wer trägt Beweislast.
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
13
Nicht-Monotonie: Negation Closed World Assumption (CWA)
Default-Annahme • Eine Aussage H gilt nicht (¬ H gilt), falls sie – nicht bekannt ist – nicht gefunden wird (Datenbank) – nachweislich nicht bewiesen werden kann (PROLOG)
Unterschied: • Unschuldig. • Freispruch mangels Beweises.
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
14
7
Nicht-Monotonie: Negation
Annahme der Gültigkeit von ¬ H bewirkt Nichtmonotonie: Zusätzliche Vorraussetzungen können H bekannt/auffindbar/beweisbar machen, d.h. ¬ H wird ungültig
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
15
Schließen auf ¬H • Strenge CWA (Datenbanken, OPS-5, STRIPS) ¬H , falls H nicht in Datenbasis • Negation by failure (PROLOG mit „finite failure“) ¬H , falls H nachweislich nicht beweisbar • CWA in Logik: ¬H , falls H nicht folgt/nicht beweisbar Korrekt nur dann, wenn stets ¬H oder H gültig („vollständige Theorie“). Im PK1 ist H∉Fl(X) nicht entscheidbar (nicht aufzählbar). H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
16
8
Schließen auf ¬H • Unabhängige Beschreibungen H+ (für H ) und H- (für ¬H ) ggf. spezieller Umgang mit Inkonsistenzen erforderlich. • Dialektische Negation ¬H , falls „Argumente gegen H sprechen“
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
17
Unterschiede bzgl. „Negation by failure“ Klassische Logik: ¬H00 ∉ Fl {¬H0 → H00 , H0 } Negation by failure (speziell PROLOG) not H00 ∈ FlNegation by failure{ not H0 → H00 , H0 } Beweis für not H00 : – Versuche H00 zu beweisen: – Versuche not H0 zu beweisen: – schlägt fehl wegen H0 – Beweis für H00 fehlgeschlagen not H00 gültig H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
18
9
Vervollständigung mittels CWA Theorie Th heiße vollständig, falls für jede atomare Grundformel H gilt: Entweder H∈Th oder ¬H∈Th . Vervollständigung: Hinzunahme von fehlenden Formeln (H oder ¬H ).
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
19
Vervollständigung mittels CWA CWA-Vervollständigung zu X : VCWA(X) := { ¬H | H Grundatom ∧ H ∉ Fl( X )} (erfordert Entscheidung ob H ∉ Fl( X ) ) Th(X) := Fl(X) CWA(X) := Fl( X ∪ VCWA(X) ) = Th(X ∪ VCWA(X) )
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
20
10
Vervollständigung mittels CWA CWA kann zu Inkonsistenz führen: X = { P(a) ∨ Q(a) } mit P(a) ∉ Fl(X) und Q(a) ∉ Fl(X) folglich: { P(a) ∨ Q(a) , ¬ P(a) , ¬ Q(a) } ⊆ CWA(X) -- inkonsistent!
Nicht-Monotonie: X = { P(b) → Q(b) } mit ¬Q(b) ∈ CWA(X) aber ¬Q(b) ∉ CWA(X ∪ {P(b)})
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
21
Vervollständigung mittels CWA Unterschied positive/negative Grundliterale: X = { P(b), Q(a) } mit
¬Q(b) ∈ CWA(X) P1=Df ¬ P ,
Q1= Df ¬Q
X1 = {¬P1(b), ¬Q1(a)} mit
¬Q1(b) ∈ CWA(X1)
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
22
11
Vervollständigung mittels CWA Satz 1. X sei konsistent. CWA(X) ist inkonsistent gdw. Grundatome L1,...,Ln existieren mit L1 ∨ ... ∨ Ln ∈Th(X) , aber L1,..., Ln ∉ Th(X) . 2. X sei konsistent. Umformung von X in Klauselform führt zu Hornklauseln. Dann ist CWA(X) konsistent. 3. Für Hornklauseln gilt: Falls X konsistent, so auch CWA(X) . H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
23
Auftreten von Nicht-Monotonie CWA (und weitere Schlussformen bzgl. Annahme von ¬H) Überschreiben von Defaults/Standardwerten Ausnahmeregeln vs. allgemeine Regeln Behandlung des Frameproblems (und verwandter Probleme) • Behandlung impliziter Annahmen/Kontexte/Hintergründe • Partielle Modellierung mit Annahmen
• • • •
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
24
12
Auftreten von Nicht-Monotonie Anpassung von Inferenzmethoden an Nichtmonotonie, z.B. • Regelsysteme, • Vererbung/Überschreiben
Allgemein: Partielle Information wegen • unvollständigem Wissen • veränderlichem Wissen • zu hoher Beschreibungskomplexität
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
25
Formale Behandlung von Nicht-Monotonie Nichtmonotone Logiken - Default Logiken - Auto-epistemische Logiken - Circumscription - Präferenzlogiken Belief-Revision, Truth-Maintenance-Systeme – Protokollierung von Schlussfolgerungen/Abhängigkeiten – Revision früherer Schlußfolgerungen
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
26
13
Ansatzpunkte für Formalismen • Unterscheidung: • Striktes Wissen • Annahmen • Spezielle Inferenzregeln Default-Regeln: Aus a folgt b, falls nichts gegenteiliges bekannt ist. • Modale Operatoren belief( Geburtsjahr(Napoleon, 1869) )
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
27
Ansatzpunkte für Formalismen Inkonsistenz der gesamten Folgerungs-/ Ableitungsmenge.
P(a)
¬ P(a)
Konsistente Teilmengen: „Extensionen"
P(a)
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
¬ P(a)
28
14
Ansatzpunkte für Formalismen "Auswahl"-Strategie: spezielle Extension bevorzugen („Präferenzen“)
Skeptische Strategie: Durchschnitt der Extensionen verwenden
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
P(a)
Vorlesung Einführung in die KI Nichtmonotones Schließen..
¬ P(a)
29
Default Logik (Reiter 1980) Default-Regeln: Falls a gilt, so gilt im allgemeinen auch b. Aus a folgt b, falls nichts gegenteiliges bekannt ist. Erweiterung des PK1 durch zusätzliche Ableitungsregeln der Form (Default-Regel): P : D1,...,Dn C Außer den Prämissen P ist die Berechtigung der Annahmen D1,...,Dn erforderlich für die Ableitbarkeit der Konklusion C H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
30
15
Default-Regel
P : D1,...,Dn C
Falls P ableitbar ist und alle Di konsistent (¬Di nicht ableitbar) so ist C ableitbar. vogel(X) : fliegt(X) fliegt(X) Bei gegebenen Voraussetzungen
vogel(pfiffi), vogel(tweety), ¬ fliegt(tweety) Ist dann mittels obiger Default-Regel ableitbar: fliegt(pfiffi) Vorlesung Einführung in die KI Nichtmonotones Schließen..
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Default-Regel
31
P : D1,...,Dn C
Spezialfall:
:D D
Falls ¬D nicht ableitbar, so gilt D .
CWA: Falls D nicht ableitbar, so gilt ¬D .
: ¬D
¬D
„Asymmetrie“: Kontrapositionen von Defaultschlüssen müssen (falls erwünscht) durch entsprechende Regeln formuliert werden. ¬C : D1,...,Dn ¬P H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
32
16
Extensionen der Default-Logik Möglicher (aber nicht ausreichender) Ansatz:: X sei konsistente Menge von Formeln, D sei Menge von Default-Regeln Iteration: Z0 := X Zi+1 := Th(Zi ) ∪ { C |
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
P:D1,...,Dn ∈ D ∧ P∈ Zi ∧ ¬D1,...,¬Dn ∉ Zi } C
Vorlesung Einführung in die KI Nichtmonotones Schließen..
33
Extensionen der Default-Logik Möglicher (aber nicht ausreichender) Ansatz:: Fixpunkt-Ansatz gemäß Iteration
Y := Th(Y ) ∪ { C |
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
P:D1,...,Dn ∈ D ∧ P∈ Y ∧ ¬D1,...,¬Dn ∉ Y} C
Vorlesung Einführung in die KI Nichtmonotones Schließen..
34
17
Extensionen der Default-Logik Ziel einer Definition: 1. Sicheres Wissen X ist enthalten 2. Deduktiver Abschluss 3. Defaultregeln angewendet soweit möglich 4. Keine unbegründeten Formeln XÕ Y Th(Y) = Y { C | P:D1,...,Dn ∈ D ∧ P∈ Y ∧ ¬D1,...,¬Dn ∉Y }) Õ Y C
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
35
Extensionen der Default-Logik XÕ Y Th(Y) = Y { C | P:D1,...,Dn ∈ D ∧ P∈ Y ∧ ¬D1,...,¬Dn ∉Y }) Õ Y C
Problem bei diesem Ansatz: Für [X,D] = [ {Vog(Tw)}, {Vog(Tw):Flt(Tw)/Flt(Tw) } ] ist außer Th( X ∪ Flt(Tw) ) auch Th( X ∪ ¬Flt(Tw) ) ein minimaler Fixpunkt. Dabei aber 4. nicht erfüllt: Benötigen Konsistenz-Test. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
36
18
Extensionen der Default-Logik X sei konsistente Menge von Formeln, D sei Menge von Default-Regeln Y Formelmenge ΓX,D(Y) ist definiert als kleinste Formelmenge mit • X Õ ΓX,D(Y) • Th(ΓX,D(Y) ) = ΓX,D(Y) • { C | P:D1,...,Dn ∈ D ∧ P∈ ΓX,D (Y) ∧ ¬D1,...,¬Dn ∉Y })Õ ΓX,D(Y) C
Fixpunkte ΓX,D(Y) = Y sind die Extensionen. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
37
Extensionen der Default-Logik X Õ ΓX,D(Y) Th(ΓX,D(Y) ) = ΓX,D(Y) { C | P:D1,...,Dn ∈ D ∧ P∈ ΓX,D (Y) ∧ ¬D1,...,¬Dn ∉Y })Õ ΓX,D(Y) C
Ziel der Definition: 1. 2. 3. 4.
Sicheres Wissen X ist enthalten Deduktiver Abschluss Defaultregeln angewendet soweit möglich Keine unbegründeten Formeln
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
38
19
Beispiele (Brewka): Extensionen X
D
Vog(Tw)
Vog(x):Flt(x) / Flt(x)
Fixpunkte (E) E = Th( X ∪ Flt(Tw) )
Vog(Tw) Vog(x):Flt(x) / Flt(x) Pin(Tw) ∀x(Pin(x) → ¬Flt(x))
E = Th( X )
Vog(Tw) Pin(Tw)
Vog(x): Flt(x) / Flt(x) Vog(x): ¬Flt(x) / ¬Flt(x)
E1= Th(X ∪ Flt(Tw)) E2= Th(X ∪¬Flt(Tw))
Vog(Tw) Pin(Tw)
Vog(x):Flt(x)∧¬Pin(x) / Flt(x) Vog(x): ¬Flt(x) / ¬Flt(x) E= Th(X ∪¬Flt(Tw))
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Nicht-Monotonie
Vorlesung Einführung in die KI Nichtmonotones Schließen..
39
Extensionen der Default-Logik Pseudo-Iteration unter den Voraussetzungen: X sei konsistente Menge von Formeln, D sei Menge von Default-Regeln Y sei Menge von Formeln Z0
:= X
Zi+1 := Th(Zi ) ∪ { C |
P:D1,...,Dn ∈ D ∧ P∈ Zi ∧ ¬D1,...,¬Dn ∉ Y } C
Dann gilt: Y ist Extension, falls Y = ∩ Zi H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
40
20
Default-Logik Extensionen haben die Form X ∪ { zulässige Folgerungen gemäß D } Überprüfung durch Test von Kandidaten auf Fixpunktbedingung Extensionen sind konsistent (falls X konsistent). Teilmengen einer Extension sind keine Extension
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
Probleme Default-Logik – Kreisförmige Schlüsse – Inkonsistenzen
41
Weiteres: Siehe Literatur
[X,D] = [ ∅, { : ¬D / D} ] hat keine Extensionen – unerwartetes Verhalten aus { a:D / D, b:D / D, a ∨ b } ist D nicht ableitbar – Unentscheidbarkeit von „¬D nicht ableitbar" – Default-Logik nicht axiomatisierbar H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
42
21
Auto-Epistemische Logik (Moore, 1985) Modaler Operator Bel: Bel(p) = es wird geglaubt, dass p gilt Zusätzliche Axiome der Form: P ∧ Bel(D) → C
P ∧ ¬ Bel(D) → C
vogel(X) ∧
Bel( fliegt(X)) →
vogel(X) ∧
Bel(¬ fliegt(X)) → ¬ fliegt(X)
fliegt(X)
vogel(X) ∧ ¬ Bel( fliegt(X)) → ¬ fliegt(X) vogel(X) ∧ ¬ Bel( ¬ fliegt(X)) → fliegt(X) H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
43
Auto-Epistemische Logik: Extensionen E ist Extension von einer Axiomenmenge X, falls E := Ab( X ∪ { Bel(H) | H∈ E} ∪ { ¬Bel(H) | H ∉ E } )
Beispiel: X={ vogel(Tw) ∧ (¬Bel(¬fliegt(Tw)) → fliegt(Tw)) , vogel(Tw) } fliegt(Tw)) ∈ E
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
44
22
Auto-Epistemische Logik/Default-Logik Default-Logik (DL) und Auto-Epistemische Logik (AEL) sind in gewisser Weise äquivalent. P: D1,...,Dn / C entspricht Bel(P) ∧ ¬Bel( ¬D1) ∧ ... ∧ ¬Bel( ¬Dn) → C DL-Extensionen entsprechen gewissen Bel-freien AEL-Extensionen.
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
45
Circumscription (Mc Carthy, 1980) Idee: Gültigkeitsbereich spezieller Prädikate minimal festlegen. – Bei CWA: Festlegung auf einen minimalen Gültigkeitsbereich mittels Folgerungs-/Ableitungsrelation.
– Bei Circumscription: Festlegung auf einen gewünschten (minimalen) Gültigkeitsbereich mittels zusätzlicher Axiome.
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
46
23
Circumscription (Mc Carthy, 1980) Gültigkeitsbereich eines Prädikats P eingrenzbar durch • positive Festlegungen, z.B. – P(a), P(b),... – ∀x (H(x) → P(x)),... – „im Zweifelsfalle für den Angeklagten“ • negative Festlegungen, z.B. – ¬P(c), ¬P(d),... – ∀x (H(x) → ¬P(x)),... – CWA
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Auswirkungen jeweils für P(e) ?
Vorlesung Einführung in die KI Nichtmonotones Schließen..
47
Circumscription (Mc Carthy, 1980) Minimaler Gültigkeitsbereich mittels zusätzlicher Axiome. Beispiel: verheiratet(Peter). verheiratet(Petra). als weiteres Axiom: ∀x(verheiratet(x) → x = Peter ∨ x = Petra) allgemein: (Axiomen-)Schema Prädikaten-Circumscription für ein Prädikat P bezüglich einer Formel H.
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
48
24
(Axiomen-)Schema Prädikaten-Circumscription Definition: P sei n-stelliges Prädikatensymbol, H sei Formel ohne freie Variable. H(Q) entstehe aus H indem Prädikatensymbol P durch ein n-stelliges Prädikatensymbol Q ersetzt wird. Schema der Prädikaten-Circumscription von P bezüglich H ist Menge aller mit unterschiedlichen Q möglichen Formeln ( H(Q) ∧ ∀x1 ... ∀xn (Q(x1,...,xn) → P(x1,...,xn) )) → ∀x1 ... ∀xn (P(x1,...,xn) → Q(x1,...,xn) )
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
49
(Axiomen-)Schema Prädikaten-Circumscription Instanzen dieses Schemas gemeinsam mit H(P) und den sonstigen Axiomen für Ableitungen benutzen: Geeignetes Q erzwingt P mit minimalen Gültigkeitsbereich.
Alternativ z.B.: Circumscription-Axiom in PK2
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
50
25
Präferenzen • Präferierte Theorie: – Präferenz-Relation bzgl. der maximalen konsistenten Teiltheorien einer inkonsistenten Theorie. • Präferierte Modelle: – Präferenz-Relation über den Modellen. – Folgerungsrelation nur bzgl. der präferierten Modelle. – Präferenz von Modellen z.B. durch • Modelle mit wenig Ausnahmen • Modelle mit vielen Standard-Annahmen Circumscription bedeutet Präferenz von Modellen mit minimalem Gültigkeitsbereich für Prädikat P . H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
51
Revisions-Mechanismen „Belief Revision“: Im Inferenz-Prozess werden aus Axiomen/Annahmen A1, A2,... Schlussfolgerungen H1, H2,... gezogen. Bei Revision von Ai kann Rechtfertigung für Hj entfallen: ggf. muß auch Hj revidiert werden. Z.B. in nicht-monotonen Systemen: – Konsistenz-Prüfung bei veränderten Voraussetzungen – Überprüfung der bisher erfolgten Schlüsse „Belief Update“: Durch Zustandsänderung notwendige Aktualisierungen. H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
52
26
Revisions-Mechanismen Wissensbasis B ∪{ p } sei inkonsistent
{ a , b, c, a∧b→c, ¬c } Syntaktische Revision: Ziel: konsistente Teilmenge B´ ⊆ B ∪{ p } auswählen Kriterien für Auswahl: • Zuverlässigkeit der Information • Wichtigkeit der Information
Semantische Revision: Betrachtung von Modellen H.D.Burkhard, HU Berlin Winter-Semester 2009/10
{ b, a∧b→c, ¬c } { a, a∧b→c, ¬c } { a , b, ¬c } { a , b, c, a∧b→c }
Vorlesung Einführung in die KI Nichtmonotones Schließen..
53
Truth Maintenance Systeme Truth Maintenance Systeme (TMS) (auch „Reason Maintenance Systeme“ - RMS) protokollieren die Ableitungsprozesse bzw. die Abhängigkeiten und ermöglichen damit die Revision von Schlussfolgerungen. • JTMS - Justification Based TMS ( Doyle, 1979) Protokolliert die Begründungen: Regelanwendungen mit unmittelbaren Voraussetzungen • ATMS - Assumption Based TMS (de Kleer, 1984) Protokolliert die jeweils zugrunde liegenden Axiome H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
54
27
JTMS - Justification Based TMS Darstellung als Abhängigkeitsnetz J1: A → B J2: B → C J3: D ⁄ E → C
A
J1
B
D
J2
C
E
J3
Rekursiver Basis-Algorithmus (bis Stabilität eintritt): • Bei Änderung einer Bedingung b: Alle davon abhängigen Begründungen J überprüfen: Falls eine von J abhängige Bedingung b‘ keine weitere Begründung hat: b‘ zurückziehen. Vorlesung Einführung in die KI Nichtmonotones Schließen..
H.D.Burkhard, HU Berlin Winter-Semester 2009/10
55
JTMS - Justification Based TMS Probleme mit kreisförmigen Begründungen: (erfordern spezielle Behandlung, Ineffizienz)
J2 A
J1
C
B
J4
D
J3 (Wechselseitige Begründung kann aber sinnvoll sein) H.D.Burkhard, HU Berlin Winter-Semester 2009/10
Vorlesung Einführung in die KI Nichtmonotones Schließen..
56
28
