Database Reference
In-Depth Information
W
r
RP(W
r
|
R)
H
r
RSP(H
r
|
R, S)
H
r
RSP(H
r
|
R, S)
00
.8
000
1
100
0
01
0
001
.1
101
.9
10
.2
010
0
110
1
11
1
011
0
111
1
1. Berechnen Sie die gemeinsame Verteilung P uber R, S, H
r
,W
r
.
2. Bestimmen Sie die Verteilungen P (W
r
) und P (H
r
).
3. Bilden Sie den permanenten Cliquenbaum mit Potentialdarstellung zu G und
P .
13.3.3
Der Algorithmus von Lauritzen und Spiegelhalter
Durch die Zerlegung der gemeinsamen Verteilung in ein Produkt gewisser Funktio-
nen wird eine Darstellung der Verteilung im Rechner oft erst moglich. Jede benotig-
te Wahrscheinlichkeit lasst sich aus der Potentialdarstellung bestimmen. Dennoch
kann die Berechnung einzelner Wahrscheinlichkeiten sehr aufwendig sein. Gerade
die Wahrscheinlichkeiten der Werte der Aussagenvariablen selbst, die meistens von
besonders großem Interesse sind, erfordern das Aufsummieren einer großen Anzahl
von Elementarwahrscheinlichkeiten, von denen jede einzelne erst einmal aus der
Potentialdarstellung berechnet werden muss.
Der
(Propagations)Algorithmus von Lauritzen und Spiegelhalter
nutzt die
Struktur eines Cliquenbaumes, um sukzessive die Randverteilungen der einzelnen
Cliquen P (
C
i
) zu berechnen. Dann lassen sich die Wahrscheinlichkeiten einer Aus-
sagenvariablen V
V
aus den Randverteilungen (die im Allgemeinen sehr viel
kleiner als die globale Verteilung sind) einer jeden Clique
C
j
,zuderV gehort,
bestimmen:
∈
P (V )=
C
j
−{V }
P (
C
j
)
Wir gehen von dem permanenten Cliquenbaum als Wissensbasis aus: Sei
{
eine Potentialdarstellung der gemeinsamen Verteilung P auf
V
,wo-
bei die Cliquen-Ordnung (
C
1
,
C
2
,...,
C
p
) die fortlaufende Schnitteigenschaft RIP
besitze. Aus Proposition 13.33 folgt
C
1
,...,
C
p
; ψ
}
P (
C
i
|
S
i
)=P (
R
i
|
S
i
)
und wegen
S
i
⊆
C
i
erhalten wir
P (
C
i
)=P (
R
i
|
S
i
)P (
S
i
)
(13.28)
Das reduziert das Problem der Bestimmung von P (
C
i
) auf die Bestimmung der
Wahrscheinlichkeiten P (
R
i
.
Wir beginnen dabei mit der letzten Clique
C
p
. Nach Proposition 13.35 ist
|
S
i
) und P (
S
i
)fur jedes i
∈{
1,...,p
}
ψ(
C
p
)
R
p
ψ(
C
p
)
P (
R
p
|
S
p
)=
