Information Technology Reference
In-Depth Information
A
A
B
C
B
C
E
D
F
D
E
F
G
H
G
H
Abbildung 24.3: Zwei Graphen zur Illustration der Zerlegung einer Verteilung.
Nachdem nun die beiden Begriffe der Zerlegbarkeit bezüglich eines Graphen
und der Unabhängigkeitskarte definiert wurden, fehlt uns noch die Verknüpfung
zwischen ihnen. Unser Ziel ist es, anhand von Separationen in einer Unabhängig-
keitskarte korrekt auf bedingte Unabhängigkeiten in einer zugrunde liegenden Ver-
teilung zu schließen. Diese Verknüpfung liefern uns die beiden folgenden Sätze.
Satz 24.3
Sei p
V
eine strikt positive Wahrscheinlichkeitsverteilung über einer Menge V von
(diskreten) Attributen. p
V
ist genau dann faktorisierbar bezüglich eines ungerichteten Gra-
phen G
=(
V
,
E
)
,wennGeinbedingterUnabhängigkeitsgraphfürp
V
ist.
Satz 24.4
Sei p
V
eine Wahrscheinlichkeitsverteilung über einer Menge V von (diskreten)
Attributen. p
V
ist genau dann faktorisierbar bezüglich eines gerichteten azyklischen Gra-
phen G
=(
V
,
E
)
,wennGeinbedingterUnabhängigkeitsgraphfürp
V
ist.
Beide Sätze lassen sich (unter Beachtung der Einschränkung, was die strikte Po-
sitivität von
p
in Satz 24.3 betrifft) folgermaßen zusammenfassen:
G
faktorisiert
p
G
ist Unabhängigkeitskarte von
p
Machen wir uns klar, welche Schlussfolgerungen uns diese Äquivalenz erlaubt. An-
genommen, wir stellen fest, dass sich eine Verteilung
p
V
bezüglich eines gegebenen
Graphen
G
zerlegen lässt. Unmittelbar ist klar, dass
G
eine Unabhängigkeitskarte
von
p
V
sein muss (Implikation von links nach rechts). Dies wiederum erlaubt es uns,
jede Separation in
G
als gültige bedingte Unabhängigkeit in
p
V
zu lesen (Implikation
von rechts nach links).
Bisher wurden in den Definitionen und Sätzen meist eine Verteilung und ein
Graph als gegeben angenommen. In der Praxis ist dies allerdings eher die Ausnah-
me. Wir wollen daher nun die beiden Fragen beantworten, wie man bei gegebener
Ve r t e i l ung e i ne mi n ima l e Una bhäng i gke i t s ka r t e ( s owoh l ge r i c h t e t a l s auc h unge r i c h -
tet) erzeugen kann und wie man anhand eines gegebenen Graphen (wieder mit Un-
terscheidung hinsichtlich ungerichteter und gerichteter Kanten) eine Verteilung er-
zeugt, für die der Graph eine minimale Unabhängigkeitskarte ist. Wir werden also
