Efficient inference on sequence segmentation models

ABSTRACT

Sequence segmentation is a flexible and highly accurate mechanism for modeling several applications. Inference on segmentation models involves dynamic programming computations that in the worst case can be cubic in the length of a sequence. In contrast, typical sequence labeling models require linear time. We remove this limitation of segmentation models vis-a-vis sequential models by designing a succinct representation of potentials common across overlapping segments. We exploit such potentials to design efficient inference algorithms that are both analytically shown to have a lower complexity and empirically found to be comparable to sequential models for typical extraction tasks.

REFERENCES

• 1: Bartlett, P. L., Collins, M., Taskar, B., & McAllester, D. (2005). Exponentiated gradient algorithms for large-margin structured classification. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17, 113--120. Cambridge, MA: MIT Press.
• 2: Borthwick, A., Sterling, J., Agichtein, E., & Grishman, R. (1998). Exploiting diverse knowledge sources via maximum entropy in named entity recognition. Sixth Workshop on Very Large Corpora New Brunswick, New Jersey. Association for Computational Linguistics.
• 3: Cohen, W. W., Ravikumar, P., & Fienberg, S. E. (2003). A comparison of string distance metrics for name-matching tasks. Proceedings of the IJCAI-2003 Workshop on Information Integration on the Web (IIWeb-03). To appear.
• 4: Hal Daumé, III , Daniel Marcu, Learning as search optimization: approximate large margin methods for structured prediction, Proceedings of the 22nd international conference on Machine learning, p.169-176, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102373]
• 5: Keshet, J., Shalev-Shwartz, S., & Singer, Y. (2005). Phoneme alignment using large margin techniques. Workshop on the Advances in Structured Learning for Text and Speech Processing, NIPS.
• 6: McDonald, R., Crammer, K., & Pereira, F. (2005). Flexible text segmentation with structured multilabel classification. Human Language Technology Conference Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP).
• 7: Peng, F., & McCallum, A. (2004). Accurate information extraction from research papers using conditional random fields. HLT-NAACL (pp. 329--336).
• 8: Sarawagi, S., & Cohen, W. W. (2004). Semi-markov conditional random fields for information extraction. NIPS.
• 9: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 9/1/2005
• 10: Tong Zhang , Fred Damerau , David Johnson, Text chunking based on a generalization of winnow, The Journal of Machine Learning Research, 2, 3/1/2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms