Baum-Welch-Algorithmus

aus Wikipedia, der freien Enzyklopädie

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 ist auch unter dem Namen Forward-Backward Algorithmus bekannt.

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 des gesamten Strings. Dieser Wert kann dann zum neuen Wert des Übergangs gemacht werden.

Ein häufiges numerisches Problem ist, dass das Produkt vieler kleiner Wahrscheinlichkeiten durch numerischen Unterlauf 0 wird. Dies lässt sich vermeiden, indem man statt Wahrscheinlichkeiten zu multiplizieren, deren Logarithmen addiert. Um Wahrscheinlichkeiten ohne numerischen Unterlauf zu addieren, nutzt man die Gleichung

$\operatorname{ln}\left(e^a + e^b\right) = \operatorname{max}(a,b) + \operatorname{ln}\left(1+e^{-|a-b|}\right)$ .

Der Baum-Welch-Algorithmus ist eine Instanz des EM-Algorithmus.

[Bearbeiten] Literatur

Lawrence R. Rabiner und Biing-Hwang Juang: An Introduction to Hidden Markov Models. IEEE ASSP Magazine, January 1986
Christopher D. Manning und Hinrich Schütze: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge MA, 1999
Jeff A. Bilmes: A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. International Computer Science Institute, Berkeley CA, 1998