Baum-Welch-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik und in statistischen Berechnungsmodellen wird der Baum-Welch-Algorithmus benutzt, um die unbekannten Parameter eines Hidden Markov Models (HMM) zu finden. Er nutzt den Forward-Backward-Algorithmus zur Berechnung von Zwischenergebnissen, ist aber nicht mit diesem identisch.

Der Baum-Welch-Algorithmus ist ein erwartungsmaximierender Algorithmus. Er berechnet die Maximalwahrscheinlichkeitsschätzungen (Maximum-Likelihood-Schätzwerte) und die sogenannten Posterior-Mode-Schätzungen für die gegebenen Parameter (Übergangs- und Emissionswahrscheinlichkeit) eines HMMs, wenn nur die Emissionen als Trainingsdaten gegeben sind.

Der Algorithmus arbeitet in zwei Schritten: Erstens berechnet er die Vorwärtswahrscheinlichkeit (forward probability) und die Rückwärtswahrscheinlichkeit (backward probability) für jeden Zustand des HMMs. Zweitens, auf der Basis dieses ersten Schrittes, berechnet er die Frequenz der Übergangs-Emissions-Paar-Werte und dividiert diese durch die Wahrscheinlichkeit des gesamten Strings (sog. posterior decoding). Dies führt zu der Berechnung der erwarteten Zählung des einzelnen Übergangs-Emissions-Paares. Jedes Mal, wenn ein einzelner Übergang gefunden wird, erhöht sich der Wert des Quotienten des Übergangs und der Wahrscheinlichkeit der gesamten Zeichenkette. Dieser Wert kann dann zum neuen Wert des Übergangs gemacht werden.

Der Baum-Welch-Algorithmus ist eine Instanz des EM-Algorithmus und wurde nach Leonard E. Baum und Lloyd R. Welch benannt.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]