Abstract
Hidden Markov Models (HMM) have proven to be useful in a variety of real world applications where considerations for uncertainty are crucial. Such an advantage can be more leveraged if HMM can be scaled up to deal with complex problems. In this paper, we introduce, analyze and demonstrate Self-Similar Layered HMM (SSLHMM), for a certain group of complex problems which show self-similar property, and exploit this property to reduce the complexity of model construction. We show how the embedded knowledge of selfsimilar structure can be used to reduce the complexity of learning and increase the accuracy of the learned model. Moreover, we introduce three different types of self-similarity in SSLHMM, and investigate their performance in the context of synthetic data and real-world network databases. We show that SSLHMM has several advantages comparing to conventional HMM techniques and it is more efficient and accurate than one-step, flat method for model construction.
Chapter PDF
Similar content being viewed by others
Keywords
- Hide Markov Model
- State Transition Matrix
- Partial Observable Markov Decision Process
- Hide Markov Model Model
- Packet Rate
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adibi, J., Shen, W-M. General structure of mining through layered phases. submitted to International Conference on Data Engineering. (2002). San Jose, California, USA: IEEE.
Barbara, D. Chaotic Mining: Knowledge discovery using the fractal dimension. in ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD). (1999). Philadelphia, USA,.
Bertsekas, D.C., Tsitsiklis, N. J., Parallel and distributed computation: Numerical Methods. (1989), Englewood Clifffs, New Jersey: Printice-Hall.
Boutilier, R.I., Brafman, I., Geib, C. Prioritized goal decomposition of Markov Decision Processes: Toward a synthesis of classical and decision theoretic planning. in IJCAI-97. (1997). Nagoya, Japan.
Brand, N., Oliver, N., and Pentland, A.,. Coupled Hidden Markov Models for complex action recognition. in CVPR. (1997).
Chang, J.W., Glass, J, Segmentation and modeling in segment-based recognition. (1997).
Cohen, J., Segmentation speech using dynamic programming. ASA, (1981). 69(5): p. 1430–1438.
Dean, T.L., S. H. Decomposition techniques for planning in stochastic domains. in IJCAI. (1995). Montreal, CA.
Faloutsos, C., Seeger, B., Traina, A. and Traina Jr., C. Spatial Join selectivity using power law. in SIGMOD. (2000). Dallas, TX.
Feldmann, A., Gilbert, A. C., Willinger, W., Kurtz, T.G., The changing nature of Network traffic: Scaling phenomena. ACM Computer Communication Review, (1998). 28(April): p. 5–29.
Fine, S., Singer Y, Tishby N, The hierarchical Hidden Markov Model: Analysis and applications. Machine Learning, (1998). 32(1): p. 41–62.
Ghahramani, Z., Jordan, M., Factorial Hidden Markov Models. Machine Learning, (1997). 2: p. 1–31.
Holmes, W.J., Russell, M. L., Probablistic-trajectory segmental HMMs. Computer Speech and Languages, (1999). 13: p. 3–37.
Leland, W., Taqqu, M., Willinger, W., Wilson, D. On the self-similar nature of Ethernet traffic. in ACM SIGComm. (1993). San Francisco, CA.
Oates, T. Identifying distinctive subsequences in multivariate time series by clustering. in KDD-99. (1999). San Diego, CA: ACM.
Pearl, J., Probabilistic reasoning in intelligence: Network of plausible inference. (1988), San Mateo, CA: Morgan Kaufmann.
Precup, D., Sutton, R. S., Multi-time models for temporally abstract planning, in NIPS-11, M. Moser, Jordan, M. Petsche, T., Editor. 1998, MIT Press: Cambridge.
Puterman, M.L., Markov Decision Process: discrete stochastic dynamic programming. (1994), New Yourk: Wiley.
Rabiner, L.R., A tutorial on Hidden Markov Models and selected applications in speech recognition. IEEE, (1989). 7(2): p. 257–286.
Sutton, R., Barto, A., Reinforcement learning: An Introduction. (1998), Cambridge: MIT Press.
Traina, C., Traina, A., Wu, L., and Faloutsos, C. Fast feature selection using the fractal dimension. in XV Brazilian Symposium on Databases (SBBD). (2000). Paraiba, Brazil.
Vogler, C., Metaxas, D. Parallel Hidden Markov Models for American Sign Language recognition. in International Conference on Computer Vision. (1999). Kerkyra, Greece.
Williams, C., Hinton, G.E., ed. Mean field networks that leat discriminate temporally distorted strings., ed. D. Touretzkey, Elman, J., Sejnowski, T. and Hinton G. (1991).
Willinger, W., Taqqu M. S., Erramilli, A., ed. A bibliographical guide to self-similar trace and performance modeling for modern high-speed networks. Stochastic Networks: Theory and Applications, ed. F.P. Kelly, Zachary, S. and Ziedins, I. (1996), Clarendon Press, Oxford University Press: Oxford. 339–366.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Adibi, J., Shen, WM. (2001). Self-Similar Layered Hidden Markov Models. In: De Raedt, L., Siebes, A. (eds) Principles of Data Mining and Knowledge Discovery. PKDD 2001. Lecture Notes in Computer Science(), vol 2168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44794-6_1
Download citation
DOI: https://doi.org/10.1007/3-540-44794-6_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42534-2
Online ISBN: 978-3-540-44794-8
eBook Packages: Springer Book Archive