Backward-Algorithmus


aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 <math>\lambda=(S;V;A;B;\pi)</math>, wobei

  • <math>S</math> die Menge der verborgenen Zustände,
  • <math>V</math> das Alphabet der beobachtbaren Symbole,
  • <math>A</math> die Matrix der Übergangswahrscheinlichkeiten,
  • <math>B</math> die Matrix der Emissionswahrscheinlichkeiten,
  • <math>\pi</math> die Anfangswahrscheinlichkeitsverteilung für die möglichen Anfangszustände,

bezeichnet.

Aufgabenstellung und Backward-Variablen

Gegeben sei ein Wort <math>\boldsymbol o = o_1 o_2 \dots o_T \in V^*</math> der Backward-Algorithmus berechnet nun <math>P(\boldsymbol o|\lambda)</math>, also die Wahrscheinlichkeit im vorhandenen Modell <math>\lambda</math> tatsächlich die Beobachtung <math>\boldsymbol o</math> zu machen.

Dafür werden die Backward-Variablen <math>\beta_t(i)</math> verwendet, sie bezeichnen die Wahrscheinlichkeit das Suffix <math>o_{t+1} o_{t+2} \ldots o_T</math> zu beobachten, falls das HMM zum Zeitpunkt <math>1 \le t \le T</math> im Zustand <math>s_i \in S</math> gewesen ist:

<math>\beta_t(i) = P(o_{t+1} o_{t+2} \dotsc o_T | q_t = s_i; \lambda)</math>

Algorithmus

Die Backward-Variablen werden rekursiv bestimmt:

Initialisierung
<math>\beta_T(i) = 1, \qquad 1 \le i \le \left| S \right|</math>
Rekursion
<math>\beta_t(i) = \sum_{j=1}^{\left|S\right|} b_j(o_{t+1}) \cdot a_{ij} \cdot \beta_{t+1}(j), \qquad 1 \le i \le \left| S \right|,\ 1 \le t < T</math>
Termination
<math>P(\boldsymbol o|\lambda) = \sum_{j=1}^{\left|S\right|} \pi_j \cdot b_j(o_1)\cdot \beta_1(j)</math>

Komplexität

Die Matrix aller Backward-Variablen braucht <math>O(|S| \cdot T)</math> Speicher, werden die Zwischenergebnisse im Anschluss nicht mehr verwendet, so reduziert sich der Platzbedarf auf <math>O(|S|)</math>, da nur mehr zwei Spalten der Länge <math>|S|</math> benötigt werden, um die Werte von <math>\beta_{t+1}(i)</math> und <math>\beta_t(i)</math> in jedem Rekursionsschritt zu speichern.

Für jede einzelne Variable wird über <math>|S|</math> Zeilen summiert, also liegt die Laufzeit in <math>O(|S|^2 \cdot T)</math>.

Weitere Anwendungen

Die Backward-Variablen <math>\beta_t(i)</math> werden zusammen mit den Forward-Variablen <math>\alpha_t(i) = P(o_1,o_2,\ldots,o_t,q_t=s_i|\lambda)</math> 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 <math>\boldsymbol o</math> zu einem festen Zeitpunkt <math>t</math> im Zustand <math>s_i</math> gewesen zu sein, denn nach dem Satz von Bayes gilt:

<math>P(q_t = s_i|\boldsymbol o; \lambda) = \frac{\alpha_t(i) \cdot \beta_t(i)}{P(\boldsymbol o|\lambda)}</math>

Siehe auch

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