Active learning for Hidden Markov Models: objective functions and algorithms

ABSTRACT

Hidden Markov Models (HMMs) model sequential data in many fields such as text/speech processing and biosignal analysis. Active learning algorithms learn faster and/or better by closing the data-gathering loop, i.e., they choose the examples most informative with respect to their learning objectives. We introduce a framework and objective functions for active learning in three fundamental HMM problems: model learning, state estimation, and path estimation. In addition, we describe a new set of algorithms for efficiently finding optimal greedy queries using these objective functions. The algorithms are fast, i.e., linear in the number of time steps to select the optimal query and we present empirical results showing that these algorithms can significantly reduce the need for labelled training data.

REFERENCES

• 1: Boyen, X., & Koller, D. (1998). Tractable inference for complex stochastic processes. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (pp. 33--42).
• 2: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 3: Cohn, D. A., Ghahramani, Z., & Jordan, M. I. (1995). Active learning with statistical models. Advances in Neural Information Processing Systems (pp. 705--712). The MIT Press.
• 4: Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (2000). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge Univ. Press, Durbin.
• 5: Yoav Freund , H. Sebastian Seung , Eli Shamir , Naftali Tishby, Selective Sampling Using the Query by Committee Algorithm, Machine Learning, v.28 n.2-3, p.133-168, Aug./Sept. 1997
• 6: Krause, A., & Guestrin, C. (2005). Optimal nonmyopic value of information in graphical models (Technical Report). Carnegie Mellon University.
• 7: Krishnamurthy, V. (2002). Algorithms for optimal scheduling and management of hidden markov model sensors. IEEE Transactions on Signal Processing, 50, 1382--1397.
• 8: Lewis, D. D., & Catlett, J. (1994). Heterogeneous uncertainty sampling for supervised learning. Proceedings of ICML-94, 11th International Conference on Machine Learning (pp. 148--156). New Brunswick, US: Morgan Kaufmann Publishers, San Francisco, US.
• 9: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 10: MacKay, D. (1997). Ensemble learning for hidden markov models (Technical Report). University of Cambridge.
• 11: Thomas P. Minka , Rosalind Picard, A family of algorithms for approximate bayesian inference, 2001
• 12: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 13: Rezek, I., & Roberts, S. J. (2002). Ensemble hidden markov models for biosignal analysis.
• 14: Nicholas Roy , Andrew McCallum, Toward Optimal Active Learning through Sampling Estimation of Error Reduction, Proceedings of the Eighteenth International Conference on Machine Learning, p.441-448, June 28-July 01, 2001
• 15: Tobias Scheffer , Christian Decomain , Stefan Wrobel, Active Hidden Markov Models for Information Extraction, Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis, p.309-318, September 13-15, 2001
• 16: H. S. Seung , M. Opper , H. Sompolinsky, Query by committee, Proceedings of the fifth annual workshop on Computational learning theory, p.287-294, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130417]
• 17: Steck, H., & Jaakkola, T. (2002). Unsupervised active learning in large domains. Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (UAI-02) (pp. 469--476). San Francisco, CA: Morgan Kaufmann Publishers.
• 18: Tong, S., & Koller, D. (2000). Active learning for parameter estimation in bayesian networks. NIPS (pp. 647--653).
• 19: Tong, S., & Koller, D. (2001). Active learning for structure in bayesian networks. IJCAI (pp. 863--869).
• 20: Tur, G., Schapire, R., & Hakkani-Tur, D. (2003). Active learning for spoken language understanding.