Information Technology Reference
In-Depth Information
Kapitel 24
Zerlegungen
Ziel dieses Kapitels ist die Zusammenführung des Konzeptes der bedingten Unab-
hängigkeit und der Separation in Graphen. Beide wurden als dreistellige Relatio-
nen
(· · | ·)
auf entweder Attributen oder Knoten dargestellt und es scheint viel-
versprechend, die wahrscheinlichkeitstheoretischen Gegebenheiten einer Verteilung
mit Hilfe eines Graphen zu beschreiben, um dann lediglich anhand graphentheore-
tischer Eigenschaften (Separationen) auf (bedingte) Unabhängigkeiten zu schließen.
Denn letztere sind es, welche eine Zerlegung und Evidenzpropagation erst ermögli-
chen.
Wir werden zuerst eine Axiomatisierung des Begriffes der bedingten Unabhän-
gigkeit (bzw. der Separation) vornehmen, was auf [Dawid 1979] und [Pearl u. Paz
1987] zurückgeht. Damit können dann rein syntaktisch neue Unabhängigkeiten bzw.
Separationen aus einer Menge bereits bekannter abgeleitet werden, ohne die wahr-
scheinlichkeits- oder graphentheoretischen Definitionen selbst zu prüfen.
Definition 24.1 (Semi-Graphoid- und Graphoid-Axiome)
Sei V eine Menge mathematischer Objekte und
(· · | ·)
eine dreistellige Relation auf V.
Weiter seien W, X, Y und Z vier disjunkte Teilmengen von V. Dann heißen die Aussagen
a) Symmetrie:
(
X
Y
|
Z
) (
Y
X
|
Z
)
(
W
X
Y
|
Z
) (
W
Y
|
Z
) (
X
Y
|
Z
)
b) Zerlegung:
c) Schwache Vereinigung:
(
W
X
Y
|
Z
) (
X
Y
|
Z
W
)
d) Zusammenziehung:
(
X
Y
|
Z
W
) (
W
Y
|
Z
) (
W
X
Y
|
Z
)
die
Semi-Graphoid-Axiome
.EinedreistelligeRelation
(· · | ·)
,diedieSemi-Graphoid-
Axiome für alle W, X, Y und Z erfüllt, heißt
Semi-Graphoid
.DieobigenAussagenund
e) Schnitt:
(
W
Y
|
Z
X
) (
X
Y
|
Z
W
) (
W
X
Y
|
Z
)
heißen
Graphoid-Axiome
.EinedreistelligeRelation
(· · | ·)
,diedieGraphoid-Axiome
für alle W, X, Y und Z erfüllt, heißt
Graphoid
.
Die Axiome b) bis e) sind in Abbildung 24.1 schematisch dargestellt.
Wenn wi r von Mengen
I
von Unabhängigkeits- oder Separationsaussagen spre-
chen, meinen wir algebraisch dieselben Strukturen, lediglich deren Herkunft ist ver-
schieden.
