Modellierung wissensintensiver Probleme Benno Stein
Inhalt I. Einführung
Ziele Wie entwickelt man Softwaresysteme zur Lösung von wissensintensiven Aufgaben
Bemerkungen:
Literatur Künstliche Intelligenz
Literatur
Literatur
Kapitel MK:I I. Einführung
Künstliche Intelligenz Was ist Intelligenz?
Künstliche Intelligenz Was ist Intelligenz?
Künstliche Intelligenz Was ist Intelligenz?
Künstliche Intelligenz Was ist Intelligenz?
Künstliche Intelligenz Intelligenzbegriff
Künstliche Intelligenz Was ist Künstliche Intelligenz?
Künstliche Intelligenz Was ist Künstliche Intelligenz?
Künstliche Intelligenz Was ist Künstliche Intelligenz?
Bemerkungen:
Kapitel MK:I I. Einführung
Starke KI versus Schwache KI KI ist der Versuch, auf Computern intelligentes Verhalten nachzubilden.
Starke KI versus Schwache KI Turing’s Szenario: Turing Test [Turing 1950]
Starke KI versus Schwache KI Weizenbaum’s Szenario: Eliza [Weizenbaum 1966]
Starke KI versus Schwache KI Schank’s Szenario: Restaurant-Geschichten [Schank 1977]
Starke KI versus Schwache KI Schank’s Szenario
Starke KI versus Schwache KI Searle’s Szenario: chinesisches Zimmer [Searle 1980]
Bemerkungen:
Starke KI versus Schwache KI Searle’s Szenario
Starke KI versus Schwache KI Behauptung der Vertreter der Starken KI:
Starke KI versus Schwache KI Behauptung der Vertreter der Starken KI:
Starke KI versus Schwache KI Behauptung der Vertreter der Starken KI:
Starke KI versus Schwache KI Hat „echtes“ Verstehen mit Bewusstsein zu tun?
Kapitel MK:I I. Einführung
Geschichte der Künstlichen Intelligenz 1956 Geburtsstunde. Sommerseminar in Dartmouth.
Einschub: Blocks World Anordnung:
Geschichte der Künstlichen Intelligenz 1965 – 1975 Romantische Periode.
Geschichte der Künstlichen Intelligenz >1975 Moderne Periode.
Geschichte der Künstlichen Intelligenz >1985 Neue Trends.
Geschichte der Künstlichen Intelligenz >1990 Trends danach.
Kapitel MK:I I. Einführung
Gebiete der KI Ursprung der Methoden der KI/Wissensverarbeitung
Gebiete der KI Aus einer anwendungsorientierten Sicht spielen in der Künstlichen Intelligenz
Bemerkungen:
Gebiete der KI Maschinelles Lernen. Beispiel Klassifikation
Gebiete der KI Maschinelles Lernen. Beispiel Klassifikation
Gebiete der KI Maschinelles Lernen. Beispiel Klassifikation
Gebiete der KI Intelligent Computer Aided Instruction, ICAI
Gebiete der KI Natürlichsprachliche Systeme
Gebiete der KI Natürlichsprachliche Systeme. Beispiel Dialogsystem
Gebiete der KI Bildverarbeitende Systeme
Gebiete der KI Bildverarbeitende Systeme
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Bildverarbeitende Systeme. Beispiel Szenenanalyse
Gebiete der KI Robotertechnologie
Gebiete der KI Robotertechnologie
Gebiete der KI Deduktionssysteme
Gebiete der KI Deduktionssysteme. Beispiel Schlussfolgern
Gebiete der KI Deduktionssysteme. Beispiel Schlussfolgern
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI Deduktionssysteme. Beispiel Textanalyse
Gebiete der KI SWT
Kapitel MK:II II. Wissensrepräsentation
Wissensrepräsentation in der Klassifikation
Wissensrepräsentation in der Klassifikation
Wissensrepräsentation in der Klassifikation (a) Kodierung des Klassifikationswissens durch Regeln
Wissensrepräsentation in der Klassifikation (b) Erlernung des Klassifikationswissens
Wissensrepräsentation in der Klassifikation Berechnung im Perzeptron
Wissensrepräsentation in der Klassifikation Berechnung im standardisierten Perzeptron
Wissensrepräsentation in der Klassifikation Präsentation von Beispielen dem Perzeptron:
Wissensrepräsentation in der Klassifikation Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Darstellung der Objekte im Merkmalsraum
Wissensrepräsentation in der Klassifikation Anpassung des Gewichtsvektors
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Wissensrepräsentation in der Klassifikation Illustration des Perzeptron-Lernalgorithmus
Kapitel MK:II II. Wissensrepräsentation
Symbolisch versus subsymbolisch Zwei grundlegenden Ansätze der Wissensrepräsentation
Symbolisch versus subsymbolisch Definition 1 (Symbol)
Symbolisch versus subsymbolisch Akustische Repräsentation eines gesprochenen Symbols:
Symbolisch versus subsymbolisch Beispiel: J. S. Bach, „Die Kunst der Fuge“ [(vgl. [Ultsch 1998])]
Bemerkungen: Im Kontext des Musikhörens besitzt eine einzelne Zahl für sich alleine genommen keine
Symbolisch versus subsymbolisch Vorteile symbolischer Repräsentation:
Bemerkungen:
Symbolisch versus subsymbolisch Erwerb neuen Wissens
Symbolisch versus subsymbolisch Hybride Systeme: Kombination der Paradigmen
Symbolisch versus subsymbolisch Hybride Systeme: Kombination der Paradigmen
Marvin Minsky
Kapitel MK:II II. Wissensrepräsentation
Problemlösungswissen
Problemlösungswissen Beispiel 1: Diagnose einer hydraulischen Schaltung.
Problemlösungswissen Beispiel 1: Diagnose einer hydraulischen Schaltung.
Problemlösungswissen Beispiel 1: Diagnose einer hydraulischen Schaltung.
Problemlösungswissen Beispiel 2: Entwurf einer hydraulischen Schaltung.
Problemlösungswissen Beispiel 2: Entwurf einer hydraulischen Schaltung.
Problemlösungswissen Beispiel 2: Entwurf einer hydraulischen Schaltung.
Kapitel MK:II II. Wissensrepräsentation
Kennzeichen von Problemlösungswissen Das Problemlösungswissen wie
Kennzeichen von Problemlösungswissen Wissensformen innerhalb von Problemlösungsverfahren:
Kennzeichen von Problemlösungswissen Problemlösungswissen unterscheidet sich nicht durch seine Kompliziertheit von
Kennzeichen von Problemlösungswissen Die Beherrschung von Methoden und Techniken (Softwaretechnik, Algorithmen,
Kapitel MK:II II. Wissensrepräsentation
Prinzipien wissensbasierter Systeme Wunsch: Operationalisierung von Problemlösungswissen
Prinzipien wissensbasierter Systeme Definition 2 (wissensbasiertes System, WBS)
Prinzipien wissensbasierter Systeme Fragen zu konventionellen Softwaresystemen:
Prinzipien wissensbasierter Systeme Fragen zu konventionellen Softwaresystemen:
Prinzipien wissensbasierter Systeme Fragen zu konventionellen Softwaresystemen:
Kapitel MK:II II. Wissensrepräsentation
Expertensysteme, XPS „. . . ein intelligentes Computerprogramm, das Wissen und Inferenzverfahren
Expertensysteme Expertensysteme versuchen, die Eigenschaften eines Experten hinsichtlich einer
Expertensysteme Der ideale menschliche Experte
Expertensysteme Expertensystem versus Experte
Expertensysteme Expertensystem versus Standardprogramm
Expertensysteme Expertensystem versus Standardprogramm
Kapitel MK:II II. Wissensrepräsentation
Problemklassen für Expertensysteme Analyse
Problemklassen für Expertensysteme Analyse
Problemklassen für Expertensysteme Synthese
Problemklassen für Expertensysteme Synthese
Bemerkungen: Die Problemklassen bestimmen die in Exeprtensystemen zum Einsatz kommenden
Kapitel MK:II II. Wissensrepräsentation
Erstellung wissensbasierter Systeme Die Erstellung von Programmen, die eine Lösung schlecht strukturierbarer bzw.
Bemerkungen: Die Lösung des Akquisitions-, Repräsentations- und Inferenzproblems ist keine Garantie für
Erstellung wissensbasierter Systeme Lösung des Akquisitionsproblems [Karbach/Linster 1990]
Erstellung wissensbasierter Systeme Werkzeuge
Bemerkungen: (a) Shells (EMycin, Nexpert Object, Twaice):
Erstellung wissensbasierter Systeme Aus meiner Erfahrung
Erstellung wissensbasierter Systeme LOOPS [PARC 1982-1986]
Erstellung wissensbasierter Systeme Colab [PARC 1982-1986]
Bemerkungen: Blickt man zurück, kann man von dem Fortschritt enttäuscht sein.
Kapitel MK:III III. Begriffe der Modellierung
System und Modell Beispiel 1: Der unbequeme Philosoph
System und Modell Beispiel 1: Der unbequeme Philosoph
System und Modell Beispiel 2: Fail-Safe-Überprüfung einer Presse
System und Modell Beispiel 2: Fail-Safe-Überprüfung einer Presse
System und Modell Definition 1 (System)
System und Modell Ein Analyseproblem zu lösen, bedeutet, Fragen bezüglich eines Systems zu
System und Modell Ein Analyseproblem zu lösen, bedeutet, Fragen bezüglich eines Systems zu
System und Modell Ausführung eines Experiments am System? – dagegen spricht:
System und Modell Definition 3 (Model, Modell [Minsky 1965])
System und Modell Definition 3 (Model, Modell [Minsky 1965])
Kapitel MK:III III. Begriffe der Modellierung
Modellieren zum Schlussfolgern Beispiel 1: Der unbequeme Philosoph
Modellieren zum Schlussfolgern Beispiel 2: Fail-Safe-Überprüfung einer Presse
Modellieren zum Schlussfolgern Nahezu alle Situationen, in denen wir einen Sachverhalt analysieren, basieren auf
Modellieren zum Schlussfolgern Nahezu alle Situationen, in denen wir einen Sachverhalt analysieren, basieren auf
Modellieren zum Schlussfolgern Die Beschreibung des Wissens über ein System (Realität) geschieht
Modellieren zum Schlussfolgern Die Beschreibung des Wissens über ein System (Realität) geschieht
Bemerkungen:
Kapitel MK:III III. Begriffe der Modellierung
Modellbildung Klassifikation von Modellen hinsichtlich ihrer Repräsentation:
Modellbildung Klassifikation von Modellen hinsichtlich ihrer Repräsentation:
Modellbildung Ablauf der Top-Down-Modellbildung: Abstrakte Modelle werden auf weniger
Kapitel MK:III III. Begriffe der Modellierung
Systemraum und Modellraum Ein Syntheseproblem zu lösen, bedeutet, Fragen bezüglich einer Menge von
Systemraum und Modellraum Ein Syntheseproblem zu lösen, bedeutet, Fragen bezüglich einer Menge von
Systemraum und Modellraum Ausweg: Synthese von Modellen für die interessierenden Systeme (Modellraum)
Systemraum und Modellraum Klassifikation von Modellräumen hinsichtlich ihrer Repräsentation:
Systemraum und Modellraum Klassifikation von Modellräumen hinsichtlich ihrer Repräsentation:
Kapitel MK:III III. Begriffe der Modellierung
Adäquate Modellierung
Adäquate Modellierung
Adäquate Modellierung
Adäquate Modellierung Wieviel ist bekannt über das System?
Adäquate Modellierung Wieviel ist bekannt über das System?
Kapitel MK:IV IV. Modellieren mit Constraints
Einführung und frühe Systeme Constraints sind eine Softwaretechnik zur deklarativen Beschreibung und zum
Einführung und frühe Systeme Beispiel
Bemerkungen: Regeln stellen gerichtete Zusammenhänge auf.
Einführung und frühe Systeme Algebraische Constraints in EL [Sussmann/Stallman 1977]
Einführung und frühe Systeme Algebraische Constraints in EL
Einführung und frühe Systeme Nicht-algebraische Constraints in Waltz [Waltz 1972]
Einführung und frühe Systeme Nicht-algebraische Constraints in Waltz
Einführung und frühe Systeme Nicht-algebraische Constraints in Waltz
Bemerkungen:
Einführung und frühe Systeme Nicht-algebraische Constraints in Waltz
Einführung und frühe Systeme Nicht-algebraische Constraints in Waltz
Bemerkungen: Eventuell führt Waltz-Filtern nicht zu einer eindeutigen Lösung. Warum nicht?
Einführung und frühe Systeme Gegenüberstellung von EL und Waltz
Bemerkungen: Die Algebra setzt der Leistungsfähigkeit des Ansatzes enge Grenzen.
Einführung und frühe Systeme Constraint-Repräsentationsformen
Einführung und frühe Systeme Constraint-Repräsentationsformen
Einführung und frühe Systeme Einsatz von Constraints
Einführung und frühe Systeme Einsatz von Constraints
Bemerkungen: Oft impliziert die Lösung von (1) die Lösung von (2).
Kapitel MK:IV IV. Modellieren mit Constraints
Konsistenz I Definition 1 (Constraint, erfüllt, Constraint-Netz)
Konsistenz I Definition 1 (Constraint, erfüllt, Constraint-Netz)
Bemerkungen: Einstellige Constraints werden auch als unäre Constraints bezeichnet.
Konsistenz I Beispiel für ein algebraisches Constraint-Netz:
Konsistenz I Definition 2 (lokale Konsistenz)
Konsistenz I Beispiel:
Bemerkungen:
Konsistenz I Definition 3 (globale Konsistenz)
Konsistenz I Beispiel:
Konsistenz I Definition 4 (Constraint-Graph)
Konsistenz I Definition 4 (Constraint-Graph
Bemerkungen: Der Kanten-Constraint-Graph ist im allgemeinen Fall ein Hypergraph, wobei jeder Knoten
Konsistenz I Beispiel-Constraint-Graph:
Konsistenz I Satz 5 (hinreichende Konsistenzbedingungen [Freuder 1982])
Kapitel MK:IV IV. Modellieren mit Constraints
Binarization Definition 6 (CSP-FD [vgl. Constraint-Definition])
Binarization Definition 7 (Binarization)
Bemerkungen:
Binarization Beispiel (als Kanten-Constraint-Graph):
Binarization Beispiel (als Kanten-Constraint-Graph):
Binarization Beispiel (als Knoten-Constraint-Graph):
Binarization Beispiel (als Knoten-Constraint-Graph):
Kapitel MK:IV IV. Modellieren mit Constraints
Generate-and-Test (GT) Lösungsverfahren für ein CSP auf endlichen Wertebereichen
Bemerkungen:
Generate-and-Test Schema eines GT-Algorithmus:
Bemerkungen: Weiterhin können die genannten Lösungsverfahren hinsichtlich einer konstruktiven und einer
Generate-and-Test Propose-and-Improve
Generate-and-Test Propose-and-Improve
Generate-and-Test Propose-and-Improve
Kapitel MK:IV IV. Modellieren mit Constraints
Backtracking (BT) -basierte Verfahren Lösungsverfahren für ein CSP auf endlichen Wertebereichen
Backtracking-basierte Verfahren Schema eines BT-Algorithmus:
Backtracking-basierte Verfahren Algorithm:
Bemerkungen:
Backtracking-basierte Verfahren Durch die sukzessive Hinzunahme von Variablen wird das Constraint-Netz bei der
Backtracking-basierte Verfahren Probleme bei Backtracking
Backtracking-basierte Verfahren Probleme bei Backtracking
Bemerkungen: Ursache für Thrashing: Existenz von Constraint(s) C(xi , xj ), so dass die Belegung(en) für xi
Backtracking-basierte Verfahren Probleme bei Backtracking
Bemerkungen: Ursache für Redundancy: Nach einem Backtracking stellt man erneut fest, dass bestimmte
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Bemerkungen:
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Bemerkungen: Wegen des Rücksprungs nach x1 wird die Lösung nicht gefunden.
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Bemerkungen: Findet man bei einem Rücksprung zur Variable x keinen Wert in ihrem Grundbereich D, der
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Bemerkungen:
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Backtracking-basierte Verfahren Backtracking mit Konfliktanalyse: Backjumping (BJ)
Backtracking-basierte Verfahren Algorithm:
Bemerkungen: returnDepth definiert die Tiefe, zu der zurückgesprungen werden darf.
Backtracking-basierte Verfahren Verbessertes Backjumping: Conflict-Directed Backjumping (CBJ)
Backtracking-basierte Verfahren Verbessertes Backjumping: Conflict-Directed Backjumping (CBJ)
Backtracking-basierte Verfahren Algorithm:
Bemerkungen: Prinzip von Conflict-Directed Backjumping (CBJ): Betrachte bei einem Rücksprung die
Backtracking-basierte Verfahren Weitere Ansätze zur Effizienzsteigerung bei der Suchraumexploration
Bemerkungen: Backmarking verfolgt exakt den Suchpfad von Backtracking, macht aber weniger ConstraintAuswertungen.
Kapitel MK:IV IV. Modellieren mit Constraints
Konsistenz II Ziel der Konsistenzanalyse ist die Entfernung inkonsistenter Werte in den
Konsistenz II Definition 8 (Knotenkonsistenz)
Konsistenz II Definition 9 (Kantenkonsistenz)
Bemerkungen: Algorithmen zur Konsistenzanalyse sind lokale Verfahren. Was bedeutet das?
Konsistenz II Lemma 10
Konsistenz II Lemma 10
Kapitel MK:IV IV. Modellieren mit Constraints
Konsistenzanalyse Lösungsverfahren für ein CSP auf endlichen Wertebereichen
Konsistenzanalyse Kantenkonsistenz in CSP-FD
Konsistenzanalyse Kantenkonsistenz in CSP-FD
Bemerkungen:
Konsistenzanalyse Kantenkonsistenz in CSP-FD
Bemerkungen: Die Kantenkonsistenz eines Constraint-Netzes garantiert nicht seine globale Erfüllbarkeit
Konsistenzanalyse Kantenkonsistenz in CSP-FD
Bemerkungen:
Konsistenzanalyse Pfadkonsistenz in CSP-FD
Bemerkungen: Jeder Constraint-Graph kann als vollständiger Graph interpretiert werden.
Konsistenzanalyse Pfadkonsistenz in CSP-FD
Konsistenzanalyse Pfadkonsistenz in CSP-FD [Montanari 1974]
Bemerkungen:
Konsistenzanalyse Definition 14 (k-Konsistenz, strenge k-Konsistenz)
Bemerkungen: Knotenkonsistenz ist äquivalent zu strenger 1-Konsistenz.
Konsistenzanalyse k-Konsistenz und Backtracking-freie Suche
Bemerkungen: Ein streng (n − 1)-konsistentem Constraint-Netz auf n Variablen muss keine Lösung
Konsistenzanalyse k-Konsistenz und Backtracking-freie Suche
Konsistenzanalyse k-Konsistenz und Backtracking-freie Suche
Bemerkungen: Jedes Suchverfahren definiert implizit eine Ordnung auf den Constraint-Variablen.
Konsistenzanalyse k-Konsistenz und Backtracking-freie Suche
Bemerkungen: Die Instanziierungsreihenfolge ist durch die Ordnung des Constraint-Netzes gegeben, bei
Konsistenzanalyse k-Konsistenz und Backtracking-freie Suche
Konsistenzanalyse Viele Suchverfahren instanziieren die Variablen in einer festen Reihenfolge (Stichwort: Tree-Search).
Konsistenzanalyse Gerichtete Verfahren
Bemerkungen:
Konsistenzanalyse Gerichtete Verfahren
Bemerkungen:
Konsistenzanalyse Praktikabilität der Verfahren
Konsistenzanalyse Lösungsverfahren für ein CSP auf endlichen Wertebereichen
Konsistenzanalyse Kombination mit Backtracking
Konsistenzanalyse Kombination mit Backtracking
Konsistenzanalyse Kombination mit Backtracking
Bemerkungen: Generate-and-Test erzeugt eine Instanziierung für alle Variablen; Konsistenzanalyse (Filtern)
Konsistenzanalyse Kombination mit Backtracking
Konsistenzanalyse Kombination mit Backtracking
Kapitel MK:IV IV. Modellieren mit Constraints
Weitere Analyseverfahren Lösungsverfahren für ein CSP auf endlichen Wertebereichen
Weitere Analyseverfahren Variablensortierung
Bemerkungen:
Weitere Analyseverfahren Constraint-Netz-Reformulierung
Weitere Analyseverfahren Constraint-Netz-Reformulierung: Cycle-Cut-Set-Analyse
Bemerkungen:
Weitere Analyseverfahren Constraint-Netz-Reformulierung: Cycle-Cut-Set-Analyse
Kapitel MK:IV IV. Modellieren mit Constraints
Algebraische Constraints Beispiel Addierer A + B = C:
Algebraische Constraints Beispiel Addierer A + B = C:
Algebraische Constraints Definition 19 (lokal bestimmt (locally determined))
Algebraische Constraints Definition 20 (Einschrittableitung)
Bemerkungen: Algebraische Constraints sind Constraints auf nicht-endlichen Wertebereichen.
Algebraische Constraints Grenzen lokaler Wertepropagierung I
Algebraische Constraints Grenzen lokaler Wertepropagierung II
Algebraische Constraints Constraint-Löser „gaussElimination“
Algebraische Constraints Intervallpropagierung
Algebraische Constraints Intervallpropagierung
Kapitel MK:IV IV. Modellieren mit Constraints
Intervall Constraints Intervall Constraint Satisfaction Problem (I-CSP)
Intervall Constraints Intervall Constraint Satisfaction Problem (I-CSP)
Intervall Constraints Intervall Constraint Satisfaction Problem (I-CSP)
Bemerkungen:
Intervall Constraints Lokale Toleranzpropagierung für I-CSP
Bemerkungen: Intervallpropagierung erfordert die Berechnung von Minimum und Maximum der expliziten
Intervall Constraints Lokale Toleranzpropagierung für I-CSP
Kapitel MK:V V. Diagnoseansätze
Diagnoseproblemstellung Begriffe
Bemerkungen:
Diagnoseproblemstellung Modellierung
Diagnoseproblemstellung Modellierung
Diagnoseproblemstellung Statistische Diagnose
Diagnoseproblemstellung Statistische Diagnose
Diagnoseproblemstellung Prinzip der statistischen Diagnose
Kapitel MK:V V. Diagnoseansätze
Diagnose mit Bayes Satz von Bayes
Diagnose mit Bayes Satz von Bayes
Diagnose mit Bayes Satz von Bayes (Verallgemeinerung)
Diagnose mit Bayes Satz von Bayes (Verallgemeinerung)
Bemerkungen: Ereignisse sind Teilmengen eines Ergebnisraums Ω = {ω1 , . . . , ωn }. Wie Ω tatsächlich
Diagnose mit Bayes Beispiel
Diagnose mit Bayes Beispiel
Diagnose mit Bayes Beispiel
Diagnose mit Bayes Diskussion
Diagnose mit Bayes Diskussion
Bemerkungen:
Diagnose mit Bayes Interpretation des Konzeptes „Wahrscheinlichkeit“
Diagnose mit Bayes Interpretation des Konzeptes „Wahrscheinlichkeit“
Diagnose mit Bayes Interpretation des Konzeptes „Wahrscheinlichkeit“
Diagnose mit Bayes Subjektivistische Verwendung von Bayes
Diagnose mit Bayes Subjektivistische Verwendung von Bayes
Bemerkungen:
Diagnose mit Bayes Subjektivistische Verwendung von Bayes
Diagnose mit Bayes Subjektivistische Verwendung von Bayes
Diagnose mit Bayes Subjektivistische Verwendung von Bayes
Chapter MK:V V. Diagnoseansätze
Evidenztheorie von Dempster/Shafer Forderungen der klassischen Wahrscheinlichkeitstheorie
Evidenztheorie von Dempster/Shafer Evidenzen statt Wahrscheinlichkeiten
Evidenztheorie von Dempster/Shafer Evidenzen statt Wahrscheinlichkeiten
Evidenztheorie von Dempster/Shafer Evidenzen statt Wahrscheinlichkeiten
Evidenztheorie von Dempster/Shafer Definition 1 (Wahrnehmungsrahmen (Frame of Discernment))
Evidenztheorie von Dempster/Shafer Definition 2 (Basismaß (Evidenz), fokales Element)
Bemerkungen:
Evidenztheorie von Dempster/Shafer Beispiel [Lehmann 2002]:
Evidenztheorie von Dempster/Shafer Definition 3 (Believe-Funktion)
Bemerkungen:
Evidenztheorie von Dempster/Shafer Beispiel [Lehmann 2002]
Evidenztheorie von Dempster/Shafer Definition 5 (Doubt-Funktion)
Bemerkungen:
Evidenztheorie von Dempster/Shafer Definition 7 (Unwissenheit, Unsicherheitsintervall)
Evidenztheorie von Dempster/Shafer Beispiel [Lehmann 2002]
Bemerkungen: C als Nichtraucher kommt nach dem Fund der Zigarrenasche als Täter nicht mehr in Frage,
Evidenztheorie von Dempster/Shafer Theorem 8 (Belief-Funktion und Wahrscheinlichkeiten)
Bemerkungen:
Evidenztheorie von Dempster/Shafer Frage: Wie verheiratet man zwei Expertenmeinungen ('‘best of both'’)?
Evidenztheorie von Dempster/Shafer Frage: Wie verheiratet man zwei Expertenmeinungen ('‘best of both'’)?
Evidenztheorie von Dempster/Shafer Theorem 11 (akkumulierte Evidenz)
Bemerkungen:
Chapter MK:V V. Diagnoseansätze
Diagnose mit Dempster/Shafer Beispiel
Diagnose mit Dempster/Shafer Beispiel
Diagnose mit Dempster/Shafer Beispiel
Diagnose mit Dempster/Shafer Beispiel
Diagnose mit Dempster/Shafer Beispiel
Bemerkungen: Die leere Menge repräsentiert die Hypothese, dass keine der Diagnosen zutrifft.
Diagnose mit Dempster/Shafer Diskussion
Bemerkungen:
Diagnose mit Dempster/Shafer Diskussion
Statistische Diagnoseverfahren Zusammenfassung
Bemerkungen: Es existieren nur wenige erfolgreiche Diagnosesysteme auf der Basis des Bayes’schen
Chapter MK:V V. Diagnoseansätze
Truth Maintenance Non-Monotonicity
Remarks: The examples are typical for many diagnosis situations.
Truth Maintenance Operationalization
Truth Maintenance Definition 12 (Datum, Node)
Truth Maintenance Communication between the TMS and the inference engine is in terms of nodes:
Remarks: A datum is worth to be to be remembered / maintained / reasoned about / retracted /
Truth Maintenance The inference engine communicates the important (a subset of all) deductions to
Remarks: In the example, “N0003” is the consequent, “MODUS-PONENS” is the informant, and
Truth Maintenance Definition 14 (TMS Node Types)
Remarks:
Truth Maintenance Graphical notation, adopted from [Forbus/deKleer 1993]:
Truth Maintenance How Justifications Help
Truth Maintenance How Justifications Help
Truth Maintenance Formalization
Truth Maintenance Label
Remarks: If the rate of assumption changes is much larger then the number of queries about node
Truth Maintenance Label
Remarks: The inference engine should introduce as few assumptions as possible.
Truth Maintenance JTMS versus ATMS
Chapter MK:V V. Diagnoseansätze
Assumption-Based TMS (ATMS) Example
Assumption-Based TMS Example
Assumption-Based TMS Terminology
Remarks: The node h holds in six environments.
Assumption-Based TMS ATMS Labels
Assumption-Based TMS ATMS Labels
Assumption-Based TMS ATMS Labels
Remarks: If a node n has a label with no environment then n has no support; it does not mean that n is
Assumption-Based TMS Summary of ATMS concepts in propositional logics:
Assumption-Based TMS Definition 15 (Hold, Nogood Set, Miminality)
Assumption-Based TMS Definition 15 (Hold, Nogood Set, Miminality)
Assumption-Based TMS Definition 16 (ATMS Label Properties)
Assumption-Based TMS Label Update
Assumption-Based TMS Label Update
Assumption-Based TMS Label Update
Assumption-Based TMS Label Update
Assumption-Based TMS Label Update
Remarks:
Chapter MK:V V. Diagnoseansätze
Diagnosis Setting Technical Terms (recapitulation)
Diagnosis Setting Modeling
Diagnosis Setting Model-based Diagnosis Example
Diagnosis Setting Model-based Diagnosis Example
Chapter MK:V V. Diagnoseansätze
Diagnosis with the GDE The most well-known model-based diagnosis approach is the quantitative,
Diagnosis with the GDE Reasoning in the Polybox Example
Remarks: At least one of M 1, M 2, A1 must be faulted to explain F = 10.
Diagnosis with the GDE Conflicts in Model-based Diagnosis
Diagnosis with the GDE Reasoning in the Polybox Example
Diagnosis with the GDE Reasoning in the Polybox Example
Diagnosis with the GDE Reasoning in the Polybox Example
Remarks:
Diagnosis with the GDE Reasoning in the Polybox Example
Diagnosis with the GDE Reasoning in the Polybox Example
Diagnosis with the GDE Polybox Example + ATMS
Remarks:
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Remarks: The ATMS label database lists every possible prediction that can be made from the user
Diagnosis with the GDE Polybox Example + ATMS
Remarks: The ATMS maintains five environments in the shown situation: {M 1}, {M 2}, {M 3},
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Remarks: There is a one-to-one correspondence between ATMS nogood sets mentioning only
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Polybox Example + ATMS
Diagnosis with the GDE Minimal Diagnoses
Remarks: A multiple fault diagnosis may not be composed out of combinations of single fault
Diagnosis with the GDE Minimal Diagnoses
Remarks: Bottom of the lattice: Diagnosis in which nothing is faulted.
Diagnosis with the GDE Minimal Diagnoses
Remarks:
Diagnosis with the GDE Measurement Selection
Diagnosis with the GDE Measurement Selection
Diagnosis with the GDE Measurement Selection
Diagnosis with the GDE Measurement Selection
Diagnosis with the GDE Measurement Selection
Remarks:
Chapter MK:V V. Diagnoseansätze
Diagnosis with Reiter Diagnosis from First Principles
Remarks: SD defines the behavior of the components and the structure of the system.
Diagnosis with Reiter Diagnosis from First Principles
Remarks:
Diagnosis with Reiter Example
Diagnosis with Reiter Example
Diagnosis with Reiter Diagnosis from First Principles
Remarks: Retracting all assumptions will always work, but is not very useful.
Diagnosis with Reiter Diagnosis from First Principles
Diagnosis with Reiter Diagnosis from First Principles
Remarks: Each diagnosis ∆ for hSD, COM P S, OBSi establishes a minimum hitting set respecting the
Kapitel MK:V V. Diagnoseansätze
Grundlagen fallbasierten Schließens Einleitung
Grundlagen fallbasierten Schließens Einleitung
Grundlagen fallbasierten Schließens Einleitung
Grundlagen fallbasierten Schließens Einleitung
Grundlagen fallbasierten Schließens Historie
Bemerkungen: Die englische Bezeichnung für fallbasiertes Schließen ist Case-Based Reasoning (CBR).
Grundlagen fallbasierten Schließens Definition 21 (Fall, Fallbasis)
Grundlagen fallbasierten Schließens Repräsentation eines Falles hP, Si ∈ C:
Grundlagen fallbasierten Schließens Problemmenge
Grundlagen fallbasierten Schließens Zyklus des fallbasierten Schließens [Aamodt/Plaza 1994]
Grundlagen fallbasierten Schließens Zyklus des fallbasierten Schließens
Grundlagen fallbasierten Schließens Klassen fallbasierter Ansätze [Althoff 1992, Wess 1992]:
Grundlagen fallbasierten Schließens
Grundlagen fallbasierten Schließens
Bemerkungen:
Grundlagen fallbasierten Schließens Retrieve
Grundlagen fallbasierten Schließens Retrieve
Grundlagen fallbasierten Schließens Retrieve
Grundlagen fallbasierten Schließens Retrieve
Bemerkungen:
Grundlagen fallbasierten Schließens Retrieve
Grundlagen fallbasierten Schließens Retrieve
Bemerkungen:
Grundlagen fallbasierten Schließens Reuse
Grundlagen fallbasierten Schließens Reuse
Grundlagen fallbasierten Schließens Revise und Retain
Bemerkungen: Der Retain-Schritt stellt die Lernkomponente in einem fallbasierten System dar.
Kapitel MK:V V. Diagnoseansätze
Fallbasierte Diagnose Beispiel
Fallbasierte Diagnose Beispiel
Fallbasierte Diagnose Beispiel
Fallbasierte Diagnose Beispiel
Fallbasierte Diagnose Beispiel
Bemerkungen:
Fallbasierte Diagnose Diskussion
Chapter MK:VI VI. Planning and Configuration
Remarks:
Agent Systems Example: Monkey-and-Banana-Problem
Agent Systems Example: Monkey-and-Banana-Problem
Agent Systems Intelligent Agents
Remarks:
Agent Systems Modeling in Agent Design: Classical View [Russell & Norvig]
Agent Systems Modeling in Agent Design: Model Levels
Agent Systems Modeling in Agent Design: Model Levels
Agent Systems Modeling in Agent Design: Model Levels
Agent Systems Agents as Part of the System Model: Observer’s View
Remarks:
Remarks: (continued)
Agent Systems Agent Capabilities: Designer’s View
Agent Systems Agent Capabilities: Designer’s View
Agent Systems Example: Loading Dock [Ghallab, Nau, Traverso]
Agent Systems Example: Loading Dock [Ghallab, Nau, Traverso]
Agent Systems Example: Loading Dock
Agent Systems Agents as Part of the System Model: Observer’s View
Remarks:
Agent Systems Example: Loading Dock
Agent Systems Example: Loading Dock
Agent Systems Possible Restrictions of Planning Problems
Remarks:
Agent Systems Possible Restrictions of Planning Problems
Chapter MK:VI VI. Planning and Configuration
Deductive Reasoning Agents Tasks in Planning
Deductive Reasoning Agents Agent Capabilities: Designers View
Remarks:
Deductive Reasoning Agents Example: Loading Dock
Deductive Reasoning Agents Describing States
Deductive Reasoning Agents Describing States
Deductive Reasoning Agents Describing States
Deductive Reasoning Agents Describing State Spaces
Deductive Reasoning Agents Example: Monkey-and-Banana-Problem
Deductive Reasoning Agents Example: Monkey-and-Banana-Problem
Deductive Reasoning Agents Example: Monkey-and-Banana-Problem
Deductive Reasoning Agents Modeling Knowledge in Logic
Deductive Reasoning Agents Example: Monkey-and-Banana-Problem
Remarks:
Deductive Reasoning Agents Example: Theorem Proving
Chapter MK:VI VI. Planning and Configuration
Planning Language STRIPS Planning Language
Remarks:
Planning Language STRIPS Language (restricted version)
Remarks:
Planning Language Example: Loading Dock
Planning Language STRIPS Language (restricted version)
Remarks:
Planning Language Example: Loading Dock
Planning Language STRIPS Language (restricted version)
Remarks:
Planning Language Example: Loading Dock
Planning Language STRIPS Language (restricted version)
Planning Language Example: Loading Dock
Planning Language Example: Blocks World [Nilsson]
Remarks:
Planning Language Example: Blocks World [Nilsson]
Remarks:
Planning Language Classical Planning in STRIPS
Remarks:
Chapter MK:VI VI. Planning and Configuration
Planning Algorithms Properties
Planning Algorithms Approaches and Restrictions
Planning Algorithms Approaches and Restrictions
Planning Algorithms Planning as State Space Search
Planning Algorithms Planning as Plan Space Search
Planning Algorithms HTN Planning
Remarks:
Chapter MK:VI VI. Planning and Configuration
State-Space Planning Forward Search in State Spaces (Progression Planning)
State-Space Planning Forward Search in State Spaces (Progression Planning)
Remarks:
State-Space Planning Example: Forward Search in Blocks World
State-Space Planning Heuristics by Simplified Models
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
Remarks:
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
State-Space Planning Generation of Heuristics by Simplified Models
State-Space Planning Example: Model Simplification for the 8-Puzzle Problem
State-Space Planning Backward Search in State Spaces (Regression Planning)
State-Space Planning Backward Search in State Spaces (Regression Planning)
State-Space Planning Backward Search in State Spaces (Regression Planning)
Remarks:
State-Space Planning Regression Planning To create a plan for a list of goal literals, we try to achieve all
Remarks:
State-Space Planning Example: Regression Planning in Blocks World
State-Space Planning Determining Weakest Preconditions
Remarks:
State-Space Planning Example: Regression Planning in Blocks World
State-Space Planning Example: Regression Planning in Blocks World
Remarks:
State-Space Planning Regression Planning
State-Space Planning Example: Regression Planning in Blocks World
State-Space Planning Lifted Regression Planning in State Spaces
Remarks:
State-Space Planning Lifted Regression Planning in State Spaces
Remarks:
State-Space Planning Determining Lifted Weakest Preconditions
Remarks:
State-Space Planning Determining Lifted Weakest Preconditions
State-Space Planning Example 1: Lifted Weakest Preconditions in Blocks World
State-Space Planning Example 1: Lifted Weakest Preconditions in Blocks World
State-Space Planning Example 1: Lifted Weakest Preconditions in Blocks World
State-Space Planning Example 2: Lifted Weakest Preconditions in Blocks World
State-Space Planning Example 2: Lifted Weakest Preconditions in Blocks World
State-Space Planning Example 2: Lifted Weakest Preconditions in Blocks World
Remarks:
State-Space Planning Recursive STRIPS-Planning
Remarks:
State-Space Planning Example: Sussman Anomaly in Blocks World
State-Space Planning Example: Sussman Anomaly in Blocks World
State-Space Planning Example: Sussman Anomaly in Blocks World
Remarks:
State-Space Planning Example: Register Swapping Problem
Remarks:
Plan-Space Planning Differences to State-Space Planning
Remarks:
Plan-Space Planning Prerequisites for Partial-Order Planning
Remarks:
Chapter MK:VI VI. Planning and Configuration
Plan-Space Planning Prerequisites for Partial-Order Planning
Plan-Space Planning Example: Representation of a Partial Plan for a Blocksworld Problem
Plan-Space Planning Example: Representation of a Partial Plan for a Blocksworld Problem
Plan-Space Planning Example: Representation of a Partial Plan for a Blocksworld Problem
Plan-Space Planning Example: Representation of a Partial Plan for a Blocksworld Problem
Plan-Space Planning Prerequisites for Partial-Order Planning
Plan-Space Planning Prerequisites for Partial-Order Planning
Plan-Space Planning Partial-Order Planning
Remarks:
Plan-Space Planning Prerequisites for Partial-Order Planning
Remarks:
Plan-Space Planning Partial-Order Planning
Remarks:
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Plan-Space Planning Example: Partial-Order Planning for the Sussman Anomaly
Chapter MK:VI VI. Planning and Configuration
HTN Planning Prerequisites
HTN Planning Prerequisites
Remarks:
HTN Planning Prerequisites
HTN Planning Prerequisites
HTN Planning Prerequisites
HTN Planning Prerequisites
HTN Planning Abstract HTN Planning
Remarks:
HTN Planning Simplification of HTN Planning
Remarks:
HTN Planning Total-Order Forward Decomposition HTN Planning
Remarks:
HTN Planning Total-Order Forward Decomposition vs. Abstract HTN Planning
Remarks:
Chapter MK:VI VI. Planning and Configuration
Erweiterungen Kontrolle der Planausführung
Bemerkungen:
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen Beispiel Dreiecktabelle in Blocks World
Erweiterungen STRIPS Grenzen
Bemerkungen:
Erweiterungen Beispiel: STRIPS Grenzen bei impliziten Effekten (Ferber)
Erweiterungen Beispiel: STRIPS Grenzen bei impliziten Effekten (Ferber)
Erweiterungen Beispiel: STRIPS Erweiterung auf Multiagentensysteme (Ferber)
Erweiterungen Beispiel: STRIPS Erweiterung auf Multiagentensysteme (Ferber)
Erweiterungen Beispiel: STRIPS Erweiterung auf Multiagentensysteme (Ferber)
Erweiterungen Beispiel: STRIPS Erweiterung auf Multiagentensysteme (Ferber)
Erweiterungen ADL: Erweiterung von STRIPS
Erweiterungen PDDL: Erweiterung von ADL (McDermott)
Erweiterungen PDDL: Erweiterung von ADL (McDermott)
Erweiterungen PDDL: Erweiterung von ADL (McDermott)
Chapter MK:VI VI. Planning and Configuration
Konfigurierungsproblemstellung Definition 23 (Konfigurieren)
Konfigurierungsproblemstellung Merkmale von Konfigurierungsaufgaben [vgl. Bergmann, Richter]:
Konfigurierungsproblemstellung mögliche Kompositionen
Bemerkungen: Konfigurierungsproblemstellungen gehören zur Problemklasse der Synthese.
Konfigurierungsproblemstellung 1. Erstellen einer neuen Konfiguration.
Konfigurierungsproblemstellung
Konfigurierungsproblemstellung Automatisierung
Bemerkungen:
Konfigurierungsproblemstellung Automatisierung
Konfigurierungsproblemstellung Automatisierung
Konfigurierungsproblemstellung Automatisierung
Chapter MK:VI VI. Planning and Configuration
Konfigurierungsansätze Paradigmen zum Lösen von Konfigurierungs- und Entwurfsaufgaben verknüpfen
Konfigurierungsansätze Modellierung
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Bemerkungen: Der Suchraum ist ein Und-Oder-Graph.
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Bemerkungen: Verarbeitung des Und-Oder-Graphen mittels General Best First, GBF.
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Bemerkungen:
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Konfigurierungsansätze Paradigma 1: Skelett-Konfigurieren
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Bemerkungen: Ressourcen-basiertes Konfigurieren ist Generate-and-Test mit Bilanz-Abgleich.
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Bemerkungen:
Konfigurierungsansätze Paradigma 2: Ressourcen-basiertes Konfigurieren
Konfigurierungsansätze Paradigma 3: Fallbasiertes Konfigurieren
Konfigurierungsansätze Paradigma 4: Funktionale Abstraktion
Konfigurierungsansätze Realisierungsaspekte