Information Technology Reference
In-Depth Information
Kapitel 25
Evidenzpropagation
Nachdemwir die effiziente Repräsentation von Experten- und Domänenwissen ken-
nengelernt haben, wollen wir nun diese nutzen, um Schlussfolgerungen zu zie-
hen, wenn neue Erkenntnisse (Evidenz) zur Verfügung stehen. Das Volkswagen-
Beispiel des letzten Kapitels aufgreifend könnte dies dem Aktualisieren der einzel-
nen Verbauraten aller Fahrzeugteile gleichkommen, wenn beispielsweise bekannt
wird, dass der Kunde einen bestimmten Motortyp
m
verlangt hat. Ziel wird es sein,
die bekannt gewordene Evidenz durch das zugrunde liegende Netz zu leiten (zu pro-
pagieren), um somit sämtliche relevanten Attribute zu erreichen. Es lässt sich schon
absehen, dass hierfür die Graphenstruktur eine wichtige Rolle spielen wird.
Ist ein graphisches Modell (egal ob Markov- oder Bayes-Netz)
G
=(
V
,
E
) über
einer Attributmenge
V
und zugrunde liegender Verteilung
p
V
gegeben und wird
der Wert
a
o
eines Attributes
A
o
V
bekannt, so entspricht das Propagieren dieser
Evidenz formal der Berechnung der folgenden bedingten Wahrscheinlichkeiten:
1
A
V
\{
A
o
} :
a
dom(
A
) :
P
(
A
=
a
|
A
o
=
a
o
)
Es findet sich eine Vielzahl von Algorithmen zum Thema Evidenzpropagation.
Diese unterscheiden sich je nach zugrunde liegendem graphischen Modell (Markov-
oder Bayes-Netz), nach Graphtopologie (Baum, Polybaum
2
,allgemeinerGraphoder
gänzlich losgelöst von einer Graphenstruktur), oder nach Art der Berechnung (exakt
oder approximativ), um nur die wichtigsten Merkmale dieser Verfahren zu nennen.
Es kann uns soll nicht Ziel dieses Kapitels sein, einen umfassenden Überblick über
die Verfahren zur Evidenzpropagation zu geben. Vielmehr soll ein Verfahren, wel-
ches mit beliebigen graphischen Modellen umgehen kann, ausführlich beschrieben
und durchgesprochen werden.
Wir hatten im Einleitungskapitel 22 an einem Minimalbeispiel gesehen, dass der
die Zerlegung beschreibende Graph uns ebenfalls für die Evidenzpropagation dien-
lich ist: Die (ungerichtete) Baumstruktur garantierte zum einen eindeutige Pfade
zwischen den Attributen, zum anderen zerfällt sie beim Entfernen eines (inneren)
1
Der Index
o
stehe für engl.
observed
,also
beobachtet
.
2
Ein Polybaum ist ein gerichteter Baum, in dem Knoten mehr als einen Elternknoten besitzen können.
Graph
G
1
in Abbildung 25.2 auf Seite 405 ist beispielsweise ein Polybaum, während es sich bei
G
2
um
einen einfachen Baum handelt.
