Hier sind spezielle Inferenzalgorithmen im Vergleich zu "bewundern":

• Naiver Ansatz über die Vollständige Wahrscheinlichkeitstafel aller Knoten
• Junction-Tree (HUGIN-Propagation)
• Loopy-Belief-Propagation (nach Pearl)
• Likelihood-Weighting-Sampling
• Gibbs-Sampling

Dies ist die Fortsetzung zu den hier dargestelleten Beispielen (bitte ggf. zunächst dort nachlesen, wie die Netze zu bedienen sind).

In diesem Beispiel wird eine vollständige Wahrscheinlichkeitstafel über alle Knoten erzeugt (Full-Joint-Probability-Table). Diese hat in diesem Beispiel mit fünf Knoten a 2 Zuständen und einem Knoten mit vier Zuständen 2 x 2 x 2 x 2 x 2 x 4 = 128 Zellen, was noch einigermaßen handhabbar ist (die Tafel ist unter dem Netz zu sehen und wird je nach eingegebener Evidenz aktualisiert). Wie man sich leicht vorstellen kann wächst diese Tafel für komplexere Netze aber schnell über die Grenze des verfügbaren Speichers (und selbst wenn man die Tafel im Speicher halten könnte möchte man nicht über derart viele Werte iterieren). Dafür ist die Berechnung von der Theorie her einfach:

• Erzeuge die Tafel (hier mit 2 x 2 x 2 x 2 x 2 x 4 = 128 Elementen)
• Initialisiere alle Werte mit "1"
• Multipliziere die bedingten Wahrscheinlichkeitstafeln aller Knoten in diese Tafel
• Multipliziere die "Finding-Vektoren", die die aktuellen Beobachtungen (Evidenz) wiederspiegeln ebenfalls in diese Tafel
• Renormiere diese Tafel, so dass alle Werte zusammen 1 ergeben (der Normierungsfaktor ist Eins durch die Summe aller Werte der Tafel und entspricht der Wahrscheinlichkeit der gesamten Evidenz in diesem Modell: P(e|M))
• Marginalisiere die resultierenden Posterior-Verteilungen für alle Knoten aus dieser Tafel

Junction-Trees stellen das ursprüngliche Netz in einer anderen Form dar. Diese besteht aus Cliquen (Knoten des Junction-Trees) und Separatoren (Kanten des Junction-Trees). Jede Clique repräsentiert dabei eine vollständig verbundene Menge von Knoten des moralisierten und triangulierten Bayes'schen Netzes (d.h. insbes. die dazugehörige Wahrscheinlichkeitstafel, die jeweils über [probs] geöffnet werden kann). Dabei sind die enthaltenen Knoten mit "◊" markiert, wenn die Clique die sogenannte "Home-Clique" des Knotens ist - das ist jeweils eine, von ggf. mehreren möglichen Cliquen, die diesen Knoten und alle seine Eltern-Knoten enthält. Der Knoten durch dessen "Eliminierung" die Clique entstanden ist, ist jeweils mit "×" gekennzeichnet. Separatoren sind die Schnittmengen der Cliquen, über die Information zwischen den Cliquen ausgetauscht wird (auch die aktuelle Separator-Tafel kann über [p] angesehen werden). Genaueres kann man hier nachlesen. Junction-Trees stellen ein exaktes Verfahren dar, d.h. es kommen (bis auf Rundungsfehler) dieselben Ergebnisse heraus wie bei dem oben dargestellten "naiven" Ansatz, jedoch meist ohne übergroße Wahrscheinlichkeitstafeln zu benötigen. Für sehr komplexe Netze sind aber auch Junction-Trees nicht handhabbar. So hat der Junction-Tree für ein vollständig verbundenes Bayes'sches Netz nur eine Clique, die alle Knoten enthält und somit auch die vollständige Wahrscheinlichkeitstafel aller Knoten (genau wie beim naiven Ansatz).

Damit man noch etwas tiefer in den Junction-Tree hineinschauen kann hier einige Spezialmethoden (beim Setzen von Evidenz durch Anklicken eines States wird sonst ja immer gleich eine vollständige Propagation angestoßen):

• Klicke hier um den Junction-Tree nur mit den aktuellen Beobachtungen zu initialisieren, jedoch ohne die Collect- und Distribute-Phasen durchzuführen.
• Klicke hier um zusätzlich noch die Collect-Phase durchzuführen, jedoch ohne die Normalisierung und ohne die Distribute-Phase durchzuführen.
• Klicke hier um zusätzlich auch die Normalisierung der Root-Clique(n) vorzunehmen, aber ohne die Distribute-Phase durchzuführen.
• Klicke hier um eine vollständige Propagation mit Update der A-Posteriori-Wahrscheinlichkeiten der Knoten durchzuführen.

Hier sollte ich noch erwähnen, dass das HUGIN-Schema nicht der einzige Inferenz-Algorithmus ist, der auf Junction-Trees arbeitet (arbeiten kann). Daneben existieren z.B. noch der Shafer-Shenoy-Algorithmus, der aber generell weniger effektiv ist als HUGIN, sowie der Lazy-Propagation-Algorithmus, der insbesondere dann, wenn (harte) Evidenz für eine Reihe von Knoten gegeben ist Vorteile gegenüber HUGIN hat. Lazy-Propagation wertet nämlich die durch Evidenz ggf. induzierten (Un-)Abhängigkeiten (vgl. d-separation / d-connection) aus und versendet dann nur solche "Nachrichten" von Clique zu Clique, die tatsächlich nötig sind (d.h. solche, die eine Änderung in der Zielclique bewirken). Dabei werden die Potenziale (CPTs), die einer Clique zugeordnet werden, nicht sofort zusammenmultipliziert sondern zunächst einzeln gehalten. Leider ist das Verfahren deutlich umständlicher als HUGIN (oder zumindest stellt es sich mir bisher so dar), weshalb ich auf eine Implementierung hier verzichtet habe.

Dieser Ansatz ist älter als die Junction-Tree-Verfahren, hat aber unter bestimmten Umständen noch seine Berechtigung. In der hier gewählten Repräsentation wird jeder Knoten mit seinen Eltern in eine Clique (siehe Junction-Tree) "gesteckt". Diese Cliquen werden entsprechend den Knoten im Bayes'schen Netz durch Separatoren verbunden. Es entsteht also i.d.R. keine Baumstruktur wie beim Junction-Tree. Nun empfangen alle Cliquen, von allen Nachbarn Informationen (die gemeinsamen Knoten betreffend). Dies wird ein paar mal (in obigen Beispiel jeweils 10x) wiederholt, so dass das Ergebnis konvergeriert. Allerdings konvergiert es nur dann gegen die korrekten Werte, wenn das Bayes'sche Netz selbst und damit auch die Struktur aus Cliquen und Separatoren eine Baumstruktur ist. Da die Fehler in anderen Strukturen aber oft recht klein sind, ist das Verfahren auch für Fälle geeignet, in denen Junction-Trees nicht anwendbar sind. Wie groß der Fehler werden kann ist im Voraus nicht absehbar. Im oben gezeigten Beispiel treten z.B. Fehler von über 4% auf (im Knoten "Unfälle", wenn "Straße" = rutschig). Da hier jeweils eine Clique für jeden Knoten und seine Eltern gebildet wird ist dieser Knoten jeweils sowohl mit "◊" (Clique ist Home-Clique dieses Knotens) als auch mit "×" (Clique ist für diesen Knoten entstanden) gekennzeichnet.

Damit man auch in diesen Algorithmus noch etwas tiefer hineinschauen kann hier wieder einige Spezialmethoden:

• Klicke hier um die Cliquen nur mit den aktuellen Beobachtungen zu initialisieren, jedoch ohne die eigentliche Propagation auszuführen.
• Um nur eine bestimmte Anzahl von Iterationen zu berechnen klicke auf die entsprechende Zahl: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10