www.wikidata.de-de.nina.az

Forward Algorithmus Der auch Vorwärts Algorithmus Vorwärts Prozedur berechnet mit Hilfe sogenannter Forward Variablen fü

Forward-Algorithmus

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 dynamischen Programmierung.

Markov-Modell Bearbeiten

Das Markov-Modell ist definiert als , wobei

  • die Menge der verborgenen Zustände,
  • das Alphabet der beobachtbaren Symbole,
  • die Matrix der Übergangswahrscheinlichkeiten,
  • die Matrix der Emissionswahrscheinlichkeiten,
  • die Anfangsverteilung für die möglichen Anfangszustände,

bezeichnet.

Aufgabenstellung und Forward-Variablen Bearbeiten

Gegeben sei ein Wort . Der Forward-Algorithmus berechnet nun , also die Wahrscheinlichkeit im vorhandenen Modell tatsächlich die Beobachtung zu machen.

Dafür werden die Forward-Variablen verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt das Präfix beobachtet zu haben und im Zustand zu sein gespeichert:

Funktionsweise Bearbeiten

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

Komplexität Bearbeiten

Der Algorithmus benötigt Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit. Der Speicherbedarf liegt in , da zur Erreichung der polynomiellen Laufzeit alle in einer Matrix abgelegt werden.

Wenn die Zwischenergebnisse von für nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf , da zwei Spaltenvektoren der Länge ausreichen um und in jedem Rekursionsschritt zu speichern.

Weitere Anwendungen Bearbeiten

Die Forward-Variablen werden zusammen mit den Backward-Variablen 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 zu einem festen Zeitpunkt im Zustand gewesen zu sein, denn nach dem Satz von Bayes gilt:

Siehe auch Bearbeiten

Literatur Bearbeiten

  • R. Durbin et al.: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. 11th printing, corrected 10. reprinting. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, S. 59.

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Forward Algorithmus auch Vorwarts Algorithmus Vorwarts Prozedur berechnet mit Hilfe sogenannter Forward Variablen fur ein gegebenes Hidden Markov Modell die Wahrscheinlichkeit einer bestimmten Beobachtung Er verwendet die Programmiermethode der dynamischen Programmierung Inhaltsverzeichnis 1 Markov Modell 2 Aufgabenstellung und Forward Variablen 3 Funktionsweise 4 Komplexitat 5 Weitere Anwendungen 6 Siehe auch 7 Literatur 8 WeblinksMarkov Modell BearbeitenDas Markov Modell ist definiert als l S V A B p displaystyle lambda S V A B pi nbsp wobei S displaystyle S nbsp die Menge der verborgenen Zustande V displaystyle V nbsp das Alphabet der beobachtbaren Symbole A displaystyle A nbsp die Matrix der Ubergangswahrscheinlichkeiten B displaystyle B nbsp die Matrix der Emissionswahrscheinlichkeiten p displaystyle pi nbsp die Anfangsverteilung fur die moglichen Anfangszustande bezeichnet Aufgabenstellung und Forward Variablen BearbeitenGegeben sei ein Wort o o 1 o 2 o T V displaystyle boldsymbol o o 1 o 2 dots o T in V nbsp Der Forward Algorithmus berechnet nun P o l displaystyle P boldsymbol o lambda nbsp also die Wahrscheinlichkeit im vorhandenen Modell l displaystyle lambda nbsp tatsachlich die Beobachtung o displaystyle boldsymbol o nbsp zu machen Dafur werden die Forward Variablen a t i displaystyle alpha t i nbsp verwendet Darin ist die Wahrscheinlichkeit zum Zeitpunkt 1 t T displaystyle 1 leq t leq T nbsp das Prafix o 1 o 2 o t displaystyle o 1 o 2 ldots o t nbsp beobachtet zu haben und im Zustand s i S displaystyle s i in S nbsp zu sein gespeichert a t i P o 1 o 2 o t q t s i l displaystyle alpha t i P o 1 o 2 ldots o t q t s i lambda nbsp Funktionsweise BearbeitenDie Forward Variablen und damit auch die Gesamtwahrscheinlichkeit lassen sich rekursiv berechnen Initialisierung a 1 i p i b i o 1 1 i S displaystyle alpha 1 i pi i cdot b i o 1 qquad 1 leq i leq left S right nbsp Rekursion a t i j 1 S a t 1 j a j i b i o t 1 lt t T 1 i S displaystyle alpha t i left sum j 1 S alpha t 1 j a ji right cdot b i o t qquad 1 lt t leq T 1 leq i leq left S right nbsp Terminierung P o l j 1 S a T j displaystyle P boldsymbol o lambda sum j 1 S alpha T j nbsp Komplexitat BearbeitenDer Algorithmus benotigt O S 2 T displaystyle O S 2 cdot T nbsp Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit Der Speicherbedarf liegt in O S T displaystyle O S cdot T nbsp da zur Erreichung der polynomiellen Laufzeit alle a t i displaystyle alpha t i nbsp in einer S T displaystyle S times T nbsp Matrix abgelegt werden Wenn die Zwischenergebnisse von a t i displaystyle alpha t i nbsp fur t lt T displaystyle t lt T nbsp nach der Beendigung der Rekursion nicht benotigt werden dann reduziert sich der Speicherbedarf auf O S displaystyle O S nbsp da zwei Spaltenvektoren der Lange S displaystyle S nbsp ausreichen um a t 1 i displaystyle alpha t 1 i nbsp und a t i displaystyle alpha t i nbsp in jedem Rekursionsschritt zu speichern Weitere Anwendungen BearbeitenDie Forward Variablen a t i displaystyle alpha t i nbsp werden zusammen mit den Backward Variablen b t i P o t 1 o T q t s i l displaystyle beta t i P o t 1 dots o T q t s i lambda nbsp fur den Baum Welch Algorithmus zur Losung des mit Hidden Markov Modellen gegebenen Lernproblems benotigt Ausserdem ermoglicht deren Kenntnis die Bestimmung der Wahrscheinlichkeit bei der Beobachtung von o displaystyle boldsymbol o nbsp zu einem festen Zeitpunkt t displaystyle t nbsp im Zustand s i displaystyle s i nbsp gewesen zu sein denn nach dem Satz von Bayes gilt P q t s i o l a t i b t i P o l displaystyle P q t s i boldsymbol o lambda frac alpha t i cdot beta t i P boldsymbol o lambda nbsp Siehe auch BearbeitenBackward Algorithmus Viterbi Algorithmus Baum Welch AlgorithmusLiteratur BearbeitenR Durbin et al Biological sequence analysis Probabilistic models of proteins and nucleic acids 11th printing corrected 10 reprinting Cambridge University Press Cambridge u a 2006 ISBN 0 521 62971 3 S 59 Weblinks BearbeitenE G Schukat Talamazzini Spezielle Musteranalysesysteme PDF 1 3 MB Vorlesung im WS 2012 13 an der Universitat Jena Kapitel 5 Folie 32ff Abgerufen von https de wikipedia org w index php title Forward Algorithmus amp oldid 207603695