Efficient algorithms for training the parameters of hidden Markov models using stochastic expectation maximization (EM) training and Viterbi training
2010

Efficient Algorithms for Training Hidden Markov Models

publication Evidence: moderate

Author Information

Author(s): Lam Tin Y, Meyer Irmtraud M

Primary Institution: University of British Columbia

Hypothesis

Can we develop more efficient algorithms for training hidden Markov models that reduce memory requirements?

Conclusion

The new algorithms for Viterbi training and stochastic EM training significantly improve computational efficiency by reducing memory requirements.

Supporting Evidence

  • The new algorithms reduce memory requirements from O(ML) to O(M) for Viterbi training.
  • For stochastic EM training, memory requirements are reduced from O(ML) to O(MK + Tmax).
  • The algorithms are easier to implement than traditional methods.

Takeaway

This study introduces new ways to train models that help computers understand biological data better, making it faster and easier to do so.

Methodology

The study presents two new algorithms for Viterbi training and stochastic EM training that require only one step and scan the input sequence in one direction.

Limitations

The algorithms were tested on a limited number of example models and may not generalize to all hidden Markov models.

Digital Object Identifier (DOI)

10.1186/1748-7188-5-38

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication