TUTORIAL:
BAYES'SCHE NETZE
PROBABILISTISCHE NETZE
(Bayesian Networks / Probabilistic Networks / Causal Belief Networks)
Interaktive Online-Beispiele IV (Y-Propagation)
Hier wird die Y-Propagation für Junction-Trees vorgestellt. Dieser spezielle Propagtionsalgorithmus für Junction-Trees dient dazu die gemeinsame Wahrscheinlichkeitstafel für eine beliebige Untermenge aller Knoten des Netzes zu berechnen. Dies ist die Fortsetzung zu den hier dargestelleten Beispielen (bitte ggf. zunächst dort nachlesen, wie die Netze zu bedienen sind).
Junction-Tree (HUGIN)
BEISPIEL-NETZ
JUNCTION-TREE

Knoten für die die gemeinsame Wahrscheinlichkeitsverteilung gesucht ist:
Wetter
Tageszeit
Sicht
Konzentration
Straße
Unfälle

Zunächst ein Wort zu anderen Inferenz-Algorithmen: Beim naiven Ansatz über die "Full-Joint-Tafel" aller Knoten ist die gemeinsame Wahrscheinlichkeitstafel für eine bestimmte Untermenge von Knoten leicht zu erhalten: man marginalisiert in der Full-Joint-Tafel eben über alle Knoten die nicht in der gesuchten Knotenmenge enthalten sind. Auch bei Sampling-Algorithmen ist die Berechnung einfach: Man legt die entsprechende Tafel an, zählt wieviele Samples jeweils in jede Zelle fallen und trägt diese Zahl dort ein. Am Ende muss die so gewonnene Tafel nur noch normiert werden und man hat eine Schätzung der gesuchten Wahrscheinlichkeitstafel, wobei neben den normalen Problemen beim Samplen natürlich noch hinzukommt, dass diese Schätzung umso ungenauer sein muss je größer die gesuchte Tafel ist. Die Größe - also die Anzahl der Zellen - hängt dabei direkt von der Anzahl der Knoten in der gesuchten Knotenmenge ab.

Bei Junction-Tree-Algorithmen ist das Problem etwas schwieriger, weil gemeinsame Wahrscheinlichkeitstafeln nur für Knotenmengen vorhanden sind, die gemeinsam in einer Clique vorkommen. Ist die gesuchte Knotenmenge also in einer einzelnen Clique vollständig enthalten, so kann die gesuchte Tafel aus der Tafel dieser Clique durch Marginalisierung über evtl. weitere (nicht benötigte) Knoten in dieser Clique vorhandenen Knoten gewonnen werden. Andernfalls hilft die Y-Propagation: Hierbei werden die Cliquen und Separatoren derart erweitert, dass die gesuchten Knoten alle in der Root-Clique enthalten sind. Dieses kann für beliebige Knotenmengen "on the fly" erfolgen, oder der Junction-Tree wird für eine bestimmte Knotenmenge entsprechend fix angelegt. Hier wird letzteres Verfahren benutzt, weil es besser geeignet ist, in den Algorithmus "hineinzuschauen". Zudem wird eine extra "Super-Root-Clique" angelegt, die nur die gesuchten Knoten enthält und Eltern-Clique jeweils einer Clique aus jedem unverbundenen Cluster des ursprünglichen Junction-Trees ist. Im einfachsten Fall wird die Super-Root-Clique einfach mit allen bisherigen Root-Cliquen Verbunden. Hier wird allerdings noch eine Optimierung durchgeführt, die darin besteht, dass in jedem Cluster die geeignetste Connector-Clique gesucht wird. Das ist jene Clique die die größte Übereinstimmung mit den gesuchten Knoten hat (hier wird das einfach anhand der Anzahl der gesuchten Knoten, die auch in einer Clique enthalten sind bestimmt; man könnte aber auch noch die Anzahl der Zustände berücksichtigen, oder - noch komplizierter - die Cliquen als Connector-Cliquen bestimmen mit denen der entstehende Junction-Tree insgesamt am kompaktesten bleibt). In diesem Fall müssen dann aber u.U. auch noch einzelne Kanten umgedreht werden, damit alle Pfade im Junction-Tree von der Super-Root-Clique weg bis zu den entferntesten Cliqhen (den "Blättern") führen. Die gesuchte Tafel ist dann in einem so umgeforten Junction-Tree direkt aus der Super-Root-Clique abzulesen. Zu Cliquen hinzugefügte Knoten, die nur für die Y-Propagation notwendig sind, sind hier mit einem "+" gekennzeichnet.

Hinweis: Ich war etwas faul, daher ändern sich die Knotennamen an den Checkboxen nicht falls man auf die Idee kommt die Knoten umzubenennen (was man hier also besser nicht tun sollte)...

Patrick Rammelt, 09/2011