Database Reference
In-Depth Information
Die Faktoren α
i
und β
i
spiegeln z. B. die Kontakthaufigkeit des entsprechenden
Paares wider. Mit diesem Ansatz erhalt man beispielsweise
P (abcd)=K
·
α
1
α
2
α
3
α
4
P (abc d)=K
·
β
1
α
2
α
3
β
4
Selbst wenn die Verteilung P bekannt ist, ist die Bestimmung von α
i
und β
i
aus allen
solchen Gleichungen nicht einfach. Umgekehrt ist die probabilistische Interpretation
der ψ
i
und der entsprechenden Faktoren nicht klar - in welcher Beziehung stehen
sie zu absoluten und bedingten Wahrscheinlichkeiten?
Dieses Beispiel unterstreicht ubrigens gut die Existenzberechtigung ungerich-
teter Markov-Graphen: Wegen der vollstandigen Gegenseitigkeit der Ansteckungs-
gefahr ließe sich hier eine azyklische Richtung der Kanten aus der Problemstellung
heraus nur schwerlich motivieren.
Die korrekte Deutung und Spezifikation der Potentialfunktionen wirft im allge-
meinen Fall erhebliche Probleme auf. Fur Unabhangigkeitsgraphen einer speziellen
Bauart lasst sich jedoch noch eine einfachere Produktdarstellung angeben:
Theorem 13.20 ([175])
Ist
ein triangulierter Unabhangigkeitsgraph zur Vertei-
lung
P
,sofaktorisiert
P
in der Form
P (
V
)=
C
i
P (
C
i
)
G
S
j
P (
S
j
)
(13.14)
wobei die
C
i
und
S
j
die Cliquen und Separatoren eines Cliquenbaumes von
G
sind
(siehe Anhang B, S. 516).
Die Produktdarstellung (13.14) ist von grundlegender Bedeutung fur die ma-
schinelle Handhabung von Wahrscheinlichkeiten, da sie die globale Verteilung in
kleinere, lokale Verteilungen aufspaltet und so die gefurchtete Komplexitat einer
Verteilung aufbricht.
Beispiel 13.21
Wir betrachten den triangulierten Graphen
G
in Abbildung 13.3;
G
besitzt die Cliquen
{
B, C, D
}
,
{
B, D, E
}
,
{
A, B, E
}
,
{
D, E, G
}
,
{
E,F,G
}
,
{
D, H
}
und die Separatoren
{
B, D
}
,
{
B, E
}
,
{
D, E
}
,
{
E,G
}
,
{
D
}
(vgl. Beispiel B.38, S.
517). Ein Markov-Feld P zu
G
hat dann die folgende Darstellung:
P (A, B, C, D, E, F, G, H)
P (B, C, D)P (B, D, E)P (A, B, E)P (D, E, G)P (E,F,G)P (D, H)
P (B, D)P (B, E)P (D, E)P (E,G)P (D)
=
ein minimaler Unabhangigkeitsgraph
zu P ist. Ein triangulierter Unabhangigkeitsgraph lasst sich immer aus dem Markov-
Graphen von
Theorem 13.20 setzt nicht voraus, dass
G
durch Einfugen von Kanten (sog.
Fill-in
, vgl. Definition B.19, S.
511) gewinnen. Diese zusatzlichen Kanten vereiteln moglicherweise die graphische
Reprasentation gewisser bedingter Unabhangigkeiten, doch der entstehende trian-
gulierte Graph ist immer noch ein Unabhangigkeitsgraph zu P , aus dem sich die
obige Produktdarstellung (13.14) ableiten lasst.
G
