Baum-Welch-Algorithmus

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.

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Expectation-Maximization-Algorithmus — Der Expectation Maximization Algorithmus (kurz EM Algorithmus, selten auch Estimation Maximization Algorithmus) ist ein Algorithmus der mathematischen Statistik. Der EM Algorithmus wird vorrangig zur Ballungsanalyse verwendet (Siehe hierzu den… …   Deutsch Wikipedia

  • Viterbi-Algorithmus — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • EM-Algorithmus — Der Expectation Maximization Algorithmus (kurz EM Algorithmus, selten auch Estimation Maximization Algorithmus) ist ein Algorithmus der mathematischen Statistik. Inhaltsverzeichnis 1 Kernidee 2 Mathematische Formulierung 2.1 Funktionsweise …   Deutsch Wikipedia

  • Forward-Algorithmus — Der Forward Algorithmus (auch Vorwärts Algorithmus, Vorwärts Prozedur) berechnet mit Hilfe der Forward Variablen αt(i) für ein gegebenes Hidden Markov Modell λ die Wahrscheinlichkeit P einer Beobachtung O, d.h. P(O | λ). Er verwendet die… …   Deutsch Wikipedia

  • HMM — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden-Markov-Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden Markov Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden Markov model — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Verborgenes Markow-Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Verdecktes Markow-Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”