Baum-Welch algorithm

Baum-Welch algorithm

In computer science, statistical computing and bioinformatics, the Baum-Welch algorithm is used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the forward-backward algorithm and is named for Leonard E. Baum and Lloyd R. Welch.

Explanation

The Baum-Welch algorithm is a generalized expectation-maximization (GEM) algorithm. It can compute maximum likelihood estimates and posterior mode estimates for the parameters (transition and emission probabilities) of an HMM, when given only emissions as training data.

The algorithm has two steps:
# Calculating the forward probability and the backward probability for each HMM state;
# On the basis of this, determining the frequency of the transition-emission pair values and dividing it by the probability of the entire string. This amounts to calculating the expected count of the particular transition-emission pair. Each time a particular transition is found, the value of the quotient of the transition divided by the probability of the entire string goes up, and this value can then be made the new value of the transition.

References

The algorithm was introduced in the paper:
*L. E. Baum, T. Petrie, G. Soules, and N. Weiss, [http://links.jstor.org/sici?sici=0003-4851%28197002%2941%3A1%3C164%3AAMTOIT%3E2.0.CO%3B2-V "A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains"] , Ann. Math. Statist., vol. 41, no. 1, pp. 164--171, 1970.The Shannon Lecture by Welch:
* [http://www.itsoc.org/publications/nltr/it_dec_03final.pdf Hidden Markov Models and the Baum-Welch Algorithm] , IEEE Information Theory Society Newsletter, Dec. 2003.The path-counting algorithm, an alternative to the Baum-Welch algorithm:
* [http://citeseer.ist.psu.edu/677948.html Comparing and Evaluating HMM Ensemble Training Algorithms Using Train and Test and Condition Number Criteria] , Journal of Pattern Analysis and Applications, 2003.

ee also

* Forward-backward algorithm
* Viterbi algorithm

External links

* [http://www.cs.jhu.edu/~jason/papers/#tnlp02 An Interactive Spreadsheet for Teaching the Forward-Backward Algorithm] (spreadsheet and article with step-by-step walkthrough)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Baum Welch algorithm — …   Википедия

  • 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… …   Deutsch Wikipedia

  • Baum — is a German surname meaning tree and may refer to:* Antoine Baum (Antoine Baumé), (1728 1804), French chemist * Bernie Baum, American song writer * Eric Baum, American computer scientist and artificial intelligence researcher * Edgar Schofield… …   Wikipedia

  • Expectation-maximization algorithm — An expectation maximization (EM) algorithm is used in statistics for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an… …   Wikipedia

  • Viterbi algorithm — The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states ndash; called the Viterbi path ndash; that results in a sequence of observed events, especially in the context of Markov information… …   Wikipedia

  • Forward-backward algorithm — In computer science, the forward backward algorithm, a dynamic programming algorithm for computing the probability of a particular observation sequence, given the parameters of the model, operates in the context of hidden Markov models. Overview… …   Wikipedia

  • Eric Baum — Eric B. Baum is an American computer scientist, artificial intelligence researcher and author. He is known for his materialist and evolutionist theories of intelligence and consciousness, set forth in his 2004 book What is Thought? (ISBN… …   Wikipedia

  • Lloyd R. Welch — Lloyd Richard Welch is a noted American information theorist, and co inventor of the Baum Welch algorithm.Welch received his B.S. in mathematics from the University of Illinois, 1951, and Ph.D. in mathematics from the California Institute of… …   Wikipedia

  • Hidden Markov model — Probabilistic parameters of a hidden Markov model (example) x mdash; states y mdash; possible observations a mdash; state transition probabilities b mdash; output probabilitiesA hidden Markov model (HMM) is a statistical model in which the system …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

Share the article and excerpts

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