Information Technology Reference
In-Depth Information
Definition 24.9 (Markov-Netz)
Ein
Markov-Netz
ist ein ungerichteter bedingter Unab-
hängigkeitsgraph G
=(
V
,
E
)
einer Wahrscheinlichkeitsverteilung p
V
zusammen mit einer
Familie von nichtnegativen Funktionen
M
der durch den Graphen induzierten Faktorisie-
rung.
Der ungerichtete Graph in Abbildung 24.3 zusammen mit der Zerlegung aus Bei-
spiel 24.2 (und geeignet gewählten Cliquenpotentialen) ist ein Markov-Netz.
Definition 24.10 (Bayes-Netz)
Ein
Bayes-Netz
ist ein gerichteter bedingter Unabhängig-
keitsgraph einer Wahrscheinlichkeitsverteilung p
V
zusammen mit einer Familie von beding-
ten Wahrscheinlichkeiten der durch den Graphen induzierten Faktorisierung.
Der gerichtete, azyklische Graph in Abbildung 24.3 zusammen mit der Zerle-
gung aus Beispiel 24.3 (und geeignet gewählten bedingten Verteilungen) ist ein
Bayes-Netz.
24.2 Eine reale Anwendung
Wir besitzen nun Mechanismen, um die erste der drei wesentlichen Fragen von Sei-
te 353 zu beantworten:
Wie kann (Experten-)Wissen über komplexe Anwendungsbereiche effizi-
ent repräsentiert werden?
Das Expertenwissen wird formal von einer Verteilung
p
V
über der Menge
V
von
relevanten Attributen (Kundendaten, Produktdaten, Bestellinformationen, etc.) re-
präsentiert. Bedingte Unabhängigkeitenwerden genutzt, umdiese Verteilung in eine
Menge von Verteilungen geringerer Dimension zu zerlegen (entweder als Markov-
oder Bayes-Netz). Abbildung 24.4 zeigt ein Markov-Netz einer realen Anwendung
des VW-Konzerns [Gebhardt u. Kruse 2005]. Die verschiedenen Ausstattungsmerk-
male eines Fahrzeugs werden durch 186 Attribute beschrieben, welche in der Abbil-
dung durch Zahlen anonymisiert wurden. Das Markov-Netz in der Abbildung hat
174 drei- bis neundimensionale Cliquen. Machen wir uns die Effizienzsteigerung ei-
ner solchen Speicherung klar und vergleichen den theoretisch benötigten Speicher-
platz der originalen 186-dimensionalen Verteilung
p
o
rig
mit der durch das Markov-
Netz repräsentierten Verteilung
p
net
.UmdieAbschätzungzuvereinfachen,nehmen
wir für jedes Attribut einen Wertebereich von 5 Werten an, was sich imMittel mit Er-
fahrungswerten aus anderen Industrieprojekten deckt. Unsere Argumentation hin-
sichtlich der Effizienzsteigerung ändert sich jedoch nicht, wenn andere Zahlen ver-
wendet werden. Zusätzlich werden wir annehmen, dass jede Clique des Markov-
Netzes die Maximaxanzahl von 9 Attributen besitzt, um die Überschlagung der Grö-
ße zu vereinfachen. Es ergeben sich folgende Anzahlen an zu speichernden Parame-
tern (d. h. Einzelwahrscheinlichkeiten bzw. Einträge in den Cliquenpotentialen):
Ve r t e i l ung
Anz ah l de r Pa r ame t e r
1 · 5
186
10
130
p
orig
174
·
5
9
3.4
·
10
8
p
net