Forward-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 & Forward-Variablen[Bearbeiten]

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 \le t \le 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[Bearbeiten]

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 \le i \le \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\le T,\ 1 \le i \le \left| S \right|
Terminierung
P(\boldsymbol o|\lambda) = \sum_{j=1}^{|S|} \alpha_T(j)

Komplexität[Bearbeiten]

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[Bearbeiten]

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 der Bayes-Formel gilt:

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

Siehe auch[Bearbeiten]

Literatur & Weblinks[Bearbeiten]

  •  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.
  • E.G. Schukat-Talamazzini: Spezielle Musteranalysesysteme (PDF, 1.3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 32ff.