Forward-Algorithmus
# Forward-Algorithmus

Der Forward-Algorithmus (auch Vorwärts-Algorithmus, Vorwärts-Prozedur) berechnet mit Hilfe sogenannter Forward-Variablen für ein gegebenes Hidden-Markov-Modell die Wahrscheinlichkeit einer bestimmten Beobachtung. Er verwendet die Programmiermethode der dynamischen Programmierung.

## Markov-Modell

Das Markov-Modell ist definiert als $\lambda =(S;V;A;B;\pi )$, wobei

* $S$ die Menge der verborgenen Zustände,
* $V$ das Alphabet der beobachtbaren Symbole,
* $A$ die Matrix der Übergangswahrscheinlichkeiten,
* $B$ die Matrix der Emissionswahrscheinlichkeiten,
* $\pi$ die Anfangsverteilung für die möglichen Anfangszustände,

bezeichnet.

## Aufgabenstellung und Forward-Variablen

Gegeben sei ein Wort ${\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}$. Der Forward-Algorithmus berechnet nun $P({\boldsymbol {o}}|\lambda )$, also die Wahrscheinlichkeit im vorhandenen Modell $\lambda$ tatsächlich die Beobachtung ${\boldsymbol {o}}$ zu machen.

Dafür werden die Forward-Variablen $\alpha _{t}(i)$ verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt $1\leq t\leq T$ das Präfix $o_{1}o_{2}\ldots o_{t}$ beobachtet zu haben und im Zustand $s_{i}\in S$ zu sein gespeichert:

    $\alpha _{t}(i)=P(o_{1}o_{2}\ldots o_{t};q_{t}=s_{i}|\lambda )$

## Funktionsweise

Die Forward-Variablen, und damit auch die Gesamtwahrscheinlichkeit, lassen sich rekursiv berechnen:

### Initialisierung

    $\alpha _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\qquad 1\leq i\leq \left|S\right|$

### Rekursion

    $\alpha _{t}(i)=\left(\sum _{j=1}^{|S|}\alpha _{t-1}(j)a_{ji}\right)\cdot b_{i}(o_{t});\qquad 1<t\leq T,\ 1\leq i\leq \left|S\right|$

### Terminierung

    $P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{|S|}\alpha _{T}(j)$

## Komplexität

Der Algorithmus benötigt $O(|S|^{2}\cdot T)$ Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit. Der Speicherbedarf liegt in $O(|S|\cdot T)$, da zur Erreichung der polynomiellen Laufzeit alle $\alpha _{t}(i)$ in einer $|S|\times T$ Matrix abgelegt werden.

Wenn die Zwischenergebnisse von $\alpha _{t}(i)$ für $t<T$ nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf $O(|S|)$, da zwei Spaltenvektoren der Länge $|S|$ ausreichen um $\alpha _{t-1}(i)$ und $\alpha _{t}(i)$ in jedem Rekursionsschritt zu speichern.

## Weitere Anwendungen

Die Forward-Variablen $\alpha _{t}(i)$ werden zusammen mit den Backward-Variablen $\beta _{t}(i)=P(o_{t+1}\dots o_{T}|q_{t}=s_{i};\lambda )$ für den Baum-Welch-Algorithmus zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

Außerdem ermöglicht deren Kenntnis die Bestimmung der Wahrscheinlichkeit, bei der Beobachtung von ${\boldsymbol {o}}$ zu einem festen Zeitpunkt $t$ im Zustand $s_{i}$ gewesen zu sein, denn nach dem Satz von Bayes gilt:

    $P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}$
