Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model
Applied and Computational Mathematics
Volume 6, Issue 4-1, July 2017, Pages: 39-47
Received: Mar. 12, 2016; Accepted: Mar. 14, 2016; Published: Jun. 17, 2016
Views 4224      Downloads 138
Loc Nguyen, Sunflower Soft Company, Ho Chi Minh City, Vietnam
Article Tools
Follow on us
Uncovering problem is one of three main problems of hidden Markov model (HMM), which aims to find out optimal state sequence that is most likely to produce a given observation sequence. Although Viterbi is the best algorithm to solve uncovering problem, I introduce a new viewpoint of how to solve HMM uncovering problem. The proposed algorithm is called longest-path algorithm in which the uncovering problem is modeled as a graph. So the essence of longest-path algorithm is to find out the longest path inside the graph. The optimal state sequence which is solution of uncovering problem is constructed from such path.
Hidden Markov Model, Uncovering Problem, Longest-path Algorithm
To cite this article
Loc Nguyen, Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model, Applied and Computational Mathematics. Special Issue: Some Novel Algorithms for Global Optimization and Relevant Subjects. Vol. 6, No. 4-1, 2017, pp. 39-47. doi: 10.11648/j.acm.s.2017060401.13
Copyright © 2016 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
J. G. Schmolze, “An Introduction to Hidden Markov Models,” 2001.
E. Fosler-Lussier, “Markov Models and Hidden Markov Models: A Brief Tutorial,” 1998.
L. R. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257-286, 1989.
X. Luo, S. Li, B. Liu and F. Liu, “Improvement of the viterbi algorithm applied in the attacks on stream ciphers,” in The 7th International Conference on Advanced Communication Technology, 2005, ICACT 2005, Dublin, 2005.
N. P. Bidargaddi, M. Chetty and J. Kamruzzaman, “A Fuzzy Viterbi Algorithm for Improved Sequence Alignment and Searching of Proteins,” in Applications of Evolutionary Computing, F. Rothlauf, J. Branke, S. Cagnoni, D. W. Corne, R. Drechsler, Y. Jin, P. Machado, E. Marchiori, J. Romero, G. D. Smith and G. Squillero, Eds., Lausanne, Springer Berlin Heidelberg, 2005, pp. 11-21.
R. A. Soltan and M. Ahmadian, “Extended Viterbi Algorithm for Hidden Markov Process: A Transient/Steady Probabilities Approach,” International Mathematical Forum, vol. 7, no. 58, pp. 2871-2883, 2012.
L. La, Q. Guo, D. Yang and Q. Cao, “Improved Viterbi Algorithm-Based HMM2 for Chinese Words Segmentation,” in The 2012 International Conference on Computer Science and Electronics Engineering, Hangzhou, 2012.
S. Chatterjee and S. Russell, “A temporally abstracted Viterbi algorithm,” arXiv.org, vol. 1202.3707, 14 February 2012.
D. Golod and D. G. Brown, “A tutorial of techniques for improving standard Hidden Markov Model algorithms,” Journal of Bioinformatics and Computational Biology, vol. 7, no. 04, pp. 737-754, August 2009.
K. S. Arunlal and S. A. Hariprasad, “An Efficient Viterbi Decoder,” International Journal of Computer Science, Engineering and Applications (IJCSEA), vol. 2, no. 1, pp. 95-110, February 2012.
P. Fariselli and P. L. Martelli, “A new decoding algorithm for hidden Markov models improves the prediction of the topology of all-beta membrane proteins,” BMC Bioinformatics, vol. 6(Suppl 4), no. S12, 1 December 2005.
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
Tel: (001)347-983-5186