Forward-Algorithmus

Der Forward-Algorithmus (auch Vorwärts-Algorithmus, Vorwärts-Prozedur) berechnet mit Hilfe der Forward-Variablen $α t (i)$ für ein gegebenes Hidden-Markov-Modell $λ = (S, A, B,π, V)$ die Wahrscheinlichkeit $P$ einer Beobachtung $O$ , d.h. $P (O | λ)$ .

Weiteres empfehlenswertes Fachwissen

Dauerhaft genaue Prüfgewichte dank 12 kostenloser Tipps

Richtiges Wägen mit Laborwaagen: Die Wägefibel

Leitfaden zu den grundlegenden Laborkenntnissen

Forward-Variable

Die Forward-Variable, d.h. die Wahrscheinlichkeit zum Zeitpunkt $t$ bei gegebener Beobachtung $O = (o 1, o 2,..., o t)$ im Zustand $s i$ zu sein, ist:

$\mathcal{\alpha}_t(i)=P(o_1,o_2,...,o_t,q_t=s_i|\mathcal{\lambda})$

Funktionsweise

$α t (i)$ (und damit auch die Gesamtwahrscheinlichkeit $P$ ) lässt sich induktiv berechnen:

1. Initialisierung

$\mathcal{\alpha}_1(i)=P(o_1,q_1=s_i|\mathcal{\lambda})=\pi_ib_{io_1}$

2. Induktion

$\mathcal{\alpha}_{t+1}(j)=P(o_1,...,o_t,o_{t+1},q_{t+1}=s_j|\mathcal{\lambda})=\sum_{i=1}^{|S|} \mathcal{\alpha}_t(i)a_{ij}b_{jo_{t+1}}$

3. Terminierung

$P(\mathcal{\mathcal{O}|\lambda})=\sum_{i=1}^{|S|} \mathcal{\alpha}_T(i)$

Erläuterungen

Der Algorithmus benötigt $| S | 2 T$ Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit $P$ . Die Forward-Variable $α t (i)$ wird zusammen mit der Backward-Variable $β t (i)$ für den Baum-Welch-Algorithmus zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

Kategorie: Bioinformatik

Dieser Artikel basiert auf dem Artikel Forward-Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.

Zuletzt angesehen