Backward-Algorithmus
# 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 )}}$
