Database Reference
In-Depth Information
F
1
(A,
nb
(A))
A
F
1
(A,
nb
(A))
Andererseits erhalt man durch Aufsummieren
P (A
|
V
−{
A
}
)=
P (A,
nb
(A))
=
K
·
F
1
(A,
nb
(A))F
2
(
V
−{
A
}
)
V
−(nb(A)∪{A})
⎛
⎞
⎝
⎠
=
K
·
F
1
(A,
nb
(A))
·
F
2
(
V
−{
A
}
)
V
−(nb(A)∪{A})
und
P (
nb
(A))
=
K
·
F
1
(A,
nb
(A))F
2
(
V
−{
A
}
)
A
V
−(nb(A)∪{A})
⎛
⎝
⎞
⎠
=
K ·
F
1
(A,
nb
(A))
F
2
(
V
−{A})
A
V
−(nb(A)∪{A})
folglich
F
1
(A,
nb
(A))
A
F
1
(A,
nb
(A))
P (A
|
nb
(A)) =
Insgesamt folgt P (A
|
V
−{
A
}
)=P (A
|
nb
(A)), d.i. die lokale Markov-Eigenschaft.
Es gelten sogar noch die beiden folgenden, starkeren Resultate:
Theorem 13.16 ([175])
Zu jedem ungerichteten Graphen
G
gibt es eine Vertei-
lung
P
, so dass
G
ein perfekter Graph zu
P
ist.
Besitzt eine Wahrscheinlichkeitsverteilung P eine Darstellung der Form (13.12)
bzgl. eines Graphen
G
, so sagt man, P
faktorisiert uber den Cliquen von
G
.
Theorem 13.17 ([128])
Eine strikt positive Verteilung
P
erfullt die Markov-
Eigenschaften bzgl. eines Graphen
G
genau dann, wenn sie uber den Cliquen von
G
faktorisiert.
Die Funktionen ψ
i
in (13.12) werden als
Potentialfunktionen
bezeichnet, und
(13.12) nennt man
Potentialdarstellung
, wobei dieser Begriff etwas allgemeiner de-
finiert wird:
Definition 13.18 (Potentialdarstellung)
Sei
V
eine (endliche) Menge von Aus-
sagenvariablen, und sei P eine gemeinsame Verteilung uber
V
.Sei{
W
i
| 1 ≤ i ≤ p}
eine Menge von Teilmengen von
V
mit
i=1
W
i
=
V
, und sei
IR
≥0
ψ
:
{
w
i
|
w
i
ist Vollkonjunktion uber
W
i
, 1
≤
i
≤
p
}→
eine Funktion, die jeder Vollkonjunktion von Variablen in
W
i
(1
≤
i
≤
p)eine
nicht-negative reelle Zahl zuordnet. Gilt nun
