TUTORIAL:
BAYES'SCHE NETZE
PROBABILISTISCHE NETZE
(Bayesian Networks / Probabilistic Networks / Causal Belief Networks)
Dynamische Bayes'sche Netze
In einem Dynamischen Bayes'schen Netz (DBN) wird nicht nur eine zu einem Zeitpunkt gemachte Beobachtung über eine Anzahl von Merkmalen verarbeitet, sondern eine ganze Zeitreihe von Beobachtungen. Daher treten die selben Merkmale für die benötigte Anzahl von Zeitpunkten mehrfach auf. Entsprechend dieser Zeitpunkte sind die Knoten des DBN sogenannten Zeitscheiben zugeordnet. Kanten existieren in einem DBN nicht nur unter den Knoten einer Zeitscheibe, sondern auch zeitscheibenübergreifend.
Man macht normalerweise folgende vereinfachende Grundannahmen:
  1. Zeitscheibenübergreifende Kanten zeigen immer in Richtung zukünftiger Zeitscheiben, d.h. die Zukunft hängt (u.a.) von der Vergangenheit ab, jedoch nicht umgekehrt (diese Annahme sollte wohl unstrittig sein).
  2. Das Problem ist stationär, d.h. die Struktur und die bedingten Wahrscheinlichkeiten sind in allen Zeitscheiben identisch (bis auf die erste, die sogenannte Prior-Zeitscheibe)
  3. Die Markov-Bedingung erster Ordnung wird erfüllt, d.h. es existieren nur Kanten innerhalb einer Zeitscheibe t und zur nächsten Zeitscheibe t+1. Damit ist eine Zeitscheibe t-1 unabhängig von der Zeitscheibe t+1, wenn alle Knoten in t gegeben sind (siehe auch Abschnitt "Abhängigkeitsstruktur (d-separation)")
Damit ist zur Definition eines DBN nur die Prior-Zeitscheibe (t=0) und die folgende Zeitscheibe (t=1) notwendig.



DBN: Knoten der Prior-Zeitscheibe (t=0) enden auf "0" dieses DBN hat (pro Zeitscheibe) eine "dynamische" Kante (rot)

Die Abbildung zeigt die einfachste sinnvolle Struktur eines DBN's. Der Knoten State bleibt unbeobachtet (hidden) und wird durch Beobachtungen geschätzt, die in den Knoten Observation eingebracht werden. Ein solches Modell ist das DBN-Äquivalent zu einem Hidden Markov Model (HMM). Die bedingte Wahrscheinlichkeitstafel des State-Knotens enthält die Übergangswahrscheinlichkeiten. Dabei ist normalerweise die Beibehaltung des aktuellen Zustands die wahrscheinlichste Variante. Geringe Wahrscheinlichkeiten existieren für den Übergang in bestimmte "Nachbarzustände", während der Übergang in andere Zustände ganz ausgeschlossen wird (z.B. P(State(t)=s3|State(t-1)=s1)=0). Die Werte der Übergangswahrscheinlichkeiten hängen insbesondere von der Aufzeichnungsrate also der Zeitdifferenz zwischen zwei Zeitscheiben ab.





Entrolltes DBN mit 7 Zeitscheiben (inkl. A-Priori-Zeitscheibe)

Eine offensichtliche Möglichkeit in einem solchen Netz zu rechnen ist diese:
Die Zeitscheibe t=1 wird für die benötigte Anzahl von Schritten (T) automatisch kopiert und dem Netz hinzugefügt. Dieses Verfahren nennt sich Entrollen. Danach kann dann wie für ein statisches BN ein kompletter Junction-Tree für das so gewonnene Gesamtnetz erstellt werden.
Diese Verfahren hat aber mehrere Nachteile:

  • Es muss vor dem Start der Berechnungen bekannt sein wieviele Zeitscheiben benötigt werden.
  • Für sehr viele Zeitscheiben entsteht ein riesiger Junction-Tree. Dabei ist auch zu beachten, dass bereits zum ersten Zeitpunkt t=0 (nur Merkmale der Zeitscheibe t=0 beobachtet) der Einfluss bis zu den Knoten der letzten Zeitscheibe berechnet wird. Umgekehrt wird auch zum letzten Zeitpunkt (Merkmale aus aus den Zeitscheiben t=0...T beobachtet) noch der Einfluss auf die unbeobachtet gebliebenen Merkmale der vorangegangenen bis zur Prior-Zeitscheibe zurückverfolgt. I.d.R. ist der Einfluss über einige Zeitscheiben hinweg aber nur noch minimal.
Oft interessieren ohnehin nur die Merkmale innerhalb eines Zeitfensters um eine "aktuelle" Zeitscheibe t herum.
Es existieren Verfahren um Junction-Trees zu erzeugen, die wie das DBN selbst zeitscheibenweise in Richtung Vergangenheit gekürzt und in Richtung Zukunft erweitert werden können. Eines ist das dHugin-Verfahren [1]. Voraussetzung dafür ist ein Junction-Tree, der für alle Zeitscheiben (ausser der Prior-Zeitscheibe) eine identische Struktur aufweist (vgl. Definition stationärer DBN's). Dieses kann nur gewährleistet werden wenn die gesamte Information die von einer Zeitscheibe t an die folgende Zeitscheibe t+1 weitergegeben wird auch über nur einen Separator weitergereicht wird.  Dazu müssen alle Knoten die im moralischen Graphen Verbindungen über die Zeischeibengrenze t/t+1 hinweg haben in einer Clique vereint sein. Dieses ist einfach zu erreichen, indem diese Knoten durch evtl. einzufügende fill-in-Kanten paarweise verbunden werden (s.a. Abschnitt "Inferenz (Junction-Tree)").
Auch dieses Verfahren hat einen entscheidenden Nachteil:
Wenn mehrere Kanten über die Zeit verwendet werden, diese aber im Netz "weit" auseinander liegen entsteht eine übergroße Clique, die schnell die Grenzen der Handhabbarkeit überschreitet.
Referenzen
[1]  "dHugin: A computational system for dynamic time-sliced Bayesian networks", U. Kjærulff, International Journal of Forecasting, 1995
Patrick Rammelt, 12/2002