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 ${\displaystyle \lambda =(S;V;A;B;\pi )}$, wobei

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

bezeichnet.

Aufgabenstellung und Forward-Variablen

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

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

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

Funktionsweise

Die Forward-Variablen, u​nd damit a​uch die Gesamtwahrscheinlichkeit, lassen s​ich rekursiv berechnen:

Initialisierung

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

Rekursion

${\displaystyle \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

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

Komplexität

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

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

Weitere Anwendungen

Die Forward-Variablen ${\displaystyle \alpha _{t}(i)}$ werden zusammen mit den Backward-Variablen ${\displaystyle \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 ${\displaystyle {\boldsymbol {o}}}$ zu einem festen Zeitpunkt ${\displaystyle t}$ im Zustand ${\displaystyle s_{i}}$ gewesen zu sein, denn nach dem Satz von Bayes gilt:

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

Siehe auch

• Backward-Algorithmus
• Viterbi-Algorithmus
• Baum-Welch-Algorithmus

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.