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

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

bezeichnet.

Aufgabenstellung und Backward-Variablen

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

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

${\displaystyle \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

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

Rekursion

${\displaystyle \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

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

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

Weitere Anwendungen

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

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

Siehe auch

• Forward-Algorithmus
• Viterbi-Algorithmus
• Baum-Welch-Algorithmus

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.