Database Reference
In-Depth Information
Selbsttestaufgabe B.34 (d-Separation)
Es sei P eine (positive) Wahrschein-
lichkeitsverteilung uber den Variablen A, B, C,inderA
B gilt.
Geben Sie alle (zusammenhangenden) DAG's an, die diese bedingte Un-
abhangigkeit graphisch reprasentieren, d.h. in denen gilt: B d-separiert A und C.
P
C
|
B.3
Die running intersection property RIP
Definition B.35 (running intersection property, RIP)
Sei
ein
ungerichteter Graph mit q Cliquen. Eine (lineare) Ordnung (
C
1
,...,
C
q
) dieser Cli-
quen hat die
running intersection property, RIP (fortlaufende Schnitteigenschaft)
,
wenn es fur jedes i
G
=
V
,
E
∈{
2,...,q
}
ein j<igibt, so dass
C
i
∩
(
C
1
∪
...
∪
C
i−1
)
⊆
C
j
(B.1)
gilt.
Selbsttestaufgabe B.36 (running intersection property)
Prufen Sie, ob die
Ordnung (
C
1
,
C
2
,...,
C
7
) der Cliquen in Beispiel B.14 die RIP besitzt.
Nicht in jedem Fall kann eine Cliquen-Ordnung mit der
running intersection
property
gefunden werden. Bei triangulierten Graphen ist das jedoch immer moglich,
wobei eine passende Cliquen-Ordnung durch eine MCS-Ordnung bestimmt werden
kann.
Theorem B.37 (MCS und RIP)
Sei
ein triangulierter ungerichteter
Graph. Sei α eine Ordnung auf
V
, die dem MCS-Kriterium folgt, und die Cliquen
von
G
=
V
,
E
seien gemaß ihrer maximalen Knoten geordnet. Dann besitzt diese Cliquen-
Ordnung die
running intersection property
.
G
Ein Beweis dieses Theorems findet sich z. B. in [168].
Die
running intersection property
ermoglicht die Anordnung der Cliquen eines
Graphen in einer Baumstruktur, dem sog.
Cliquen-
oder
Verbindungsbaum
(
junction
tree
), dessen Knoten gerade die Cliquen sind:
Sei also
C
1
,...,
C
q
eine RIP-Ordnung der Cliquen eines triangulierten Graphen
G
.Fur i
∈{
2,...,q
}
definiere die Menge
S
i
:=
C
i
∩ (
C
1
∪ ...∪
C
i−1
)
Wegen der
running intersection property
gibt es zu jedem solchen i ein j<iso,
dass
S
i
⊆
C
j
ist; gibt es mehrere solcher j,sowahle man eines, j(i), aus.
C
j(i)
wird dann als Elternclique zu
C
i
bestimmt. Auf diese Weise entsteht ein Baum
mit Knotenmenge
{
C
1
,...,
C
q
}
.DieMengen
S
i
sind Separatoren des zerlegbaren
Graphen
(im Sinne von Definition B.26) und werden auch als
Separatoren
des
Cliquenbaumes bezeichnet. Haufig notiert man sie als Label an den Kanten des
Cliquenbaumes.
G
