Information Technology Reference
In-Depth Information
I
p
I
G
I
G
= I
p
I
G
I
p
Abhängigkeitskarte
Unabhängigkeitskarte
perfekte Karte
Abbildung 24.2: Zusammenhänge der Folgerbarkeit von bedingten Unabhängigkei-
ten in den verschiedenen Kartenarten.
24.1 Abhängigkeits- und Unabhängigkeitsgraphen
Aufgrund der i. Allg. nicht herstellbaren Isomorphie der Unabhängigkeits- und Se-
parationsbegriffe, werden wir uns mit abgeschwächten Varianten befassen. Dazu be-
trachten wir zuerst die folgenden Definitionen.
Definition 24.5 (Abhängigkeitskarte, Unabhängigkeitskarte, perfekte Karte)
Sei
(·
p
·|·)
eine dreistellige Relation, die die bedingten Unabhängigkeiten einer gege-
benen Verteilung p über der Attributmenge V repräsentiert. Ein ungerichteter (gerichteter)
Graph G
=(
V
,
E
)
heißt
bedingter Abhängigkeitsgraph
oder
Abhängigkeitskarte
be-
züglich p genau dann, wenn für alle disjunkten Teilmengen X
,
Y
,
Z
V
X
p
Y
|
Z
X
G
Y
|
Z
gilt, d. h. wenn G durch u-Separation (d-Separation) alle bedingten Unabhängigkeiten in p
beschreibt und folglich ausschließlich korrekte Abhängigkeiten erklärt.
Ein ungerichteter (gerichteter) Graph G
=(
V
,
E
)
heißt
bedingter Unabhängigkeits-
graph
oder
Unabhängigkeitskarte
bezüglich p genau dann, wenn für alle disjunkten Teil-
mengen X
,
Y
,
Z
V
X
G
Y
|
Z
X
p
Y
|
Z
gilt, d. h. wenn G durch u-Separation (d-Separation) nur solche bedingten Unabhängigkeiten
beschreibt, die auch in p gelten. G heißt
perfekte Karte
der bedingten (Un)abhängigkeiten
in p genau dann, wenn er sowohl eine Abhängigkeits- als auch eine Unabhängigkeitskarte
(bezüglich p) ist.
Ein Abhängigkeitsgraph kann also zusätzlich zu sämtlichen bedingten Unabhän-
gigkeiten der Verteilung
p
weitere enthalten, die in
p
ungültig sind. Ein Unabhängig-
keitsgraph hingegen kodiert nur solche bedingten Unabhängigkeiten, die auch in
p
gültig sind, möglicherweise aber nicht alle. Abbildung 24.2 illustriert diesen Zusam-
menhang.
Wir haben in Kapitel 22 gesehen, dass wir unter Ausnutzung von bedingten Un-
abhängigkeiten in der Lage sind, Verteilungen zu zerlegen und effizient mit ihnen
zu rechnen. Folglich muss sichergestellt werden, dass aus einem Graphen unter kei-
nen Umständen (in der Verteilung) ungültige bedingte Unabhängigkeiten abgeleitet
