Information Technology Reference
In-Depth Information
jedem seiner Nachbarknoten genau eine Nachricht. Die Nachricht
M
B
C
vom Kno-
ten
B
zum Knoten
C
ist auf den Attributen der Separatormenge
S
BC
erklärt. Der
Wert der Nachricht von
B
nach
C
ist abhängig von der Potentialtabelle des senden-
den Knotens
B
und den Nachrichten aller
anderen
Nachbarn, die
B
empfangen hat.
Diese Werte werden aufmultipliziert und auf die Attribute in
S
BC
marginalisiert:
M
B
C
(
s
BC
)=
b
B
(
b
)
D
adj(
B
)\{
C
M
D
B
(
s
DB
)
·
(25.2)
\
s
BC
Da zur Berechnung einer Nachricht von
B
nach
C
auch die restlichen empfangenen
Nachrichten von
B
benötigt werden, ist klar, dass zuerst jene Knoten ihre Nachrich-
ten senden können, die keine weiteren Nachbarknoten besitzen: also die äußeren
Knoten des Verbundbaumes. Wir werden später sehen, wie sich so Kaskaden von
Nachrichten ergeben.
3. Aktualisierung
Nachdem alle Nachrichten gesendet wurden, kann jeder Knoten
C
seine Verbund-
wahrscheinlichkeit
P
(
c
) als Produkt seines Potentialwertes und aller empfangenen
Nachrichten berechnen:
B
adj(
C
)
proj
S
BC
(
c
)
P
(
c
)
C
(
c
)
·
M
B
C
(25.3)
Das -Zeichen bedeutet, dass die Verteilung
P
(
c
)
normalisiert wird, falls die
Summe über alle
c
nicht Eins ergeben sollte.
4. Marginalisierung
Nachdem nun jeder Knoten seine aktualisierte Verbundverteilung berechnet hat,
wird für jedes Attribut
A
die kleinste Clique
C
gesucht, die es enthält, um den Mar-
ginalisierungsaufwand möglichst gering zu halten (eine Marginalisierung aus allen
anderen Cliquen, die
A
enthalten wäre natürlich ebenfalls möglich):
P
(
a
)=
c
\
a
P
(
c
)
Betrachten wir nun einen vollständigen Lauf des Algorithmus. Das Bayes-Netz
in Abbildung 25.3 (a) habe die in Abbildung 25.4 gezeigte Parametrisierung.
Beispiel 25.2 (Initialisierung)
Für den Verbundbaum in Abbildung 25.3 (d) nutzen wir
das ursprüngliche Bayes-Netz aus Abbildung 25.3 (a) und erhalten folgende Potentiale:
C
1
(
b
,
c
,
e
,
g
)=
P
(
e
|
b
,
c
) ·
P
(
g
|
e
,
b
)
C
2
(
a
,
b
,
c
)=
P
(
b
|
a
) ·
P
(
c
|
a
) ·
P
(
a
)
C
3
(
c
,
f
,
g
)=
P
(
f
|
c
)
C
4
(
b
,
d
)=
P
(
d
|
b
)
C
5
(
g
,
f
,
h
)=
P
(
h
|
g
,
f
)
