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)