SPIRAL: efficient and exact model identification for hidden Markov models

ABSTRACT

Hidden Markov models (HMMs) have received considerable attention in various communities (e.g, speech recognition, neurology and bioinformatic) since many applications that use HMM have emerged. The goal of this work is to identify efficiently and correctly the model in a given dataset that yields the state sequence with the highest likelihood with respect to the query sequence. We propose SPIRAL, a fast search method for HMM datasets. To reduce the search cost, SPIRAL efficiently prunes a significant number of search candidates by applying successive approximations when estimating likelihood. We perform several experiments to verify the effectiveness of SPIRAL. The results show that SPIRAL is more than 500 times faster than the naive method.

REFERENCES

• 1: http://archive.ics.uci.edu/ml/.
• 2: http://www.ncbi.nlm.nih.gov.
• 3: P. Baldi, Y. Chauvin, T. Hunkapiller, and M. A. McClure. Hidden markov models of biological primary sequence information. Proceedings of the National Academy of Science, 91:1059--1063, Feb. 1994.
• 4: E. Bocchieri. Vector quantization for the efficient computation of continuous density likelihoods. In ICASSP, pages 692--695, 1993.
• 5: R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press, 1999.
• 6: Hidden Markov Model Based Continuous Online Gesture Recognition, Proceedings of the 14th International Conference on Pattern Recognition-Volume 2, p.1206, August 16-20, 1998 [doi>10.1109/ICPR.1998.711914]
• 7: Roberto Esposito , Daniele P. Radicioni, CarpeDiem: an algorithm for the fast evaluation of SSL classifiers, Proceedings of the 24th international conference on Machine learning, p.257-264, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273529]
• 8: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 9: D. F. G. Pfurtscheller and C. Neuper. Differentiation between finger, toe and tongue in man based on 40hz eeg. Electroencephalography and Clinical Neurophysiology, pages 456--460, 1994.
• 10: D. Haussler, A. Krogh, I. S. Mian, and K. Sjolander. Protein modeling using hidden Markov models: Analysis of globins. In HICSS 39, pages 792--802, 1993.
• 11: Jianying Hu , Michael K. Brown , William Turin, HMM Based On-Line Handwriting Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.10, p.1039-1045, October 1996 [doi>10.1109/34.541414]
• 12: J. Huang, Z. Liu, and Y. Wang. Joint scene classification and segmentation based on hidden markov model. IEEE Transactions on Multimedia, 7(3):538--550, 2005.
• 13: M. Hunt and C. Lefebvre. A comparison of several acoustic representations for speech recognition with degraded and undegraded speech. In ICASSP, pages 262--265, 1989.
• 14: J. Kwon and K. Murphy. Modeling freeway traffic with coupled hmms. Tech. Rep., University of California at Berkeley, 2000.
• 15: T. Lane. Hidden markov models for human/computer interface modeling. In IJCAI-99 Workshop on Learning About Users, pages 35--44, 1999.
• 16: S. E. Levinson, L. R. Rabiner, and M. M. Sondhi. An introduction to the application of the theory of probabilistic functions of a markov process to automatic speech recognition. Bell Syst. Tech. J, 62:1035--1074, 1982.
• 17: D. W. Mount. Bioinformatics: sequence and genome analysis. Cold Spring Harbor Laboratory Press, 2001.
• 18: H. Ney, D. Mergel, A. Noll, and A. Paesler. Data driven search organization for continuous speech recognition. IEEE Trans. Signal Processing., 40(2):272--281, 1992.
• 19: D. Novak, Y. H. T. Al-Ani, and L. Lhotska. Electroencephalogram processing using hidden markov models. In EUROSIM, 2004.
• 20: L. R. Rabiner and B. H. Juang. An introduction to hidden markov models. IEEE ASSP Magazine, 3:4--16, 1986.
• 21: S. Sagayama, K. Knill, and S. Takahashi. On the use of scalar quantization for fast hmm computation. In ICASSP, pages 213--216, 1995.
• 22: Sajid M. Siddiqi , Andrew W. Moore, Fast inference and learning in large-state-space HMMs, Proceedings of the 22nd international conference on Machine learning, p.800-807, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102452]
• 23: S. P. Singh, T. Jaakkola, and M. I. Jordan. Reinforcement learning with soft state aggregation. In NIPS, pages 361--368, 1994.
• 24: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada
• 25: S. Zhong and J. Ghosh. Hmms and coupled hmms for multi-channel eeg classification. In IEEE Int. Joint Conf. on Neural Networks, pages 1154--1159, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Theory

Keywords:
Hidden Markov model, likelihood, upper bound