Information Technology Reference
In-Depth Information
in C beschreiben lassen. Dann heißt p
V
zerlegbar oder faktorisierbar bezüglich G, wenn es
Funktionen
C
:
E
C
IR
0
,
C
C
,gibtso,dassgilt:
a
1
dom(
A
1
) : ···
a
n
dom(
A
n
) :
p
V
=
C
C
C
A
i
=
a
i
A
i
=
a
i
A
i
V
A
i
C
Definition 24.8 (zerlegbar bezüglich eines gerichteten azyklischen Graphen)
Eine Wahrscheinlichkeitsverteilung p
V
über einer Menge V
= {
A
1
,...,
A
n
}
von Attri-
buten heißt zerlegbar oder faktorisierbar bezüglich eines gerichteten azyklischen Graphen
G
=(
V
,
E
)
genau dann, wenn sie geschrieben werden kann als Produkt der bedingten
Wahrscheinlichkeiten der Attribute gegeben ihre Elternknoten in G, d. h., wenn gilt
a
1
dom
(
A
1
)
:
···
a
n
dom
(
A
n
)
:
p
V
A
j
=
A
i
V
P
A
i
=
a
i
A
i
=
a
i
A
j
=
a
j
A
i
V
pa
G
(
A
i
)
Betrachtenwir zwei Beispiele, umdie Zerlegung anhand eines ungerichteten und
eines gerichteten Graphen zu illustrieren.
Beispiel 24.2 (Zerlegung anhand eines ungerichteten Graphen)
Der in Abbildung 24.3 gezeigte ungerichtete Graph besitzt die folgenden Cliquen:
C
1
= {
B
,
C
,
E
,
G
}
,
C
2
= {
A
,
B
,
C
}
,
C
3
= {
C
,
F
,
G
}
,
C
4
= {
B
,
D
}
,
C
5
= {
G
,
F
,
H
}
Die durch sie induzierte Zerlegung lautet:
a
dom(
A
) : ···
h
dom(
H
) :
p
V
(
A
=
a
,...,
H
=
h
)=
C
1
(
B
=
b
,
C
=
c
,
E
=
e
,
G
=
g
)
·
C
2
(
A
=
a
,
B
=
b
,
C
=
c
)
·
C
3
(
C
=
c
,
F
=
f
,
G
=
g
)
·
C
4
(
B
=
b
,
D
=
d
)
·
C
5
(
G
=
g
,
F
=
f
,
H
=
h
)
Beispiel 24.3 (Zerlegung anhand eines gerichteten, azyklischen Graphen)
Der in Abbildung 24.3 gezeigte gerichtete, azyklische Graph induziert die folgende Zerle-
gung:
a
dom
(
A
)
:
···
h
dom
(
H
)
:
p
V
(
A
=
a
,...,
H
=
h
)=
P
(
H
=
h
|
G
=
g
,
F
=
f
) ·
P
(
G
=
g
|
B
=
b
,
E
=
e
)
·
P
(
F
=
f
|
C
=
c
) ·
P
(
E
=
e
|
B
=
b
,
C
=
c
)
·
P
(
D
=
d
|
B
=
b
) ·
P
(
C
=
c
|
A
=
a
)
·
P
(
B
=
b
|
A
=
a
) ·
P
(
A
=
a
)
