Vorlesung "Wissensbasierte Systeme" 
für die Fachrichtung Informationstechnik 
im Sommersemester 2002 (TI99)

Vorlesungstermine:

• Donnerstag, 21. März 2002    13.00 - 16.15 Uhr (KI-Einführung, XPS-Einführung)
• Montag, 25. März 2002              9.00 - 13.00 Uhr (Suche, Constraints)
• Montag, 08. April 2001               9.00 - 13.00 Uhr (Aussagenlogik)
• Montag, 22. April 2001               9.00 - 13.00 Uhr (etwas PL1 + Prolog, Vorwärtsregeln, Semantische Netze + Frames)
• Montag, 06.   Mai 2001               9.00 - 13.00 Uhr (Exkurs Ontologien&Semantic Web, Unsicherheit + Vagheit)
• Montag, 27.   Mai 2001               9.00 - 13.00 Uhr (Zusammenfassung - Bau von Diagnosesysteme, Schlußbemerkungen)

• Ü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).
• 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)
• Wissensrepräsentation und Inferenz: Von PL1 zu PROLOG (das hatten wir nur in aller Kürze gestreift)
• Handouts gibt's hier als Postscript  (1.8 MB) und da als PDF (298 KB)
• Prolog zum Rumspielen: Hier ist die Homepage zu SWI-Prolog von der Uni Amsterdam
• weitere Links stehen auf den Handouts
• Vorwärtsregelsprachen
• Handouts dazu in PDF (199 KB)
• 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)
• Frames und Semantische Netze
• 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
• auch dies ganz gut von Gerald Reif beschrieben: da ist der Link
• Exkurs: Semantic Web
• wir hatten einen Exkurs zum Thema Ontologien gemacht. Die umfassendere Motivation (nicht die einzige, aber eine wichtige) dafür ist das Semantic Web - dazu hier einige Links
• Methoden der Wissensrepräsentation (aus den Themen Frames & Semantische Netze herkommend; Ontologien) und der Inferenz (Regeln) finden in den letzten Jahren zunehmendes Interesse als Grundlage der Vision eines "Semantic Web" für intelligente Netzdienste und -agenten für Endanwender und im E-Commerce
• folgende Links sind gute Einstiege in diese Thematik:
• das Spektrum der Wissenschaft schreibt über's Semantic Web
• Ralf Möller von der FH Wedel motiviert die Thematik schön aus den Themen der KI-Wissensrepräsentation: Einleitung zum Thema Semantic Web
• eine umfassende grundlegende Einführung in das ontologiebasierte Wissensmanagement mit einem Fokus auf Karlsruher Projekten gibt Prof. Rudi Studer
• einen weiteren Rahmen zum Thema Ontologien und Semantic Web baut dann Prof. Dieter Fensel
• Unsicherheit und Vagheit
• Übersicht: verschiedene Arten und Ursachen von Unsicherheit und Vagheit in wissensbasierten Systemen. Eine sehr kurze, aber die wesentlichen Punkte umfassende Einführung zu Bayes, Fuzzy, Sicherheitsfaktoren und anderen Techniken kann man bei Andreas Tolk finden. 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. 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.
• Methode 2: Sicherheitsfaktoren in Regeln. 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. In der Kürze der Zeit können wir das Thema nur anreißen. Etwas mehr Details finden sich in den Handouts als PDF.
• Methode 3: Fuzzy-Logic für vage Begriffe. Auch hier können wir das Thema nur anreißen. Eine umfassende Einführung zur Fuzzy Control findet sich am Fuzzy Logic Laboratorium Linz-Hagenberg. Kernaussagen dieser Darstellung wurden im folgenden Foliensatz eingebunden.  Hinter diesem Link findet sich ein Beispiel (inklusive einer vollständigen Einführung) für die Nutzung von Fuzzy-Methoden zur Entscheidungsunterstützung in der Raumplanung.
• 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)
• 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 einmal anschauen:
• über Planung und Scheduling mit Such- und Constraint-Methoden von Jürgen Dorn,
• über Wissensbasierte Konfiguration mit Regeln oder Constraints von Markus Stumptner  oder
• über Definition und Anwendungen Intelligenter Agenten von Robert Baumgartner aus den Vorlesung "Konzepte der AI" an der TU Wien oder
• Überblick zum Data Mining von Knut Hinkelmann  (380 KB)
• Einführung in das Fallbasierte Schliessen von Ralph Bergmann (200 KB)
• Einige DFKI-Beiträge zum Thema Wissensmanagement (2.2 MB !)
• Beispiel für die Grenzen der heutigen KI-Implementierungen: Automatische Dialogsysteme :-)