Efficient Algorithms for Training Hidden Markov Models
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)
Want to read the original?
Access the complete publication on the publisher's website