research-article

SPIRAL: efficient and exact model identification for hidden Markov models

Authors:

Yasuhiro Fujiwara,

Yasushi Sakurai,

Masashi YamamuroAuthors Info & Claims

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 247 - 255

https://doi.org/10.1145/1401890.1401924

Published: 24 August 2008 Publication History

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]

S. Eickeler, A. Kosmala, and G. Rigoll. Hidden markov model based continuous online gesture recognition. In ICPR, pages 1206--1208, 1998.

Digital Library

[7]

R. Esposito and D. P. Radicioni. Carpediem: an algorithm for the fast evaluation of ssl classifiers. In ICML, pages 257--264, 2007.

Digital Library

[8]

F. Jelinek. Statistical methods for speech recognition. The MIT Press, 1999.

Digital Library

[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]

J. Hu, M. K. Brown, and W. Turin. Hmm based on-line handwriting recognition. IEEE Trans. Pattern Anal. Mach. Intell., 18(10):1039--1045, 1996.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

S. M. Siddiqi and A. W. Moore. Fast inference and learning in large-state-space hmms. In ICML, pages 800--807, 2005.

Digital Library

[23]

S. P. Singh, T. Jaakkola, and M. I. Jordan. Reinforcement learning with soft state aggregation. In NIPS, pages 361--368, 1994.

[24]

T. Zhang, R. Ramakrishnan, and M. Livny. Birch: An efficient data clustering method for very large databases. In SIGMOD Conference, pages 103--114, 1996.

Digital Library

[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.

Cited By

Matsubara YSakurai YFaloutsos C(2017)Ecosystem on the WebWorld Wide Web10.1007/s11280-016-0389-x20:3(439-465)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s11280-016-0389-x
Sakurai YMatsubara YFaloutsos CBourdeau JHendler JNkambou RHorrocks IZhao B(2016)Mining Big Time-series Data on the WebProceedings of the 25th International Conference Companion on World Wide Web10.1145/2872518.2891061(1029-1032)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2872518.2891061
Sakurai YMatsubara YFaloutsos CSellis TDavidson SIves Z(2015)Mining and Forecasting of Big Time-series DataProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2731081(919-922)Online publication date: 27-May-2015
https://dl.acm.org/doi/10.1145/2723372.2731081
Show More Cited By

Index Terms

SPIRAL: efficient and exact model identification for hidden Markov models
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Fast likelihood search for hidden Markov models

Hidden Markov models (HMMs) are receiving considerable attention in various communities and many applications that use HMMs have emerged such as mental task classification, biological analysis, traffic monitoring, and anomaly detection. This article has ...
A Hidden Semi-Markov Model-Based Speech Synthesis System

A statistical speech synthesis system based on the hidden Markov model (HMM) was recently proposed. In this system, spectrum, excitation, and duration of speech are modeled simultaneously by context-dependent HMMs, and speech parameter vector sequences ...
Intrusion Detection Method Based on Fuzzy Hidden Markov Model
FSKD '09: Proceedings of the 2009 Sixth International Conference on Fuzzy Systems and Knowledge Discovery - Volume 03

Because of the excellent performance of the HMM (Hidden Markov Model), it has been widely used in pattern recognition. Due to the high false alarm rate in the classical intrusion detection system(IDS) based on HMM, a fuzzy approach for the HMM, called ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2008

1116 pages

ISBN:9781605581934

DOI:10.1145/1401890

General Chair:
Ying Li
Microsoft adCenter Labs
,
Program Chairs:
Bing Liu
University of Illinois at Chicago
,
Sunita Sarawagi
Indian Institute of Technology, Bombay

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD08

Sponsor:

KDD08: The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2008

Nevada, Las Vegas, USA

Acceptance Rates

KDD '08 Paper Acceptance Rate 118 of 593 submissions, 20%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Matsubara YSakurai YFaloutsos C(2017)Ecosystem on the WebWorld Wide Web10.1007/s11280-016-0389-x20:3(439-465)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s11280-016-0389-x
Sakurai YMatsubara YFaloutsos CBourdeau JHendler JNkambou RHorrocks IZhao B(2016)Mining Big Time-series Data on the WebProceedings of the 25th International Conference Companion on World Wide Web10.1145/2872518.2891061(1029-1032)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2872518.2891061
Sakurai YMatsubara YFaloutsos CSellis TDavidson SIves Z(2015)Mining and Forecasting of Big Time-series DataProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2731081(919-922)Online publication date: 27-May-2015
https://dl.acm.org/doi/10.1145/2723372.2731081
Matsubara YSakurai YFaloutsos CDyreson CLi FÖzsu M(2014)AutoPlaitProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2588556(193-204)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2588556
Matsubara YSakurai YUeda NYoshikawa M(2014)Fast and Exact Monitoring of Co-Evolving Data StreamsProceedings of the 2014 IEEE International Conference on Data Mining10.1109/ICDM.2014.62(390-399)Online publication date: 14-Dec-2014
https://dl.acm.org/doi/10.1109/ICDM.2014.62
Fujiwara YSakurai Y(2011)Fast Algorithm for Monitoring Data Streams by Using Hidden Markov ModelsNTT Technical Review10.53829/ntr201112ra29:12(53-60)Online publication date: Dec-2011
https://doi.org/10.53829/ntr201112ra2
Fujiwara YSakurai YKitsuregawa M(2009)Fast likelihood search for hidden Markov modelsACM Transactions on Knowledge Discovery from Data10.1145/1631162.16311663:4(1-37)Online publication date: 4-Dec-2009
https://dl.acm.org/doi/10.1145/1631162.1631166

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents