Wissensbasierte Systeme KE 1&2

• Trennung Wissensbasis vs. Wissensverbeitung

  • = Wissen über Problembereich vs. Verarbeitung des Wissens (= anwendungsabhängige Problemlösungskomponente)

• Folgen:

  • klare Trennung Problembeschreibung & Problemlösung

  • Wissen über Anwendungsbereich ist direkt ausdrückbar

• Expertensystem ist Computersystem, das menschlichen Experten nachbildet

  • bzgl. Wissen und Schlussfolgerungsfähigkeit

  • immer auf Bereich bezogen

• Art WS

• Wissen stammt von Experten

  
  

Eigenschaften von Experten:

• überdurchschnittliche Problemlösefähigkeiten

• verwerten Erfahrung

• verwenden Heuristiken

• haben Allgemeinwissen

• handeln intuitiv richtig, ohne Entscheidung begründen zu können

• lösen Probleme auch mit unvollständigem oder unsicherem Wissen

• sind selten und teuer

• schwankende Leistung

• oft allein nicht ausreichend (mehrere Experten nötig)

• Expertenwissen kann verloren gehen

• Expertenwissen oft nicht vermittelbar/ weitergebbar

• Fachwissen ist nicht gleich Expertenwissen

  • Erfahrung kommt hinzu

  • andere Struktur, Inhalt, ..

Eigenschaften von Expertensystemen:

• verwendet Wissen eines oder mehrerer Experten für Problemlösung in speziellem Bereich

• expliziite, deklarative Darstellung des Wissens

• Experte unterstützt beim Transfer seines Wissens ins System

• Wissen im System leicht zu erweitern und zu warten

• Wissen leicht lesbar dargestellt

• verwendet unsicheres Wissen

• natürliche und anschauliche Benutzerschnittstelle

• Ergebnisse werden erklärt/ begründet

• klare Trennung zwischen Faktenwissen und Problemlöseheuristiken

• einmal erworbenes Wissen kann in verwandten Problembereichen wiederverwendet werden

• Fallspezifisches Wissen

  • Wissen über aktuellen Problemfall

    • z.B. Beobachtungen, Untersuchungsergebnisse

  • auch evidentielles Wissen/ Evidenz genannt

• Regelhaftes Wissen

  • enhält:

    • Bereichsbezogenes Wissen

      • Erfahrungswissen

      • theoretisches Fachwissen

    • Allgemeinwissen

      • generelle Problemlösungsheuristiken

      • Optimierungsregeln

      • Wissen über Objekte und Beziehungen in realer Welt

1.a) Wissensbasis

1.b) Arbeitsspeicher für fallspezifisches Wissen

2) Wissenverarbeitungskomponente

3) Wissenserwerbskomponente

4) Erklärungungskomponente

5) Dialogkomponente

• a) Schnittstelle für Experten zum Aufbau und Entwicklung des Systems

• b) Benutzerschnittstelle für Anwender

• 1. Problembeschreibung

• 2. Wissensquellen

  • z.B. Datenbanken, Bücher, menschliche Experten

• 3. Design

• 4. Entwicklungswerkzeug

  • zur Not Programmiersprache

• 5. Entwicklung eines Prototypen

• 6. Testen eines Prototyps

• 7. Verfeinerung und Generalisierung

• 8. Wartung und Pflege

Inferenz = Relation zwischen (Repräsentation von) vorgegebenen Wissen und (Repräsentation von) abzuleitendem Wissen

(W, B) \in R

• W = gegebenes Wissen

• B = neues Wissen

• R = Inferenzrelation

  • zwischen W und B

  • wenn B aus W gefolgert werden kann

  • binäre Relation

Schlussfolgerung geht nur auf formaler Repräsentation

Syntax

• Aufbau der Sprache

Semantik

• Begriffe

• geben Sätze der Repräsentationssprache Bedeutung

• ob Satz in geg. Welt wahr ist oder nicht

1. W gegeben -> Prognose B treffen

2. B gegeben -> Erklärung W finden

3. W und B gegeben -> Testen, ob B logisch aus W folgt

1. Qualifikationsproblem

• reale Welt durch Formel W umfassend beschreiben

• \= alle Vorbedingungen anführen, die nötig sind (oder die dagegen sprechen könnten)

• Bsp. Fliegender Vogel (Flügel gebrochen, Pinguin, ...)

2. Charakterisierung von R

• z.B. unpräzise Beschreibungen

• probabilistische Aussagen

• spezifisch räumliches Wissen

1. Deduktion

• aus W B schließen

• Regel vorhanden

2. Induktion

• aus wiederholter Beobachtung von B auf W schließen

• Regel ermitteln

3. Abduktion

• Erklärung für Beobachtung

• auch von B auf W -> aber einmalig

• Regel vorhanden

• häufig in Medizin und Technik

• W muss nicht notwendig wahr sein

• daneben gibt es auch:

  • kein plausibler Schluss

  • wenn Konklusion nicht aus den Prämissen folgt

pragmatische Anforderung an Schlussfolgerungen

ohne notwendig mathematisch formale Korrektheit vorauszusetzen

• Schlussfolgerungen werden nicht zurück genommen

  • einmal bewiesen, steht unumstößlich fest

  • nur Menge der beweisbaren Aussagen wächst monoton

• Syntax und Semantik mathematisch präzise definiert

  
  

Beispiele:

• Aussagenlogik

• Prädikatenlogi 1. Stufe

1. Signaturen

• Menge von Namen = Symbole mit bestimmter Stelligkeit

  • können zu komplexeren Namen verbunden werden

  • können klassifiziert werden

  • z.B.

    • 0, 1, a, +, < in der Mathematik

    • kann_fliegen, soll_erfolgen

• geht nur um Syntax

  • mögliche Assoziationen sind egal

• in Aussagenlogik: "Aussagenvariablen"

  • Menge von (nullstelligen) Namen

  • \Sigma_{AL} = { Fieber, Krank, Arbeitsunfähig}

    • eine Aussagenlogik mit drei Aussagevariablen

• in Prädikatenlogik: null- und mehrstellige Funktions- und Prädikatensymbole

• logisches System hat Menge von Signaturen

2. Formeln

• wieder nur syntaktische Ebene

• drücken Dinge über Welt aus

• wohlgeformt = entspricht den Regeln

• rekursiv aufgebaut

  • aus atomaren Formel mit Junktor komplexere Formeln bilden

• in Aussagenlogik

  • atomare Formeln

  • komplexere Formeln werden mit Junktoren gebildet

• in Prädikatenlogik

  • wie Aussagenlogik

  • auch Individuenvariablen

  • Quantifizierungen

• -> Wissensbasis W

  = Menge von Formeln über \Sigma

  • für gegebene Signatur \Sigma

  • \latex W \subseteq Formel(\Sigma)

3. Interpretationen

• semantische Ebene

• Verbindung zwischen syntaktischer Ebene und Objekten der repräsentierten Welt

• Aussagenlogik:

  • Aussagenvariable steht für Aussage

  • Aussage ist sprachliche Form, die wahr oder falsch ist

    • zweiwertigkeit ist charakteristisch für Aussagenlogik/ klassische Logiken - nur {true, false}, bzw. {1, 0}

    • keine anderen Wahrheitswerte

    • wofür A steht ist egal

      • zählt nur, ob true oder false

  • Belegung

    • Wahrheitswert einer Aussagenvariable

• Intepretation

  = Bezeichnung von Belegung in allgemeinen logischen Systemen

  • Zuordnung von Namen der Signatur \Sigma zu Elementen und ihren Beziehungen innerhalb der Welt

  • gibt willkürlichen Namen ihre Bedeutung in der Welt

  • int(\Sigma) = Menge aller Interpretationen der Signatur \Sigma

4. Erfüllungsrelation

• Verbindung zwischen syntaktischer Ebene der Formeln und semantischer Ebene der Interpretationen

  • besagt, wann eine Formel in einer Interpretation gilt

  • ob, Formel F in Interpretation I wahr oder falsch ist

• wahrheitsfunktional

  • Interpretation eines Junktors als Funktion

  • z.B. Abbildung von zwei Wahrheitswerten auf Wahrheitswert bei "und" in Aussagenlogik

    • muss wahr ergeben

    • \latex \vDash vs \nvDash

      • wenn wahr vs. falsch

• \latex \vDash_\Sigma \subseteq Int(\Sigma) \times Formel(\Sigma)

  • zwischen Interpretationen und Formeln definiert

• logische Folgerung

  • Erfüllungsrelation zwischen Formeln

  • \latex F \vDash_\Sigma G

  • bedeutet: jede Interpretation die F erfüllt, erfüllt auch G

• Konjunktion ("und")

• Disjunktion ("oder")

• Implikation ("wenn ... dann ...")

  • \latex \rightarrow

• materiale Implikation

  • Name für Implikation in klassischen Logiken (Aussagen- & Prädikatenlogik)

  • \latex \Rightarrow

• Negation ("nicht")

  • \latex \neg

[F]_I Wahrheitswert von F unter Interpretation I

[-]_I: Formel(\Sigma) -> BOOL

wahrheitsfunktional:

• Interpretation der Junktoren

• jeder Junktor wird durch Funktion interpretiert

Interpretation I erfüllt Formel F, genau dann wenn Wahrheitswert in I wahr ist

andere Ausdrücke für "I erfüllt F"

• F gilt in I

• F ist wahr für I

• I ist ein (\Sigma-)Modell von F

1) erfüllbar

• konsistent, Konsistenz

• gdw. Mod_\Sigma(F) != \emtpyset

  • also wird von min. einer Interpretation erfüllt

2) unerfüllbar

• widersprüchlich, inkonsistent, Kontradiktion

• gdw. Mod_\Sigma(F) = \emptyset

  • also wird von keiner Interpretation erfüllt

  • Formel ist nicht erfüllbar

3) allgemeingültig

• Tautologie

• Mod_\Sigma(F) = Int(\Sigma)

  • also wird von jeder Interpretation erfüllt

  • Formel ist nicht falsifizierbar

4) falsifizierbar

• gdw. Mod_\Sigma(F) != Int(\Sigma)

  • wird von min einer Interpretation nicht erfüllt/ falsifiziert

Besonderheiten für Aussagenlogik & Prädikatenlogik 1. Stufe:

• 5) Formel ist allgemeingültig, wenn Negation unerfüllbar ist

• 6) Formel ist erfüllbar, wenn ihre Negation falsifizierbar ist

• eine Formelmenge F \subseteq Formel(\Sigma)

• Cn(F) = F

• Cn(F) bzw. F heißen Theorien

• eine Theorie ist ein Fixpunkt des Operators Cn

• gilt für Aussagenlogik und PL1-Formeln

• fundamentale Beziehung zwischen logischer Folgerung und Implikation

• erlaubt logische Folgerung auf den Begriff der Allgemeingültigkeit zurückzuführen

• F |= G gdw. |= F => G

  • das |= nach gdw. ist wichtig für Allgemeingültigkeit

= Menge von logischen Axiomen und Inferenzregeln

Zweck: syntaktische Ableitungsrelationen |- zwischen Formeln definieren

• Relation |- soll semantische Folgerelation |= möglichst gut nachbilden

Axiome sind:

• Menge von elementaren Tautologien = positiver Kalkül

• Menge von elementaren Widersprüchen = negativer Kalkül

= Menge von Vorschriften

• um aus Formeln weitere Formeln abzuleiten

• \frac{F1, ..., Fn}{F}

  • bedeutet: aus F1 bis Fn kann F abgeleitet werden

  • F1 bis Fn sind die Bedingungen

  • F ist die Schlussfolgerung

Arten:

1. modus ponens (MP)

• also wenn F vorliegt und F => G gilt, kann man G annehmen

  
  

1. modus tollens (MT)

• Umkehrung des modus ponens

1. log_und-Einführung (\land-Einf)

• aus Gültigkeit von zwei Formeln kann man auf deren Konjunktion schließen

1. log_und_Elimination (\land-Elim)

• also aus Konjunktion auf ein Konjunktionsglied schließen

ist F aus F1, ..., Fn ableitbar durch Anwendungen von Inferenzregeln eines Kalküls K, schreibt man:

• F1, ..., Fn |- F

1. korrekt

   , wenn durch Kalkül definierte Ableitungen auch semantische Folgerungen sind

1. vollständig

   wenn alle semantischen Folgerungen dadurch abgeleitet werden können

aus Unerfüllbarkeit einer Formel(menge) lässt sich semantische Folgerbarkeit schließen

F, G sind aussagenlogische Formeln oder geschlossene PL1-Formeln

Widerlegungsvollständigkeit

• mit R aus jeder unerfüllbaren Formel einen elementaren Widerspruch ableiten

• R soll die Unerfüllbarkeit einer Formelmenge durch Ableitung eines Widerspruchs zeigen

• die Ableitungsrelation |-_R soll aus unerfüllbaren Formeln einen elementaren Widerspruch ableiten

• elementarer Widerspruch wird als Quadrat dargestellt

• M ist entscheidbar

  • gdw. es gibt einen Algorithmus der für jedes x angibt ob x in M oder x not in M

• M ist unentscheidbar

  • gdw. M ist nicht entscheidbar

• M ist semi-entscheidbar

  • es gibt einen Algorithmus der für jedes x aus M angibt, dass x \in M

  • Algorithmus muss für ein x \notin M nicht terminieren

Beispiele

• Aussagenlogik ist entscheidbar

  • z.B. mit Wahrheitstafeln

• Allgemeingültigkeitsproblem der Prädikatenlogik 1. Stufe ist unentscheidbar

  • d.h. Menge der allgemeingültigen PL1-Formeln ist nicht entscheidbar

• Menge der unerfüllbaren PL1-Formeln ist unentscheidbar

• Menge der falsifizierbaren PL1-Formeln ist unentscheibar

• Menge der erfüllbaren PL1-Formeln ist unentscheidbar

• Menge der allgemeingültigen PL1-Formeln ist semi-entscheidbar = rekursiv aufführbar

• Menge der unerfüllbaren PL1-Formeln ist semi-entscheidbar

• aber:

  • Menge der falsifizierbaren PL1-Formeln ist nicht rekursiv aufzählbar

  • Menge der erfüllbaren PL1-Formeln ist nicht rekursiv aufzählbar

• es folgt:

  • in Prädikatenlogik 1. Stufe ist die Frage, ob semantische Folgerung F |= G gilt nur semi-entscheidbar, aber nicht entscheidbar

1. Aussagenlogische Signatur

   = Aussagevariablen (= eine Menge von Bezeichnern)

   
   

2. Aussagenlogische Formeln

   1. atomare Formeln

      • nur eine Aussagenvariable

   2. Kombination aus ein oder zwei atomare Formeln

      • a) Negation

      • b) Konjunktion

      • c) Disjunktion

      • d) Implikation

      • e) Koimplikation, Äquivalenz (A genau dann wenn B)

(links stärker):

• Neg, Konj, Disj, Impl, Koimpl

• zwei Formel F und G sind (semantisch) äquivalent

  • \latex \equiv (Gleichheitszeichen mit drittem Strich)

  , wenn für alle Interpretationen I gilt:

• "aus semantisch äquivalenter Teilformen erhält man eine semantisch äquivalente Formel"

• F, G seien äquivalente Formeln

• H eine Formel, in der F mindestens zweimal vorkommt

• dann ist H \equiv H'

• wobei H' aus H gewonnen wird, indem man F durch G ersetzt

Vokabular kann ausdrücken:

1. Objekte (Zahlen, Menschen, Farben)

2. Funktionen auf den Objekten (z.B. Nachfolger)

3. Aussagen (wie Aussagenlogik)

4. Eigenschaften von Objekten (z.B. groß, gelb, usw.)

5. Relationen zwischen Objekten (z.B. Großvater von, kleiner als)

PL1-Signatur \Sigma = (Func, Pred)

• Menge Func von Funktionen

• Menge Pred von Prädikatssymbolen

• jedes Symbol in den Mengen hat bestimmte Stelligkeit (s >= 0)

• Stelligkeit 0 = Konstante

  • in Signatur gibt es immer mindestens eine Konstante

• /

  • = Bezeichung für Funktions- oder Prädikatensymbol

  • = Stelligkeit (Anzahl der Argumente

  • z.B.

    • Primzahl/ 1

    • Bruder / 2

    • teilerfremd / 2

= weist Namen einer Signatur \Sigma Bedeutungen über Menge von Objekten zu

Regeln für Zuweisung zwischen Funktions-/Prädikatensymbolen der Signatur zu Funktions-/Prädikatensymbolen des Universums

1. Nullstellige Funktionsymbole durch Objekte/ Individuen des Universums (= der betrachteten Welt) interpretiert

   • je Konstante einer Signatur eine Interpretation

   • verschiedene Konstanten können durch dasselbe Objekt interpretiert werden

     • Max und Moritz können in einer Interpretation unterschiedliche Individuen sein

     • in einer anderen Interpretation dasselbe Element in U bezeichnen

2. Ein- und mehrstellige Funktionssymbole durch Funktionen interpretieren

3. Nullstellige Prädikatensymbole wie Aussagenvariablen der Ausagenlogik

   • Interpretation weist ihr Wahrheitswert zu

4. Einstellige Prädikatensymbole durch Teilmengen des Universums interpretieren

   • Teilmenge von U ist einstellige Relation über U

   • z.B. einstellige Prädikatensymbol gelb gibt Menge aller Dinge, die gelb sein sollen

5. mehrstellige Prädikatensymbole durch Relationen der entsprechenden Stelligkeit über U interpretieren

   • z.B. 2-stelliges Prädikatsymbol "Großvater" als durch zweistellige "Großvater-von-Beziehung" interpretieren

gibt es in Aussagenlogik nicht

ist funktionaler Ausdruck

• mit Funktionssymbolen der Signatur gebildet

• durch Objekte des Universums interpretiert

Def Terme

• Menge Term_\Sigma(V)

• über Signatur \Sig = (Func, Pred)

• und Menge V von Variablen

• ist kleinste Menge mit Elementen gemäß:

• Grundterm

  • Element aus Term_\Sigma(\emptyset)

    • also ein Term ohne Variablen

  • Term_\Sigma ist ide Menge der Grundterme

erlauen Negation von Quantoren in quantifizierte AUssage hineinzuziehen, so dass Negationszeichen nur vor Atomen steht

Punkt 3 ist wichtig - aber Achtung:

• allquantor nur bei Konjunktion nach außen ziehbar

  • nicht bei Disjunktion

• existenzquantor nur bei disjunktion

  • nicht bei Konjunktion

Punkt 4: Reihenfolge ist auch wichtig

• Bsp. Lieben(x, y) -> x liebt y

  • jeder liebt jemanden vs.

  • Es gibt jemanden, den jeder liebt

• Formel F heißt geschlossen, wenn es keine freie Variablen darin gibt

• Allabschluss, wenn alle Variablen mit Allquantoren auftreten

1. "Für alle" Instantiierungsregel

• aus Formel mit allquantifizierten Variablen Instanz der Formel ableiten

• indem man Variable durch beliebigen variablenfreien Term t ersetzt

  • jedes freie Auftreten von x in F durch t ersetzen

• ist wie Instanzen (aus Universum) mit Konjunktionen in Formel einsetzen

1. "Es gibt"-Instanziierungsregel

• ist wie Instanzen mit Disjunktionen in Formel einsetzen

1. Pränexform = alle Quantoren stehen außen

2. verneinungstechnische Normalform

   • Formel in Pränexform

   • nur Konjunktion, Disjunktion und Negation als Junktor

   • Negation nur unmittelbar vor Atomen

1. bereinigte Formel erstellen

   • keine Variable sowohl frei als auch gebunden

   • hinter allen Quantoren stehen unterschiedliche Variablen

   • Umbenennungen (5. der Transformationen anwenden)

2. Junktoren => und <=> beseitigen

   • durch Äquivalenzen 11 und 12

   • ggf. Schritt 1 noch einmal ausführen

3. Negationszeichen bis vor Atome schieben

   • mit de Morgan'schen Gesetzen

   • Satz der doppelten Negationen

4. Quantoren nach außen schieben

   • Regeln 2 und 3

• nicht im Geltungsbereich eines Allquantors

  • Existenzquantor weglassen

  • quantifizierte Variable wird durch neue Konstante ersetzt

    • "Skolemkonstante"

    • ist c eine Konstante, ist P(c) die Skolemisierung von \exists x P(x)

• im Geltungsbereich eines Allquantors

  • ersetzen durch Skolemfunktion

  • \exists x durch Term f(y1, ..., yn) ersetzen

    • y ist allquantifizierte Variable

    • f muss neues Funktionssymbol sein

    • z.B. \forall y \exists x P(x,y) wird zu \forall y P(f(y),y)

  • weitere Beispiele: Bild 3_56_skolem

• erfüllbarkeitsäquivalent

  • vollständige Skolemisierung einer Funktion

  • aus Formel F wird F'

  • F ist erfüllbar gdw. F' ist erfüllbar

• weitere Schritte zu oben dazu:

  • 5. Alle Existenzquantoren durch Skolemisierung entfernen

  • 6. Allquantoren weglassen

    • alle Variablen sind allquantifiziert

• Mengendarstellung der konjunktiven Normalform

• innere Mengen von Literalen heißen Klauseln

• die gesamte Menge der Klauseln heißt Klauselmenge

Klauselform:

Substitution

• Grundinstanz

  • wenn \sigma(t) keine Variable enthält

• Komposition von zwei Substitutionen

  • r o s(t) = r(s(t))

• identische, leere Substitution

  • id = {}

  • id(t) = t

• Variablenumbenennung

  • Substitution die alle Variablen in ihrem Definitionsbereich injektiv auf die Variablen abbildet

def Unifikator

allgmeinster Unifikator (mgu)

Formel G wird negiert zu Formelmenge F hinzugefügt

dann wird unerfüllbarkeit von F \land \neg G gezeigt

• also Ziel = elementaren Widerspruch zeigen, der leerer Klausel entspricht

• leere Klausel {} als Quadrat darstellen

• kann man leere Klausel ableiten, ist K unerfüllbar

somit ist F |= G bewiesen

• Resolutionskalkül ist dann korrekt und wiederlegungsvollständig

arbeitet auf Formeln in Klauselform

• Beispiel:

Resolutionsregel

• überm Strich sind Elternklauseln

• abgeleitete Klausel unterm Strich heißt Resolvente

• Literale L und \neg L sind Resolutionsliterale

• einzige Regel des Resolutionskalküls für Aussagenlogik

• (PL1 braucht auch Faktorisierung)

  • Terme mit identischen Variablen L und \neg L wird von L und \neg L' ausgegangen

• volle Resultionsregel:

• \sigma ist allgemeinster Unifikator von L und L'

• Elternklausel eines Resolutionsschrittes haben keine gemeinsamen Variablen

  • z.B. durch Variablenumbenennung erreichen

1. disjunktive Normalform

   Disjunktiv: K1 v ... v Kn

   • DNF

   • K sind Konjunktionen von Literalen

2. konjunktive Normalform

   Konjunktiv: D1 /\ ... /\ Dn

   • KNF

   • Dn sind Disjunktionen von Literalen