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 $𝒐=o_1{o}_2\dots o_T\in V^{*}$. Der Forward-Algorithmus berechnet nun $P(𝒐|\lambda )$, also die Wahrscheinlichkeit im vorhandenen Modell $\lambda$ tatsächlich die Beobachtung $𝒐$ zu machen.

Dafür werden die Forward-Variablen ${\alpha }_t(i)$ verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt $1\le t\le T$ das Präfix $o_1{o}_2\dots o_t$ beobachtet zu haben und im Zustand $s_i\in S$ zu sein gespeichert:

${\alpha }_t(i)=P(o_1{o}_2\dots 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),1\le i\le \left|S\right|$

Rekursion

${\alpha }_t(i)=(\sum _{j=1}^{|S|}{\alpha }_{t-1}(j)a_{ji})\cdot b_i(o_t);1<t\le T,1\le i\le \left|S\right|$

Terminierung

$P(𝒐|\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 $𝒐$ zu einem festen Zeitpunkt $t$ im Zustand $s_i$ gewesen zu sein, denn nach dem Satz von Bayes gilt:

$P(q_t=s_i|𝒐;\lambda )=\frac{{\alpha }_t(i)\cdot {\beta }_t(i)}{P(𝒐|\lambda )}$

Siehe auch

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

Literatur

• Vorlage:Literatur

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.