CoboCards App FAQ & Wishes Feedback
Language: English Language
Sign up for free  Login

Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Enter your e-mail address and import flashcard set for free.  
Go!
All main topics / Informatik / Wisensbasierte Systeme

Knowledge Representation (86 Cards)

Say thanks
1
Cardlink
0
Was ist Wissen?
Beziehung zwischen einem Knower (Person) und einer Proposition (Fakt bzw. Satz)

Beispiel
John weiß, dass Lincoln ermordet wurde.

Knower: John
Proposition: Lincoln wurde ermordet
Tags: Einführung
Source:
2
Cardlink
0
Was ist eine Proposition?
  • abstraktes Gebilde
  • kann true/false bzw. right/wrong sein

Ergänzung
Präposition muss zuerst interpretiert werden, beispielsweise:
— Lincoln bezeichnet Abraham Lincoln, Präsident der USA
→nur die Interpretation kann wahr bzw. falsch sein
Tags: Einführung
Source:
3
Cardlink
0
Was ist (Knowledge) Representation?
= Beziehung zwischen zwei Domänen
wobei einer der Domänen konkreter ist und die erste für die zweite steht

Symbole
= typische Repräsentationsform
→Halbmond für Islam, "Sieben", "Seven" und "7" für 7
— zugänglicher als Propositionen, die sie repräsentieren
Tags: Einführung
Source:
4
Cardlink
0
Was ist Reasoning?
= Schlußfolgern
= formale Manipulation von Symbolen (die Propositionen repräsentieren) und die Erzeugung neuer Propositionen sowie Symbole hierfür

Beispiel 1
Symbole: 1011 und 10
Manipulation: +
Ergebnis: 1101 → neues Symbol

Beispiel 2
Satz 1: John loves Mary
Satz 2: Mary is coming to the Party
Neuer Satz: Someone that John loves is coming to the Party
Tags: Einführung
Source:
5
Cardlink
0
Welche Vorteile bieten wissensbasierte Systeme?
  • Erweiterbarkeit: Neue Funktionalität
  • Erweiterbarkeit: Neues Wissen
  • einfaches Debuggen durch Korrektur des Wissens
  • Nachvollziehbarkeit des Verhaltens, in dem die Annahmen des Programms ausgegeben werden
Tags: Einführung
Source:
6
Cardlink
0
Was ist cognitive penetrability?
= Aktionen eines Agenten, die abhängig von seinem Wissen sind

Beispiel
Feueralarm
Wissen: Nur Probealarm → keine Flucht

Gegenbeispiel
— Reflexe zum Beispiel des Auges
→auch wenn wir wissen, dass uns die Faust nicht trifft, blinzelt man

Tags: Einführung
Source:
7
Cardlink
0
Welche logischen Symbole besitzt die First Order Language (FOL)?
Punctation
  • (
  • )
  • .

Connectives
  • ¬ (Negation)
  • ⋀ (UND)
  • ⋁ (ODER)
  • ∃ (es existiert) →Quantifier
  • ∀ (für alle … gilt) →Quantifier

Variablen
  • unendlich viele
  • x, y, z, …
Tags: Einführung
Source:
8
Cardlink
0
Was sind nicht-logische Symbole und welche besitzt die First Order Language (FOL)?
= Symbole mit domänenabhängiger Bedeutung
besitzen eine Stelligkeit

function symbols
  • bestFriend, Dog, happy, …
  • a, b, c …

predicate symols
  • OlderThan, fatherOf, …
  • P, Q, R…
Tags: Einführung
Source:
9
Cardlink
0
Was ist das propositional subset der First Order Language (FOL)?
— keine Terme
— keine Formeln
— keine Quantifizierer
+ Prädikatsymbole mit einer Wertigkeit von 0

Beispiel
(P⋀¬(Q⋁R))
Tags: Einführung
Source:
10
Cardlink
0
Welche Abkürzungen werden üblicherweise in der First Order Language (FOL) eingeführt?
Implikation: ( A ⊃ B ) für (¬A ⋁ B)
Logische Äquivalenz: (A ≡ B) für ((A ⊃ B) ⋀(B ⊃ A))
Tags: Einführung
Source:
11
Cardlink
0
Erläutere die Operatoren ⊭, ⊨ , ⊦ und ⊥.
Zeichen Bedeutung Beispiel Erklärung
falsch T ⊭⊥ aus T kann nichts falsches gefolgert werden
Ableitbarkeit/Folgerbarkeit a ⊦ b b kann aus a gefolgert werden
"ist erfüllt durch" a ⊨ b b wird durch a erfüllt
kann nicht gefolgert werden a ⊭ b b kann nicht aus a gefolgert werden
Tags: Einführung
Source:
12
Cardlink
0
Was ist der Scope einer Variable?
→Eine Variable ist gebunden, wenn sie hinter einem Quantifier steht

∀y. P(x) ∧ ∃x[P(y) ∨ Q(x)]

→erstes Auftreten von x ist frei
→restliche Vorkommen von x gebunden
→Vorkommen von y gebunden
Tags: Einführung
Source:
13
Cardlink
0
Was ist ein Satz?
= eine Formel ohne freie Variablen
→α [v/t] →Formel α, in der alle freien Vorkommen der Variable v durch t ersetzt werden

Bedeutung eines Satzes
→nicht eindeutig, da Symbole domänenabhängig
= Funktion der Interpretation der nicht-logischen Symbole
Tags: Einführung
Source:
14
Cardlink
0
Wie werden nicht-logische Symbole interpretiert?
  1. Die Welt besteht aus Objekten
  2. Für ein Prädikat P mit einer Stelligkeit 1 erfüllen einige Objekte P, andere nicht. Die Interpretation von P sagt, welche das sind. Dito für andere Stelligkeiten und Funktionssymbole
  3. Andere Aspekte der Welt spielen keine Rolle
Tags: Einführung
Source:
15
Cardlink
0
Was sind Interpretationen und wie werden sie notiert?
= ein Paar  J = ( D, I )
→D: Domäne, nichtleere Menge von Objekten
→I: Mapping der nichtlogischen Symbole auf die Objekte in D


I[P] ⊆ D × · · · × D .
n times
Tags: Einführung
Source:
16
Cardlink
0
Was sind parakonsistente Logiken?
klassiche Logik
aus einer falschen/widersprüchlichen Information kann jede beliebige Aussage gefolgert werden
→ in der Praxis nicht sinnvoll

parakonsistente Logik
möglichst sinnvolle Schlüsse aus inkonsistenten Wissensbasen ziehen
→ Behandlung der Inkonsistenz
Es gibt Formeln A, B, sodass gilt:
{A, ¬A} ⊭(L) B
Tags: Inkonsistenzbehandlung
Source:
17
Cardlink
0
Welche Eigenschaft hat eine (in)konsistente Wissensbasis?
Konsistenz
WB ist konsistent ⇔ WB ⊭⊥⇔ WB hat mindestens ein Modell

Inkonsistenz
WB ist inkonsistent ⇔ WB ⊨⊥⇔ WB hat kein Modell

Beispiel für inkonsistente Wissensbasen
{p, q, ¬q}, {p, q ∧ ¬ q}, …
Tags: Inkonsistenzbehandlung
Source:
18
Cardlink
0
Was ist der deduktive Abschluss einer Wissensbasis?
Th(T) = { A | T ⊦ A}

→Jede aus T folgerebare Aussage A ist bereits in T enthalten
= sämtliches implizites Wissen ist explizit vorhanden
Tags: Inkonsistenzbehandlung
Source:
19
Cardlink
0
Welche Anforderungen werden an eine parakonsistente Logik L gestellt?
  • erfüllt Prinzip der Parakonsistenz
  1. Jede Formel der Aussagenlogik ist auch eine Formel in L
  2. wenn T⊨(L) A dann auch T ⊨ A
  3. Wenn T konsistent, dann T ⊨(L) A gdw. T ⊨ A

Wenn Schluss in L möglich, dann muss er auch in klassischer Logik möglich sein
→ L ist strengere Aussagenlogik
Tags: Inkonsistenzbehandlung
Source:
20
Cardlink
0
Welche Ansätze zur Inkonsistenzbehandlung gibt es?
Theoriebasiert
  • Inkonsistenz wird auf Elementebene behandelt
  • →Wenn WB inkonsistent, betrachte konsistente Teilmenge T' ⊆ T


Logikbasiert
  • Inkonsistenz wird auf Formelebene behandelt
  • →Teilmenge der Folgerungen wird betrachtet
Tags: Inkonsistenzbehandlung
Source:
21
Cardlink
0
Was ist eine maximal konsistente Teilmenge?
Eine Teilmenge T' ist maximal konsistent, wenn
  1. T' ist konsistent
  2. für alle T'' sodass für T' ⊆ T '' ⊆ T kein konsistentes T'' existiert


MC(T) bezeichnet die Menge aller maximal konsistenten Teilmengen von T
Tags: Inkonsistenzbehandlung
Source:
22
Cardlink
0
Was ist die freie Basis und das freie Konsequent von T?
freie Basis S
=
(Durchschnitt aller maximal konsistenten Teilmengen von T)

freies Konsequent A
T ⊨(MC) A ⇔ S ⊨A
→A ist eine Folgerung, die sich aus S ergeben kann

Beobachtung bei Konsistenz
  • MC(T) = {T}
  • S= T
  • T ⊨ A
  • →Folgerungen die sich aus T ergeben, ergeben sich auch aus A
Tags: Inkonsistenzbehandlung
Source:
23
Cardlink
0
Welche Abwandlungen des theoriebasierten parakonsistenten Schließens gibt es?
Cautious Consequence
T ⊨(c) A gdw. S ⊨ A für alle S ∊ MC(T)
→A folgt aus T, wenn A aus jeder maximal konsistenten Teilmenge  folgt

Brave Consequence
T ⊨(b) A gdw. S ⊨ A für mind. ein S ∊ MC(T)
→A folgt aus T, wenn A aus zumindest einer maximal konsistenten Teilmenge folgt
→erlaubt inkonsistente Schlussfolgerungen
Tags: Inkonsistenzbehandlung
Source:
24
Cardlink
0
Was sind strukturierte Wissensbasen?
Unterteilung der Wissensbasis in sicheres und unsicheres Wissen:
KB = (S, U)
→ggf. weitere Hierarchiestufen
Tags: Inkonsistenzbehandlung
Source:
25
Cardlink
0
Was sind bevorzugte maximal konsistente Teilmengen?
Es gibt eine Strukturierte Wissensbasis mit T_1 .. T_n
→ Es wird die Maximalkonsistente Menge von T1 gebildet, dann von T2, T3 und so weiter

wenn F konsistent
BMC(KB) = {S  ∈ MC(F  ∪ H) | F  ⊆ S)
Tags: Inkonsistenzbehandlung
Source:
26
Cardlink
0
Was ist logikbasiertes parakonsistentes Schließen?
= Modelle Mod' (•) definieren die schwächer sind als klassische Modelle:

Mod'(T) ) ⊇ Mod(T)

→ weniger zulässige Ableitungen

  • Verwenden einer 3-wertigen Logik (true, false, u ("both"))
  • logische Inferenz mittels 3-wertiger Modelle die möglichst nah am klassischen 2-wertigen Modell sind
Tags: Inkonsistenzbehandlung
Source:
27
Cardlink
0
Wie ist eine formale 3-wertige Logik aufgebaut?
  • selbe Sprache wie für klassische Aussagenlogik
  • Interpretation: Funktion, die jeder propositionalen Konstante ein Element aus {0,1,u} zuordnet
Tags: Inkonsistenzbehandlung
Source:
28
Cardlink
0
Wie sieht die Wahrheitstabelle einer 3-wertigen Logik für ¬ aus?
¬  
1 0
0 1
u u
Tags: Inkonsistenzbehandlung
Source:
29
Cardlink
0
Wie sieht die Wahrheitstabelle einer 3-wertigen Logik für ∨
  aus?
1 0 u
1 1 1 1
0 1 0 u
u 1 u u
Tags: Inkonsistenzbehandlung
Source:
30
Cardlink
0
Wie sieht die Wahrheitstabelle einer 3-wertigen Logik für → aus?
1 0 u
1 1 0 u
0 1 1 1
u 1 0* u


*nicht logisch erklärbar. Wurde (wahrscheinlich) so definiert, damit mehr Gesetze gelten. Zu erwarten wäre ein u
Tags: Inkonsistenzbehandlung
Source:
31
Cardlink
0
Redefiniere die Begriffe wahr, falsch, erfüllbar, Modell und semantische Konsequenz für 3-wertige Logiken!
wahr
A ist wahr in m falls V^m(A) ∈ {1, u}

falsch
A ist falsch in m falls V^m(A) = 0

erfüllbar
A ist erfüllbar falls es ein m gibt, sodass V^m(A) ∈  {1,u}

Modell
m ist ein Modell von A falls V^m(A) ) ∈ {1,u}
Eine Interpretation m ist ein Modell einer Theorie T gdw. V^m(A)  ∈  {1,u}, für alle A ∈ T

semantische Konsequenz
A ist eine semantische Konsequenz von T, auch: T  |=³ A, falls jedes Modell von T auch ein Modell von A ist
Tags: Inkonsistenzbehandlung
Source:
32
Cardlink
0
Nenne einige Eigenschaften 3-wertiger Logiken!
  • jede implikationsfreie Theorie ist konsistent
  • es gilt die Deduktionseigenschaft: T  ∪ {A} |=3 B ⇐⇒ T |=3 (A ⊃ B)
  • ¬A ∨ B und A ⊃ B sind nicht äquivalent
Tags: Inkonsistenzbehandlung
Source:
33
Cardlink
0
Warum gibt es die Priests Logik?
  • reine 3-wertige Logik ist zu schwach um ein geeignetes Werkzeug zu sein
  • im Falle konsistenter Prämissen stimmt sie nicht mit klassischer Logik überein
  • →Minimierungsmethoden um Modelle "minimaler Undefiniertheit" zu betrachten

Beispiel
((p ∨ q) ∧ ¬p ⊭³ q,
→in klassischer Logik kann q gefolgert werden
→in 3-wertiger Logik: Model {p:u, q:0} → q wird nicht gefolgert
Tags: Inkonsistenzbehandlung
Source:
34
Cardlink
0
Was besagt die Priest-Logik?
  • es wird m ≤p n definiert, das als "m ist besser als n" zu lesen ist
  • gezählt wird die Anzahl der undefinierten Wahrheitswerte
  • →klassische Modelle sind immer minimal bzgl. ≤p→bei konsistenter WB liefert klassische und Priest-Logik dieselben Ergebnisse


T |=p A bedeutet:
jedes 3-wertige Modell von T das minimal bzgl. ≤p ist, ist ein 3-wertiges Modell von A
Tags: Inkonsistenzbehandlung
Source:
35
Cardlink
0
Welche weiteren Ansätze zur Inkosistenzbehandlung gibt es?
  • 4-wertige Logiken
  • Goal-directed inconsistency handling
  • Argumenationsframeworks
Tags: Inkonsistenzbehandlung
Source:
36
Cardlink
0
Was ist der Grundgedanke der Belief Revision?
= konsistente Wissensbasis KB soll um gesicherte Information A erweitert werden
  • A ist inkonsistent zu KB
  • neue Wissensbasis W soll entstehen, die A enthält, konsistent ist und das Wissen aus KB so wenig beeinflusst wie möglich

Verwandte Probleme
  • Belief Merging
  • Belief Contraction
Tags: Belief Revision
Source:
37
Cardlink
0
Was ist ein Belief Set?
  • deduktiv abgeschlossene Wissensbasis
  • →alles ableitbares Wissen bereits explizit vorhanden
  • ggf. unendliche Menge
Tags: Belief Revision
Source:
38
Cardlink
0
Welche Anforderungen werden an die Belief Revision gestellt?
  1. Wissensbasis soll nach Möglichkeit konsistent bleiben
  2. Ableitbares Wissen soll erhalten bleiben
  3. Der Verlust von Wissen soll minimiert werden
  4. "Unwichtigeres" Wissen sollte eher aufgegeben werden
Tags: Belief Revision
Source:
39
Cardlink
0
Was ist der Unterschied zwischen Expansion und Revision?
Revision
Vorgang der Belief Revision, also:
Aufbauen der Wissensbasis W und Entfernen von Inkonsistenzen

Expansion
einfaches Hinzufügen von A in KB
→klappt nur bei Konsistenz
Tags: Belief Revision
Source:
40
Cardlink
0
Nenne alle AGM-Postulate!
  1. W ⨢ A ist ein Belief Set
  2. →Revision muss eine Teilmenge der einfachen Expansion sein
  3. A  ∈ W ⨢ A
  4. W ⨢ A  ⊆ W + A
  5. Wenn ¬A  ∉ W , dann W + A ⊆ W ⨢A
  6. →Bei Konsistenz, dann sind Expansion und Revision identisch
  7. W ⨢ A  ̇ist inkonsistent gdw. A inkonsistent
  8. Wenn |= A ≡ B, dann W ⨢ A= W ⨢ B
  9. →Logisch äquivalente Formeln sollen zum selben Ergebnis führen
  10. W ⨢(A  ∧ B) ⊆ (W ⨢A)  + B.
  11. Wenn ¬B ∈ W ⨢ A, dann (W ⨢ A)  + B ⊆ W ⨢ (A ∧ B)


  • Die letzten beiden Postulate sind nicht ganz so wichtig und werden auch von einigen Ansätzen nicht eingehalten
  • Postulate erzwingen keine eindeutige konkrete Definition für ⨢
Tags: Belief Revision
Source:
41
Cardlink
0
Was ist das Epistemic Entrenchment?
Es muss entschieden werden, welches Wissen "weniger verankert" ist
→ verwenden einer totalen Präordnung  ≤

Beispiel
p  ≤ q
→ p ist weniger verankert als q

Anforderungen
  • Transitivität
  • Dominanz
  • Konjunktivität
  • Minimalität
  • Maximalität
Tags: Belief Revision
Source:
42
Cardlink
0
Was bedeutet Transitivität in der Epistemic Entrenchment?
p  ≤ q und q  ≤ r, dann p  ≤ r

Wenn p weniger verankert als q … dann p weniger verankert als r
Tags: Belief Revision
Source:
43
Cardlink
0
Was bedeutet Dominanz in der Epistemic Entrenchment?
Regel
wenn p ⊦ q, dann p ≤ q

Wenn q aus p gefolgert werden kann ist p weniger verankert als q
→Wenn q aufgegeben wird, muss p auch aufgegeben werden
Tags: Belief Revision
Source:
44
Cardlink
0
Was bedeutet Konjunktivität in der Epistemic Entrenchment?
Regel
p ≤ (p ∧ q) oder q ≤ (p ∧ q)

(p ∧ q) kann nur aufgegeben werden, indem man p oder q aufgibt.
Eine der Formeln also höchstens so verankert wie die Konjunktion

Tags: Belief Revision
Source:
45
Cardlink
0
Was bedeutet Minimalität in der Epistemic Entrenchment?
Regel
Wenn W konsistent, dann  p ∉ W gdw. p ≤ q für alle q

→Formeln die nichti m W enthalten sind, sind am wenigsten verankert
Tags: Belief Revision
Source:
46
Cardlink
0
Was bedeutet Maximalität in der Epistemic Entrenchment?
Regel
wenn p ≤ q für alle p, dann is q eine Tautologie

→Tautologien werden immer geglaubt, also am meisten verankert
Tags: Belief Revision
Source:
47
Cardlink
0
Was ist der Revisionsoperator?
das da: ⨢

→AGM-Postulate geben keine konkrete Definition des Operators vor, aber man kann zeigen:

  1. Jeder vollständige rationale Revisionsoperator wird durch eine epistemic entrenchment-Ordnung erzeugt
  2. Jeder durch eine epistemic entrenchment Ordnung erzeugte Revisionsperator ist vollständig rational
Tags: Belief Revision
Source:
48
Cardlink
0
Wie funktionieren die modellbasierten Ansätze zur Belief Revision?
  • es werden Modelle der Belief Sets betrachtet statt der Belief Sets selbst
  • die Modelle von W ⨢ A sollen eine Teilmenge der Modelle von A sein
  • → garantiert A ∈ W ⨢ A
  • Modell von A mit der geringsten symmetrische Differenz zu W wird ausgewählt
Tags: Belief Revision
Source:
49
Cardlink
0
Was ist die symmetrische Differenz?
formal: S∆T := (S \ T ) ∪ (T \ S).
→S ohne T vereinigt mit T ohne S

Informell: Die symmetrische Differenz zwischen zwei Interpretationen beinhaltet jene prop. Konstanten, die in genau einer der beiden Interpretationen wahr sind

Beispiel
m = p:1, q:0

n1 = p:1 q:1
n2 = p:0, q:1

m∆n1 = {q}
m∆n2= {p,q}
Tags: Belief Revision
Source:
50
Cardlink
0
Wie funktioniert der modellbasierte Ansatz nach Winslett?
  • Aufstellung der Modelle wie bei allen Ansätzen
  • Ermittlung des Minimums der symmetrischen Differenz für jedes Modell für W bzgl. der Teilmengeninklusion
  • →dieses Modell wird in W⨢A übertragen
  • Verletzt 4. AGM-Postulat:
  • Bei Konsistenz, dann sind Expansion und Revision nicht identisch

Beispiel
Mod(W) = p:1,q:1,r:0     p:1,q:1,r:1
Mod(A) = p:1,q:1,r:1     p:1,q:0,r:0

*∆ p : 1, q : 1, r : 1 p : 1, q : 0, r : 0
p:1,q:1,r:0 {r} {q}
p:1,q:1,r:1  ∅ {q,r}

→Minimum: {{q},{r}} und ∅
Problem, da leere Menge intendiert
Ursache: Minimum wird für jede Zeile berechnet statt global
Tags: Belief Revision
Source:
51
Cardlink
0
Wie funktioniert der modellbasierte Ansatz nach Satoh?
  • Anstelle der Berechnung der Distaznen für jedes einzelne m ∈ Mod(W) betrachte die Distanzen zu den Modellen global
  • →im Beispiel von Winslett wird nun nur {∅} akzeptiert


Verletzt 8. AGM-Postulat
Tags: Belief Revision
Source:
52
Cardlink
0
Was ist die Grundidee der Basisrevision?
  • Repräsentation des Belief State durch Endliche Formelmenge T (=Belief base)
  • Repräsentation der Präferenzen als Relation auf T
  • Belief Base T wird partiniert in T1, …, Tn
  • →Mengen mit niedrigerem Index haben höhere Priorität. Möglichst viele Formeln mit hoher Priorität sollen behalten werden
Tags: Belief Revision
Source:
53
Cardlink
0
Wie funktioniert die Basisrevision?
  • T⊥p ist die Menge aller maximalen Teilmengen von T, aus denen p nicht gefolgert werden kann
  • (T1, …, Tn) ⊥ p ist die Menge aller maximal bevorzugten Elemente von (T1 ∪ … ∪ Tn)  ⊥ p
  • Seien B und B'  ∈  (T1 ∪ …∪ Tn) ⊥ p. B wird bevorzugt vor B. gdw. es ein k gibt, sodass gilt:
  •      — B  ∩ Tk ist eine echte Obermenge von B'  ∩ Tk     — für 1 <= i <= k gilt: B  ∩ Ti = B'  ∩ Ti
  • erfüllt alle Postulate bis auf 8
  • man erhälte mehrere Lösungen S1 … Sn
  • Endergebnis: Th(T) + p = Th((S1^ v S2 …) ^ p)

Beispiel
T1: p ⊃ q
T2: p, q ⊃ r
T3: q ⊃ s
A: ¬r

S1 { p ⊃ q, p, q ⊃ s} ∪ {¬r}
S2:  { p ⊃ q,  q ⊃ r, q ⊃ s} ∪ {¬r}
fertiges Beliefset: Th[(S1^ v S2^) ^ ¬r]
Tags: Belief Revision
Source:
54
Cardlink
0
Was ist die Cut base Revision?
  • Nachteil der Baserevision: revidierte Wissensbasis kann exponentiell groß werden
  • Lösung: Nur vollständige Level T1 … Tn aus denen nicht ¬p hergeleitet werden kann, werden übernommen
  • Vorteil: einfache Repräsentation: T1 ∪ … ∪ Tj ∪ {p}
  • Nachteil: viel Information geht verloren


Tags: Belief Revision
Source:
55
Cardlink
0
Was ist die Linear base revision?
  • Wie bei der cut base revision werden nur komplette Level übernommen oder verworfen
  • es wird jedoch nicht beim ersten Level aufgehört, aus dem ¬p hergeleitet werden kann
  • auch höhere (= unwichtigere) Level werden übernommen, sofern konsistent zu p
  • Ergebnis ohne Präferenzen
Tags: Belief Revision
Source:
56
Cardlink
0
Was ist Diagnose und welche Arten gibt es?
= Identifikation eines vorliegenden Fehlers auf der Basis von …
  • Beobachtungen/Symptomen und
  • Hintergrundwissen über das System

Arten
  • abduktiv
  • konsistenzbasiert
Tags: Abduktion & Diagnose
Source:
57
Cardlink
0
Was ist die Grundidee der abduktiven bzw. konsistenzbasierten Diagnose?
Abduktive Diagnose
  • man kennt die Symptome von Fehlern und kann auf die Ursachen schließen

Konsistenzbasierte Diagnose
  • Annahme: Alle Komponenten arbeiten korrekt
  • außer dies führt zu Widersprüchen, dann minimale Menge an fehlerhaften Komponenten identifizieren
Tags: Abduktion & Diagnose
Source:
58
Cardlink
0
Welche Abkürzungen werden bei der Abduktion verwendet?
H .. Symptome von Fehlern
S .. beobachtete Symptome
N .. nicht aufgetretene Symptome
O .. Beobachtungen
F .. Menge von aufgetretenen Fehlern
59
Cardlink
0
Was funktioniert die abduktive Diagnose?
Gegeben
Informationen über
  • Wirkung von Fehlern H (→logische Implikationen)
  • beobachtete Symptome S (Atome)
  • nicht aufgetretene Symptome N (negierte Literale)

Gesucht
Erklärung für S, das heißt minimale Menge von Fehlern F, sodass
  • F ∪ H |= S
  • F ∪ H ∪ N konsistent
Tags: Abduktion & Diagnose
Source:
60
Cardlink
0
Wie funktioniert die konsistenzbasierte Charakterisierung?
Gegeben
Menge K von Komponenten und Informationen über
  • Wirkung/Verhalten der Komponenten im fehlerfreien Fall M
  • Beobachtungen O

Gesucht
  • minimale Menge K' an Komponenten, sodass die Annahme der Korrektheit aller Komponenten  in K\K' konsistent mit M ∪ O ist
Tags: Abduktion & Diagnose
Source:
61
Cardlink
0
Welche Schritte sind bei der konsistenzbasierten Diagnose auszuführen?
  1. Erkennen von Abnormalitäten/Konflikten
  2. Generieren und Testen von Hypothesen (→Kandidaten)
  3. Diskriminieren zwischen Hypothesen (Meßpunktauswahl)
Tags: Abduktion & Diagnose
Source:
62
Cardlink
0
Was ist die GDE?
= General Diagnostic Engine

  • modelliert Struktur von Schaltkreisen, um deren Verhalten vorherzusagen
  • ermittelt durch Constraint-Propagierung erwartete Werte
  • Nichtübereinstimmung mit gemessenen Werten initiiert Diagnose
Tags: Abduktion & Diagnose
Source:
63
Cardlink
0
Was ist ein Konflikt?
Menge von Komponenten K', sodass die Annahme des korrekten Verhaltens aller Elemente in K' zur Prognose eines Wertes führt, der im Widerspruch zur Beobachtung steht
Tags: Abduktion & Diagnose
Source:
64
Cardlink
0
Wie funktioniert die Konflikterkennung der GDE?
  • Erkennen, ob ein Konflikt vorliegt
  • System überprüft Prognosen erst, wenn alle Teilmenge der Annahmemenge A konfliktfrei sind
  • →nur minimale Konflikte werden erzeugt
  • in GDE realisiert mittels eines Assumption Based Truth Maintenance System (ATMS)
Tags: Abduktion & Diagnose
Source:
65
Cardlink
0
Wie funktioniert ein ATMS?
  • verwaltet Abhängigkeitsgraphen aus Basis der vom Problemlöser gelieferten justifications J
  • berechnet Labels L
  • Label des Knotens false enthält alle minimalen Konflikte

Input
  • aussagenlogische Hornklausen (justifications): Instanzen von Regeln, die das Diagnosesystem angewandet hat
  • Menge von Annahmen A (assumptions): Komponenten des zugrunde liegenden Systems, die als ok angenommen werden

Output
  • für jede Proposition p die Menge von Annahmen, unter denen p abgeleitet werden kann
Tags: Abduktion & Diagnose
Source:
66
Cardlink
0
Was ist ein Problemlöser?
  • verfügt über Modell des Systems, das Verhalten der Komponenten beschreibt
  • erfragt Daten vom Benutzer
  • wendet Regeln an, auf deren Basis Annahmen über die Korrektheit der Komponenten ermittelt werden
  • übergibt justifications an ATMS
  • erzeugt Hypothesen aus den minimalen Konflikten
Tags: Abduktion & Diagnose
Source:
67
Cardlink
0
Welche Elemente gibt es in einem ATMS-Abhängigkeitsgraph?
Prämisse: {{}} (Grundannahme)
Label: Menge L von Annahmemenge A, sodass A ∪ J |- k
Annahme: Label, zB.: {{Batterie}}
Knoten: Propositionen
eckig: Komponenten
Kanten: justifications
Kontradiktion: Knoten false
nogoods: Elemente des Labels von false

Tags: Abduktion & Diagnose
Source:
68
Cardlink
0
Welche Bedingungen gelten für Labels des ATMS-Abhängigkeitsgraphen?
sei n Knoten, {E1, … , En} seien Label

Korrektheit
  ∪ J |- n.

Konsistenz
nicht   ∪ J |- false (falls n ≠ false)

Vollständigkeit
wenn E ∪ J |- n, dann gibt es  mit  Teilmenge von E

Minimalität
es gibt keine  im Label, sodass  echte Teilmenge von 
Tags: Abduktion & Diagnose
Source:
69
Cardlink
0
Wie funktioniert das ATMS-Update?
Gegeben: Abhängigkeitsgraph mit korrekten Labels
Problemlöser liefert neue justification n1 ^ … ^ nk =>n

  1. berechne neue temporäre Labels für n
  2. = alle möglichen Kombinationen der Labels der nj
  3. eliminiere nogoods und subsumiere nichtminimale Annahmemengen
  4. propagiere ggfs. neues Label von n im Netz


Beispiel

e: {{A,B},{C}} e ist wahr, falls A,B gilt oder falls C gilt
f: {{A},{D}}  f ist wahr, falls A gilt oder falls D gilt
nogood{C,D}  C und D können nicht beide wahr sein
neue justification: e ∧ f => g

1. Schritt: alle Kombinationen der Labels von e und f: g:{{A,B},
{A,B,D},{C, A},{C, D}}
2. 2. Schritt: daraus nicht-minimale und nogoods weg: g:{{A,B},
{C, A}}

Label von false enthält gerade alle minimalen Konfliktmengen!
Tags: Abduktion & Diagnose
Source:
70
Cardlink
0
Wie funktioniert die Hypothesengenerierung in der GDE?
  • auf Basis der minimalen Konflikte werden Hypothesen über mögliche Diagnosen ermittelt
  • aus jedem Konflikt muss mindestens eine Komponente in der Hypothese enthalten sein
  • wird neue Konfliktmenge K1 gefunden, sodass H ∩ K1 = ∅, so wird für alle k aus K1  H ∪ {k}  anstelle von H als neue Hypothese verwendet

Hypothese
eine Hypothese ist eine minimale Menge H von Komponenten, so dass H ∩ K ≠ ∅ für alle Konflikte K (minimal corvering set)

Beispiel
Konflikte: {A,B}     {B,C}     {A,D}
Hypothese: {A,B } oder {A,C} oder {B,D}
keine Hypothese: {A,B,D} →nicht minimal
{C,D} →erster Konflikt nicht abgedeckt
Tags: Abduktion & Diagnose
Source:
71
Cardlink
0
Welche Arten der Hypothesenanzahl gibt es?
Single fault Assumption
= Hypothese enthält genau 1 Element
  • liefert eindeutiges Ergebnis
  • oft unrealistisch, da defekte Komponente zu anderen Defekten führen kann etc

Multiple fault assumption
  • erhebliche kombinatorische Probleme:
  • bei nur 1 Fehlermode 2^n mögliche Fehler (n= Anzahl an Komponenten)


→häufig Hierarchien und Ranking von Hypothesen aufgrund von Wahrscheinlichkeiten
Tags: Abduktion & Diagnose
Source:
72
Cardlink
0
Warum sind Fehlermodelle wichtig?
Beispiel mit Birne:
Es sind Aussagen möglich wie: Die Birne brennt, wie sie defekt ist.
→Wissen notwendig, dass eine defekte Birne nicht brennen kann um unsinnige Konflikte auszuschließen
Tags: Abduktion & Diagnose
Source:
73
Cardlink
0
Was ist der Ansatz von Defaults und welche Arten gibt es?
  • klassische Aussagen trifft Aussagen über alle Elemente oder gar keine
  • Realität ist aber komplexer und wird oft durch allgemeine Aussagen beschrieben


Arten von Defaults
  • allgemeine Aussagen →normalerweise
  • Gegenteil nicht bekannt →keine Info, dass man keinen Bruder hat
  • Konventionen →außer eine andere information ist bekannt
  • Trägheit → ?!
Tags: Nichtmonotones Schließen
Source:
74
Cardlink
0
Was sind CWA?
= Closed World Assumption
  • es gibt mehr negative als positve Fakten
  • →Annahme, dass Wissensbasis die Welt vollständig beschreibt


Beispiel
  • Zugfahrplan
  • nur Züge aufgeführt, die es gibt
  • es gibt auch ganz viele Züge, die es nicht gibt
  • →Annahme, dass Zugfahrplan vollständig
Tags: Nichtmonotones Schließen
Source:
75
Cardlink
0
Wie ist die Konsistenz von CWA?
  • wenn KB nur Atome enthält, dann ist KB ∪ Negs immer konsistent
  • dito, wen KB Konjunktionen oder negative Disjunktionen:
  • If KB contains (¬p ∨ ¬q). Add both ¬p, ¬q

Problem
wenn KB |= (α ∨ β), aber  KB|≠ α und KB|≠ β}→Negs = {¬p, ¬q}
→KB ∪ Negs ist inkonsistent

Lösung (GCWA)
  • wende CWA-Atome nur auf nicht-kontroverse Atome an:
  • Negs = {¬p | If KB |= (p ∨ q1 ∨ ... ∨ qn) then KB |= (q1 ∨ ... ∨ qn)

wenn KB konsistent:
→KB ∪ Negs ist konsistent
→alles was ableitbar ist, ist auch durch CWA ableitbar
Tags: Nichtmonotones Schließen
Source:
76
Cardlink
0
Was ist (nicht-) monotones Schließen?
Monotones Schließen
If KB |= α, then KB' |= α, for any KB ⊆ KB'
→Wird die Wissensbasis erweitert, dann kann auch immer mehr (oder genausoviel) abgeleitet werden

Nicht-Monotones Schließen
Durch eine Erweiterung der Wissensbasis kann es passieren, dass nun weniger abgeleitet werden kann

KB |=c α, KB ⊆ KB', but KB' |≠c α
Tags: Nichtmonotones Schließen
Source:
77
Cardlink
0
Welche Ansätze des Nichtmonotonen Schließens gibt es?
  • Minimal Entailment/Circumscription
  • Default-Logik
  • Autoepistemic Logic
Tags: Nichtmonotones Schließen
Source:
78
Cardlink
0
Was ist Circumscription?
∀x[Bird(x) ∧ ¬Ab(x) ⊃ Flies(x)]
→Alle Vögel, die nicht abnormal sind, fliegen

So können allgemeine Aussagen (Vögel können fliegen) aber auch Ausnahmen definiert werden: Ab(penguin)

Problem
Werden alle möglichen Modelle ermittelt, sind auch immer alle abnormalen Fälle enthalten
→I[AB] (=Vorkommen von AB) sollte minimiert werden

Achtung: verschiedene Ab-Prädikate für jede Abnormalität (fliegen, fressen, Nestbau, …) notwendig!

→Minimierung muss kein eindeutiges Modell hervorbringen
Tags: Nichtmonotones Schließen
Source: Folie 189/190
79
Cardlink
0
Welches Problem verursacht Circumscription?
Knowledge Base
∀x[Bird(x) ∧ ¬Ab(x) ⊃ Flies(x)]
∀x[Penguin(x) ⊃ Bird(x) ∧ ¬Flies(x)]

→ KB |= ∀x[Penguin(x) ⊃ Ab(x)]

Problem
  • Minimierung von Ab minimiert auch Pinguine:
  • KB |=≤ ∀x¬Penguin(x)


Lösung
fixed Prädikat Q das konstant bleibt, wenn P minimiert wird
1. [P] ⊆ [P], for every P ∈ P            Ab predicates
2.[Q] = [Q], for every Q ∉ Q           fixed predicates

→cannot conlude ¬Penguin(tweety) by default!
Tags: Nichtmonotones Schließen
Source:
80
Cardlink
0
Was ist der Grundgedanke von Reiters Default Logik?
Beispiel
Quäker sind normalerweise Pazifisten.
Republikaner sind normalerweise keine Pazifisten.
Nixon ist Quäker und Republikaner.

→Ist Nixon Pazifist?

  • es gibt mehrere akzeptable Mengen
  • Reiter nennt diese Extensionen

Sichtweisen
  1. jede Exetension ist interessant
  2. Schnittmenge aller Extensionen
Tags: Nichtmonotones Schließen
Source:
81
Cardlink
0
Wie sind Reiters Default-Theorien aufgebaut?
= Paar (D,W)
W: Menge von Formeln (= sicheres Wissen)
D: Menge von Inferenzregeln der Form:
A:B1, …, Bn/C
sprich: wenn A ableitbar, alle  ¬Bi nicht, dann leite C ab

Default-Theorien generieren Extensionen

Tags: Nichtmonotones Schließen
Source:
82
Cardlink
0
Nenne die erwünschten Eigenschaften der Extensionen in Reiters Default Logik!
Eine Extension E …

  1. soll sicheres Wissen W enthalten
  2. soll (klassisch) deduktiv abgeschlossen sein
  3. alle anwendbaren Defaults sollen angewandt worden sein
  4. soll keine unbegründeten Formeln enthalten, d.h. für jedes p ∈ E gibt es einen gültigen Default-Beweis


Hinweis
Extensionen sind nicht definierbar als minimale Menge, welche die ersten 3 Kriterien erfüllen
Tags: Nichtmonotones Schließen
Source:
83
Cardlink
0
Welche Teilklassen von Reiters Default-Regeln gibt es?
  • Normale Defaults
  • Super-normale Defaults
  • Semi-normale Defaults
Tags: Nichtmonotones Schließen
Source:
84
Cardlink
0
Was sind normale Defaults?
  • Existenz von Extensionen garantiert
  • Semimonotonie
  • →wenn E Extension von (D,W), dann gibt es E' von (D  ∪ D', W) mit E ⊆ E'

Form
Tags: Nichtmonotones Schließen
Source:
85
Cardlink
0
Was sind Super-normale Defaults?
  • Extensionen sind Theoreme von W zusammen mit maximal W-konsistenter Teilmenge von Default-Konklusionen

Form
Tags: Nichtmonotones Schließen
Source:
86
Cardlink
0
Was sind semi-normale Defaults?
  • Prioritäten lassen sich codieren

Form
Tags: Nichtmonotones Schließen
Source:
Flashcard set info:
Author: David
Main topic: Informatik
Topic: Wisensbasierte Systeme
School / Univ.: Universität Leipzig
City: Leipzig
Published: 20.02.2013
Tags: Brewka
 
Card tags:
All cards (86)
Abduktion & Diagnose (16)
Belief Revision (20)
Einführung (15)
Inkonsistenzbehandlung (20)
Nichtmonotones Schließen (14)
Report abuse

Cancel
Email

Password

Login    

Forgot password?
Deutsch  English