Open Access Peer-reviewed

Some Algorithms for Large Hidden Markov Models

Sanaa Chafik1,, Daoui Cherki1

1University Sultan Moulay Slimane, Laboratory of modelisation and calcul, Béni Mellal

World Journal Control Science and Engineering. 2013, 1(1), 9-14. DOI: 10.12691/wjcse-1-1-2
Published online: August 25, 2017

Abstract

The Hidden Markov Model (HMM) has become increasingly popular in the last several years because it is used in a wide range of applications. There are some inherent limitations of this type of statistical model. The major limitation of HMM is large hidden state space, which limits their practical purview. The objective of this work is to reduce the task of solving some classical algorithms (Forward, Backward, Baum-Welch) by review of their theoretical aspects, offering faster improved algorithms based on the decomposition technique which represent a general approach to solving a problem by breaking it up into smaller ones and solving each of the smaller ones separately.

Keywords:

Hidden Markov Model, Forward, Backward, Baum Welch, large hidden state space, divide and conquer, decomposition, communicating class, graph theory
[1]  Pellegrini T., Duée R., "Suivi de Voix Parlée grace aux Modèles de Markov Cachés," IRCAM, PARIS, 2003.
 
[2]  Juang B. H.; Rabiner L. R., "Hidden Markov Models for Speech Recognition," Technometrics, Vol. 33, No. 3. pp. 251-272. Aug 1991.View Article
 
[3]  Ben Amara N., Belaïd A., Ellouze N., "Utilisation des modèles markoviens en reconnaissance de l'écriture arabe état de l'art," Colloque International Francophone sur l'Ecrit et le Document (CIFED'00), Lyon, France, 2000.
 
[4]  Nakai M., Akira N., Shimodaira H., Sagayama S., "Substroke Approach to HMM-based On-line Kanji Handwriting Recognition," Sixth International Conference on Document Analysis and Recognition (ICDAR 2001). pp.491-495. 2001.View Article
 
[5]  Ramy Al-Hajj M., Mokbel C., Likforman-Sulem L., "Reconnaissance de l’écriture arabe cursive: combinaison de classifieurs MMCs à fenêtres orientées," Université de Balamand, Faculté de Génie, pp 1-6. 2006.
 
[6]  Krogh A. ,Mian I. S., Haussler D., "A Hidden Markov model that finds genes in E.coli DNA," Nucleic Acids Research, Vol. 22, No. 22. 1994.View Article  PubMed
 
[7]  Morwal S., Jahan N., Chopra D., "Named Entity Recognition using Hidden Markov Model (HMM)," International Journal on Natural Language Computing (IJNLC) Vol. 1, No.4. 2012.View Article
 
[8]  RABINER R., "A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition," Proceding of the IEEE, Vol. 77, No. 2. 2010.
 
[9]  Daoui C., "Decomposition des problèmes de decision markoviens," Thesis of doctorat in Faculty of science Rabat , pp 64-69. 2002.
 
[10]  Jaafer S. A. , Mohamed I. O., Elhafiz M. M., "Text-Independent Speaker Identification Using Hidden Markov Model," World of Computer Science and Information Technology Journal (WCSIT), ISSN: 2221-0741, Vol. 2, No. 6, 203-208. 2012.
 
[11]  Baldi P., Chauvin Y., "Smooth On-Line Learning Algorithms for Hidden Markov Models," Neural Computation 6, 307-318. 1994.View Article
 
[12]  Khreich W., Granger E, Miri A., Sabourin R., "On the memory complexity of the forward–backward algorithm," Pattern Recognition Letters 31. 2010.
 
[13]  Rust J., "Using Randomization to Break the Curse of Dimensionality,” Econometrica, Vol. 65, No. 3, pp. 487-516. May 1997.View Article
 
[14]  Canet L., "Algorithmique, graphes et programmation dynamique," pp 23-25. 2003.
 
[15]  Van Caneghem M., "Algorithmes recursifs Diviser pour régner,". Janvier, 2003.
 
[16]  Gondran M., Minoux M., "Graphes et Algorithmes," Paris 2nd edition. 546 p. 1990.
 
[17]  ROURA S., "Improved Master Theorems for Divide-and-Conquer Recurrences," Journal of the ACM, Vol. 48, No. 2, pp. 170-205. March 2001.View Article
 
[18]  Drmota M., Szpankowski W., "A Master Theorem for Discrete Divide and Conquer Recurrences," Austrian Science Foundation FWF Grant No. S9604. 2011.