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  , wobei

  •   die Menge der verborgenen Zustände,
  •   das Alphabet der beobachtbaren Symbole,
  •   die Matrix der Übergangswahrscheinlichkeiten,
  •   die Matrix der Emissionswahrscheinlichkeiten,
  •   die Anfangsverteilung für die möglichen Anfangszustände,

bezeichnet.

Aufgabenstellung und Forward-Variablen

Bearbeiten

Gegeben sei ein Wort  . Der Forward-Algorithmus berechnet nun  , also die Wahrscheinlichkeit im vorhandenen Modell   tatsächlich die Beobachtung   zu machen.

Dafür werden die Forward-Variablen   verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt   das Präfix   beobachtet zu haben und im Zustand   zu sein gespeichert:

 

Funktionsweise

Bearbeiten

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

Initialisierung
 
Rekursion
 
Terminierung
 

Komplexität

Bearbeiten

Der Algorithmus benötigt   Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit. Der Speicherbedarf liegt in  , da zur Erreichung der polynomiellen Laufzeit alle   in einer   Matrix abgelegt werden.

Wenn die Zwischenergebnisse von   für   nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf  , da zwei Spaltenvektoren der Länge   ausreichen um   und   in jedem Rekursionsschritt zu speichern.

Weitere Anwendungen

Bearbeiten

Die Forward-Variablen   werden zusammen mit den Backward-Variablen   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   im Zustand   gewesen zu sein, denn nach dem Satz von Bayes gilt:

 

Siehe auch

Bearbeiten

Literatur

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.
Bearbeiten