Lernen Graphischer Modelle - Computational Intelligence - page 399

Kapitel 26
Lernen Graphischer Modelle
Wir wollen nun die dritte Frage aus Kapitel 22 beantworten, nämlich, wie graphische
Modelle aus Daten generiert werden können. Bisher war die Graphenstruktur vor-
gegeben, nun wollen wir diese mit verschiedenen Heuristiken aus Daten ableiten.
Prinzipiell suchen wir zu einer gegebenen Datenbasis D den zu ihr passendsten
Graphen G . In der Tat umfassen alle Lernalgorithmen für graphische Modelle die
folgenden beiden Teile:
• Eine Heuristik, die den Suchraum aller Graphen möglichst effizient durchläuft
und geeignete Kandidatengraphen liefert.
• Eine Bewertungsfunktion, die jedemGraphenkandidaten eine Güte (bezüglich
der Datenbasis) zuordnet und anhand derer die Heuristik die nächsten Kandi-
daten erzeugt.
Eine vollständige Suche im Raum aller möglichen Graphen scheidet aus, da die
Anzahl der möglichen Graphen selbst für kleine Anzahlen von Knoten zu groß wird.
Die Menge gerichteter, azyklischer Graphen wächst beispielsweise superexponenti-
ell in der Anzahl der Knoten [Robinson 1977]: Schon für 10 Knoten hat die Graphen-
menge eine Kardinalität von 4.18 · 10 18 .
Die Bewertungsfunktion soll angeben, wie „gut“ der Kandidatengraph eine Da-
tenbasis erklärt. Eine Möglichkeit besteht darin, die Wahrscheinlichkeit zu berech-
nen, mit der der Graph die Datenbasis generiert haben könnte. 1 Das Generieren ei-
ner Datenbasis anhand eines Graphen bedeute, dass die durch den Graphen kodierte
Wahr s che i n l i chke i t sve r t e i l ung zum e r zeugen zuf ä l l i ge r Tupe l genut z t we rde .
Wir wollen im Folgenden die Graphenstruktur (egal , ob gerichtet oder unge-
richtet) eines graphischen Modells mit B S bezeichnen und die Menge aller Wahr-
scheinlichkeitsparameter (die Potentialtabelleneinträge bzw. die bedingten Wahr-
scheinlichkeiten) als B P .BetrachtenwirdieKomponente B P für den Fall eines Bayes-
Netzes. Sie beinhaltet die konkreten Einträge der bedingten Wahrscheinlichkeits-
verteilungen P ( A | pa ( A )) .ZujedemKnotengehörteinesog. Potentialtabelle ,die
1 Wir werden zwar sehen, dass die reine Form dieser Wahrscheinl ichkeit nicht für einen Lernalgorith-
mus geeignet ist, jedoch werden Abwandlungen dieser Herleitungen für viele Algorithmen verwendet,
so auch für den im Weiteren beschriebenen K2-Algorithmus.