Elamur Research⌕
☰
home / papers / 2001 / Chunking with Support Vector Machines

Chunking with Support Vector Machines

Summary

The paper addresses chunking: splitting a token sequence into non-overlapping base phrases and assigning each a grammatical class. Chunking is treated as tagging each token with a chunk label. The authors argue that HMM and Maximum Entropy models depend on hand-picked feature sets and feature combinations. SVMs instead generalize well in very high-dimensional spaces, and a polynomial kernel lets them consider feature conjunctions implicitly.

Each token is classified from a fixed window of context: neighbouring words, their POS tags, and the chunk labels already assigned. Tagging runs either left-to-right or right-to-left. The multi-class problem is decomposed into pairwise binary SVMs. Eight systems, built with different chunk representations and parsing directions, are combined by weighted voting. Some of the weights come from SVM theory (VC bound, Leave-One-Out bound) rather than only from cross validation.

On WSJ-based data, the combined system reaches F 94.22 (baseNP-S), 95.77 (baseNP-L) and 93.91 (CoNLL-2000 chunking). These scores beat earlier MBL/ME-based voting systems, which shows that margin-based learners handle rich, sparse NLP features well.

Key points

  • Datasets: baseNP-S, baseNP-L and the CoNLL-2000 chunking data (WSJ corpus).
  • Best F-scores with weighted voting:
    • baseNP-S: 94.22 (P 94.15%, R 94.29%)
    • baseNP-L: 95.77
    • chunking: 93.91
  • Comparison with prior work:
    • Single representations already give 93.76–94.11 on baseNP-S and 95.29–95.34 on baseNP-L.
    • Tjong Kim Sang et al. report 93.86 and 94.90 on the same sets.
  • Several chunk representations are described: IOB1, IOB2, IOE1, IOE2 and Start/End (B/I/O/E/S). Voting results are reported for the IOB/IOE variants, with forward and backward parsing.
  • The authors' CoNLL-2000 shared-task entry scored 93.48 with IOB2-F (beam width 5). The re-run in this paper got 93.46 with deterministic tagging (width 1) and TinySVM.

Interesting ideas

  • I1. Diversity from label encodings. The same learner is trained on different encodings of the same chunks (IOB vs IOE variants, forward vs backward direction), and the outputs are then voted. This gives ensemble diversity cheaply, without needing different algorithms. It could transfer to NER or segmentation tasks for Ukrainian.
  • I2. Theory-derived voting weights. Each system's vote is weighted by its estimated error from the VC bound or the Leave-One-Out bound, computed from the trained model itself. The VC-bound weights performed about as well as cross-validation weights at no extra training cost. This is attractive when compute is limited.
  • I3. Pairwise decomposition to cut training cost. SVM training cost grows faster than linearly with data size. Many small pairwise classifiers can therefore be cheaper to train than a few one-vs-all models, and they may also be more accurate.
  • I4. Kernel instead of manual feature engineering. A polynomial kernel covers all feature combinations up to a chosen degree. This replaces heuristic selection of conjunctions over words, POS tags and previous labels.
  • I5. Previous predictions as features. Labels already assigned to neighbouring tokens are fed back in as features. Reversing the parsing direction then yields a second, complementary model from the same feature design.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Part-of-speech tagging

Cited by

127 papers of our library cite it (of the 140884 whose bibliographies we read); 9 of them have a page here, 118 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{kudo2001chunking,
  title = {{Chunking with Support Vector Machines}},
  author = {Kudo, Taku and Matsumoto, Yuji},
  booktitle = {Second Meeting of the North American Chapter of the Association for Computational Linguistics},
  year = {2001},
  doi = {10.3115/1073336.1073361},
  url = {https://doi.org/10.3115/1073336.1073361}
}

References

22 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Erin L. Allwein, Robert E. Schapire, and Yoram Singer. 2000. Reducing multiclass to binary: A unifying approach for margin classifiers. In International Conf. on Machine Learning (ICML), pages 9–16. find
  2. Eric Brill. 1995. Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part-of-Speech Tagging. Computational Linguistics, 21(4). find our card
  3. Oliver Chapelle and Vladimir Vapnik. 2000. Model selection for support vector machines. In Advances in Neural Information Processing Systems 12. Cambridge, Mass: MIT Press. find
  4. C. Cortes and Vladimir N. Vapnik. 1995. Support Vector Networks. Machine Learning, 20:273– 297. find
  5. T. G. Dietterich and G. Bakiri. 1995. Solving multi-class learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286. find
  6. Yoav Freund and Robert E. Schapire. 1996. Experiments with a new boosting algorithm. In International Conference on Machine Learning (ICML), pages 148–146. find
  7. Thorsten Joachims. 1998. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. In European Conference on Machine Learning (ECML). find our card
  8. Ulrich H.-G Kreßel. 1999. Pairwise Classification and Support Vector Machines. In Advances in Kernel Mathods. MIT Press. find
  9. Taku Kudo and Yuji Matsumoto. 2000a. Japanese Dependency Structure Analysis Based on Support Vector Machines. In Empirical Methods in Natural Language Processing and Very Large Corpora, pages 18–25. find
  10. Taku Kudo and Yuji Matsumoto. 2000b. Use of Support Vector Learning for Chunk Identification. In Proceedings of the 4th Conference on CoNLL-2000 and LLL-2000, pages 142–144. find
  11. Lance A. Ramshaw and Mitchell P. Marcus. 1995. Text chunking using transformation-based learning. In Proceedings of the 3rd Workshop on Very Large Corpora, pages 88–94. find our card
  12. Manabu Sassano and Takehito Utsuro. 2000. Named Entity Chunking Techniques in Supervised Learning for Japanese Named Entity Recognition. In Proceedings of COLING 2000, pages 705–711. find
  13. Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. 1997. Boosting the margin: a new explanation for the effectiveness of voting methods. In International Conference on Machine Learning (ICML), pages 322–330. find
  14. Hirotoshi Taira and Masahiko Haruno. 1999. Feature Selection in SVM Text Categorization. In AAAI-99. find
  15. Erik F. Tjong Kim Sang and Sabine Buchholz. 2000. Introduction to the CoNLL-2000 Shared Task: Chunking. In Proceedings of CoNLL-2000 and LLL-2000, pages 127–132. find our card
  16. Erik F. Tjong Kim Sang and Jorn Veenstra. 1999. Representing text chunks. In Proceedings of EACL’99, pages 173–179. find our card
  17. Erik F. Tjong Kim Sang, Walter Daelemans, Hervé Déjean, Rob Koeling, Yuval Krymolowski, Vasin Punyakanok, and Dan Roth. 2000. Applying system combination to base noun phrase identification. In Proceedings of COLING 2000, pages 857–863. find
  18. Erik F. Tjong Kim Sang. 2000a. Noun phrase recognition by system combination. In Proceedings of ANLP-NAACL 2000, pages 50–55. find
  19. Erik F. Tjong Kim Sang. 2000b. Text Chunking by System Combination. In Proceedings of CoNLL-2000 and LLL-2000, pages 151–153. find
  20. Kiyotaka Uchimoto, Qing Ma, Masaki Murata, Hiromi Ozaku, and Hitoshi Isahara. 2000. Named Entity Extraction Based on A Maximum Entropy Model and Transformation Rules. In Processing of the ACL 2000. find
  21. Hans van Halteren. 2000. Chunking with WPDV Models. In Proceedings of CoNLL-2000 and LLL-2000, pages 154–156. find
  22. Vladimir N. Vapnik. 1998. Statistical Learning Theory. Wiley-Interscience. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kudo-2001-chunking-support-vector-machines/