Backward Algorithmus Der auch Rückwärts Algorithmus Rückwärts Prozedur berechnet mit Hilfe von Backward Variablen die Wa

Backward-Algorithmus

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 Bearbeiten

Gegeben sei ein HMM , wobei

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

bezeichnet.

Aufgabenstellung und Backward-Variablen Bearbeiten

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

Dafür werden die Backward-Variablen verwendet, sie bezeichnen die Wahrscheinlichkeit, das Suffix zu beobachten, falls das HMM zum Zeitpunkt im Zustand gewesen ist:

Algorithmus Bearbeiten

Die Backward-Variablen werden rekursiv bestimmt:

Komplexität Bearbeiten

Die Matrix aller Backward-Variablen braucht Speicher, werden die Zwischenergebnisse im Anschluss nicht mehr verwendet, so reduziert sich der Platzbedarf auf , da nur mehr zwei Spalten der Länge benötigt werden, um die Werte von und in jedem Rekursionsschritt zu speichern.

Für jede einzelne Variable wird über Zeilen summiert, also liegt die Laufzeit in .

Weitere Anwendungen Bearbeiten

Die Backward-Variablen werden zusammen mit den Forward-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

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 Bearbeiten

Ernst G. Schukat-Talamazzini: Spezielle Musteranalysesysteme. (PDF, 1,3 MB). Vorlesung im Wintersemester 2012/2013 an der Universität Jena. Kapitel 5, Folie 34 ff.

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: November 27, 2023, 16:27 pm

Der Backward Algorithmus auch Ruckwarts Algorithmus Ruckwarts 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 Inhaltsverzeichnis 1 Markov Modell 2 Aufgabenstellung und Backward Variablen 3 Algorithmus 4 Komplexitat 5 Weitere Anwendungen 6 Siehe auch 7 Literatur 8 WeblinksMarkov Modell BearbeitenGegeben sei ein HMM 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 Ubergangsmatrix B displaystyle B nbsp die Matrix der Emissionswahrscheinlichkeiten p displaystyle pi nbsp die Anfangswahrscheinlichkeitsverteilung fur die moglichen Anfangszustande bezeichnet Aufgabenstellung und Backward 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 Backward 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 Backward Variablen b t i displaystyle beta t i nbsp verwendet sie bezeichnen die Wahrscheinlichkeit das Suffix o t 1 o t 2 o T displaystyle o t 1 o t 2 ldots o T nbsp zu beobachten falls das HMM zum Zeitpunkt 1 t T displaystyle 1 leq t leq T nbsp im Zustand s i S displaystyle s i in S nbsp gewesen ist b t i P o t 1 o t 2 o T q t s i l displaystyle beta t i P o t 1 o t 2 dotsc o T q t s i lambda nbsp Algorithmus BearbeitenDie Backward Variablen werden rekursiv bestimmt Initialisierung b T i 1 1 i S displaystyle beta T i 1 qquad 1 leq i leq left S right nbsp Rekursion b t i j 1 S b j o t 1 a i j b t 1 j 1 i S 1 t lt T displaystyle beta t i sum j 1 left S right b j o t 1 cdot a ij cdot beta t 1 j qquad 1 leq i leq left S right 1 leq t lt T nbsp Termination P o l j 1 S p j b j o 1 b 1 j displaystyle P boldsymbol o lambda sum j 1 left S right pi j cdot b j o 1 cdot beta 1 j nbsp Komplexitat BearbeitenDie Matrix aller Backward Variablen braucht O S T displaystyle O S cdot T nbsp Speicher werden die Zwischenergebnisse im Anschluss nicht mehr verwendet so reduziert sich der Platzbedarf auf O S displaystyle O S nbsp da nur mehr zwei Spalten der Lange S displaystyle S nbsp benotigt werden um die Werte von b t 1 i displaystyle beta t 1 i nbsp und b t i displaystyle beta t i nbsp in jedem Rekursionsschritt zu speichern Fur jede einzelne Variable wird uber S displaystyle S nbsp Zeilen summiert also liegt die Laufzeit in O S 2 T displaystyle O S 2 cdot T nbsp Weitere Anwendungen BearbeitenDie Backward Variablen b t i displaystyle beta t i nbsp werden zusammen mit den Forward Variablen 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 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 BearbeitenForward Algorithmus Viterbi Algorithmus Baum Welch AlgorithmusLiteratur BearbeitenRichard 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 BearbeitenErnst G Schukat Talamazzini Spezielle Musteranalysesysteme PDF 1 3 MB Vorlesung im Wintersemester 2012 2013 an der Universitat Jena Kapitel 5 Folie 34 ff Abgerufen von https de wikipedia org w index php title Backward Algorithmus amp oldid 207722665