Information Technology Reference
In-Depth Information
Entfernen wir die Kantenrichtungen, so erhalten wir den darunter abgebildeten un-
gerichteten Graphen
G
u
,dessenMengekodierterbedingterUnabhängigkeitenje-
doch keine Teilmenge derjenigen von
G
1
ist:
I
G
u
= {
A
G
1
D
|
C
,
B
G
1
D
|
C
,
A
G
1
B
|
C
}I
G
1
Es gibt also mindestens eine neue bedingte Unabhängigkeit (hier:
A
G
u
B
|
C
), die
nicht im ursprünglichen Graphen
G
1
gilt.
4
Somit ist
G
u
kein äquivalenter ungerich-
teter Graph zu
G
1
!Zielmussesdahersein,eineTransformationzufinden,dieunter
keinen Umständen zusätzliche bedingte Unabhängigkeiten erzeugt und sei es zum
Preis des Verlustes vorhandener bedingter Unabhängigkeiten.
Es sei angemerkt, dass nicht jeder gerichtete, azyklische Graph von dem eben ge-
zeigten Phänomen betroffen ist. Schauen wir uns den Graphen
G
2
in Abbildung 25.2
an. Für sein ungerichtetes Pendant
G
u
gilt sehr wohl
I
G
u
I
G
2
.
(Hier ist sogar die Gleichheit erreicht, was nicht notwendig immer so sein muss.)
Offensichtlich ist die asymmetrische Definition der d-Separation verantwortlich
dafür, dass im Falle konvergierender Kanten, Probleme auftreten. Es muss also ver-
hindert werden, dass die beiden Elternknoten eines gemeinsamen Kindknotens be-
dingt unabhängig werden, sobald der Kindknoten instanziiert ist. Dies erreicht man,
indem Elternknoten, die noch nicht durch eine Kante verbunden sind, nun verbun-
den werden (Die Kantenrichtung kann willkürlich gewählt werden, da sie im näch-
sten Schritt ignoriert wird). Dies ist rechts in Abbildung 25.2 anhand des Graphen
G
1
gezeigt. Durch das Verbinden der beiden Knoten
A
und
B
geht zwar eine (marginale,
also unbedingte) Unabhängigkeit verloren, allerdings verhindern wir das Auftreten
einer neuen, sodass
I
G
u
I
G
1
gilt.
Die Transformation, unverbundene Elternknoten zu verbinden, kennen wir be-
reits als Moralisierung.
5
Somit sind wir in der Lage, jedes gegebene graphische
Modell in ein einheitliches Eingabeformat (nämlich einen Verbundbaum) für den
Evidenzpropagationsalgorithmus zu bringen: Handelt es sich um ein Markov-Netz,
wird der entsprechende ungerichtete Graph lediglich gegebenenfalls trianguliert,
um dann sofort in einen Verbundbaum überführt zu werden. Haben wir es mit ei-
nem Bayes-Netz zu tun, so wird der zugrunde liegende Graph moralisiert, gegebe-
nenfalls trianguliert und dann ebenfalls in einen Verbundbaum überführt. Wir wol-
len dies an einem Beispiel illustrieren, welches uns auch für die eigentliche Evidenz-
propagation begleiten wird.
Beispiel 25.1 (Verbundbaum aus Bayes-Netz)
Wir werden im Folgenden eine Evidenz-
propagation im Bayes-Netz aus Abbildung 25.3 (a) betrachten. Das Ergebnis der Morali-
sierung ist in Abbildung 25.3 (b) zu sehen. Der Kreis E
C
F
GbesitztkeineSehne
und muss daher um eine solche ergänzt werden. Wir entscheiden uns für die Sehne C
G
(E
Fwäreebensomöglichgewesen)underhaltendentrianguliertenGrapheninAbbil-
dung 25.3 (c). Wir kennen diesen Graphen bereits aus Abbildung 24.3 und Beispiel 24.2,
4
Die Tatsache, dass außerdem eine vorher vorhandene bedingte Unabhängigkeit, nämlich
A
G
1
B
|
,verlorenging,istzwarunschön,ändertaberamCharakterderUnabhängigkeitskartenichts.
5
Siehe Definition 23.29 auf Seite 368.
