Information Technology Reference
In-Depth Information
weshalb wir die dort identifizierten Cliquen wiederverwenden können und unmittelbar den
Ve r bundbaum i n Abb i l dung 25 . 3 ( d ) e rh a l t en . Es s e i ang eme r k t , d a s s auc h b e i d e r Tr i angu l i e -
rung (ebenso wie bei der Moralisierung) maximal Kanten hinzugefügt werden, sich also der
Charakter der bedingten Unabhängigkeitskarte nicht ändert.
Die Evidenzpropagation wird folgende prinzipielle Schritte besitzen:
1. Initialisierung:
Die Evidenzen, d. h., die bekannten Attributwer-
te, werden in die relevanten Cliquenpotentiale
eingepflegt.
2. Nachrichtenversand:
Benachbarte Cliquen schicken sich gegenseitig
je eine Nachricht, um diese Änderungen mitzu-
teilen. Es werden also über jede Kante genau
zwei Nachrichten geschickt. Bei
r
Cliquen in der
Baumstruktur folglich 2
(
r
1
)
Nachrichten.
3. Aktualisierung:
Nachdem alle Nachrichten gesendet wurden,
kann jede Clique die Verbundwahrscheinlichkeit
ihrer Attribute neu berechnen.
4. Marginalisierung:
Da wir an Marginalwahrscheinlichkeiten einzel-
ner Attribute interessiert sind, marginalisieren
wir jedes Attribut aus der kleinsten Clique, die
es enthält.
Wir werden nun diese vier Schritte näher untersuchen.
1. Initialisierung
Wir haben mit Algorithmus 24.1 auf Seite 395 bereits eine Variante zur Festlegung
der Cliquenpotentiale kennengelernt. Stammt der Verbundbaum (wie in unserem
Fall hier) aus einem Bayes-Netz, so können wir die Potentiale aller Cliquen
C
C
sehr einfach als Produkt der bedingten Wahrscheinlichkeiten aller Knotenfamilien,
die vollständig in
C
liegen, bestimmen:
fa
(
A
)
C
A
=
proj
{
A
}
(
c
)
pa
(
A
)=
proj
pa
(
A
)
(
c
)
C
(
c
)=
1
·
P
(25.1)
We rden d i e We r t e e i ne r ode r mehre re r At t r i but e bekannt , so f ühr t d i e s e Ev i denz zur
Modifikation von Potentialen derjenigen Cliquen, die ein oder mehrere diese Evi-
denzattribute enthalten: Für Attributwertkombinationen, die mit der Evidenz nicht
kompatibel sind, liefere die Potentialfunktion den Wert Null, in allen anderen Fällen
bleibt der Wert unverändert:
0, falls proj
E
C
(
c
) = proj
E
C
(
e
)
C
(
c
),son t
C
(
c
)=
2. Nachrichtenversand
Es werden nun zwischen Nachbarknoten wechselseitig Nachrichten ausgetauscht,
um die Änderungen in den Potentialen zu kommunizieren. Jeder Knoten schickt
