Vorlesung "Wissensbasierte Systeme"
für die Fachrichtung Informationstechnik
im Wintersemester 2004/5 (IT02)
Vorlesungstermine:
- Montag, 27. September 2004 / 08.15 Uhr - 12.30 Uhr
- Montag, 11. Oktober 2004 / 08.15 Uhr - 12.15 Uhr
- Montag, 18. Oktober 2004 / 08.15 Uhr - 12.00 Uhr
- Mittwoch, 20. Oktober 2004 / 13.30 Uhr - 17.15 Uhr
- Montag, 25. Oktober 2004 / 08.15 Uhr - 12.00 Uhr
- Montag, 08. November 2004 / 08.15 Uhr - 12.00 Uhr
- Montag, 15. November 2004 / 08.15 Uhr - 12.00 Uhr
- Überblick Themen und Techniken der KI
- Motivation und Grundansatz, Teilgebiete und Basistechniken
- Die Darstellung in der Vorlesung verwendet Folien von
Hättenschwiler und von Hinkelmann.
- Eine Obermenge dessen, was wir in der Vorlesung hören
werden, findet sich im folgenden
PDF-File (ca. 400 KB).
- Wer weitergehendes Interesse am Thema hat, kann sich
beispielsweise auch einmal die Überblicksfolien
von Prof. Gottlob (TU Wien )
anschauen.
- Überblick Aufbau und Ziele von
Expertensystemen
- Definitionsversuch, Merkmale typischer Aufgabenstellungen,
Klassifikation von Aufgabenstellungen (analytisch - synthetisch,
automatisch - assistierend - überprüfend)
- Anwendungsgebiete (Diagnose, Klassifikation, Konfiguration,
Planung, Design; Tutoring, Entscheidungsunterstützung,
Datenanalyse, Prozeßkontrolle)
- Grundansatz (Wissensrepräsentation + Inferenz +
Problemlösemethode) und generische Architektur
- Meine Folien zum Thema als PDF-File
(118 KB, Quellen: M.M. Richter; Hinkelmann; Socher-Ambrosius &
Heinsohn; AA).
- Zum Nachlesen: Eine gute Darstellung wurde von Gerald Reif im
Rahmen seiner Diplomarbeit an der TU Graz elektronisch zur
Verfügung gestellt. Dort findet sich als Bestandteil eine
komplette Einführung in Expertensysteme, die den Stoff unserer
Veranstaltung in großen Teilen überdeckt. Eine Kopie
dieser Darstellung
gibt's hier . Relevant hiervon für uns zuerst einmal die
Teilkapitel 6.1 bis 6.6.
- Schwache Problemlösemethoden: Suche
- Problembeschreibung als Suchproblem (Beispiel Weinkrüge,
Schach)
- Uninformierte, systematische Suchverfahren: Tiefensuche,
Breitensuche, Iterative Deepening
- Informierte, heuristische Suche (Beispiel Schiebepuzzle)
- Die Algorithmen und Beispiele zum ersten Teil stammten aus
dem Buch von Socher-Ambrosius/Heinsohn. Dazu gibt es folgenden
(allerdings weit umfassenderen) Foliensatz
(PDF, 98 KB) von Rolf Socher-Ambrosius (relevant so etwa die
Seiten 9-22).
- Fragestellung der Suche mit Kosten und Optimierungsziel:
Beispiel Graphensuche (kürzester Weg). An diesem Beispiel wurden
ganz knapp die Prinzipien der Branch&Bound-Suche, der
dynamischen Programmierung und der heuristischen Suche mit
Restkostenunterschätzung vorgestellt. Alles zusammen ergibt den
A*-Algorithmus.
- Eine gute Darstellung, die am Buch von Winston orientiert
ist, wurde von Gerald Reif im Rahmen seiner Diplomarbeit an der TU
Graz elektronisch zur Verfügung gestellt. Das Stück
zum Thema Suche zur Problemlösung findet sich hier. Eine lokale
Kopie dieses Kapitels habe ich hier.
- Als weitere Komplikation wurde die Problemklasse der
kombinatorischen Optimierungsprobleme identifiziert (Merkmale,
Beispiele, Komplexität). Hier kann der Ansatz des A*-Verfahrens
nicht mehr greifen, weil man die zulässige optimistische
Schätzfunktion nicht mehr findet. Lösungsansätze haben
entweder das Problem der lokalen Optima usw (Beispiel Hill-Climbing)
oder bauen häufig Elemente der randomisierten Suchen ein. In
aller Kürze wurden die Ideen der genetischen Algorithmen und
des Simulated Annealing angesprochen.
- Schwache Problemlösemethoden:
Constraints
- Begriffe und Definitionen am Beispiel n-Damen Problem
- einfacher Backtracking-Algorithmus mit seinen Ineffizienzen
(Bedeutung der Variablenauswahl und lokal schon inkonsistenter Werte am
Beispiel)
- allgemeine Heuristiken für Variablenauswahl und
Werteauswahl
- Constraint-Propagierung zur Herstellung lokaler Konsistenz
schon vor der Suche (Beispiel Kreuzworträtsel)
- Anmerkungen zum praktischen Einsatz (Konfiguration,
Scheduling, Arbeitsplanung, Timetabling-Probleme, dort
Möglichkeiten für domänenspezifische Heuristiken,
Constraint-Programmiersprachen und -libraries)
- die Darstellung war am Buch von Socher-Ambrosius/Heinsohn
orientiert
- Zum Weiterlesen: Eine gute Darstellung wurde von Gerald Reif im Rahmen
seiner Diplomarbeit an der TU Graz elektronisch zur Verfügung
gestellt. Dort findet sich als Bestandteil eine komplette
Einführung in Expertensysteme, die den Stoff unserer
Veranstaltung in großen Teilen überdeckt. Eine knappe
Einführung zur Idee der Constraints
als Repräsentationsformalismus findet sich hier (offensichtlich
stark am Buch von Puppe orientiert).
- viele Links zu Grundlagen und einige Beispiele für die
Anwendung von Constraints finden sich in den Lehrveranstaltungen der
TU München, z.B. bei Slim
Abdenadher
- Wissensrepräsentation und Inferenz:
Aussagenlogik
- Definitionen und Grundlagen, Syntax, Semantik,
Interpretation, Modell, Erfüllbarkeit, Tautologie, Semantische
Folgerung
- Resolution als Kalkül (Beispiel Abtrageverfahren)
- die Darstellung folgte Kapitel 4 aus dem Buch von
Socher-Ambrosius/Heinsohn
- KI-Programmierung: Von PL1 zu PROLOG
- Handouts hier als PDF
(298 KB, Quellen: i.w. Hinkelmann; AA; wird so in jedem Buch zur
Logik für Informatiker eingeführt)
- das Thema konnte allerdings in der Vorlesung nur SEHR
oberflächlich überflogen werden
- Ideen waren: "Hochziehen" der A-Logik auf den komplexeren
Repräsentationsapparat der PL1; Übertragung der Inferenz mit
Resolution (korrekt und vollständig, Unifikation kommt hinzu, nur
noch semi-entscheidbar); dann wiederum Einschränkung der
Syntax aus Effizienzgründen: Horn-Logik; damit ist man bei der
logischen Grundlage der Programmiersprache Prolog
- Prolog zum Rumspielen: Hier ist die Homepage zu
SWI-Prolog von der Uni Amsterdam
- weitere Links stehen auf den Folien
- KI-Programmierung:
Vorwärtsregelsprachen
- Handouts dazu in PDF (199 KB,
Quellen: Jackson; Hinkelmann; M.M. Richter; AA)
- wer etwas mit Produktionsregeln herumspielen möchte,
sollte sich einmal die CLIPS-Homepage
anschauen
- die "klassische" Darstellung von OPS-5 findet sich immer noch
bei Peter Jackson "Expertensysteme"
- Beispiel zu OPS5: nur die einfache Blocks World
- Frames und Semantische Netze
- Handouts
als PDF (252 KB, Quellen: Hinkelmann; AA)
- Zum Nachlesen: z.B. bei Gottlob
- auch dies ganz gut von Gerald Reif beschrieben: da
ist der Link
- heutige Relevanz: Netzformalismen entsprechen in ihrem
Grundansatz der Internet-Ressourcenbeschreibung mit RDF;
Frame-Sprachen bilden die Basis, solche Inhaltsbeschreibungen im Web
mit mehr Semantik zu versehen (Stichwort RDF Schema. Ein paar Links
zur Idee des Semantic Web (intelligente Netzdienste und -agenten
für Endanwender und im E-Commerce):
- Unsicherheit und Vagheit
- Übersicht: verschiedene Arten und Ursachen von
Unsicherheit und Vagheit in wissensbasierten Systemen. Wichtig ist
es, das Spektrum und die Anwendungsbereiche von Unsicherheit und
Vagheit zu kennen, von einigen Ansätzen etwas gehört zu
haben und zu wissen, daß diese Ansätze auch
Einsatzvoraussetzungen, Stärken und Schwächen haben.
- Methode 1: Bayes Theorem.
- Methode 2: Sicherheitsfaktoren in Regeln. Die
Darstellung dazu folgt der von Hinkelmann (Folien weiter unten). Da
die Sicherheitsfaktoren mit MYCIN eingeführt wurden, kann das
Buch von Jackson ebenso als Referenz herangezogen werden.
- Methode 3: Fuzzy-Logic für vage Begriffe.
- Eine excellente Darstellung der Fuzzy Control findet sich
am Fuzzy Logic Laboratorium Linz-Hagenberg. Kernaussagen dieser
Darstellung wurden im folgenden
Foliensatz eingebunden.
- Zahlreiche weitere Verfahren und Erweiterungen existieren
(wie Bayes-Netze oder die Evidenztheorie nach Dempster-Shafer). Diese
werden bei Puppe kurz angerissen, bei Socher-Ambrosius &
Heinsohn, M.M. Richter oder Russel & Norvig im Detail
beschrieben
- Abschluß
- kurze Wiederholung der Dinge, die wir bis jetzt durchgenommen
haben
- Zusammenfügung der Teile am Beispiel Expertensysteme
für die Diagnose
- kurzer Abriss, was alles dazugehört, aber nicht in die
Vorlesung gepaßt hat (Wissensakquisition,
XPS-Projektmanagement, XPS-Software-Technik etc)
- kurzer Ausblick, was es in der KI sonst noch gibt, aber nicht
mehr in die Veranstaltung gepaßt hat (Maschinelles Lernen,
Data Mining, Fallbasiertes Schließen, Subsymbolische KI -
Neuronale Netze, Intelligente Agenten, Wissensmanagement, Semantic
Web)
- das alles in aller Kürze auf
diesen Folien (1.3 MB).
- Zum Weiterlesen: wer noch etwas Interesse an Anwendungen der
vorgestellten oder weiterführender Methoden hat, kann sich z.B.
die entsprechenden Foliensätze
- Beispiel für die Grenzen der heutigen
KI-Implementierungen: Automatische
Dialogsysteme :-)