imported>Aka: https, Kleinkram

2021-01-16T19:39:14Z

https, Kleinkram

Neue Seite

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 [[Dynamische Programmierung|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 (Informatik)|Alphabet]] der beobachtbaren Symbole,
* <math>A</math> die [[Übergangsmatrix]],
* <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 (Theoretische Informatik)|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 [[Wort (Theoretische Informatik)#Suffix|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-Algorithmus#Aufgabenstellung und Forward-Variablen|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 ==
* [[Forward-Algorithmus]]
* [[Viterbi-Algorithmus]]
* [[Baum-Welch-Algorithmus]]

== Literatur ==
* {{Literatur
|Autor=Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison
|Titel=Biological sequence analysis. Probabilistic models of proteins and nucleic acids
|Verlag=11th printing, corrected 10th reprinting. Cambridge University Press
|Ort = Cambridge u. a.
|Jahr=2006
|ISBN=0-521-62971-3
|Seiten=59–60
}}

== Weblinks ==
* Ernst G. Schukat-Talamazzini: [https://www.minet.uni-jena.de//fakultaet/schukat/MAS/Scriptum/lect05-HMM.pdf ''Spezielle Musteranalysesysteme.''] (PDF, 1,3 MB). Vorlesung im Wintersemester 2012/2013 an der Universität Jena. Kapitel 5, Folie 34 ff.

[[Kategorie:Algorithmus]]
[[Kategorie:Bioinformatik]]
[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Maschinelles Lernen]]
[[Kategorie:Stochastik]]

[[en:Forward-backward algorithm]]

Backward-Algorithmus - Versionsgeschichte

imported>Aka: https, Kleinkram