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 16:22 by rck