Ich benutze derzeit Viterbi-Training für ein Bildsegmentierungsproblem. Ich wollte wissen, welche Vor- und Nachteile die Verwendung des Baum-Welch-Algorithmus anstelle des Viterbi-Trainings hat.
machine-learning
hidden-markov-model
image-processing
viterbi-algorithm
baum-welch
Digital Gal
quelle
quelle
Antworten:
Der Baum-Welch-Algorithmus und der Viterbi-Algorithmus berechnen verschiedene Dinge.
Wenn Sie die Übergangswahrscheinlichkeiten für den verborgenen Teil Ihres Modells und die Emissionswahrscheinlichkeiten für die sichtbaren Ausgaben Ihres Modells kennen, erhalten Sie mit dem Viterbi-Algorithmus die wahrscheinlich vollständige Folge von verborgenen Zuständen, die sowohl von Ihren Ausgaben als auch von Ihrer Modellspezifikation abhängig sind.
Der Baum-Welch-Algorithmus gibt Ihnen sowohl die wahrscheinlichsten versteckten Übergangswahrscheinlichkeiten als auch die wahrscheinlichste Menge von Emissionswahrscheinlichkeiten an, wenn nur die beobachteten Zustände des Modells (und normalerweise eine Obergrenze für die Anzahl der versteckten Zustände) angegeben werden. Sie erhalten auch die "punktweisen" Höchstwahrscheinlichkeitspunkte in den versteckten Zuständen, die sich häufig geringfügig von der einzelnen versteckten Sequenz unterscheiden, die insgesamt am wahrscheinlichsten ist.
Wenn Sie Ihr Modell kennen und nur die latenten Zustände möchten, gibt es keinen Grund, den Baum-Welch-Algorithmus zu verwenden. Wenn Sie Ihr Modell nicht kennen, können Sie den Viterbi-Algorithmus nicht verwenden.
Bearbeitet, um hinzuzufügen: Siehe Peter Smits Kommentar; Die Nomenklatur weist einige Überschneidungen / Unklarheiten auf. Ein wenig herumstöbern führte mich zu einem Kapitel von Luis Javier Rodrıguez und Ines Torres in "Mustererkennung und Bildanalyse" (ISBN 978-3-540-40217-6, S. 845-857), in dem die Kompromisse zwischen Geschwindigkeit und Genauigkeit besprochen wurden die beiden Algorithmen.
Kurz gesagt, der Baum-Welch-Algorithmus ist im Wesentlichen der Expectation-Maximization (EM) -Algorithmus, der auf ein HMM angewendet wird. Als strenger EM-Algorithmus konvergieren Sie garantiert zu mindestens einem lokalen Maximum, und für unimodale Probleme finden Sie den MLE. Es sind jedoch zwei Durchläufe Ihrer Daten für jeden Schritt erforderlich, und die Komplexität wird in Bezug auf die Länge der Daten und die Anzahl der Trainingsmuster sehr groß. Sie haben jedoch die volle bedingte Wahrscheinlichkeit für Ihre verborgenen Parameter.
Der Viterbi-Trainingsalgorithmus (im Gegensatz zum "Viterbi-Algorithmus") approximiert den MLE, um auf Kosten der Genauigkeit einen Geschwindigkeitsgewinn zu erzielen. Es segmentiert die Daten und wendet dann den Viterbi-Algorithmus (wie ich ihn verstanden habe) an, um die wahrscheinlichste Zustandssequenz in dem Segment zu erhalten, und verwendet dann diese wahrscheinlichste Zustandssequenz, um die verborgenen Parameter neu zu schätzen. Dies gibt im Gegensatz zum Baum-Welch-Algorithmus nicht die volle bedingte Wahrscheinlichkeit für die verborgenen Parameter an und führt zu einer Verringerung der Genauigkeit, während erhebliche Rechenzeit eingespart wird (das Kapitel gibt 1 bis 2 Größenordnungen an).
quelle
Vorwärts-Rückwärts wird verwendet, wenn Sie "unsichtbare Dinge" zählen möchten. Zum Beispiel, wenn Sie EM verwenden, um ein Modell über nicht überwachte Daten zu verbessern. Ich denke, dass Petrovs Papier ein Beispiel ist. In der Technik, an die ich denke, trainieren Sie zuerst ein Modell mit annotierten Daten mit ziemlich groben Annotationen (z. B. ein Tag für 'Verb'). Dann teilen Sie die Wahrscheinlichkeitsmasse für diesen Zustand willkürlich in zwei leicht ungleiche Größen auf und trainieren erneut, indem Sie vorwärts und rückwärts laufen, um die Wahrscheinlichkeit zu maximieren, indem Sie die Masse zwischen den beiden Zuständen neu verteilen.
quelle