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 $𝒐=o_1{o}_2\dots o_T\in V^{*}$. Der Backward-Algorithmus berechnet nun $P(𝒐|\lambda )$, also die Wahrscheinlichkeit, im vorhandenen Modell $\lambda$ tatsächlich die Beobachtung $𝒐$ zu machen.

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

${\beta }_t(i)=P(o_{t+1}{o}_{t+2}\dots o_T|q_t=s_i;\lambda )$

Algorithmus

Die Backward-Variablen werden rekursiv bestimmt:

Initialisierung

${\beta }_T(i)=1,1\le i\le \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),1\le i\le \left|S\right|,1\le t<T$

Termination

$P(𝒐|\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,\dots ,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 $𝒐$ zu einem festen Zeitpunkt $t$ im Zustand $s_i$ gewesen zu sein, denn nach dem Satz von Bayes gilt:

$P(q_t=s_i|𝒐;\lambda )=\frac{{\alpha }_t(i)\cdot {\beta }_t(i)}{P(𝒐|\lambda )}$

Siehe auch

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

Literatur

• Vorlage:Literatur

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.