WIssensbasierte Systeme KE 6 & 7

1. Ähnliche Probleme haben ähnliche Lösungen

2. jedes Problem ist anders, Typen der Aufgabenstellung wiederholen sich

Vorteile

• schnelle Problemlösungen

• Problemlösungen für Bereiche ohne allgemeine Regeln

• mit Falldatensammlung lassen sich auch schwach strukturierte, vage Konzepte interpretieren

• wichtige Teile einer Aufgabenstellung lassen sich leichter identifizieren und behandeln

  • man muss nur wesentliche Charakteristika eines Problems herausstellen

• Beispiele warnen vor Besonderheiten und Schwierigkeiten eines Problems

• komplexe Aufgaben können behandelt werden, weil Beispiel Lösungen für ähnlich komplexe Aufgaben enthalten

• gute Erklärungsfähigkeit

  • positive und Gegenbeispiele

    -> hohe Akzeptanz

Vorteile beim Wissenserwerb:

• Episoden dokumentieren implizites Wissen

• Experten kooperieren mehr wegen der konkreten Fälle ("Bericht von der Front")

• gespeicherte Computerberichte können als Fälle in Wissensbasis aufgenommen werden

• System lernt automatisch und kontinuierlich

  • durch Bearbeiten und Speichern neuer Fälle

Kern: Falldatensammlung

• enhält Fallbeispiele/ Fälle

• Zweck der Fälle:

  • liefern Kontext für Verstehen neuer Situationen

  • gelöste Fälle zeigen Lösungen für neue Probleme

    • manchmal verschmilzt man Lösungen

  • Fallbasis dient zur Evaluation von Lösungsvorschlägen

• wichtig: repräsentative Fälle

  • dann auch gute Ergebnisse mit kleiner Datensammlung

  • "seed cases"

• enthält auch allgemeines (bereichsabhängiges) Wissen

  • z.B. modellbasiertes oder regelbasiertes Wissen

• Erfahrung (Umfang der Fallbasis)

• Verbindung zwischen neuen Situationen mit gespeicherten Fähigkeiten

• Anpassun alter Lösungen an neue Probleme

• Evaluation und Korrektion neuer Lösungen

• Integration neuer Erfahrungen in die Fallbasis

• Analogschließen

  • beide: Lösungen mit Bezug auf frühere analoge Fälle finden

  • aber: Analogschließen eher abstraktes Wissen und strukturelle Ähnlichkeit

  • CBR: Beziehungen zwischen spezifischen Episoden

    • + pragmatisch orientiert

    • -> wie nützlich ist ein früherer Fall

• induktives Schließen

  • beide: verwenden Sammlungen von Beispielen

  • aber: Induktiv hat Ziel allgemeine Gesetzmäßigkeiten abzuleiten

    • eher abstrahierend

  • CBR Konzepte und Kontexte immer an Einzelfällen festmachen

    • konkreter Fall

• Datenbanken/ informationssuchende Systeme (information retrieval systems)

  • CBR: Datenbanken sind Informationsquelle

  • CBR sucht aber aktiver als informationssuchene Systeme

  • dort: Benutzer müssen richtige Fragen stellen

  • dort: exakter Abgleich

  • CBR: möglichst ähnliche Fälle

1. problemlösendes CBR

   • Ziel: Lösungen eines alten Problems als Lösung für neues Problem vorschlagen

1. interpretatives CBR

   • Ziel: adäquate und differenzierte Beurteilung einer Situation

• grundlegende Prozesse beider sind ähnlich

• Unterschied in Adaption der Lösung

  
  

andere Klassifikation:

1. analytische CBR-Aufgaben

   • Diagnose

   • Klassifikation

2. synthetische CBR-Aufgaben

   • Planung

   • Konfiguration

1. Selektierung (Retrieval)

   • ähnlichster Fälle

   • 2 Phasen:

     • 1. Grobsuche

       • alle Fälle, die infrage kommen suchen

     • 2. Feinsuche

       • vielversprechendste Fälle auswählen

   • Probleme:

     • a) matching problem

       • Wie erkennt PC, welche Fälle ähnlich sind?

     • b) similarity

       • Wie Ähnlichkeit beurteilen

2. Wiederverwendung (Reuse)

   • des in den Fällen gespeicherten Wissens

   • hier unterschschied zwischen problemlösen und interpretieren

     • Grenzen aber fließend

   • erst Näherungslösung

   • dann Adaption

     • braucht Buchhaltungssysteme

       • z.B. Truth mantainance systems

       • moderieren Zustände eines Systems und Übergänge zwischen ihnen

     • um zu entscheiden, welche Komponenten der Lösung angepasst werden müssen

     • braucht Adaptionsstrategie

       • z.B. Heuristiken

3. Überprüfung (Revise)

   • der vorgeschlagenen Lösung

   • provisorische Lösung als Suchkriterium für Heraussuchen geeigneter Fälle

   • ist Lösung fehlgeschlagen, entweder Prozess neu starten oder anpassen (Reparatur)

   • Experte evaluiert -> Analysiert Fehlschläge

4. Aufnahme (Retain)

   • des neuen Falles in die Fallbasis durch Integration

   • Fall indizieren und einordnen

1. Aussage - > bestimmt den Inhalt

2. Kontext -> für Indizierung

-> sind Rahmen für Fallrepräsentation

1. Problem- und SItuationsbeschreibung

   • beinhalten aktuelle Aufgaben und Ziele

   • bei Problemlösungaufgaben: Schwerpunkt auf Formulierung der Ziele und Bedingungen

     • Ausgangssituation weniger wichtig

   • bei Interpretationsaufgaben: Schwerpunkt auf Situationsbeschreibungen

2. Lösung

   • beinhaltet:

     • Lösungsschritte

     • Begründungen

3. Resultat

   = Feedback aus der realen Welt

   • Aspekte:

     • Feedback = was geschah nach Anwendung der Lösung

     • Erfüllung von Zielen = wurden Ziele erreicht?

     • Einstufung der Lösung als Erfolg oder Fehlschlag

     • Erklärung: Wie konnte es zu einem Fehlschlag kommen?

     • Korrektur: Was kann man tun, um Irrtum zu korrigieren?

     • Vermeidung: Wie hätte Fehlschlag verhindert werden können?

   • -> hier liegt Lernpotenzial

• Index wie in einer Bücherei

  • müssen Fall von anderen Fällen unterscheiden

• Indizierungsproblem:

  • richtigen Fall bei Suche finden

• Filtert relevante Eigenschaften heraus

  • relevanz:

    • fachliche Aspekte

    • Aufgaben des Systems

      • Vorhersage der Nützlichkeit eines Falles für zukünftige Aufgaben

• man kann kein Vokabular anlegen, das alle zukünftigen Fälle abdeckt

  -> immer auf Zweck gerichtet

• gibt Ziel und Kontext eines Falles und identifizieren wichtige Merkmale

Anforderung an Indizes und Vokabular

• Indizierung mit Konzepten, die Terminologie des Gebiets gehören

• Indexvokabular nutzt Begriffe, die für Fallselektion genutzt werden

• beim Indizieren Aufgabenkontext vorwegnehmen

  = Umstände der Fallselektion

• Indizes sollten hinreichend abstrakt sein

  • passen sie zu mehr Situationen

• Indizes sollten hinreichend konkret sein

  • um Situationen leichter zu identifizieren

2 Schritte zum Erstellen eines Idexes:

1. Indexvokabular erstellen

   • als Rahmen für Klassifikation und Beurteilung von Fällen

2. Fälle durch Index-Kombination kennzeichnen

2 Teile:

1. Menge von Merkmalen/ Attributen

2. Wertemengen

   • werden den Attributen zugeordnet

• Deskriptor = Attribut-Wert-Paar

Beschreibung ist ausführlicher

1. repräsentative Fälle sammeln

2. Besonderheiten eines Falles identifizieren und der Lehre, die sich aus ihm ziehen lassen

3. Situation charakterisieren

4. Indizes formulieren

   • ausreichend abstrakt

   • ausreichend konkret

5. Bildung eines Indexvokabulars aus verwendeten Begriffen

   • Merkmale herausholen

   • ihren Wertebereich festlegen

• nur Deskriptoren aufnehmen, deren Wert wichtig ist

• Fehlen eines Deskriptors ist Normalität/ Irrelevanz

• Indizierung meist von Hand

  
  

Schrittweises Indizierungsverfahren:

1. relevanten Aspekte eines Falles bestimmen

2. Umstände des Falles bestimmen

3. Umstände in Vokabular des Systems übertragen

4. Beschreibung bearbeiten

   • um sie so weit anwendbar wie möglich zu machen

   • Generalisierungsschritt

1. Suchproblem

   • Fallbasis effektiv durchsuchen

     
     

1. Ähnlichkeitsproblem

   • Ähnlichkeitsmaß zur Beurteilung der Ähnlichkeit

1. System leitet Beschreibung der neuen Situation und aktuelles Ziel an Selektierer weiter

2. Situation analysieren

3. errechnete Indizierung des neuen Falles auls Ausgangspunkt für Suche

   • bei Suche Matchingprozeduren aufrufen

   • Grad der Übereinstimmung zwischen Fällen

   • oder Grad der Übereinstimmung zwischen Merkmalen berechnen

4. Algorithmus gibt Liste von nützlichen Fällen aus

5. Rangordnungsverfahren analysieren Liste von Fällen

6. beste Fälle an System zurück geben

1. flache Fallbasis

   • Liste, Feld oder serielle Datei

     -> keine tiefere Struktur

   • Suchalgorithmus durchläuft immer alle Fälle

   • Vorteile:

     • beste Fälle werden immer gefunden

     • einfach neue Fälle hinzuzufügen

   • Nachteil:

     • infeffektive und aufwendige Suche

   
   

2. invertierte Indizierung

   • jedes Merkmal im Indexvokabular verweist auf Fälle, in denen es enthalten ist

     -> nur Fälle berücksichtigen die zu Indizes des neuen Falles gehören

   • Indizierung muss dafür gut sein

     
     

3. Fallhierarchie

   • z.B. Netzwerk aus gemeinsamen Merkmalen

   • oder Unterschiede zwischen Fällen

   • Suche ist Breitensuche

     • beginnt mit Knoten auf höchster Hierarchie-Ebene

     • zu Kindern gehen, bis man Fälle erreicht

       • meist Blattknoten

   • Vorteil:

     • effektivere Suche

   • Nachteile:

     • mehr Speicherplatz als flache Strukturen

     • mehr Aufwand bei Integration neuer Fälle

   • Verbesserung:

     • prioritized network

     • zuerst wichtige Merkmale durchsuchen

Ähnlichkeit: quantitativ und qualitativ

1. Hamming-Ähnlichkeit:

   1 - ( dist_h(x, y) / n )

   • für zweiwertige Merkmale

   • beruht auf Hamming-Distanz:

     • dist_H(x, y) = \sum_i_n |x_i - y_i|

   
   

2. gewichtete Hamming-Ähnlichkeit

   sim_w_H(x,y) = 1 - \sum_i_n w_i ( | x_i - y_i |) / \sum_i_n w_i

   • mit nicht-negativen Gewichten w für Merkmale

1. verallgemeinerte Ähnlichkeit

   sim(x, y) = \sum_i_n w_i sim_i(x_i, y_i) / sum_i_n w_i

   • für nicht nur binäre Attribute

   • für Funktion sim_i

   • bei reellen Attributwerten: normierte Differenzen

     • quantitative Ähnlichkeitsbestimmung

   • vs. Ähnlichkeitswerte aufgrund von Klasseneinteilungen

     • qualitative Ähnlichkeit

     • subjektiv beurteilt oder festgelegt

       
       

2. PATDEX-Ähnlichkeitsmaß

   • kontextabhängige Gewichtsfaktoren

   • verarbeitet auch unvollständige Fallbeschreibungen

     • jedes Attribut durch "unbekannt" erweitert

     • sim(x;y) = 0, wenn x oder y "unbekannt"

     • basiert auf "hinreichender" Ähnlichkeit

       • hinreichend, wenn sim_i(x_i, y_i) >= 1 - delta

       • also größer als ein Schwellenwert

   • sim (x, y) = \alpha E / (alpha E + beta C + eta U + gamma A)

     • E

       • beide Attribute bekannt und Ähnlichkeit größer als Schwellwert

       • "hinreichend ähnlich"

       • \sum w_ij sim_i(x_i, y_i)

     • C

       • beide Attribute bekannt und Ähnlichkeit unter Schwellwert

       • "signifikant unterschiedlich"

       • sum w_ij(1- sim_i(x_i, y_i))

     • U

       • Attribut des neuen Falles unbekannt

       • sum wij

     • A

       • Attribut bei alt unbekannt und bei neu abnormal

       • |A|

     • alpha = 1

     • beta = 2

     • gamma = 1

     • eta = 1/2

• Vorgang alte Lösung an neues Problem anpassen

• ggf. mehrere Lösungsansätze berücksichtigen

4 Formen:

1. etwas Neues wird in alte Lösung eingefügt

2. etwas aus alter Lösung entfernen

3. Komponente austauschen

4. Teil der alten Lösung transformieren

1. Substitutionsmethoden

   • Rahmenbedingung für alte und neue Situationen passt

   • Reinstantiierung

     • Komponenten/ Rollen austauschen

   • Lokale Suche

     • Teile der alten Lösung durch neue Objekte ersetzen

     • kleinere Teile als bei Reinstantiierung

     • nutzt semantische Netze oder Abstraktionshierarchien

   • Parameteranpassung

     • verbindet unterschiede in Inputspezifikation mit Unterschieden im Output

     • z.B. Mengenanpassung bei Kochrezepten

   • Fallbasierte Substitution

     • nutzt andere Fälle für Substitutionen

2. Transformationsmethoden

   • bei neuen Rahmenbedingungen

   • Komponenten weglassen/ hinzufügen

   • Commonsense Transformation

     • nutzt Heuristiken des Allgemeinwissens

     • z.B. delete secondary component

   • Modellbasierte Transformation

     • Steuerung durch kausale Modelle

     • z.B. in Diagnose und Planung

3. Spezielle Adaption und Verbesserung

   • fuer bereichsspezfische und strukturmodifizierende Adaptionen

   • die nicht zu a oder b gehören

   • insb. fehlgeschlagene Lösungen korrigieren

4. Derivationswiederholung

   • alte Lösung ableiten für neue Lösung

• Anwendung eines Operators Cn führt zu keinen neuen Erkenntnissen

  • Cn = Consequence operation/ Folgerungsoperation

  • Cn(F) = F

    • F Menge von Formeln

• deduktiv abgeschlossene Theorie ist Fixpunkt des Operators Cn

• Cn ist monoton, weil alle Modelle eingeschlossen sind

• idealisierter Rahmen der Allwissenheit

• realistischer mit unvollständigem Wissen

• verwendet allgemeinere Inferenzoperation

  • C : 2^Form -> 2^Form

• Unterschied

  • nichtmonotone Ableitungen

    • durch nicht-montone Inferenzrelation

  • nichtmonotone Regeln

    • verallgemeinerte Regeln

    • dürfen nur unter bestimmten Bedingungen angewandt werden

• neue Regeln können zur Inaktivierung allgemeinerer Regeln führen

  • wenn sich ihre Schlussfolgerungen nicht vertragen

• TMS nehmen Aussagen zurück, wenn sie im Konflikt mit neuen Infos stehen

1. Justification-based TMS (JTMS)

   • ohne Begründung darf nichts geglaubt werden

2. Assumption-based TMS (ATMS)

   • verwaltet Menge von Annahmen, unter denen eine Aussage ableitbar ist

   • mit Inferenzkomponente, die klassisch-deduktiv schlussfolgert

• im Mittelpunkt: unsichere Regeln

  = Default-Regeln/ Defaults

  • Eigenschaften:

    • Regeln mit Ausnahmen

    • gelten allgemein/ typischerweise

    • gelten bis Gegenteil bewiesen wurde

• bilden Allgemeinwissen nach

• berücksichtigen Qualifikationsrproblem

  • alle Aussnahmen aufnehmen

• Default für

  • typisches/ normales

  • normativ

  • erwartungshaltung

• "Default" = "unsichere Regel"

• Defaults für regelhaftes und faktisches Wissen

  
  

Aussehen:

• Angeklagt : unschuldig / unschuldig

  • Schuld muss eindeutig bewiesen werden

• Formel 8.5 S.287

  • Voraussetzung : Begründung(en) / Konsequenz

  • Begründung für Teile des Defaults

• gibt Formeln Bedeutung

  • Interpretation

  • Modelle

• Übersetzung:

  • Wenn Voraussetzung bekannt ist

  • und Begründungen konsequent angenommen werden können

  • dann folgere Konsequenz

Problemstellung der Default-Logik nach Reiter

• 1. Was heißt "Voraussetzung ist bekannt"

• 2. Wann können Begründungen konsequent angenommen werden

  
  

• zur Default-Logik gehört immer eine Faktenmenge

  • Voraussetzung ist bekannt, wenn sie aus den Fakten geschlossen werden kann

  • Begründungen müssen zu Fakten konsistent sein

• aktuelle Wissensbasis erweitert Faktenmenge um "akzeptable" Thesen