Modeling interleaved hidden processes

ABSTRACT

Hidden Markov models assume that observations in time series data stem from some hidden process that can be compactly represented as a Markov chain. We generalize this model by assuming that the observed data stems from multiple hidden processes, whose outputs interleave to form the sequence of observations. Exact inference in this model is NP-hard. However, a tractable and effective inference algorithm is obtained by extending structured approximate inference methods used in factorial hidden Markov models. The proposed model is evaluated in an activity recognition domain, where multiple activities interleave and together generate a stream of sensor observations. It is shown to be more accurate than a standard hidden Markov model in this domain.

REFERENCES

• 1: Altman, R. M. (2007). Mixed hidden Markov models: An extension of the hidden Markov model to the longitudinal data setting. Journal of the American Statistical Association, 102, 201--210.
• 2: Gükhan H. Bakir , Thomas Hofmann , Bernhard Schölkopf , Alexander J. Smola , Ben Taskar , S. V. N. Vishwanathan, Predicting Structured Data (Neural Information Processing), The MIT Press, 2007
• 3: Batu, T., Guha, S., & Kannan, S. (2004). Inferring Mixtures of Markov Chains. Proceedings of the 17th Annual Conference on Learning Theory.
• 4: Brand, M. (1997). Coupled hidden Markov models for modeling interactive processes (Technical Report 405). MIT Media Lab.
• 5: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079]
• 6: Garey, M. R., & Johnson, D. S. (1975). Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM Jour. Comp., 4, 397--411.
• 7: Ghahramani, Z., & Hinton, G. E. (1998). Switching State-Space Models (Technical Report). Department of Computer Science, University of Toronto.
• 8: Zoubin Ghahramani , Michael I. Jordan, Factorial Hidden Markov Models, Machine Learning, v.29 n.2-3, p.245-273, Nov./Dec. 1997 [doi>10.1023/A:1007425814087]
• 9: Girolami, M., & Kabáán, A. (2003). Simplicial Mixtures of Markov Chains: Distributed Modelling of Dynamic User Profiles. Proc. of the 17th Ann. Conference on Neural Information Processing Systems.
• 10: Jordan, M. I., Ghahramani, Z., & Saul, L. K. (1996). Hidden Markov Decision Trees. Proceedings of the 9th Conference on Advances in Neural Information Processing Systems.
• 11: Landwehr, N., Gutmann, B., Thon, I., Philipose, M., & De Raedt, L. (2007). Relational Transformation-based Tagging for Human Activity Recognition. Proc. of the Intern. Workshop on Knowledge Discovery from Ubiquitous Data Streams.
• 12: Donald J. Patterson , Dieter Fox , Henry Kautz , Matthai Philipose, Fine-Grained Activity Recognition by Aggregating Abstract Object Usage, Proceedings of the Ninth IEEE International Symposium on Wearable Computers, p.44-51, October 18-21, 2005 [doi>10.1109/ISWC.2005.22]
• 13: Rabiner, L. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77, 257--286.
• 14: Lawrence K. Saul , Michael I. Jordan, Mixed Memory Markov Models: Decomposing Complex Stochastic Processes as Mixtures of Simpler Ones, Machine Learning, v.37 n.1, p.75-87, Oct. 1999 [doi>10.1023/A:1007649326333]
• 15: Wang, S., Pentney, W., Popescu, A.-M., Choudhury, T., & Philipose, M. (2007). Common Sense Based Joint Training of Human Activity Recognizers. Proceedings of the 20th International Joint Conference on Artificial Intelligence.
• 16: Zhang, W., Chen, F., Xu, W., & Cao, Z. (2007). Decomposition in hidden Markov models for activity recognition. Multimedia Content Anal. and Mining.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory