BAYES'SCHE NETZE
PROBABILISTISCHE NETZE
(Bayesian Networks / Probabilistic Networks / Causal Belief Networks)
Hier wird ein Lernalgorithmus für die bedingten Wahrscheinlichkeiten aus unvollständigen Daten dargestellt. Bei vollständigen Daten ist kein Lernalgorithmus nötig, denn dann kann man die CPTs einfach dadurch bestimmen, dass man auszählt wieviele Samples zu jeder Zelle einer CPT gehören (anschließend ist dann nur noch eine Normierung der so erhaltenen CPT nötig - s.a. hier).
Oben ist ein "Original"-Netz vorgegeben. Aus diesem Original-Netz werden dann mittels Sampling künstlich Daten erzeugt (vgl. Sampling), wobei ein gewisser Prozentsatz der Beobachtungen gleich wieder "vergessen" wird und dem nachfolgenden Lern-Algorithmus daher nicht zur Verfügung steht.
Der hier verwendete Expectation-Maximization-Algorithmus randomisiert zunächst die CPTs aller Knoten, aktualisiert den "Propagator" (hier ein Junction-Tree), gibt dann die Beobachtungen des ersten Samples, soweit vorhanden in das Netz ein, propagiert diese und bekommt vom Propagator die gemeinsame Wahrscheinlichkeitstafel jedes Knotens und seiner jeweiligen Eltern: P(X,pa(X)) (diese Tafel können alle Propagationsalgorithmen wie Junction-Tree-, Loopy-Belief-, oder Sampling-Algorithmen leicht "nebenbei" erzeugen). Diese einzelnen Wahrscheinlichkeitstafeln werden für alle weiteren Samples und Knoten entsprechend gewonnen und in je einer Kumulations-Tafel pro Knoten aufsummiert (wobei sie ggf. vorher noch mit der Gewichtung des Samples multipliziert werden). Nach entsprechender Normierung sind diese Tafeln die neuen CPTs für den nächsten Optimierungslauf. Abgebrochen wird die Optimierung hier nach einer vorgegebenen Maximalanzahl von Schritten bzw. wenn die größte Änderung eines einzelnen Wahrscheinlichkeitswertes einen vorgegebenen Wert unterschreitet (Konvergenzkriterium).
Man kann nun das Ausgangsnetz verändern, und verschieden unvollständige Datensätze erzeugen. Gut erkennen kann man dabei u.a., dass die Optimierung im Durchschnitt umso länger dauert, je unvollständiger die Daten sind.
Hier wird ein Lernalgorithmus für die Struktur aus (vollständigen) Daten dargestellt. Oben ist ein Original-Netz vorgegeben. Dieses enthält eine divergierende, eine konvergierende und eine serielle Verbindung, sowie einen komplett unabhängigen Knoten. Aus diesem "Original"-Netz werden dann wiederum Daten durch Sampling künstlich erzeugt (vgl. Sampling). Zum Vergleich ist dieses Netz nochmal dargestellt, wobei die bedingten Wahrscheinlichkeitstafeln mit diesen Daten angepasst wurden (wie oben beschrieben ist das einfach, da die Daten vollständig sind - s.a. hier), die Struktur jedoch unverändert blieb. Dieses Netz wäre also theoretisch das optimale Lernergebnis.
Danach wurde ein Lernalgorithmus benutzt, um aus den gesampelten Daten die Netzstruktur "zurückzurechnen". In der momentanen Ausbaustufe beschränkt sich dieser Algorithmus auf das schrittweise Hinzufügen von neuen Kanten (beginnend bei einem kantenlosen Netz), bis auf diese Weise keine weitere Verbesserung mehr erzielt werden kann. Löschen bzw. Umdrehen bestehender Kanten wird also weder bewertet noch durchgeführt. Beachtet werden muss auch, dass in diesem Test-Szenario nur Daten erzeugt werden, die prinzipiell mit einem Bayes'schen Netz "verträglich" sind (da sie ja aus einem erzeugt werden), dies ist jedoch im Allgemeinen nicht unbedingt gewährleistet. Kausalitäten (also Kantenrichtungen) lassen sich mit den hier vorgestellten Verfahren übrigens nicht bestimmen - so sind z.B. die Netze A→B und B→A aus Sicht der Bewertungskriterien vollkommen äquivalent. In komplexeren Strukturen ist die Kantenrichtung jedoch nicht mehr egal. So kann sich z.B. die Entscheidung für A→B später als günstiger herausstellen als die umgekehrte Richtung B→A, weshalb der Algorithmus in zwei Durchläufen durchaus zu unterschiedlichen und insbesondere auch unterschiedlich guten Ergebnissen kommen kann. Dieses Verhalten wird durch einen kleinen Zufallsoffset bei der Bewertung der Änderungen noch unterstützt.
Prinzipiell ist das Verfahren auch mit unvollständigen Daten realisierbar. Da jeweils die Kontingenztafeln zu jedem Knoten und seinen Eltern benötigt werden, wird hier z.B. jeweils ein Expectation-Maximization-Algorithmus angewendet. Allerdings sinkt die Performance damit ins Erbärmliche. Nicht nur, dass der EM-Algorithmus seinerseits einen Propagator (z.B. einen Junction-Tree) benötigt, der für jede geänderte Struktur neu aufgebaut werden muss; zusätzlich "verfallen" hier auch noch die Einzel-Bewertungen von Knoten, auch wenn sich ihre eigene Elternmenge überhaupt nicht verändert hat (die Bewertungen solcher Knoten müssen bei vollständigen Daten nicht jedesmal neu berechnet werden).
Man kann nun das Ausgangsnetz verändern, verschieden große Datensätze erzeugen und verschiedene Bewertungskriterien (vgl. Kapitel über das Strukturlernen) ausprobieren. Man kann dabei beobachten, dass es Datensätze gibt, mit denen alle Kriterien recht gut mit dem Original übereinstimmende Ergebnisse finden und solche bei denen es starke Abweichungen gibt. Prinzipiell liefern die "α=1"-Methode und die "Bayesian Quality" (BQ) praktisch identische Ergebnisse. Das MDL-Kriterium neigt dazu deutlich weniger (zu wenige) Kanten zu finden, während man mit der "β"-Methode (eben über den Wert von β) die Anzahl der Kanten variieren kann (normalerweise ist aber ein Wert um 0.5 angebracht). Die Methode ein (anderes) Netz (hier das Original-Netz) als Vorwissen zu benutzen und dieses Wissen mit einer "User-Sample-Size" (USS) zu gewichten funktioniert nicht wirklich, denn je höher die USS desto mehr (überflüssige) Kanten werden gefunden, obwohl man eigentlich das Gegenteil erwarten sollte (diesen Effekt habe ich bereits in meiner Diplomarbeit näher untersucht - siehe DiplomArbeit.pdf.gz). Darum ist dieses Kriterium hier auch nur in einer Art und Weise implementiert, die nur für sehr kleine Netze funktioniert (es wird ein "Full-Joint-Propagator" benutzt).