Information Technology Reference
In-Depth Information
D
C
A
B
Abbildung 23.19: Ungerichteter Graph oh-
ne äquivalenten gerichteten Graph und
gerichteter Graph ohne äquivalenten un-
gerichteten Graph.
A
B
C
aktivieren. Anders verhält es sich bei der d-Separation, bei der ein Hinzufügen von
Knoten zu
Z
sehr wohl einen Pfad aktivieren und vormals d-getrennte Mengen
X
und
Y
nun zusammenhängen lassen kann. Würden wir im Beispiel 23.8 die Men-
ge
Z
= {
E
,
J
},diedieKnoten
D
und
L
d-separiert, um beispielsweise den Knoten
K
erweitern, so aktiviert dieser den Pfad
D
H
K
I
L
und verhindert die
d-Trennung von
D
und
L
:
D
L
|
E
,
J
aber
D
L
|
E
,
J
,
K
Auch sind u-Separation und d-Separation unterschiedlich mächtig. Betrachten
wir den ungerichteten Graphen in Abbildung 23.19. Durch u-Separation liest man
leicht folgende beiden Separationen ab:
A
C
|
B
,
D
und
B
D
|
A
,
C
Es lässt sich jedoch kein gerichteter Graph finden, der diese beiden Separationen
gleichzeitig und ausschließlich
11
enthält. Würde man die Kanten von
A
ausgehend
über
B
und
D
nach
C
ausrichten, würde man per d-Separation zwar die Aussage
A
C
|
B
,
D
erhalten, jedoch folgte sofort
B
D
|
A
,
C
,da
C
ein konvergierender
Knoten wäre, der den Pfad
D
C
B
aktivierte.
Umgekehrt lässt sich auch nicht zu jedem gerichteten Graph ein (bezüglich der
in ihm kodierten Separationskriterien) äquivalenter ungerichteter Graph finden, wie
der rechte Graph in Abbildung 23.19 zeigt. In ihm ist die d-Separation
A
B
|
kodiert. Erneut lässt sich diese Aussage allein in keinem ungerichteten Graphen ab-
bilden, ohne zusätzliche Separationen zu kodieren.
11
Die Ausschließlichkeit müssen wir fordern, um keine zusätzlichen Separationen im Graphen zu ko-
dieren. Ansonsten würde ein kantenloser Graph sämtliche denkbaren Separationen beinhalten, also auch
die beiden oben angegebenen.
