Some Algorithms for Large Hidden Markov Models

Sanaa Chafik^1, and Daoui Cherki¹

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

Cite this paper:
Sanaa Chafik and Daoui Cherki. Some Algorithms for Large Hidden Markov Models. World Journal Control Science and Engineering. 2013; 1(1):9-14. doi: 10.12691/wjcse-1-1-2

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

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Figures

References:

[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.
[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.
[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.
[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.
[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.
[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.
[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.
[18]	Drmota M., Szpankowski W., "A Master Theorem for Discrete Divide and Conquer Recurrences," Austrian Science Foundation FWF Grant No. S9604. 2011.