Backward-Algorithmus

Der Backward-Algorithmus (auch Rückwärts-Algorithmus, Rückwärts-Prozedur) berechnet mit Hilfe von Backward-Variablen die Wahrscheinlichkeit, in einem gegebenen Hidden-Markov-Modell (HMM) eine bestimmte Symbolsequenz zu beobachten. Der Algorithmus verwendet die Programmiermethode der dynamischen Programmierung.

Markov-Modell

Gegeben sei ein HMM , wobei

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

bezeichnet.

Aufgabenstellung und Backward-Variablen

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

Dafür werden die Backward-Variablen verwendet, sie bezeichnen die Wahrscheinlichkeit, das Suffix zu beobachten, falls das HMM zum Zeitpunkt im Zustand gewesen ist:

Algorithmus

Die Backward-Variablen werden rekursiv bestimmt:

Initialisierung
Rekursion
Termination

Komplexität

Die Matrix aller Backward-Variablen braucht Speicher, werden die Zwischenergebnisse im Anschluss nicht mehr verwendet, so reduziert sich der Platzbedarf auf , da nur mehr zwei Spalten der Länge benötigt werden, um die Werte von und in jedem Rekursionsschritt zu speichern.

Für jede einzelne Variable wird über Zeilen summiert, also liegt die Laufzeit in .

Weitere Anwendungen

Die Backward-Variablen werden zusammen mit den Forward-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

  • Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. 11th printing, corrected 10th reprinting. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, S. 59–60.

Weblinks

  • Ernst G. Schukat-Talamazzini: Spezielle Musteranalysesysteme. (PDF, 1,3 MB). Vorlesung im Wintersemester 2012/2013 an der Universität Jena. Kapitel 5, Folie 34 ff.