# 2006 EfficientInferenceOnSeqSegModels

- (Sarawagi, 2006) ⇒ Sunita Sarawagi. (2006). “Efficient Inference on Sequence Segmentation Models.” In: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006). doi:10.1145/1143844.1143944

**Subject Headings:** Sequence Segmentation Statistical Models, Statistical Model Inference Task.

## Notes

## Cited by

## Quotes

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

Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|

2006 EfficientInferenceOnSeqSegModels | Sunita Sarawagi | Efficient Inference on Sequence Segmentation Models | ICML 2006 | http://www.it.iitb.ac.in/~sunita/papers/icml06.pdf | 10.1145/1143844.1143944 | 2006 |