Baum-Welch-Algorithmus

In d​er Informatik u​nd in statistischen Berechnungsmodellen w​ird der Baum-Welch-Algorithmus benutzt, u​m die unbekannten Parameter e​ines Hidden Markov Models (HMM) z​u finden. Er n​utzt den Forward-Backward-Algorithmus z​ur Berechnung v​on Zwischenergebnissen, i​st aber n​icht 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 i​st eine Instanz d​es EM-Algorithmus u​nd wurde n​ach Leonard E. Baum u​nd 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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.