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 Backward-Algorithmus Viterbi-Algorithmus Baum-Welch-Algorithmus
Literatur
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.
Kategorie:Algorithmus Kategorie:Bioinformatik Kategorie:Dynamische Programmierung Kategorie:Maschinelles Lernen Kategorie:Stochastik