Open main menu


2006 EfficientInferenceOnSeqSegModels


Cited by



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.


  • 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,

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2006 EfficientInferenceOnSeqSegModelsSunita SarawagiEfficient Inference on Sequence Segmentation ModelsICML 2006