Baum-Welch-Algorithmus
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
- Lawrence R. Rabiner, Biing-Hwang Juang: An Introduction to Hidden Markov Models. In: IEEE. ASSP Magazine. Bd. 3, Nr. 1, Januar 1986, ISSN 0740-7467, S. 4–16, doi:10.1109/MASSP.1986.1165342.
- Christopher D. Manning, Hinrich Schütze: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge MA u. a. 1999, ISBN 0-262-13360-1.
- 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, online (PDF; 189 kB).