imported>Aka: https, Kleinkram

2021-01-13T14:37:01Z

https, Kleinkram

Neue Seite

Der '''Forward-Algorithmus''' (auch ''Vorwärts-Algorithmus'', ''Vorwärts-Prozedur'') berechnet mit Hilfe sogenannter '''Forward-Variablen''' für ein gegebenes [[Hidden-Markov-Modell]] die [[Wahrscheinlichkeit]] einer bestimmten Beobachtung.
Er verwendet die Programmiermethode der [[Dynamische Programmierung|dynamischen Programmierung]].

== Markov-Modell ==
Das Markov-Modell ist definiert als <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 Matrix der [[Übergangswahrscheinlichkeit]]en,
* <math>B</math> die Matrix der Emissionswahrscheinlichkeiten,
* <math>\pi</math> die Anfangsverteilung für die möglichen Anfangszustände,
bezeichnet.

== Aufgabenstellung und Forward-Variablen ==
Gegeben sei ein [[Wort (Theoretische Informatik)|Wort]] <math>\boldsymbol o = o_1 o_2 \dots o_T \in V^*</math>. Der Forward-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 ''Forward-Variablen'' <math>\alpha_t(i)</math> verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt <math>1 \le t \le T</math> das [[Wort (Theoretische Informatik)#Präfix|Präfix]] <math>o_1 o_2 \ldots o_t</math> beobachtet zu haben und im Zustand <math>s_i \in S</math> zu sein gespeichert:
:<math>\alpha_t(i)=P(o_1 o_2 \ldots o_t;q_t=s_i|\lambda)</math>

== Funktionsweise ==
Die Forward-Variablen, und damit auch die Gesamtwahrscheinlichkeit, lassen sich rekursiv berechnen:

;Initialisierung
:<math>\alpha_1(i) = \pi_i \cdot b_{i}(o_1), \qquad 1 \le i \le \left| S \right|</math>

;Rekursion
:<math>\alpha_t(i) = \left( \sum_{j=1}^{|S|} \alpha_{t-1}(j) a_{ji} \right) \cdot b_i(o_t); \qquad 1<t\le T,\ 1 \le i \le \left| S \right|</math>

;Terminierung
:<math>P(\boldsymbol o|\lambda) = \sum_{j=1}^{|S|} \alpha_T(j)</math>

== Komplexität ==
Der Algorithmus benötigt <math>O(|S|^2 \cdot T)</math> Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit.
Der Speicherbedarf liegt in <math>O(|S| \cdot T)</math>, da zur Erreichung der polynomiellen Laufzeit alle <math>\alpha_t(i)</math> in einer <math>|S|\times T</math> Matrix abgelegt werden.

Wenn die Zwischenergebnisse von <math>\alpha_{t}(i)</math> für <math>t<T</math> nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf <math>O(|S|)</math>, da zwei Spaltenvektoren der Länge <math>|S|</math> ausreichen um <math>\alpha_{t-1}(i)</math> und <math>\alpha_t(i)</math> in jedem Rekursionsschritt zu speichern.

== Weitere Anwendungen ==
Die Forward-Variablen <math>\alpha_t(i)</math> werden zusammen mit den ''[[Backward-Algorithmus#Aufgabenstellung und Backward-Variablen|Backward-Variablen]]'' <math>\beta_t(i) = P(o_{t+1} \dots 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 ==
* [[Backward-Algorithmus]]
* [[Viterbi-Algorithmus]]
* [[Baum-Welch-Algorithmus]]

== Literatur ==
* {{Literatur
|Autor=R. Durbin et al.
|Titel=Biological sequence analysis. Probabilistic models of proteins and nucleic acids. ''11th printing, corrected 10. reprinting''
|Verlag=Cambridge University Press
|Ort=Cambridge u. a.
|Jahr=2006
|ISBN=0-521-62971-3
|Seiten=59
}}

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

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

Forward-Algorithmus - Versionsgeschichte

imported>Aka: https, Kleinkram