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 <math>\lambda=(S;V;A;B;\pi)</math>, wobei

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

bezeichnet.

Aufgabenstellung und Forward-Variablen

Gegeben sei ein Wort <math>\boldsymbol o = o_1 o_2 \dots o_T \in V^*</math>. Der Forward-Algorithmus berechnet nun <math>P(\boldsymbol o|\lambda)</math>, also die Wahrscheinlichkeit im vorhandenen Modell <math>\lambda</math> tatsächlich die Beobachtung <math>\boldsymbol o</math> zu machen.

Dafür werden die Forward-Variablen <math>\alpha_t(i)</math> verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt <math>1 \le t \le T</math> das Präfix <math>o_1 o_2 \ldots o_t</math> beobachtet zu haben und im Zustand <math>s_i \in S</math> zu sein gespeichert:

<math>\alpha_t(i)=P(o_1 o_2 \ldots o_t;q_t=s_i|\lambda)</math>

Funktionsweise

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

Initialisierung: <math>\alpha_1(i) = \pi_i \cdot b_{i}(o_1), \qquad 1 \le i \le \left| S \right|</math>

Rekursion: <math>\alpha_t(i) = \left( \sum_{j=1}^{|S|} \alpha_{t-1}(j) a_{ji} \right) \cdot b_i(o_t); \qquad 1<t\le T,\ 1 \le i \le \left| S \right|</math>

Terminierung: <math>P(\boldsymbol o|\lambda) = \sum_{j=1}^{|S|} \alpha_T(j)</math>

Komplexität

Der Algorithmus benötigt <math>O(|S|^2 \cdot T)</math> Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit. Der Speicherbedarf liegt in <math>O(|S| \cdot T)</math>, da zur Erreichung der polynomiellen Laufzeit alle <math>\alpha_t(i)</math> in einer <math>|S|\times T</math> Matrix abgelegt werden.

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

Weitere Anwendungen

Die Forward-Variablen <math>\alpha_t(i)</math> werden zusammen mit den Backward-Variablen <math>\beta_t(i) = P(o_{t+1} \dots o_T| q_t = s_i; \lambda)</math> 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 <math>\boldsymbol o</math> zu einem festen Zeitpunkt <math>t</math> im Zustand <math>s_i</math> gewesen zu sein, denn nach dem Satz von Bayes gilt:

<math>P(q_t = s_i|\boldsymbol o; \lambda) = \frac{\alpha_t(i) \cdot \beta_t(i)}{P(\boldsymbol o|\lambda)}</math>

Siehe auch

Literatur

{{#invoke:Vorlage:Literatur|f}}

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.