Ich suche nach einer sehr einfachen Erklärung für Baum Welch und Viterbi für HMMs mit einem einfachen, gut kommentierten Beispiel. Fast alle Erklärungen, die ich im Internet finde, springen ausnahmslos von Anfang an in eine fast vollständig auf Jargon / Symbolen basierende Erklärung. Die wenigen Male, in denen sie ein Beispiel haben, wird es normalerweise zur Seite geschoben oder schlecht kommentiert (dh es ist unklar, wie die Symbole und Das Beispiel ist miteinander verwandt.) Ich habe Dinge wie einige Quellen gehört, die behaupten, Baum Welch basiert auf dem EM-Algorithmus, andere sagen, dass er auf dem Vorwärts-Rückwärts-Algorithmus basiert, und einige sagen beides, also möchte ich Details wie erhalten das hat sich geklärt.
Das nächste, das ich bisher gefunden habe, ist ein 1-stündiges Video, das hier gepostet wurde. Die Leute sagten, es sei großartig, aber nicht abspielbar, weil Flash verboten ist, und eine Erklärung auf Wikipedia, neben der ein Hinweis steht, dass es falsch ist .
Antwort
Ich suche nach einer sehr einfachen Erklärung für Baum Welch und Viterbi für HMMs …
-
Angesichts der beobachteten Daten findet der Baum-Welch-Algorithmus die Wahrscheinlichkeitsmaximierungsparameter.
-
Angesichts der beobachteten Daten und der Parameter Der Viterbi-Algorithmus findet die wahrscheinlichste Folge versteckter Zustände.
Ich habe Dinge wie einige Quellen gehört, die behaupten, Baum Welch sei es basierend auf dem EM-Algorithmus …
Der Baum-Welch-Algorithmus ist ein Sonderfall des EM-Algorithmus.
… und andere sagen, dass es auf dem Vorwärts-Rückwärts-Algorithmus basiert
Bei der Vorwärts-Rückwärts-Zerlegung führen Sie den Schritt „E-“ aus (unter Verwendung der EM-Terminologie). Es ist spezifisch für versteckte Markov-Modelle.
Die wenigen Male, in denen sie ein Beispiel haben, wird es normalerweise zur Seite geschoben oder schlecht kommentiert (dh es ist unklar, wie Die Symbole und das Beispiel sind miteinander verbunden.)
Ich weiß nicht, welche Beispiele Sie sich ansehen, aber ich kann Ihnen das dort sagen viele gute da draußen. Denken Sie daran, dass diese Methoden vor sehr langer Zeit erfunden wurden und immer noch weit verbreitet sind . Der oben verlinkte Rabiner ist wahrscheinlich der berühmteste, aber Sie müssen einen finden, den Sie mögen, damit Sie weiterarbeiten können. Ich würde empfehlen, einen mit einem Beispiel zu finden, das Daten enthält, an denen Sie interessiert sind, und die Sie notieren Gefühl ist lernfähig. Was auch immer Sie finden, wird viel Notation haben. Daran führt kein Weg vorbei, also müssen Sie nur etwas finden, in das Sie sich einleben können.
Antwort
Ich habe Das perfekte Papier für Sie: http://www.stat.columbia.edu/~liam/teaching/neurostat-fall17/papers/hmm/rabiner.pdf
Beachten Sie, dass es neuere BW-Methoden gibt.
Versuchte einfache Erklärung für Viterbi: Das Ziel von Viterbi besteht darin, während eines bestimmten Zeitraums eine optimale Folge von Zuständen zu finden.
Beginnen Sie mit den anfänglichen Wahrscheinlichkeiten, sich zu einem bestimmten Zeitpunkt in einem Zustand $ s $ zu befinden $ t = 0 $. Erhöhen Sie dann $ t $ und finden Sie für jeden Zustand zu diesem Zeitpunkt ($ t = 1 $) den besten Zustand $ s $ bei $ t-1 $ (am besten wie in der Sequenz, die die höchste Wahrscheinlichkeit ergibt ). Speichern Sie diese Informationen. Das bedeutet, dass Sie für jeden Zustand $ s $ bei $ t = 1 $ speichern, was der beste Zustand $ s $ bei $ t = 0 $ ist. Speichern Sie auch die Wahrscheinlichkeit für diese (optimale) Sequenz.
Erhöhen Sie dann $ t $ auf $ t = 2 $ und wiederholen Sie den Vorgang (wobei die Wahrscheinlichkeiten für jeden Zustand $ s $ bei $ t-1 $ die gerade berechneten besten Wahrscheinlichkeiten für diesen Zustand sind) Der Punkt, an dem Sie $ t = T $ erreichen (letzter Zeitpunkt). Dann wählen Sie einfach den Zustand mit der höchsten Wahrscheinlichkeit aus und denken für jeden Zustand jedes Mal daran, wenn Sie den besten Zustand für $ t-1 $ gespeichert haben. Nehmen Sie also den besten Zustand bei $ t = T $ und arbeiten Sie sich dann immer rückwärts vor Auswahl dieses gespeicherten optimalen Zustands.
Um näher zu erläutern, was er auf einer allgemeineren Ebene tut: Wenn Sie eine Reihe von Zuständen $ S $ haben, die alle über einen bestimmten Zeitraum von $ T $ ausgewählt werden können, a Eine naive Lösung, um die beste Sequenz zu finden, besteht darin, alle möglichen Sequenzen aufzulisten und dann die Wahrscheinlichkeit für jede von ihnen zu berechnen (dh das Produkt aus den Zustands- und Übergangswahrscheinlichkeiten zu berechnen). Der Fehler, den man hier macht, ist, dass viele Berechnungen dupliziert werden. Als Beispiel könnten Sie zwei Sequenzen $ p_1, p_2 $ ($ p $ ist eine Folge von Zuständen) haben, wobei der einzige Unterschied der Endzustand ist, jedoch mit Bei diesem Ansatz berechnen Sie die Wahrscheinlichkeiten der gemeinsam genutzten Zustände sowohl für $ P (p_1) $ als auch für $ P (p_2) $.
Wenn Sie den in viterbi verwendeten iterativen Ansatz verwenden, gibt es keine doppelten Berechnungen viel effizienter.
Kommentare
- youtube.com/watch?v=6JVqutwtzmo Das obige Video erklärt grafisch, was Nimitz14 (wunderschön) erklärt hat.