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.
| Published in |
Applied and Computational Mathematics (Volume 6, Issue 4-1)
This article belongs to the Special Issue Some Novel Algorithms for Global Optimization and Relevant Subjects |
| DOI | 10.11648/j.acm.s.2017060401.13 |
| Page(s) | 39-47 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2016. Published by Science Publishing Group |
Hidden Markov Model, Uncovering Problem, Longest-path Algorithm
| [1] | J. G. Schmolze, “An Introduction to Hidden Markov Models,” 2001. |
| [2] | E. Fosler-Lussier, “Markov Models and Hidden Markov Models: A Brief Tutorial,” 1998. |
| [3] | 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. |
| [4] | 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. |
| [5] | 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. |
| [6] | 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. |
| [7] | 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. |
| [8] | S. Chatterjee and S. Russell, “A temporally abstracted Viterbi algorithm,” arXiv.org, vol. 1202.3707, 14 February 2012. |
| [9] | 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. |
| [10] | 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. |
| [11] | 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. |
APA Style
Loc Nguyen. (2016). Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model. Applied and Computational Mathematics, 6(4-1), 39-47. https://doi.org/10.11648/j.acm.s.2017060401.13
ACS Style
Loc Nguyen. Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model. Appl. Comput. Math. 2016, 6(4-1), 39-47. doi: 10.11648/j.acm.s.2017060401.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.acm.s.2017060401.13,
author = {Loc Nguyen},
title = {Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model},
journal = {Applied and Computational Mathematics},
volume = {6},
number = {4-1},
pages = {39-47},
doi = {10.11648/j.acm.s.2017060401.13},
url = {https://doi.org/10.11648/j.acm.s.2017060401.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.s.2017060401.13},
abstract = {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.},
year = {2016}
}
TY - JOUR T1 - Longest-path Algorithm to Solve Uncovering Problem of Hidden Markov Model AU - Loc Nguyen Y1 - 2016/06/17 PY - 2016 N1 - https://doi.org/10.11648/j.acm.s.2017060401.13 DO - 10.11648/j.acm.s.2017060401.13 T2 - Applied and Computational Mathematics JF - Applied and Computational Mathematics JO - Applied and Computational Mathematics SP - 39 EP - 47 PB - Science Publishing Group SN - 2328-5613 UR - https://doi.org/10.11648/j.acm.s.2017060401.13 AB - 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. VL - 6 IS - 4-1 ER -
Email: