Was ist der Unterschied zwischen dem Vorwärts-Rückwärts- und dem Viterbi-Algorithmus?

Zuerst ein bisschen Hintergrund, vielleicht klärt es die Dinge auf ein bisschen.

Wenn es um HMMs (Hidden Markov Models) geht, sind im Allgemeinen drei Probleme zu berücksichtigen:

1. Bewertungsproblem

   • Das Bewertungsproblem beantwortet die Frage: Wie hoch ist die Wahrscheinlichkeit, dass eine bestimmte Folge von Symbolen von einem bestimmten Modell erzeugt wird?
   • Zur Auswertung verwenden wir zwei Algorithmen: den Vorwärtsalgorithmus oder den Rückwärtsalgorithmus (verwechseln Sie sie NICHT mit dem Vorwärts-Rückwärts-Algorithmus).

2. Decodierungsproblem

   as Problem der Dekodierung beantwortet die Frage: Was ist bei einer Folge von Symbolen (Ihren Beobachtungen) und einem Modell die wahrscheinlichste Folge von Zuständen, die die Folge erzeugt haben?
3. Zum Decodieren verwenden wir den Viterbi-Algorithmus .

Trainingsproblem

• Das Trainingsproblem beantwortet die Frage: Finden Sie anhand einer Modellstruktur und einer Reihe von Sequenzen das Modell, das am besten zu den Daten passt .
• Für dieses Problem können wir die folgenden 3 Algorithmen verwenden:
  1. MLE (Maximum Likelihood Estimation)
  2. Viterbi-Training (NICHT mit Viterbi-Decodierung verwechseln)
  3. Baum Welch = Vorwärts-Rückwärts-Algorithmus

Um es zusammenzufassen, verwenden Sie den Viterbi-Algorithmus für die Dekodierungsproblem und Baum Welch / Vorwärts-Rückwärts, wenn Sie Ihr Modell auf einer Reihe von Sequenzen trainieren.

Baum Welch funktioniert folgendermaßen.

Für jede Sequenz im Trainingssatz von Sequenzen.

1. Berechnen Sie Vorwärtswahrscheinlichkeiten mit dem Vorwärtsalgorithmus
2. Berechnen Sie Rückwärtswahrscheinlichkeiten mit dem Rückwärtsalgorithmus
3. Berechnen Sie die Beiträge der aktuellen Sequenz zu den Übergängen des Modells, berechnen Sie die Beiträge der aktuellen Sequenz zu den Emissionswahrscheinlichkeiten des Modells.
4. Berechnen Sie die neuen Modellparameter (Startwahrscheinlichkeiten, Übergangswahrscheinlichkeiten, Emissionswahrscheinlichkeiten) )
5. Berechnen Sie die Neue Protokollwahrscheinlichkeit des Modells
6. Stoppen Sie, wenn die Änderung der Protokollwahrscheinlichkeit kleiner als ein bestimmter Schwellenwert ist oder wenn eine maximale Anzahl von Iterationen überschritten wird.

Wenn erforderlich Eine vollständige Beschreibung der Gleichungen für die Viterbi-Decodierung und des Trainingsalgorithmus lässt mich wissen und ich kann Sie in die richtige Richtung weisen.

Kommentare

• Hallo . Wenn wir den Pfad während der Auswertung mit dem Vorwärtsalgorithmus speichern, wird der Viterbi-Algorithmus beim Decodieren redundant verwendet?

Ich finde diese beiden folgenden Folien von {2} wirklich gut, um den Forward zu positionieren -backward- und Viterbi-Algorithmen unter allen anderen typischen Algorithmen, die mit HMM verwendet werden:

Hinweise :

• $ x $ ist die beobachtete Emission (en), $ \ pi $ sind die Parameter des HMM.
• Pfad = eine Folge von Emissionen
• Dekodierung = Inferenz
• Lernen = Training = Parameterschätzung
• Einige Artikel (z. B. {1}) behaupten, dass Baum-Welch der gleiche ist wie der Vorwärts-Rückwärts-Algorithmus, aber Ich agr ee mit Masterfool und Wikipedia: Baum-Welch ist ein Erwartungsmaximierungsalgorithmus, der den Vorwärts-Rückwärts-Algorithmus verwendet. Die beiden Abbildungen unterscheiden Baum-Welch auch vom Vorwärts-Rückwärts-Algorithmus.

Referenzen:

• {1} Lember, Jüri und Alexey Koloydenko. „Das angepasste Viterbi-Training für versteckte Markov-Modelle.“ Bernoulli 14, Nr. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Computational Biology: Genome, Netzwerke, Evolution (Herbst 2012) Vorlesung 07 – HMMs II (29.09.2012) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

Morats Antwort ist in einem Punkt falsch: Baum -Welch ist ein Expectation-Maximization-Algorithmus, mit dem die Parameter eines HMM trainiert werden. Es verwendet den Vorwärts-Rückwärts-Algorithmus während jeder Iteration. Der Vorwärts-Rückwärts-Algorithmus ist eigentlich nur eine Kombination der Vorwärts- und Rückwärtsalgorithmen: ein Vorwärtsdurchlauf, ein Rückwärtsdurchlauf. Der Vorwärts-Rückwärts-Algorithmus wird allein nicht zum Trainieren der Parameter eines HMM verwendet, sondern nur zum Glätten: Berechnen der Grenzwahrscheinlichkeiten einer Folge von Zuständen.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov hatte eine genaue Antwort. Ich würde ein Beispiel hinzufügen, um das zu sagen Unterschiede zwischen Vorwärts-Rückwärts- und Viterbi-Algorithmen.

Angenommen, wir haben dieses HMM (von der Wikipedia-HMM-Seite). Beachten Sie, dass das Modell bereits angegeben ist Hier wird nicht aus der Datenaufgabe gelernt.

Angenommen, unsere Daten sind eine Sequenz der Länge 4. (Walk, Shop, Walk, Clean). Zwei Algorithmen geben unterschiedliche Dinge.

• Der Vorwärts-Rückwärts-Algorithmus gibt das -Probabi an lity jedes versteckten Zustands . Hier ist ein Beispiel. Beachten Sie, dass jede Spalte in der Tabelle bis zu $ 1 $ summiert.

• Der Viterbi-Algorithmus gibt die wahrscheinlichste Folge versteckter Zustände . Hier ist ein Beispiel. Es ist zu beachten, dass mit dieser versteckten Zustandssequenz auch eine Wahrscheinlichkeit verbunden ist. Diese Sequenz hat max prob. über alle anderen Sequenzen (z. B. $ 2 ^ 4 = 16 $ Sequenzen von allen Sunny bis allen Rainy).

Hier sind einige R Code für die Demo

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))