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 $\lambda =(S;V;A;B;\pi )$ , wobei

$S$ die Menge der verborgenen Zustände,
$V$ das Alphabet der beobachtbaren Symbole,
$A$ die Übergangsmatrix,
$B$ die Matrix der Emissionswahrscheinlichkeiten,
$\pi$ die Anfangswahrscheinlichkeitsverteilung für die möglichen Anfangszustände,

bezeichnet.

Aufgabenstellung und Backward-Variablen

Gegeben sei ein Wort ${\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}$ . Der Backward-Algorithmus berechnet nun $P({\boldsymbol {o}}|\lambda )$ , also die Wahrscheinlichkeit, im vorhandenen Modell $\lambda$ tatsächlich die Beobachtung ${\boldsymbol {o}}$ zu machen.

Dafür werden die Backward-Variablen $\beta _{t}(i)$ verwendet, sie bezeichnen die Wahrscheinlichkeit, das Suffix $o_{t+1}o_{t+2}\ldots o_{T}$ zu beobachten, falls das HMM zum Zeitpunkt $1\leq t\leq T$ im Zustand $s_{i}\in S$ gewesen ist:

\beta _{t}(i)=P(o_{t+1}o_{t+2}\dotsc o_{T}|q_{t}=s_{i};\lambda )

Algorithmus

Die Backward-Variablen werden rekursiv bestimmt:

Initialisierung: $\beta _{T}(i)=1,\qquad 1\leq i\leq \left|S\right|$

Rekursion: $\beta _{t}(i)=\sum _{j=1}^{\left|S\right|}b_{j}(o_{t+1})\cdot a_{ij}\cdot \beta _{t+1}(j),\qquad 1\leq i\leq \left|S\right|,\ 1\leq t<T$

Termination: $P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{\left|S\right|}\pi _{j}\cdot b_{j}(o_{1})\cdot \beta _{1}(j)$

Komplexität

Die Matrix aller Backward-Variablen braucht $O(|S|\cdot T)$ Speicher, werden die Zwischenergebnisse im Anschluss nicht mehr verwendet, so reduziert sich der Platzbedarf auf $O(|S|)$ , da nur mehr zwei Spalten der Länge $|S|$ benötigt werden, um die Werte von $\beta _{t+1}(i)$ und $\beta _{t}(i)$ in jedem Rekursionsschritt zu speichern.

Für jede einzelne Variable wird über $|S|$ Zeilen summiert, also liegt die Laufzeit in $O(|S|^{2}\cdot T)$ .

Weitere Anwendungen

Die Backward-Variablen $\beta _{t}(i)$ werden zusammen mit den Forward-Variablen $\alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=s_{i}|\lambda )$ 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 ${\boldsymbol {o}}$ zu einem festen Zeitpunkt $t$ im Zustand $s_{i}$ gewesen zu sein, denn nach dem Satz von Bayes gilt:

P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}

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.