A linear memory algorithm for Baum-Welch training

Details A linear memory algorithm for Baum-Welch training A linear memory algorithm for Baum-Welch training

2005-05-11

arxiv.org/abs/cs/0505028v3

BMC Bioinformatics (2005) 6:231

Computer Science

Learning

14 pages, 1 figure version 2: fixed some errors, final version of paper

Scientific paper

Background: Baum-Welch training is an expectation-maximisation algorithm for training the emission and transition probabilities of hidden Markov models in a fully automated way. Methods and results: We introduce a linear space algorithm for Baum-Welch training. For a hidden Markov model with M states, T free transition and E free emission parameters, and an input sequence of length L, our new algorithm requires O(M) memory and O(L M T_max (T + E)) time for one Baum-Welch iteration, where T_max is the maximum number of states that any state is connected to. The most memory efficient algorithm until now was the checkpointing algorithm with O(log(L) M) memory and O(log(L) L M T_max) time requirement. Our novel algorithm thus renders the memory requirement completely independent of the length of the training sequences. More generally, for an n-hidden Markov model and n input sequences of length L, the memory requirement of O(log(L) L^(n-1) M) is reduced to O(L^(n-1) M) memory while the running time is changed from O(log(L) L^n M T_max + L^n (T + E)) to O(L^n M T_max (T + E)). Conclusions: For the large class of hidden Markov models used for example in gene prediction, whose number of states does not scale with the length of the input sequence, our novel algorithm can thus be both faster and more memory-efficient than any of the existing algorithms.

Affiliated with

Also associated with

No associations

Rating

A linear memory algorithm for Baum-Welch training does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A linear memory algorithm for Baum-Welch training, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A linear memory algorithm for Baum-Welch training will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-73290