Künstliche Intelligenz und Prolog
Copyright © 2020 Jiri Kriz, www.nosco.ch

8Experten­systeme

8.1Einführung

Expertensysteme sind Computerprogramme, die Probleme eines enggefassten Fachgebietes in einer Qualität lösen können, die derjenigen eines menschlichen Experten vergleichbar ist. Die Lösungsqualität kann leider nur sehr vage beurteilt werden. Wissensbasierte Systeme sind Computerprogramme, die Probleme eines enggefassten Fachgebietes lösen, indem sie auf ge-speichertes Wissen über das Gebiet zurückgreifen. Solches Wissen kann nicht nur statische Fakten und Sachverhalte beinhalten, sondern auch Regeln, mit denen neue Fakten ("neues Wissen") aus bekannten Fakten abgeleitet werden. Expertensysteme und wissensbasierte Systeme werden hier gleichberechtigt verwendet.

Beispiele:

FachmannExperten­system
Fach­wissen: Fakten und MethodenWissens­bank: Fakten und Regeln über ein be­schränktes Gebiet
Problem­lösung, DenkenInferenz­methode (Inferenz­maschine, Programm)
Erklärung der Lösungstereo­type Erklärung der Lösung
Lernenprimitives Lernen, wird "gelehrt" (Induktion)
Common Sensekein Common Sense
Wahr­nehmung, Selbst­beurteilungkeine Wahr­nehmung, keine Selbst­beurteilung
Kreativitätkeine Kreativität
Leistungs­schwan­kungen, Subjektivitätkonstante Leistung, Objektivität
EinmaligkeitReproduzier­barkeit
Fehlerkeine Fehler in vorgesehenen Fällen
"Graceful Degradation" der LeistungVersagen ausserhalb des Gebietes
Menschlicher DialogComputer Dialog

Aufbau von Expertensystemen:

Konven­tionelles Programm: Vermischung von: Programm, Daten, Wissen
Datenbank­programm:Trennung von Daten und Programm, Daten persistent
Wissen in Daten und im Programm
Wissens­bassiertes System: Trennung vom Wissen (Daten und Regeln) und Programm,
Wissen in einer Wissens­bank persistent gespeichert

Unterschiede fliessend, nicht eindeutig.

Aufbau eines Expertensystems

Fig 8.1: Aufbau eines Expertensystems

Vorteile der Trennung: Wissen explizit, inkrementeller Aufbau (fast Prototyping), einfache Modifikation, mehrfache Verwendung des Programms ⇒ ES Shell.

Expertsystem-Shell beinhaltet: Inferenzmethode, Wissensrepräsentationssprache (leere Wissensbank), Erklärungskomponente, Benützerschnittstelle, ...

8.1.1Grundlegende Konzepte

Repräsentation vom Wissen: prozedural / deklarativ
Prozedural:
Algorithmen, Rezepte, Verfahren, Implementationen
Reihenfolge festgelegt: "WIE" (nicht "WAS")
effizient, implementierungs­abhängig.
Beispiel - Reparatur einer defekten Glühbirne:
1. Schalter aus
2. Abdeckung entfernen
3. Birne ersetzen
4. Abdeckung einsetzen
5. Schalter ein
Deklarativ:
keine Reihenfolge, statische Beschreibung, Definition
"WAS" (nicht "WIE")
ineffizient, implementierungs­unabhängig
Beispiel:
Lexikon, Zusammen­setzung eines Velos, ...

Auch die Reparatur kann deklarativ mit Zustandsraum beschrieben werden (s. Fig. 8.2). Die ideale Reparatur entspricht dem optimalen Plan (Weg) im Zustandsraum.

Zustandsraum eines Reparaturproblems

Fig. 8.2: Zustandsraum eines Reparaturproblems

Möglichkeiten von Wissensrepräsentation / Inferenz

1) Logik / Beweisen

Wissens­bank:logische Formeln (Axiome) A1, A2, ... An
Problem:logische Formel Q
Lösung:Beweis A1, A2, ..., An ⇒ Q mit Variablen­bindungen in Q

Attraktive Möglichkeit: grosse Darstellungskraft, exakt definierte Syntax und Semantik; nicht praktisch ausführbar (Effizienz).

Beispiel:

A1: Motoren des Typs M5 werden durch die Sicherung S1 oder S2 geschützt.
A2: Falls der Stecker ST verwendet wird, dann ist die Sicherung S1 ausgeschlossen.
Q: Welche Sicherung wird beim Motor m5.1 des Typs M5 mit dem Stecker ST verwendet?
A1:∀ X: motor( X) ∧ typ( X, m5) ⇒ sicherung( X, s1) ∨ sicherung( X, s2).
A2:∀ X: motor( X) ∧ stecker( X, st) ⇒ ¬ sicherung( X, s1).
Q:∃ S: motor( m5_1) ∧ typ( m5_1, m5) ∧ stecker( m5_1, st) ⇒ sicherung( m5_1, S).

Q wird bewiesen mit S = s2.

Prolog

Wissens­bank: Horn-Klauseln, resp. Prolog Programm
Zu lösendes Problem: Frage (Goal, Query)

Nicht alles direkt darstellbar.

Möglichkeiten:

  1. Problem umformulieren und dann direkt darstellen
  2. Interpreter für höhere Konzepte (Metainterpreter) in Prolog implementieren

Beispiel:

motor( M, m5, S, ST) :- 
    (S = s1 ; S = s2), 
    (ST = st -> S \= s1).
?- motor( m5_1, m5, S, st).  ⇒  S = s2

2) Regeln / For- and backward chaining

IF Voraussetzung THEN Behauptung

Voraussetzung, Behauptung: logische Ausdrücke

Beispiel:

Regelsystem (Inferenznetz)

Fig. 8.3: Graphische Darstellung eines Regelsystems (Inferenznetz)

Forward ⇒ :
Wenn Schalter offen, dann 'kein Licht'
Backward ⇐ :
Wenn 'kein Licht", dann Schalter kann offen sein
oder Lampe kann defekt sein

Die obigen Regeln, die von Ursachen auf Folgerungen schliessen, können als (wahre) Implikationen betrachten werden. Aus der wahren Prämisse P und der Regel P ⇒ C folgt die Wahrheit von C (logische Deduktion nach Modus Ponens). Aus der Wahrheit von C folgt die Wahrheit von P nicht, da die Regel C ⇒ P nicht gilt (es gilt: ¬C ⇒ ¬P). Die logisch nicht korrekte Inferenz "Aus C und P ⇒ C folgt P" heisst Abduktion; sie wird oft verwendet mit der Bedeutung "P kann wahr sein", resp. P is eine hinreichende (aber nicht notwendige) Bedingung für C.

3) Semantische Netze

Objekte, Relationen / vereinbarte und eigene Inferenzen

Semantische Netze wurden von Quillian 1968 eingeführt. Sie sind (zu) sehr flexibel und dadurch auch vage. Sie werden insbesondere in der kognitiven AI als Denkmodelle verwendet. In der angewandten AI wurden sie von den verwandten Frame- und Objekt-Systemen abgelöst.

Interpretation: Vögel sind Tiere, Pinguin und Amseln sind Vögel.

Hierarchie mit Vererbung: Tiere atmen, Vögel fliegen ⇒ Pinguin atmen und fliegen

Ausnahmen (Exceptions): Pinguin fliegen nicht (Überschreibung).

Ein semantisches Netz

Fig. 8.4: Ein semantisches Netz

Bemerkung: Menschen verwenden wahrscheinlich semantische Netze und die is_a-Hierarchie. Experiment: Hat die Amsel Haut? (Antwortzeit)

4) Frames

Objekte, Attribute, Relationen / vereinbarte und eigene Inferenzen

Strukturierung des Wissens

Inferenzen: Vererbung, Defaults, Dämonen

Vogel:
- is_a:Tier
- fliegt:ja
- Beine:2
- Grösse:default = klein
- Bild:Zeichnungs­routine

Ein Frame

5) Objekte (Objektorientierte Programmierung)

Objekte entsprechen Frames, jedoch Zugriff nur über Nachrichtensenden, keine direkte Manipulation der Attributwerte (abstrakte Datentypen)

6) Hypertext, Multimedia

Elektronisches Lexikon; Inferenz vorwiegend durch den Benützer mit Unterstützung des Systems.

8.1.2Bekannte Expertensysteme

Feigenbaum (Stanford, 1965): Begriff ES: Einschränkung des Gebietes (kein GPS), grosse Tiefe ("Wissen ist Macht").

8.2Regelbasierte Systeme

Wissen als Fakten und Regeln (und nichts anderes) dargestellt. (P, C, A: logische Ausdrücke; Regel: log. Implikation P ⇒ C)

Regeln:
IF Premise THEN Conclusion
Premise P: Bedingung, Voraussetzung, Prämisse
Conclusion C: Folgerung, Behauptung, Aktion
Fakten:
Assertion (A)
kann auch als Regel dargestellt werden:
IF true THEN A.
Inferenz (vorwärts):
Aus bekannten Fakten werden mittels Regeln neue Fakten abgeleitet, bis der gesuchte Fakt (Goal) gefunden wird. (Data-driven)
Inferenz (rückwärts):
Der gesuchte Fakt (Goal) wird mittels Regeln (in Rückwärtsrichtung) auf neue gesuchte Fakten reduziert, bis der gesuchte Fakt ein von den bekannten Fakten ist. (Goal-driven)

Problemwissen ⇒ Formulierung in Regeln (der Inferenz angepasst) ⇒ Inferenz
Die Inferenz bedeutet eine Suche im Zustandsraum.

8.2.1Rückwärtsinferenz

Anwendung: Diagnose durch Hypothesentesten (Generate-and-Test)

Ein technisches System

Fig. 8.5: Ein technisches System

Inferenznetz

Fig. 8.6: Inferenznetz

Die Regeln werden so formuliert, dass sie von Symptomen zu Diagnosen führen. Eine Diagnose wird "bewiesen", wenn ihre Prämissen rekursiv bewiesen werden, d.h. wenn die relevanten Symptome beobachten werden. Die Regeln stellen nicht logische Implikationen dar, z.B. aus "Lampe dunkel" und "Platte warm" kann nicht "Lampe defekt" bewiesen werden (der Kocher wurde vor kurzer Zeit abgestellt und die Platte ist noch warm). Die Regeln sind in diesem Fall Abduktionsregeln: "Wenn Lampe dunkel und Platte warm, dann kann Lampe defekt sein". Die gefundenen Diagnosen sind also nur mögliche Diagnosen.

1) Wissensrepräsentation in Hornklauseln, Prolog als Inferenzmaschine

Regeln (Horn Klauseln): Conclusion :- Premise

Fakten (atomare Prädikate):

platte( defekt) :- lampe( hell), platte( kalt). /* r1 */
schalter( auf) :- strom( nein). /* r2 */
spannung( nein) :- strom( nein). /* r3 */
strom( nein) :- platte( kalt), lampe(dunkel). /* r4 */
lampe( defekt) :- lampe( dunkel), platte( warm). /* r5 */

/* Symptome, Beobachtungen (Fakten) : */
lampe( dunkel).
platte( kalt).

?- platte( defekt).  ⇒  no /* Diagnosenhypothese platte( defekt) verworfen */
?- schalter( auf).  ⇒  yes    /* Diagnosenhypothese schalter( auf) bestätigt */

Verbesserung 1: Fakten zu möglichen Diagnosen:

diagnosis( platte( defekt)). /* Mögliche Diagnosen */
diagnosis( schalter( auf)).
solve( X) :- diagnosis( X), call( X). /* Generate-Test: Hypothesentesten */

Verbesserung 2: Query-the-user (statt fest kodierte Symptome)

lampe( dunkel) :- ask( 'Ist Lampe dunkel ?').
platte( kalt) :- ask( 'Ist Platte kalt ?').
ask( Query) :- write( Query), read( yes).

Effizient, aber umständlich; führt zur Vermischung Wissen/Inferenz bei Erklärungen etc.

2) Shell in Prolog

Regeln des Anwendungsgebietes werden als Prolog-Fakten repräsentiert; Inferenz wird durch einen Meta-Interpreter realisiert. Die Regel 1 könnte z.B. wie folgt dargestellt werden:

rule( 1, if( lampe( hell) + platte( kalt)), then( platte( defekt)).

(+ ist hier ein rein symbolischer Operator.) Eine noch elegantere Darstellung (mit keiner neuen Information!) wird durch Verwendung von benützerdefinierten Operatoren erreicht, die in den meisten Prolog-Implementierungen möglich sind. Ein Operator wird meistens folgendermassen definiert:

?- op( 920, xfy, and).

Dabei ist '920' die Präzedenzzahl, 'xfy' gibt die Assoziativität an, und 'and' ist der Operatorname. Je höher die Präzedenzzahl ist, desto später wird der Operator bei der Auswertung angewendet (d.h. er ist schwächer), z.B. ist die Präzedenzzahl von * kleiner als diejenige von +. 'xfy' bedeutet rechtsassoziativ (z.B. Dot-Operator bei Listen), 'yfx' ist linksassoziativ (z.B. +, *).

Beispiele:

?- op (500, yfx, +).
?- op (1000, xfy, ',').
?- op (700, xfx, =).    /* X = Y = Z verboten */
?- op (900, fx, not).    /* not not X verboten */

Mit den Operatordefinitionen

?- op( 920, xfy, and). 
?- op( 930, xfy, or). 
?- op( 950, xfx, then). 
?- op( 960, fx, if). 
?- op( 970, xfx, :). 

wird die Regel 1 folgendermassen dargestellt:

rule( 1) :  
if lampe( hell) and platte( kalt) 
    then platte( defekt). 
Regel in Baumdarstellung

Fig. 8.7: Regel (Term) in Baumdarstellung

Das built-in Prädikat display( Term) zeigt diese Struktur-Dartstellung:

':'( rule( 1), if( then( and( lampe( hell), platte(dunkel)), strom( nein))))

Grundlegende Inferenz: Meta-Interpreter in Prolog

solve( G) :- Fact : G.
solve( G) :- 
    Rule: if G1 then G, 
    solve( G1).
solve( G1 and G2) :- 
    solve( G1), solve( G2).

In den Prämissen der Regeln könnte neben and auch noch or und not verwendet werden; der Meta-Interpreter wäre dann entsprechend erweitert. Im Folgerungsteil der Regeln können nur positive atomare Formeln stehen. Diese Shell ist enorm einfach, da sie die Prolog-Lösungsstrategie übernimmt: goal-driven (backward), top-down, depth-first. Dies beinhaltet leider auch die bekannten Probleme des Prolog-Interpreters, z.B. nichtterminierende Linksrekursion.

Interaktion mit dem Benützer (query-the-user): zusätzliche Klausel:

solve( G) :- 
    Fact: askable( G), ask( G).

(Die Antworten sollten gespeichert werden, damit der Benutzer zu einer Frage nur einmal gefragt wird: Übung)

Anwendung: Diagnose (Hypothesentesten)

Expertenwissen: Regeln, die von Symptomen zu Diagnosen führen und die Form haben:

Rule: if Syptom then Diagnosis.

Symptome: Fakten der Form:

Fact: askable( Symptom). /* abfragbar */
Fact: Symptom. /* vorhanden */

Mögliche Diagnosen: Fakten der Form:

Fact: diagnosis( Diagnosis).

Shell:

diagnose( D) :- 
    Fact: diagnosis( D), 
    solve( D).

8.2.2Erklärungen

Beispiel: Diagnose des Systems (Fig. 8.6)

1) Why-Fragen während des Beweises Warum werde ich (der Benutzer) diese Frage gefragt?

Beispiel:

System:Benutzer (yes/no/why):
lampe( hell) ? no
platte( kalt) ? (*)why
trying to prove strom( nein) by applying rule r4:
platte( kalt) ?why
trying to prove schalter( auf) by applying rule r2:
platte( kalt) ?why
schalter( auf) is my hypothesis
platte( kalt) ?why
you ask too many questions
platte( kalt) ?yes

Aufbau einer Trace von Regeln während des Beweises, z.B. [r4, r2, d2] an der Stelle (*)

shell( D) :- 
    F: diagnosis( D), 
    solve( D, [F]).
solve( G, Trace) :- 
    R : if G1 then G, 
    solve( G1, [ R| Trace]).
ask( G, Trace) :- 
    write( G), write( ?), 
    read( A), 
    respond( G, A, Trace).
respond( G, yes, T) :- !, 
    assert( told( G, yes)).
respond( G, no, T) :- !, 
    assert( told( G, no)), 
    fail.
respond( G, why, [ F]) :- !, 
    show_fact( F), 
    write( 'is my hypothesis'), 
    ask( G, [ ]).
respond( G, why, [ R| T]) :- !, 
    show_rule( R), 
    ask( G, T).
respond( G, why, [ ]) :- !, 
    write( 'you ask too many questions'), 
    ask( G, [ ]).

Für Einzelheiten siehe Übung.

2) How-Fragen nach dem Beweis

Explain Proof: Wie bist Du (Expertensystem) zum Resultat gekommen? Begründung der gefundenen Lösung.

Annahme: schalter( auf) als Diagnose bewiesen, platte( kalt) und lampe( dunkel) gesagt:

Beweisbaum

Fig. 8.8: Beweisbaum

Beweisbaum (Proof Tree): nur die bewiesenen Äste des Inferenznetzes.

Mögliche Kodierung:

r2: if 
        r4:  if    told( platte( kalt)) and told( lampe( dunkel))
             then  strom( nein)
    then schalter( auf)

P ist ein Proof-Tree von G:

  1. wenn 'told( G, yes)', dann P = told( G)
  2. wenn 'Fact: G' dann P = Fact: G
  3. wenn 'R : if G1 then G' und P1 Proof-Tree von G1, dann P = R : if P1 then G.
  4. wenn P1 Proof Tree von G1 und P2 Proof Tree von G2, dann (P1 and P2) ist Proof Tree von G1 and G2.

Generierung des Beweisbaumes:

solve( G1 and G2, Proof1 and Proof2) :- 
    solve( G1, Proof1), 
    solve( G2, Proof2).
solve( G1 or G2, Proof) :- 
    solve( G1, Proof) ; 
    solve( G2, Proof).
solve( G, Fact: G ) :- 
    Fact : G.
solve( G, R: if Proof then G) :- 
    R: if G1 then G, 
    solve( G1, Proof).
solve( G, told( G) ) :- 
    told( G, yes).
solve( G, told( G) ) :- 
    askable( G), 
    not told( G, _), 
    ask( G).

How-Fragen:

Werden durch Abarbeiten des Beweisbaumes beantwortet (s. Übung).

8.2.3Konfidenzen

Verarbeitung vom vagen Wissen; Aussagen und Regeln sind nicht ganz sicher. Konfidenzfaktor: Mass des subjektiven Glaubens in die Richtigkeit einer Aussage oder Regel. Den Prädikaten und den logischen Formeln werden Konfidenzfaktoren zugeordnet.

Beispiel:

r1: if lampe( hell) and platte( kalt) then platte(defekt) cf 0.8.

r2: if strom (nein) then schalter( auf) cf 0.9.

r3: if strom( nein) then spannung( nein) cf 0.05.

r4: if platte( kalt) and lampe( dunkel) then strom( nein) cf 0.9.

r5: if lampe( dunkel) and platte( warm) then lampe( defekt) cf 0.9.

Computer: platte( kalt)?. Benutzer: 0.9
Computer:lampe(dunkel)?. Benutzer: 1.0
Computer (Lösung): schalter( auf) cf 0.73 ; spannung( nein) cf 0.04
Prolog Operator cf: ?- op( 940, xfx, cf).

Propagation von Konfidenzfaktoren (c)

Ein Modell: 1 = yes (true), 0 = no (false), 0 ≤ c ≤ 1:

c( P1 and P2) = min[ c( P1), c( P2)]
c( P1 or P2) = max[ c( P1), c( P2)]
c( not P) = 1 - c( P)
c( Conclusion) = c( Premise) * c( Rule)
Alternativen (z.B. 2 Regeln zu einer Conclusion):
c( Conclusion | Rule1 and Rule2) =
c( Conclusion | Rule1) + c( Conclusion | Rule2) -
c( Conclusion | Rule1) * c( Conclusion | Rule2)
Heuristiken, z.B.: wenn c < 0.2, setze c = 0.

Bemerkungen:

Andere Modelle:

Empirische Modelle:

Mathematische Modelle:

8.3Framebasierte Systeme

Die regelbasierten Systeme betonen die Inferenz:

r1 : if A then B
r2 : if B then C

A, B, C sind logische Aussagen, die (implizit) Objekte beschreiben oder sich auf Objekte beziehen, z.B.:

temperatur( niedrig) ⇔ Objekt: Bügeleisen, Eigenschaft: Temperatur, Wert: niedrig

Die framebasierten Systeme betonen die strukturierte Wissensrepräsentation (b ist ein Objekt entsprechend B):

b 
-- attribute1 : value1
-- attribute2 : value2
-- ...
-- follows_from : a
-- implies : c.

Diese Darstellung heisst auch eine Property-List.

8.3.1Property-Listen

Einige Attribute sind vordefiniert und werden für den Inferenzprozess verwendet. Andere Attribute sind frei wählbar.

object 
    -- attribute1 : value1
    -- attribute2 : value2
    -- . . .
    -- attribute_n : value_n .

Repräsentation der Property-Listen in Prolog

Strukturbaum der Property-Liste

Fig. 8.9: Strukturbaum der Property-Liste

?- op( 910, xfx, :).
?- op( 930, xfy, --).

Damit wird object ein gültiger Prolog Term. Beispiel der Struktur (n = 3) :

object -- ((attr1 : v1) -- ((attr2 : v2) -- (attr3 : v3))).

Zugriffe zu Objekt - Attribut - Wert: Prädikat object( Obj, Attr, Val)

Implementierungen:

1) Rekursiv (ähnlich wie member( X, Xs)):

object( Obj, Attr, Val) :- 
    Obj -- AVs, 
    obj( Attr, Val, AVs).
obj( Attr, Val, Attr : Val).
obj( Attr, Val, Attr : Val -- AVs).
obj( Attr, Val, A1: V1 -- AVs) :- 
    obj( Attr, Val, AVs).

2) Parsen der Struktur in eine Reihe der Fakten

object( Obj, Attr, Val).

object ist ein konstanter Funktor für alle Objekte. Zugriff trivial. Parsing einfach in Prolog.

Parsen der Struktur in eine Reihe der Fakten

Object( Attr, Val).

Object ist der effektive Objektname. Zugriff:

object( Obj, Attr, Val) :- 
    F =.. [ Obj, Attr, Val], 
    call( F). 

Obj muss instantiiert sein.

Anwendung: Struktur­basierte Diagnose (Entscheidungs­baum, resp. DAG in strukturierter Darstellung)

Bei der strukturbasierten Diagnose werden verschiedene Informationen über die Ursachen eines Symptoms verwendet:

Beispiel: Diagnose beim Auto

Diagnosebaum

Fig. 8.10: Diagnosebaum: Struktur, Funktionalität, Heuristik

Symptom: Ein Problem mit dem Auto
Diag­nosen: alle atomaren Objekte, z.B. Batterie
Struktur: Auto besteht aus Fahrwerk, Antrieb und Elektrik.
Fahrwerk besteht aus Rahmen, Rädern, Bremsen.
Elektrik besteht aus Batterie und Starter.
Funktiona­lität:Antrieb funktioniert, wenn Motor funktioniert und Benzin funktioniert (vorhanden).
Heu­ristiken: Auto nicht fahrbar bei Temperaturen unter -20°
Tests :Auto startet nicht ⇒ Elektrik (defekt) oder tiefe Temperatur.
Auto fährt nicht ⇒ Antrieb oder Fahrwerk (defekt)

Wissens­repräsentation (eine Möglichkeit):

auto
-- question: 
    'Welche Probleme haben Sie mit Ihrem Auto'
-- answers: 
    [ 1: 'startet nicht', 2: 'fährt nicht', 3: anderes]
-- reasons: 
    [ 1: elektrik, 1: temperatur, 2: antrieb, 2: fahrwerk, 3:  antrieb, 3: fahrwerk].

temperatur
-- question : 
    'Ist die Temperatur unter -20° ?'
-- answers: 
    [ 1: ja, 2: nein]
-- reasons: 
    [ 1: true] .
-- explanation: 
    'Dieses Auto fährt nicht bei starkem Frost' .

benzin
-- question : 
    'Ist Benzin im Tank ?'
-- answers: 
    [ 1: ja, 2: nein]
-- reasons: 
    [ 2: true]
-- explanation: 
    'Es gibt kein Benzin. Tanken Sie' .

Allgemein:

Object
-- question : Q
-- answers : A
-- reasons : R 
-- explanation : E .

Dabei ist:

Object:
Name des Objektes.
Q:
Frage an den Benützer (oder ein Test).
A = [ 1: A1, 2: A2... ]:
Ai = mögliche Antwort (oder Resultat des Tests).
R = [ i: Gi, j: Gj, ...]:
Gi = mögliche Begründung für G, wenn Ai zutrifft.
Falls i geantwortet wurde und Gi = true, dann ist G bewiesen.
R = [ G1, G2, ...]:
G1, G2, ... sind mögliche Begründungen für G,
wenn kein Question-Attribut vorhanden ist.
E:
Erklärung (Text), wenn G bewiesen ist.

Die Attribute question und answers sind optional; das Attribut reasons ist obligatorisch; das Attribut explanation ist obligatorisch für bewiesene Goals.

Inferenz

Die Inferenz geschieht top-down, depth-first von Symptomen zu Diagnosen:

solve( G, X) :- 
    (object( G, question, _) 
    -> get_answer( G, A)),
    solve1( G, A, X).
solve1( G, A, X) :-        
    object( G, reasons, Rs),
    (var( A) -> member( G1, Rs); 
    member( A : G1, Rs)),
    solve2( G, G1, X).
solve2( G, true, G).
solve2( G, G1, X) :- 
    solve( G1, X).

8.3.2Frames

Frame (Minsky, 1975) ist ein abstraktes Konzept für die Beschreibung einer prototypischen Situation (eines Objektes, eines Konzeptes), in der alle Informationen, die für diese Situation relevant sind, zusammengefasst sind ("Kontext"). Der Frame legt einen Rahmen für die Beschreibung fest. Der Rahmen wird gefüllt, wenn neue Information über die Situation bekannt wird. Frames werden insbesondere für die Repräsentation von strukturierten und hierachischen Systemen verwendet.

Verwandte Begriffe: Script (Schank, Abelson, 1977), Unit (System KEE), ...

Beispiel 1: Tier-Taxonomie

(s. Fig. 8.4)
tier
-- atmet:  ja
-- hat_Haut: ja 
-- lebt : ja .

vogel
-- is_a : tier.
-- fliegt : ja .

pinguin
-- is_a : vogel
-- fliegt : nein
-- bewegungsart : wackelt.

amsel
-- is_a : vogel 
-- farbe: schwarz
-- frisst: wurm .
Vererbung: Amsel atmet und hat Haut.
Ausnahmen:Pinguin fliegt nicht (nach der Vererbungsregel sollte er fliegen)

Vergleiche die Formulierung in Logik:

lebt( X) :- tier( X).
tier( X) :- vogel( X).
fliegt( X) :- 
    vogel( X), 
    not pinguin( X). 
    /* unschön: alle Ausnahmen */

Die Attribute sind vom Typ:

  1. Beziehung:
    Relationen zwischen Frames, z.B. is_a. "Meta-Attribute", die hierarchische und andere Beziehungen zwischen Frames beschreiben.
  2. Eigenschaft:
    Eigentliche Attribute der Bedeutung "hat Eigenschaft", "has_a ...(value)":

Beispiel 2: Hierarchie graphischer Objekte

Graphische Objekte

Fig. 8.11: Graphische Objekte

g_objekt
-- position
    --- value: (0, 0).

rechteck
-- is_a
    --- value: g_objekt
-- seite_x
    --- value: 1
    --- range: 0..511
-- seite_y
    --- value: 2
    --- range: 0..311
-- flaeche
    --- if_needed: rechteck_flaeche.
    
rechteck_flaeche( F, S, V) :-
    get_value( F, seite_x, X), 
    get_value( F, seite_y, Y), 
    V is X * Y.

Dies ist die klassische 3-stufige Frame-Darstellung bestehend aus Frame-Name, Slots und Facets. Sie ermöglicht es, weitere Informationen (Facets) zu den Attributen (Slots) zuzuordnen, z.B. den Wertebereich oder eine Berechnungsfunktion für den Attribut-Wert.

Frame_id
-- slot_1
    --- facet_11 : value_11
    --- facet_12 : value_12
    --- . . .
-- slot_2
    --- facet_21 : value_21
    --- . . .
-- slot_n
    --- . . .
    --- facet_nk : value_nk .

Die Figur zeigt die allgemein übliche 3-stufige Frame-Struktur. In Prolog ist es ein Term mit den Operatoren:

?- op( 910, xfx, :).
?- op( 920, xfy, ---).
?- op( 930, xfy, --).

Beispiele für Facets:

value: der Wert des Slots (value ist ein ausgezeichnetes Facet)
range: der Wertebereich des Slots
default: ein Default-Wert
if_needed: Dämonfunktion, die evaluiert wird, falls der Wert des Slots
gebraucht (gelesen) wird, aber nicht vorhanden ist ("goal-driven").
if_added: Dämonfunktion, die evaluiert wird, falls der Wert des Slots
geschrieben wird ("data-driven").

Procedural Attachment

Die Slot-Werte sollten nicht nur über die eigene Werte, resp. über die Vererbung gewonnen werden. Sie sollten auch berechnet werden können (Beispiel rechteck_flaeche). Es sollten auch Abhängigkeiten zwischen Slots darstellbar sein. Dazu dienen die sog. Dämonfunktionen, die den Slots in den entsprechenden Facetten angehängt und beim entsprechendem Zugriff evaluiert (getriggert) werden.

Prolog Implementierung eines Frame-Systems

Grundlegendes Zugriffsprädikat:

frame( Frame, Slot, Facet, Value).

is_a Inferenz:

frame_up( Frame, Slot, Facet, Value) :- 
    frame( Frame, Slot, Facet, Value).
frame_up( Frame, Slot, Facet, Value) :- 
    frame( Frame, is_a, value, Parent), 
    frame_up( Parent, Slot, Facet, Value).

Lesezugriff auf Werte (nach der Z-Strategie):

a) Wert des value-Facets oder berechneter Wert der if_needed-Funktion beim Frame
b) Falls a) keinen Wert liefert, dann wiederhole a) beim Vater (etc.) des Frames
get_value( Frame, Slot, Value) :- 
    frame_up( Frame, Slot, Facet, V), 
    (Facet = value 
    -> Value = V 
    ; Facet = if_needed, 
      Demon =.. [ V, Frame, Slot, Value], 
      call( Demon)
    ), !. 
    /* Facet = if_added ignored */

Schreibzugriff auf Werte:

put_value( Frame, Slot, Value).

ist analog zu get_value( Frame, Slot, Value), jedoch Ausführung der eventuellen if_addded-Funktion (Realisierung in der Übung).

Dämonfunktionen-Syntax:

demon_name( Frame, Slot, Value) :- ...

Anwendung: Konfiguration von strukturierten Systemen

Die Prädikate put_value, sowie die Dämonfunktionen (z.B. if_added etc.) führen zu destruktiver Veränderung der Frames (Seiteneffekte) über assert / retract und sollen darum mit grosser Vorsicht verwendet werden. Vgl.: Integritätsbedingungen und Konsistenzerhaltung bei Datenbanken, TMS ("Truth Maintenance System", Doyle, 1979) und ATMS ("Assumption-based Truth Maintenance System", de Kleer 1986).