Backward-Algorithmus

Der Backward-Algorithmus (auch Rückwärts-Algorithmus, Rückwärts-Prozedur) berechnet die Wahrscheinlichkeit, dass bei einem gegebenen Hidden-Markov-Modell M und einer beobachteten Symbolsequenz m das Modell sich zur Zeit i in dem Zustand s befand. Er verwendet die Programmiermethode der dynamischen Programmierung.

Algorithmus

Gegeben ist ein HMM M = (Σ,Q,A,E,Π), wobei

• Σ das Alphabet der beobachtbaren Symbole bezeichnet
• Q die Menge der verborgenen Zustände bezeichnet
• A die Matrix der Zustandsübergangswahrscheinlichkeiten bezeichnet. Für $i,j\in Q$ ist in der Zelle a_ij die Wahrscheinlichkeit für den Übergang von Zustand i nach j gespeichert.
• E die Matrix der Emissionswahrscheinlichkeiten bezeichnet. In der Zelle $e_{ix},\, i\in Q,\, x\in\Sigma$ ist die Wahrscheinlichkeit gespeichert, dass im Zustand i das beobachtete Zeichen x ausgegeben wird.
• Der Vektor Π für jeden Zustand die Wahrscheinlichkeit, dass in diesem Zustand gestartet wird, enthält.

Gesucht wird P(q_i = s | m). Die Eingabe ist die beobachtete Symbolsequenz $m\in\Sigma^*$, der Zeitpunkt i und der Zustand $s\in Q$.

Initialisierung

$B[s, L] = 1,\quad s\in Q$

Rekursion

$B[s, i] = \sum_{t\in Q} e_{t m[i+1]} a_{st} B[t,i+1],\qquad s\in Q, 1\le i< |m|$

Termination

$P(q_i = s | n) = \frac{F[s,i] B[s,i]}{Pr(m)}$

F[s,i] wird mit dem Forward-Algorithmus berechnet (in dem dortigen Artikel als Forward-Variable $\mathcal{\alpha}_{s}(i)$ bezeichnet).

Pr(m) ist die Kurzschreibweise für Pr(m | M). Dies kann entweder mit dem Forward-Algorithmus oder mit dem Backward-Algorithmus berechnet werden:

$Pr(m) = \sum_{t\in Q} B[t,1]\Pi_t e_{t m[1]}$

Komplexität

Die Tabelle V benötigt O( | m | | Q | ) Speicher. Für jede Zelle wird über | Q | Zeilen summiert. Also ist die Laufzeit in O( | m | | Q | ²).

Siehe auch

• Viterbi-Algorithmus
• Forward-Algorithmus

Literatur

• Durbin et al.: Biological sequence analysis. Cambridge, 2006, ISBN 0-521-62971-3, S. 59-60.