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 )}}

Siehe auch

Literatur

R. Durbin et al.: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. 11th printing, corrected 10. reprinting. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, S. 59.

Weblinks

E. G. Schukat-Talamazzini: Spezielle Musteranalysesysteme (PDF, 1,3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 32ff.