Elamur Research⌕
☰
home / papers / 2006 / Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines

Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines

Summary

This paper describes the system the authors entered in the CoNLL-X shared task. The task required one trainable dependency parser to handle treebanks in many languages. The parser is built with MaltParser 0.4. It reads each sentence once, left to right, and makes a deterministic choice at each step. A stack and four basic transitions build a labeled projective dependency graph. At every step, an SVM classifier picks the next transition from symbolic features of the parsing history.

The algorithm can only produce projective trees. To handle crossing arcs, the training trees are first made projective, and the moved arcs get enriched labels. After parsing, an inverse transformation restores the non-projective structure. For each language, the authors tuned feature sets and SVM settings. Across the twelve required languages, the system reached a labeled attachment score (LAS) of 80.19, which placed it at or near the top. The paper closes with an error analysis that looks most closely at Swedish and Turkish. Together, these results show that a fast, greedy, classifier-driven parser can compete across very different languages.

Key points

  • The parser has four components:
    • a deterministic transition algorithm with the actions SHIFT, REDUCE, RIGHT-ARC(r) and LEFT-ARC(r);
    • history-based features;
    • LIBSVM classifiers with a quadratic kernel and a one-versus-all multi-class strategy;
    • pseudo-projective graph transformations using the HEAD label encoding (r↑h).
  • Test-set results:
    • Total LAS was 80.19 (Bulgarian excluded), compared with 80.46 in the dry run. This small gap suggests the models were not overfitted.
    • LAS ranged from 91.65 for Japanese to 65.68 for Turkish.
    • The system had the best reported LAS for Japanese, Swedish and Turkish.
    • Unlabeled scores were less competitive; only Turkish had the top UAS.
  • Model settings:
    • Tuned models used between 16 features (Turkish) and 30 (Spanish).
    • An artificial root token was added only for Arabic, Czech, Portuguese and Slovene, whose root labels carry information.
    • For some languages, the training data was split by the POS or CPOS of the next input token, which speeds up training.
  • Root errors and non-projectivity:
    • Treebanks with many non-projective structures produced fragmented output and lower root precision.
    • Root precision was about 69% for Czech, 71% for Dutch and 41% for Slovene.
  • Turkish results:
    • Turkish is parsed over inflectional groups (IGs), not whole words. Its IG-level UAS of 75.8% corresponds to a word-level score of 82.7%.
    • Accuracy was much lower when the head belonged to a word with several IGs: 53.2% versus 83.7% for single-IG heads.

Interesting ideas

  • I1. Pseudo-projective encoding. The authors keep a simple projective parser and push non-projectivity into the labels. Lifted arcs remember their original head's label, and a post-processing step undoes the lifting. This pre-/post-transformation trick lets a restricted model handle richer output structures.
  • I2. Splitting morphological features. The FEATS field is broken into atomic attributes such as case and possessive, rather than treated as one combined value. The classifier then chooses which attributes matter in each context. This is likely valuable for morphologically rich languages such as Ukrainian.
  • I3. Splitting the training data by the next token's POS/CPOS. Separate classifiers are trained for each POS or CPOS value of the next input token. Rare categories are pooled using a frequency threshold. This reduces SVM training time with little loss in accuracy, and it is a generic way to scale kernel methods.
  • I4. Diagnostic evaluation beyond LAS. The error analysis uses root precision and recall to reflect global structure, and accuracy by arc length to reflect local versus distant attachments. These measures help explain why languages with similar LAS behave differently.
  • I5. Evaluating at the right unit. For segmented annotations like Turkish IGs, the authors report both unit-level and word-level scores. They also break results down by single-unit versus multi-unit heads, which keeps cross-language comparisons fair.

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: Linguistics & languages

Topics: Dependency parsing · Treebanks

Cited by

104 papers of our library cite it (of the 140673 whose bibliographies we read); 10 of them have a page here, 94 not yet.

Cite

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

@inproceedings{nivre2006labeled,
  title = {{Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines}},
  author = {Nivre, Joakim and Hall, Johan and Nilsson, Jens and Eryiǧit, Gülşen and Marinov, Svetoslav},
  booktitle = {Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X)},
  year = {2006},
  doi = {10.3115/1596276.1596318},
  url = {https://doi.org/10.3115/1596276.1596318}
}

References

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

  1. A. Abeillé, editor. 2003. Treebanks: Building and Using Parsed Corpora, volume 20 of Text, Speech and Language Technology. Kluwer Academic Publishers, Dordrecht. find
  2. S. Afonso, E. Bick, R. Haber, and D. Santos. 2002. “Floresta sintá(c)tica”: a treebank for Portuguese. In Proc. of LREC-2002, pages 1698–1703. find our card
  3. N. B. Atalay, K. Oflazer, and B. Say. 2003. The annotation process in the Turkish treebank. In Proc. of LINC-2003. find our card
  4. E. Black, F. Jelinek, J. D. Lafferty, D. M. Magerman, R. L. Mercer, and S. Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proc. of the 5th DARPA Speech and Natural Language Workshop, pages 31–37. find
  5. A. Böhmová, J. Hajič, E. Hajičová, and B. Hladká. 2003. The PDT: a 3-level annotation scenario. In Abeillé (Abeillé, 2003), chapter 7. find
  6. S. Brants, S. Dipper, S. Hansen, W. Lezius, and G. Smith. 2002. The TIGER treebank. In Proc. of TLT-2002. find
  7. C.-C. Chang and C.-J. Lin, 2001. LIBSVM: A Library for Support Vector Machines. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm. ↗
  8. K. Chen, C. Luo, M. Chang, F. Chen, C. Chen, C. Huang, and Z. Gao. 2003. Sinica treebank: Design criteria, representational issues and implementation. In Abeillé (Abeillé, 2003), chapter 13, pages 231–248. find
  9. M. Civit Torruella and Ma A. Martı́ Antonı́n. 2002. Design principles for a Spanish treebank. In Proc. of TLT-2002. find
  10. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  11. S. Džeroski, T. Erjavec, N. Ledinek, P. Pajas, Z. Žabokrtsky, and A. Žele. 2006. Towards a Slovene dependency treebank. In Proc. of LREC-2006. find
  12. G. Eryiğit and K. Oflazer. 2006. Statistical dependency parsing of Turkish. In Proc. of EACL-2006. find
  13. J. Hajič, O. Smrž, P. Zemánek, J. Šnaidauf, and E. Beška. 2004. Prague Arabic dependency treebank: Development in data and tools. In Proc. of NEMLAR-2004, pages 110–117. find
  14. Y. Kawata and J. Bartels. 2000. Stylebook for the Japanese treebank in VERBMOBIL. Verbmobil-Report 240, Seminar für Sprachwissenschaft, Universität Tübingen. find
  15. M. T. Kromann. 2003. The Danish dependency treebank and the underlying linguistic theory. In Proc. of TLT-2003. find
  16. T. Kudo and Y. Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In Proc. of CoNLL-2002, pages 63–69. find
  17. J. Nilsson, J. Hall, and J. Nivre. 2005. MAMBA meets TIGER: Reconstructing a Swedish treebank from antiquity. In Proc. of the NODALIDA Special Session on Treebanks. find
  18. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. of ACL-2005, pages 99–106. find
  19. J. Nivre, J. Hall, and J. Nilsson. 2004. Memory-based dependency parsing. In Proc. CoNLL-2004, pages 49–56. find our card
  20. J. Nivre, J. Hall, and J. Nilsson. 2006. MaltParser: A data-driven parser-generator for dependency parsing. In Proc. of LREC-2006. find our card
  21. J. Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proc. of IWPT-2003, pages 149–160. find our card
  22. J. Nivre. 2006. Inductive Dependency Parsing. Springer. find
  23. K. Oflazer, B. Say, D. Zeynep Hakkani-Tür, and G. Tür. 2003. Building a Turkish treebank. In Abeillé (Abeillé, 2003), chapter 15. find
  24. K. Simov and P. Osenova. 2003. Practical annotation scheme for an HPSG treebank of Bulgarian. In Proc. of LINC-2003, pages 17–24. find
  25. K. Simov, P. Osenova, A. Simov, and M. Kouylekov. 2005. Design and implementation of the Bulgarian HPSG-based treebank. In Journal of Research on Language and Computation – Special Issue, pages 495–522. Kluwer Academic Publishers. find
  26. O. Smrž, J. Šnaidauf, and P. Zemánek. 2002. Prague dependency treebank for Arabic: Multi-level annotation of Arabic corpus. In Proc. of the Intern. Symposium on Processing of Arabic, pages 147–155. find
  27. L. van der Beek, G. Bouma, R. Malouf, and G. van Noord. 2002. The Alpino dependency treebank. In Computational Linguistics in the Netherlands (CLIN). find
  28. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT-2003, pages 195–206. find our card

↑ back to top

This page in Markdown →