Versteckte Markov-Modelle
=========================
Wolfgang Mulzer

Ein verstecktes Markov-Modell (Hidden Markov Model, HMM)
hat folgende Bestandteile:

i)   Eine endliche Zustandsmenge Q

ii)  Ein endliches Ausgabealphabet S

iii) Eine Anfangsverteilung a(q) für q in Q
      Die Werte a(q) liegen in [0,1] und summieren zu 1.

iv) Übergangsverteilungen t(q,r) für q,r in Q
      Die Werte t(q,r) liegen in [0,1] und für 
      jeden Zustand q summieren die t(q,r) zu 1.

v) Ausgabeverteilungen o(q,s) für q in Q und s in S
      Die Werte o(q,s) liegen in [0,1] und für 
      jeden Zustand q summieren die o(q,s) zu 1.


Ein verstecktes Markov-Modell modelliert den folgenden Zufallsprozess.

a) Wähle einen zufälligen Zustand q(0) gemäß der Anfangsverteilung a(q).
b) Sei q(i) der aktuelle Zustand. Wähle eine zufällige Ausgabe
   s(i) gemäß der Ausgabeverteilung o(q(i),s).
c) Wähle einen zufälligen Nachfolgezustand r gemäß der 
   Übergangsverteilung t(q(i),r). Setze q(i+1) <- r und gehe zu b).

Nun stellt sich folgendes Problem. Angenommen, wir beobachten eine
zufällige Ausgabe s(0), s(1),..., s(l-1). Welche Zustandsfolge hat
diese Ausgabe erzeugt?

Natürlich ist diese Frage so nicht zu beantworten, da potentiell 
viele verschiedene Zustandsfolgen dieselbe Ausgabe produzieren 
können. Aber dennoch können wir eine sinnvolle Frage stellen.
Die Ausgabe s(0), s(1),..., s(l-1) induziert eine Wahrscheinlichkeitsverteilung
auf den Zustandsfolgen der Länge l,  indem wir einer Folge
q(0), q(1),..., q(l-1) die bedingte Wahrscheinlichkeit

Pr[q(0), q(1),..., q(l-1) Zustände | s(0), s(1),..., s(l-1) Ausgabe]

zuordnen. Nun suchen wir eine Zustandsfolge, die diese bedingte 
Wahrscheinlichkeit maximiert. Eine solche Zustandsfolge nennen wir
auch eine wahrscheinlichste Erklärung für die Ausgabe s(0),...,s(l-1).

Mit dem Satz von Bayes sehen wir, dass eine Zustandsfolge die bedingte
Wahrscheinlichkeit genau dann maximiert, wenn sie die Wahrscheinlichkeit

Pr[s(0),..., s(l-1) Ausgabe | q(0),..., q(l-1) Zustände]*Pr[q(0),..., q(l-1) Zustände]

maximiert.
Diesen Ausdruck können wir schreiben als
o(q(0),s(0))*o(q(1),s(1))*...*o(q(l-1),s(l-1))*a(q(0))*t(q(0),q(1))*t(q(1),q(2))*...*t(q(l-2),q(l-1)).

Nun finden wir einen effizienten Algorithmus mit Hilfe von dynamischem
Programmieren.

a) Finde geeignete Teilprobleme
  
  E[q, i] = Maximale Wahrscheinlichkeit über alle Zustandsfolgen
            q(0), q(1),..., q(i)=q, dass das HMM die Zustandsfolge 
	    q(0), q(1),..., q(i)=q ausführt und dabei die Ausgabe 
	    s(0), s(1),...,s(i) produziert.

b) Finde eine Rekursion für E[q,i]

  Zu Beginn ist die Wahrscheinlichkeit, dass wir uns im Zustand q befinden,
  a(q) und die Wahrscheinlichkeit, dass s(0) ausgegeben wird, ist o(q, s(0)).

  E[q,0] = a(q)*o(q(0),s(0)) für alle q in Q.

  Für die Rekursion unterscheiden wir, welches der vorletzte Zustand einer
  optimalen Zustandsfolge war, und nehmen das Maximum.

  E[q,i] = max_{r in Q} {E[r,i-1]*t(r,q)*o(q,s(i))} für q in Q und i=1,...l-1.

c) Implementiere die Rekursion
d) Finde eine optimale Zustandsfolge
  Übung

Man erhält eine Laufzeit von O(|Q|^2*l) und Platzbedarf O(|Q|*l).