Database Reference
In-Depth Information
P
∗
=
ME
(
KGS
R
)
000 .1891
001 .1185
010 0
011 0
100 .1891
101 .2125
110 .0291
111 .2617
Abbildung 13.13
ME
-Verteilung
P
∗
zum Grippe-Beispiel 13.50
Die Berechnung der
ME
-Verteilung erfolgt mathematisch durch die Methode
der
Lagrange-Multiplikatoren
, bei der die Elementarwahrscheinlichkeiten P (ω)als
Variable aufgefasst werden und das Maximum als Nullstelle partieller Ableitungen
bestimmt wird (Ausfuhrlicheres dazu findet man z. B. in [104]).
Fur die maschinelle Berechnung werden iterative Verfahren verwendet, die nicht
auf der gesamten Verteilung, sondern auf einem Netz marginaler Verteilungen ope-
rieren. In dieser Art arbeitet SPIRIT, eine System-Shell zur Durchfuhrung von
ME
-Inferenzen [197, 195, 196, 155]. SPIRIT erzeugt aus der Menge
eingegebener
probabilistischer Regeln einen Hypergraphen bzw. einen Hyperbaum (vgl. hierzu
Anhang B.4), auf dem es die
ME
-Verteilung durch lokale Iterationen berechnet.
Zu diesem Zweck werden zunachst alle Variablen, die in einer Regel in
R
vorkom-
men, durch eine Hyperkante verbunden. Der entstandene Hypergraph wird dann
durch einen Hyperbaum
R
V
,
C uberdeckt. Der zugehorige Verbindungsbaum mit
der Knotenmenge
stellt schließlich die passende
Struktur fur Propagation und Iteration dar. Dabei nutzt man aus, dass sich auch
die entropie-maximale Verteilung P
∗
=
ME
(
C
und der Separatorenmenge
S
R
) in ein Produkt aus Randverteilun-
gen des Verbindungsbaums zerlegen lasst:
P
∗
(ω)=
C
∈C
P
∗
(
C
)
S
∈S
P
∗
(
S
)
(s. [155], S. 95). Hyperkanten gemeinsam mit ihren Randverteilungen werden auch
als
LEG (= local event groups)
bezeichnet. Daher nennt man die bei entropie-
maximaler Reprasentation entstehenden probabilistischen Netze auch
LEG-Netze
.
Der dynamische Abgleich benachbarter LEG's bei Propagation und Iteration erfolgt
durch eine Variante des
Iterative Proportional Fitting-Verfahrens (IPF-Verfahrens)
(s. [155, 220]). Durch diese lokalen Berechnungen kann, ebenso wie bei den Bayes-
schen Netzen, die probabilistische Komplexitat drastisch reduziert werden.
Wir wollen den Aufbau des Hyperbaums an einem Beispiel kurz illustrieren.
Eine ausfuhrliche Beschreibung von SPIRIT findet sich in [155], eine kompakte
Darstellung in [197].