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