Vorlesung "Wissensbasierte Systeme" für die Fachrichtung Wirtschaftsinformatik (WI01) im Wintersemester 2003/04

Klausurtermin: Freitag, 20. Februar 2004, 10 - 11.30 Uhr, Raum LO-1.01 (WI01A) und LO-1.02 (WI01B)

Vorlesungsinhalte:

• Einführung in Themen und Methoden der KI
• Lernziele: Ziele, Ansatz, Teilgebiete, Grundmethoden der Künstlichen Intelligenz kennenlernen.
• 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.
• Einführung in Expertensysteme
• Lernziele: 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 .
• Als Handouts ausgeteilt: Startkapitel von Puppe, Startkapitel von Socher-Ambrosius/Heinsohn.
• 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.
• Suche als schwache Problemlösemethode
• Suche als Problemlösemethode, Idee & Begriffe, Beispiel Weinkrügeproblem.
• Uninformierte systematische Suchverfahren: Tiefensuche, Breitensuche, Idee des iterative Deepening.
• Informierte Suchverfahren: Idee der Heuristik, Bestensuche, 3x3-Schiebepuzzle (Idee der "besseren" Heuristik).
• 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 die Prinzipien der Branch&Bound-Suche, der dynamischen Programmierung und der heuristischen Suche mit Restkostenunterschätzung vorgestellt. Alles zusammen ergibt den A*-Algorithmus. Die Darstellung folgte dem Buch von Winston. War alles recht knapp gehalten.
• Eine gute Darstellung, die ebenfalls exakt 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 wurden ganz knapp die Kombinatorischen Optimierungsprobleme vorgestellt, deren Eigenschaften (Lösungsweg ist irrelevant, Endzustand enthält alle relevante Information, Optimierungsziel wird unter globaler Randbedingung gestellt, optimistische [unterschätzende] zulässige Schätzfunktion existiert nicht) die schönen Eigenschaften der A*-Algorithmenfamilie hinfällig werden lassen - als Ansätze wurden ganz knapp die genetischen Algorithmen (evolutionary computing) und das simulierte Auskühlen (simulated annealing) angesprochen.
• Constraints zur Verbesserung der Suche
• Begriffe und Definitionen am Beispiel n-Damen Problem
• Ganz kurz: Constraint-Graph und Merkmale von Constraints für die Wissenrepräsentation
• einfacher Backtracking-Algorithmus mit seinen Ineffizienzen (Bedeutung der Variablenauswahl und lokal schon inkonsistenter Werte am Beispiel); Suchbäume für Constraint-Probleme
• allgemeine Heuristiken für Variablenauswahl und Werteauswahl am Beispiel Färben einer Landkarte
• Constraint-Propagierung zur Herstellung lokaler Konsistenz schon vor der Suche (Beispiel Kreuzworträtsel): Idee, Bedeutung, Vorgehensweise
• Anmerkungen zum praktischen Einsatz (Konfiguration, Scheduling, Arbeitsplanung, Timetabling-Probleme, dort Möglichkeiten für domänenspezifische Heuristiken, Constraint-Programmiersprachen und -libraries)
• die Darstellung war eng 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).
• Wissensrepräsentation und Inferenz: Aussagenlogik
• Definitionen und Grundlagen, Syntax, Semantik, Interpretation, Modell, Erfüllbarkeit, Tautologie, Semantische Folgerung
• Resolution als Kalkül (Beispiel Abtrageverfahren)
• Basisalgorithmus zur Resolution + Problematik der Effizienz und Ideen zur Effizienzsteigerung
• als Handout wurde das Kapitel 4 aus dem Buch von Socher-Ambrosius/Heinsohn verteilt
• Wissensrepräsentation und Inferenz: Von PL1 zu PROLOG
• Handouts gibt's als PDF (298 KB); das Thema war allerdings in der Vorlesung nur sehr kurz abgehandelt
• 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; am Beispiel hatten wir Resolutionsbäume für Hornlogik-Programme gesehen
• Prolog zum Rumspielen: Hier ist die Homepage zu SWI-Prolog von der Uni Amsterdam
• weitere Links stehen auf den Folien
• Beispiele zu Prolog als Programmiersprache hatten wir nur kurz skizziert; Abarbeitungsmechanismus kurz durchgegangen; kurz die Merkmale der Sprache und typische Einsatzgebiete skizziert
• 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)
• Beispiel zu OPS5: nur die einfache Blocks World; MYCIN
• 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
• weiterführende Erläuterungen zum Einsatz solcher Methoden im Semantic Web (Ontologien zur Informationsintegration)
  
• 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.
• Eine gute Darstellung wurde von Gerald Reif im Rahmen seiner Diplomarbeit an der TU Graz elektronisch zur Verfügung gestellt.  Das Stück zum Thema Bayes-Theorem findet sich hier.
• In der Vorlesung wurde i.w. die Darstellung von Tolk benutzt: 1 Symptom + 1 Diagnose, 1 Symptom + n Diagnosen, n Symptome + m Diagnosen. Der Beitrag von Tolk findet sich in den Handouts.
• Wir hatten das Beispiel der Autos auf dem FH-Parkplatz durchgerechnet, ferner das Kampfpanzer-Beispiel von Tolk.
• 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.
• Methode 3: Fuzzy-Logic für vage Begriffe.
• Wir hatten die Idee der Fuzzy Sets und der logischen Verknüpfungen besprochen und dann sehr knapp die Fuzzy Control im Grundprinzip angesprochen. Kernaussagen dazu sind 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.
• Diagnosesysteme & Schluß
• 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, Erklärungskomponenten 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
• ü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 der Vorlesung "Konzepte der AI" an der TU Wien oder
• Überblick zum Data Mining von Knut Hinkelmann einmal anschauen (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 :-)