Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data

ABSTRACT

In sequence modeling, we often wish to represent complex interaction between labels, such as when performing multiple, cascaded labeling tasks on the same sequence, or when long-range dependencies exist. We present dynamic conditional random fields (DCRFs), a generalization of linear-chain conditional random fields (CRFs) in which each time slice contains a set of state variables and edges---a distributed state representation as in dynamic Bayesian networks (DBNs)---and parameters are tied across slices. Since exact inference can be intractable in such models, we perform approximate inference using several schedules for belief propagation, including tree-based reparameterization (TRP). On a natural-language chunking task, we show that a DCRF performs better than a series of linear-chain CRFs, achieving comparable performance using only half the training data.

REFERENCES

• 1: Aji, S., Horn, G., & McEliece, R. (1998). The convergence of iterative decoding on graphs with a single cycle. Proc. IEEE Int'l Symposium on Information Theory.
• 2: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 3: Eric Brill, Some advances in transformation-based part of speech tagging, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.722-727, October 1994, Seattle, Washington, United States
• 4: Bui, H. H., Venkatesh, S., & West, G. (2002). Policy recognition in the Abstract Hidden Markov Model. Journal of Artificial Intelligence Research, 17.
• 5: Thomas Dean , Keiji Kanazawa, A model for reasoning about persistence and causation, Computational Intelligence, v.5 n.3, p.142-150, Aug. 1990 [doi>10.1111/j.1467-8640.1989.tb00324.x]
• 6: 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]
• 7: Frietag, D., & McCallum, A. (1999). Information extraction with HMMs and shrinkage. AAAI Workshop on Machine Learning for Information Extraction.
• 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: Taku Kudo , Yuji Matsumoto, Chunking with support vector machines, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania [doi>10.3115/1073336.1073361]
• 10: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 11: Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002 [doi>10.3115/1118853.1118871]
• 12: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 13: Mitchell P. Marcus , Mary Ann Marcinkiewicz , Beatrice Santorini, Building a large annotated corpus of English: the penn treebank, Computational Linguistics, v.19 n.2, June 1993
• 14: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 15: Thomas P. Minka , Rosalind Picard, A family of algorithms for approximate bayesian inference, 2001
• 16: Mohri, M., Pereira, F., & Riley, M. (2002). Weighted finite-state transducers in speech recognition. Computer Speech and Language, 16, 69--88.
• 17: Murphy, K., & Paskin, M. A. (2001). Linear time inference in hierarchical HMMs. Proceedings of Fifteenth Annual Conference on Neural Information Processing Systems.
• 18: Kevin Patrick Murphy , Stuart Russell, Dynamic bayesian networks: representation, inference and learning, 2002
• 19: Murphy, K. P., Weiss, Y., & Jordan, M. I. (1999). Loopy belief propagation for approximate inference: An empirical study. Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI) (pp. 467--475).
• 20: Nefian, A., Liang, L., Pi, X., Xiaoxiang, L., Mao, C., & Murphy, K. (2002). A coupled HMM for audio-visual speech recognition. IEEE Int'l Conference on Acoustics, Speech and Signal Processing (pp. 2013--2016).
• 21: Peng, F., & McCallum, A. (2004). Accurate information extraction from research papers using conditional random fields. Proceedings of Human Language Technology Conference and North American Chapter of the Association for Computational Linguistics (HLT-NAACL'04).
• 22: Peshkin, L., & Pfeffer, A. (2003). Bayesian information extraction network. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• 23: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 24: Rabiner, L. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77, 257 -- 286.
• 25: Ramshaw, L. A., & Marcus, M. P. (1995). Text chunking using transformation-based learning. Proceedings of the Third ACL Workshop on Very Large Corpora.
• 26: Ratnaparkhi, A. (1996). A maximum entropy model for part-of-speech tagging. Proc. of the 1996 Conference on Empirical Methods in Natural Language Proceeding (EMNLP 1996).
• 27: Erik F. Tjong Kim Sang , Sabine Buchholz, Introduction to the CoNLL-2000 shared task: chunking, Proceedings of the 2nd workshop on Learning language in logic and the 4th conference on Computational natural language learning, September 13-14, 2000, Lisbon, Portugal [doi>10.3115/1117601.1117631]
• 28: Fei Sha , Fernando Pereira, Shallow parsing with conditional random fields, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.134-141, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073473]
• 29: Skounakis, M., Craven, M., & Ray, S. (2003). Hierarchical hidden Markov models for information extraction. Proceedings of the 18th International Joint Conference on Artificial Intelligence.
• 30: Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI02).
• 31: Theocharous, G., Rohanimanesh, K., & Mahadevan, S. (2001). Learning hierarchical partially observable Markov decision processes for robot navigation. Proceedings of the IEEE Conference on Robotics and Automation.
• 32: Martin J. Wainwright , Alan S. Willsky , Tommi S. Jaakkola, Stochastic processes on graphs with cycles: geometric and variational approaches, 2002
• 33: Wainwright, M., Jaakkola, T., & Willsky, A. (2001). Tree-based reparameterization for approximate estimation on graphs with cycles. Advances in Neural Information Processing Systems (NIPS).
• 34: Yedidia, J., Freeman, W., & Weiss, Y. (2000). Generalized belief propagation. Advances in Neural Information Processing Systems (NIPS).