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

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

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

Initialisierung
Rekursion
Terminierung

Komplexität

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

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

Literatur

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

Weblinks