Forward-Algorithmus

Der Forward-Algorithmus (auch Vorwärts-Algorithmus, Vorwärts-Prozedur) berechnet mit Hilfe der Forward-Variablen α_t(i) für ein gegebenes Hidden-Markov-Modell λ die Wahrscheinlichkeit P einer Beobachtung O, d.h. P(O | λ). Er verwendet die Programmiermethode der dynamischen Programmierung.

Markov-Modell

Das Markov-Modell λ ist definiert als λ = (S,A,B,π,V), wobei

• S die Menge der verborgenen Zustände,
• A die Matrix der Übergangswahrscheinlichkeiten,
• B die Menge der Emissionswahrscheinlichkeiten,
• π die Anfangswahrscheinlichkeitsverteilung für die möglichen Anfangszustände,
• und V das Alphabet der beobachteten Symbole

bezeichnet.

Forward-Variable

Die Forward-Variable, d.h. die Wahrscheinlichkeit, zum Zeitpunkt t die Beobachtung $O=(o_1,o_2,\ldots,o_t)$ gemacht zu haben und im Zustand s_i zu sein, ist:

$\mathcal{\alpha}_t(i)=P(o_1,o_2,\ldots,o_t,q_t=s_i|\mathcal{\lambda})$

Funktionsweise

α_t(i) (und damit auch die Gesamtwahrscheinlichkeit P) lässt sich rekursiv berechnen:

1. Initialisierung

$\mathcal{\alpha}_1(i)=P(o_1,q_1=s_i|\mathcal{\lambda})=\pi_i b_{i}(o_1)$

2. Rekursion, $1<t\le T$

$\mathcal{\alpha}_{t}(j)=P(o_1,\ldots,o_{t},q_{t}=s_j|\mathcal{\lambda})=\sum_{i=1}^{|S|} \mathcal{\alpha}_{t-1}(i) a_{ij} b_{j}(o_{t})$

3. Terminierung

$P(\mathcal{\mathcal{O}|\lambda})=\sum_{i=1}^{|S|} \mathcal{\alpha}_T(i)$

Komplexität

Der Algorithmus benötigt O( | S | ²T) Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit P. Der Speicherbedarf liegt in O( | S | T), da zur Erreichung der polynomiellen Laufzeit alle α_t(j) in einer $|S|\times T$ Matrix gespeichert werden.

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

Erläuterungen

Die Forward-Variable α_t(i) wird zusammen mit der Backward-Variable β_t(i) für den Baum-Welch-Algorithmus zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

Siehe auch

• Backward-Algorithmus
• Viterbi-Algorithmus

Literatur

• Richard Durbin u. a.: 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.