Database Reference
In-Depth Information
ist. Diese Frage ist fur den Aufbau einer Wissensbasis von besonderer Bedeutung, da
mittels eines Graphen zunachst ein Gerust qualitativer Abhangigkeiten reprasentiert
werden kann, die dann durch eine Verteilung passend quantifiziert werden konnen.
Das folgende Theorem lost dieses Problem in konstruktiver Weise.
Theorem 13.15
Sei
ein Graph mit den Cliquen
C
1
,...,
C
m
. Jeder dieser Cli-
quen sei eine nichtnegative Funktion
ψ
i
(
C
i
)
auf den Vollkonjunktionen der entspre-
G
chenden Variablen zugeordnet, wobei
V
i=1
ψ
i
(
C
i
)
=0
ist. Man definiert eine
Wahrscheinlichkeitsverteilung
P
durch
m
P (
V
):=K
ψ
i
(
C
i
)
(13.12)
i=1
wobei
K
ein Normierungsfaktor ist, so dass
V
P (
V
)=1
ist. Dann ist
G
ein
Unabhangigkeitsgraph zu
P
.
Beweis:
Wir beweisen Theorem 13.15 fur den Fall, dass alle ψ
i
strikt positive
Funktionen sind. Dann ist auch die durch (13.12) definierte Verteilung positiv, und
alle drei Markov-Eigenschaften sind aquivalent (vgl. Theorem 13.11). Wir zeigen
die lokale Markov-Eigenschaft
A
P
[
V
−
(
nb
(A)
∪{
A
}
)]
|
nb
(A)
d. h.
P (A
|
V
−{
A
}
)=P (A
|
nb
(A))
fur jede Variable A
∈
V
,wobei
nb
(A) die Menge der Nachbarn von A im Graphen
G
ist. Nach der definierenden Gleichung (13.12) in Theorem 13.15 ist
m
P (A,
V
−{
A
}
)=P (
V
)=K
ψ
i
(
C
i
)
i=1
K
i:A∈
C
i
ψ
i
(
C
i
)
i:A∈
C
i
=
ψ
i
(
C
i
)
Da
die
Cliquen
C
i
vollstandige
Graphen
sind,
gehoren alle im Produkt
i:A∈
C
i
ψ
i
(
C
i
) auftretenden, von A verschiedenen Knoten zu den Nachbarn von
A:
ψ
i
(
C
i
)=:F
1
(A,
nb
(A))
i:A∈
C
i
im zweiten Produkt kommt A definitionsgemaß nicht vor:
ψ
i
(
C
i
)=:F
2
(
V
−{
A
}
)
i:A∈
C
i
also
P (A,
V
−{
A
}
)=K
·
F
1
(A,
nb
(A))
·
F
2
(
V
−{
A
}
)
(
A
F
1
(A,
nb
(A)))
Dann ist P (
V
−{
A
}
)=K
·
·
F
2
(
V
−{
A
}
) und daher
