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.

Inhaltsverzeichnis

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 aij 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(qi = 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 | 2).

Siehe auch

Literatur

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Backward Raytracing — Raytracing (dt. Strahlverfolgung[1] oder Strahlenverfolgung[2], in englischer Schreibweise meist ray tracing, seltener ray shooting) ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung… …   Deutsch Wikipedia

  • Baum-Welch-Algorithmus — In der Informatik und in statistischen Berechnungsmodellen wird der Baum Welch Algorithmus benutzt, um die unbekannten Parameter eines Hidden Markov Models (HMM) zu finden. Er nutzt den Forward Backward Algorithmus zur Berechnung von… …   Deutsch Wikipedia

  • Forward-Algorithmus — Der Forward Algorithmus (auch Vorwärts Algorithmus, Vorwärts Prozedur) berechnet mit Hilfe der Forward Variablen αt(i) für ein gegebenes Hidden Markov Modell λ die Wahrscheinlichkeit P einer Beobachtung O, d.h. P(O | λ). Er verwendet die… …   Deutsch Wikipedia

  • Viterbi-Algorithmus — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • Andrea Viterbi — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • Andrew Viterbi — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • Viterbi — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • HMM — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden-Markov-Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden Markov Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”