Database Reference
In-Depth Information
13.1.3
Konstruktion von Markov-Graphen
Um die Verbindung zwischen Wahrscheinlichkeitsverteilungen und Unabhangig-
keitsgraphen bzw. Markov-Graphen tragbar zu machen, mussen die folgenden bei-
den Punkte geklart werden:
•
Gibt es zu einer beliebigen Wahrscheinlichkeitsverteilung P einen Markov-
Graphen?
•
Kann man zu einem beliebigen Graphen
G
eine Wahrscheinlichkeitsverteilung
P definieren, so dass
G
ein Unabhangigkeitsgraph zu P ist?
Beide Fragen konnen im Wesentlichen positiv beantwortet werden.
Die Idee zur Losung des ersten Problems ist einfach: Ausgehend von einem
vollstandigen Graphen auf
V
entfernt man alle Kanten (A, B), fur die A
P
B
|
(
V
) gilt, fur die also die zugehorigen Variablen bedingt unabhangig
sind, wenn die restlichen Variablen gegeben sind. (Umgekehrt kann man naturlich
auch von einem leeren Graphen starten und nur die Knoten verbinden, bei denen
A
−{
A, B
}
)fur die entsprechenden Variablen
falsch
ist.) Diese Proze-
dur liefert fur alle strikt positiven Wahrscheinlichkeitsverteilungen einen Markov-
Graphen, der sogar eindeutig bestimmt ist:
P
B
|
(
V
−{
A, B
}
Theorem 13.7 ([176])
Jede strikt positive Wahrscheinlichkeitsverteilung
P
besitzt
einen eindeutig bestimmten Markov-Graphen
G
0
=
V
,
E
0
mit
(A, B) /
∈E
0
gdw.
A
P
B
|
(
V
−{
A, B
}
)
(13.8)
(13.8) wird die
paarweise Markov-Eigenschaft
genannt.
Zum Nachweis dieses Theorems benotigt man, dass
P
die Eigenschaften Sym-
metrie, Zerlegbarkeit und Schnitt erfullt (vgl. [175]). Das folgende Beispiel zeigt,
dass auf die Voraussetzung der strikten Positivitat von P nicht verzichtet werden
kann.
Beispiel 13.8
Wir
betrachten
ein
Modell
mit
vier
binaren
Variablen
A
1
,A
2
,A
3
,A
4
, die durch Gleichheit miteinander gekoppelt sind, d. h.
a
3
a
4
)=
0.5wenna
1
=a
2
=a
3
=a
4
P (a
1
a
2
0s st
Jedes Paar von Variablen A
i
,A
j
ist bedingt unabhangig, wenn das andere Varia-
blenpaar gegeben ist:
A
k
,A
l
}
Der gemaß Theorem 13.7 konstruierte Graph
A
i
P
A
j
|{
G
0
besitzt also gar keine Kanten, be-
steht folglich aus vier isolierten Knoten. Dies ist jedoch kein Unabhangigkeitsgraph
fur P , da die vier Variablen naturlich nicht unabhangig voneinander sind.
Definition 13.9 (Markov-Decke, Markov-Rand)
Sei A
V
eine Variable. Als
Markov-Decke (Markov blanket) bl
(A)
von
A wird jede Variablenmenge
B
∈
⊆
V
bezeichnet, fur die gilt:
