skip to main content

kiesler.at
WissensbasierteSysteme
Immutable Page | Raw Text | Print View | History

FrontPage > TuWienMitschriften > WissensbasierteSysteme

http://www.kiesler.at/static/wiki/wissensbasierte_systeme.jpg

2005-03-07 (Montag)

Die heutige erste Vorlesung war im wesentlichen eine Wiederholung aus bereits bekanntem Stoff. Kurz und prägnant hat Prof. Egly Inferenz und Logik definiert. Neben den Zielsetzungen der KI wurden Inferenz-Formen (Schließen), Logische Systeme, die Klassische Logik und die Aussagenlogik umfassend zusammengefasst.

Die Prädikatenlogik ging sich nur Ansatzweise aus und wird am Mittwoch fortgeführt. Sogar Monthy Python kam vor!

2005-03-09 (Mittwoch)

1

Nach der Wiederholung des vorgestrigen Stoffs haben wir uns heute wie geplant die PraedikatenLogik genauer angesehen. Im Anschluss daran waren die DescriptionLogics drann, als einführendes Beispiel die FL^-. Diese kann man sehr gut für die Abbildung von Logik-Hierarchien verwenden.

Die Wiederholung begann mit den Themen Syntax und Semantik. Ohne das eine macht das andere keinen Sinn. Außerdem gab es einen Ausflug in die Vergangenheit des Informatik-Studiums. Für Informatiker sind im Zusammenhang Wissensbasierte Systeme drei Dinge interessant:

  • die SLD Resolution
  • Das Sequential Kalkül
  • Tableaus

Unterrichtet wird das ganze nach zwei ganz verschiedenen Vorgehensweisen. Einerseits nach der KUICH Methode, die auch ich genossen habe:

  • Monoid: Tupel mit EPSILON, ...
  • Mathematisch definiert
  • NIE Kalkül

Diese Methode ist gut für Mathematiker geeignet, jedoch für Informatiker weniger. Diese sind an Kalkülen interessiert, welche beispielsweise später von Prof LEITSCH unterrichtet wurden. Hier steht das Kalkül im Vordergrund:

  • Prädikaten Logik / Resolution
  • Aussagenlogik / Resolution
  • Sequential kalkül

Ein heißer Tip für die mündliche Prüfung:

"Wie sieht Syntax aus?"

  • sie hat eine Signatur (besser als "Alphabet")
  • es gibt eine Menge Aussagen mit logischen Variablen
  • Formeln: eine Menge aller Wohlgeformten Formeln
  • Jede Aussagenvariable ist Formel
  • Damit kann man neue Formeln aus bereits bestehenden durch Rekursion bauen
  • Formeln sind Rekursiv prüfbar -- für Informatiker wichtig!
  • Zuerst immer Parsen

"Wie ist die Semantik für Aussagenlogik definiert?"

A -> C -> D allgemeingültig?

  • Variablen mit werten belegen (Durch Interpretationsfunktion)
  • Dann: Geänderte Formeln mit Wahrheitswerten (nur mehr Wahr/Falsch) -> Wahrheitstabellen!

Problem bei Aussagenlogik: Wissensrepräsentation (keine Quantoren -> Prädikatenlogik)

Herr TOMPITS wird uns bei Gelegenheit von Komplexitätsklassen erzählen, die logischen Programme machen wir später.

Heute:

2005-03-15 (Dienstag)

Wiederholung

Was braucht man für eine Logik? Syntax und Semantik!

Syntax: Formaler Aufbau (was ist eine gültige Formel?)
Semantik: Interpretation

Eine Domain besteht aus

  • nichtleerer Menge DELTA^I und
  • Interpretationsfunktion DELTA^.I

Konzept map-to subset DELTA^I
Rolle map-to subset DELTA^I x DELTA^I

Atomare Konzepte

Atomare Rollen: Binäre Relation zwischen zwei Konzepten

Formeln in FL^-

  • Atomare Konzepte
  • Konzept und Konzept
  • EXIST Rolle (nicht Dual zu FORALL!)
  • FORALL Rolle

KEINE Negation!
KEIN Oder!

Konsequenz: Erweiterung auf Formeln!

Logisches Und: Schnittmengenbildung
FORALL / EXISTS: Schema

ist FL^- erfüllbar? Wie wähle ich meine Domain?

DELTA ist immer da, jedoch nicht immer gut erfassbar!

Subsumptionskonzept: C SUBSUMTION D < = > in jeder Domain / Funktion:

- Interpretation von C
- Teilmenge von D

Domain muß wurscht sein, Rolleninterpretation auch!

Struktureller Algorithmus

- Zuerst Normalform (Klammern weg, dann Quantorenmanagement)

Zuerst Modell M? Nachher auch Modell M (ist zu beweisen)

Welche Struktur hat C_i?

Konjunktion / Existenz / All / Atom

"Funktion Description Logics"

FL^-
ALC
ALCI (Inverse)

FL^-: Erweiterung!

Mehr Aussagekraft / More Expressive Power

-> First Order Logic, Unentscheidbar!

Balance?

FL^- je nach Problemstellung irgendwas dazu (was brauch ich / was wäre angenehm)?

p-space vollständig (vs. p-time - Verhältnis Eingabelänge, polynominal time in deterministischer Touringmaschine)

Komplexitätsklassen:
- Zeitkomponente
- Speicherkomponente (p-space, log space, x-space, ... -- Zeitbedarf wurscht!)

np: polynominell auf nicht-deterministischer Touring Maschine. Ob auf deterministischer Touringmaschine auch ist ungewiss.

Wurscht, ob p-vollständig: deterministische/nicht deterministische Touringmaschine

Mehr Ausdruckskraft => Mehr Zeitbedarf!

Potentielle Fragen

Semantik von ALC?

  • Definition und/oder/nicht
  • Atomare Rollen/Konzepte
  • Interpretation und/oder/nicht


Last modified 2005-04-02 18:22 by rck