Vorlesung "Wissensbasierte Systeme" für die Fachrichtung Informationstechnik (TI97) im Sommersemester 2000

<...pagetobecompleted:-)...>

Vorlesungstermine:

• Montag, 03. April 2000 9.00 - 13.00 Uhr (KI-Einführung, XPS-Einführung)
• Montag, 10. April 2000 9.00 - 13.00 Uhr (Suche, Constraints)
• Montag, 17. April 2000 9.00 - 13.00 Uhr (Constraints, A-Logik)
• Montag, 08. Mai 2000 9.00 - 13.00 Uhr (Von PL1 zu PROLOG)
• Montag, 22. Mai 2000 9.00 - 13.00 Uhr (Vorwärtsregeln)
• Montag, 29. Mai 2000 9.00 - 13.00 Uhr (Frames & Semantische Netze, Unsicherheit & Vagheit)
• Montag, 05. Juni 2000 9.00 - 13.00 Uhr (Diagnose, Ausblick, Closing)

• Überblick Themen und Techniken der KI (2h)
• Motivation und Grundansatz, Teilgebiete und Basistechniken
• Überblick Aufbau und Ziele von Expertensystemen (2h)
• 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
• Schwache Problemlösemethoden: Suche (4h)
• Problembeschreibung als Suchproblem (Beispiel Färbeproblem, Weinkrüge, Schach)
• Uninformierte, systematische Suchverfahren: Tiefensuche, Breitensuche, Iterative Deepening
• Informierte, heuristische Suche (Beispiel Schiebepuzzle)
• Heuristische Suche mit Kosten: A*-Algorithmus (Beispiel Traveling Salesman), Optimalität bei zulässiger, optimistischer Schätzfunktion
• Charakteristik (Randbedingung + Optimierung, Suchweg irrelevant, Zielzustand enthält vollständige Lösungsinformation) und Problematik (zulässige Schätzfunktion häufig nicht zu finden, exponentielle Suchkomplexität) kombinatorischer Suchprobleme (Beispiel Rucksackproblem), Lösungsansätze angedeutet (Bergsteigeverfahren, genetische Algorithmen, Simulated Annealing)
• Schwache Problemlösemethoden: Constraints (3h)
• Begriffe und Definitionen am Beispiel n-Damen Problem
• Constraint-Graph und Merkmale für die Wissenrepräsentation am Beispiel Pausenbrotkonfigurierung
• 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)
• Zusammenspiel von Auswahlheuristiken und Propagierung am n-Damen-Beispiel
• Anmerkungen zum praktischen Einsatz (Konfiguration, Scheduling, Arbeitsplanung, Timetabling-Probleme, dort Möglichkeiten für domänenspezifische Heuristiken, Constraint-Programmiersprachen und -libraries)
• Wissensrepräsentation und Inferenz: Aussagenlogik (4h)
• Definitionen und Grundlagen, Syntax, Semantik, Interpretation, Modell, Erfüllbarkeit, Tautologie, Semantische Folgerung
• Resolution als Kalkül (Beispiel Abtrageverfahren, Beispiel Diebe im Hotel)
• Basisalgorithmus zur Resolution + Problematik der Effizienz und Ideen zur Effizienzsteigerung (Löschen tautologischer und subsumierter Klauseln, allgemeine Heuristiken, Tiefensuchaspekte, Hintergrundtheorien)
• Wissensrepräsentation und Inferenz: Von PL1 zu PROLOG (6h)
• Handouts gibt's hier als Postscript und da als PDF.
• Prolog zum Rumspielen: Hier ist die Homepage zu SWI-Prolog von der Uni Amsterdam
• weitere Links stehen auf den Handouts
• Beispiele zu Prolog: Familienbeispiele, Fibonacci-Zahlen, Symbolisches Differenzieren
• Vorwärtsregelsprachen (4h)
• Handouts dazu in PDF
• 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" (auf der CLIPS-Homepage ist allerdings auch umfassende Dokumentation zu finden)
• Beispiele zu OPS5: Pendler & Arbeitslose, Fibonacci-Zahlen
• Frames und Semantische Netze (2h)
• Darstellung i.w. übernommen aus Vorlesungen von Dr. Knut Hinkelmann (FH Solothurn, CH) an der Uni Kaiserslautern und der FH Wiesbaden
• Handouts als PDF
• Zum Nachlesen: z.B. bei Gottlob
• Unsicherheit und Vagheit (3h)
• außer einer kurzen Übersicht konnten wir aus Zeitgründen nur die Sicherheitsfaktoren aus MYCIN besprechen
• Handouts als PDF
• die Darstellung dazu folgt der von Hinkelmann, da die Sicherheitsfaktoren mit MYCIN eingeführt wurden, kann das Buch von Jackson ebenso als Referenz herangezogen werden
• weitere wichtige Verfahren (wie Fuzzy-Logic, Bayes-Theorie, Evidenztheorie nach Dempster-Shafer) werden bei Puppe kurz angerissen, bei Socher-Ambrosius & Heinsohn, M.M. Richter oder Russel & Norvig im Detail beschrieben
• Diagnose
• Handouts als PDF (4.6 MB)