Database Reference
In-Depth Information
Diese bedingte Wahrscheinlichkeit lasst sich also leicht aus der Potentialdarstel-
lung gewinnen. Proposition 13.37 zeigt nun, wie man eine Potentialdarstellung der
Randverteilung auf
C
1
∪
∪
C
p−1
durch Modifikation von ψ erhalt. Dann aber
lasst sich Proposition 13.35 auf die Mengenkette
C
1
,...,
C
p−1
anwenden, und man
erhalt P (
R
p−1
|
S
p−1
). Durch wiederholtes Anwenden der obigen beiden Satze kann
man also alle erforderlichen bedingten Wahrscheinlichkeiten P (
R
i
|
S
i
) berechnen.
Diese Prozedur lasst sich folgendermaßen veranschaulichen: Ausgehend von den
Blattern des Cliquenbaumes werden “Nachrichten” aufwarts zu den Elterncliquen
gesandt. Die Elternclique passt ihre lokale Potentialfunktion entsprechend den emp-
fangenen Nachrichten an, und wenn die Nachrichten aller Kindcliquen auf diese
Weise b er ucksichtigt worden sind, gibt sie selbst eine Nachricht an ihre Elternclique
weiter.
Dabei ist es wichtig, nach Abschluss der Propagationen wieder auf eine Potenti-
aldarstellung zuruckgreifen zu konnen. Sobald
C
i
ihre Nachricht an ihre Elternclique
geschickt hat, wird daher
...
ψ
(neu)
(
C
i
):=P (
R
i
|
S
i
)
gesetzt, und nach Beendigung des gesamten Anpassungsprozesses ist dann
ψ
(neu)
(
C
1
):=P (
R
1
|
S
1
)=P (
C
1
)
.Gemaß Satz 13.39 liefert ψ
(neu)
wieder eine Potenti-
wegen
R
1
=
C
1
und
S
1
=
∅
aldarstellung von P .
Damit ist unser Problem aber noch nicht ganz gelost. Wir haben gezeigt, wie
man alle bedingten Wahrscheinlichkeiten P (
R
i
|
S
i
)fur jedes i bestimmt. Was noch
fehlt, sind die Wahrscheinlichkeiten P (
S
i
).
Fur die Wurzelclique
C
1
ist
S
1
=
und daher P (
C
1
)=ψ
(neu)
(
C
1
)(s.o.).Fur
∅
die zweite Clique erhalten wir
S
2
)P (
S
2
)=ψ
(neu)
(
C
2
)P (
S
2
)
P (
C
2
)=P (
R
2
|
Da S
2
⊆
C
1
gilt, kann in dieser Gleichung P (
S
2
) aus der bereits bestimmten Rand-
verteilung P (
C
1
) durch Aufsummieren berechnet werden:
P (
S
2
)=
C
1
−
S
2
P (
C
1
)
Analoge Schritte fuhren nun zur Bestimmung der Randverteilungen von P auf
C
3
,...,
C
p
, also auf allen Cliquen und damit auf allen Mengen
S
i
. Wichtig ist dabei
die fortlaufende Schnitteigenschaft, die sicherstellt, dass jedes
S
i
ganz in einer der
vorher berechneten Cliquen enthalten ist.
Wieder lasst sich dieser Berechnungsprozess im Cliquenbaum veranschaulichen:
Diesmal werden, beginnend von der Wurzelclique aus, Nachrichten abwarts im
Baum zu den Kindern geschickt. Die empfangende Clique berechnet ihre margi-
nalen Wahrscheinlichkeiten durch Multiplikation der lokalen Potentialfunktion mit
den empfangenen Werten und sendet ihrerseits Nachrichten zu ihren Kindcliquen.