Elamur Research
☰
home / papers / 2009 / Non-Projective Dependency Parsing in Expected Linear Time

Non-Projective Dependency Parsing in Expected Linear Time

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P09-1040.pdf

Summary

Non-projective dependency trees, where a subtree's words are not contiguous in the sentence, are hard to parse efficiently. Exact inference is often NP-hard, and deterministic parsers that cover all such trees usually need quadratic time. Nivre proposes a transition-based system that only links words adjacent on the stack but can still build any tree. It does this with one extra transition, SWAP, which moves a stack node back into the buffer and so reorders the input. The resulting system S_u is sound and complete for all dependency trees and behaves exactly like the standard projective system on projective input. Its worst-case complexity is O(n²). However, measurements on treebank data for Arabic, Czech, Danish, Slovene and Turkish show that the number of transitions grows linearly with sentence length, staying close to the 2n of a projective parser. A deterministic, classifier-guided parser built on S_u reaches state-of-the-art accuracy and is especially strong on labeled exact match. This offers a simple, fast and easy-to-implement way to handle discontinuous constructions.

Key points

  • The transition set extends the projective system T_p (LEFT-ARC, RIGHT-ARC, SHIFT) with SWAP to form T_u. Typically the parser runs in linear time, O(n), its best case, while the quadratic O(n²) worst case seldom arises.
  • Empirically, Arabic shows the smallest variance and linear coefficients and Danish the largest; for one dataset the fit was m = 2.07n (R² = 0.96) on test data. Classifier-based parsers needed fewer transitions than oracle parsers.
  • S_u was compared with a projective parser (S_p), a pseudo-projective parser (S_pp), MST-06 and MST_Malt. It was best overall for Czech and second only to the MST parsers for Slovene; both languages have 1.9% non-projective arcs.
  • On exact match, S_u gave the best reported results for four of the five languages, sometimes by a wide margin (Czech, Slovene).
  • Attardi (2006) is equivalent to a restricted variant allowing at most two consecutive swaps, which keeps linear time but loses completeness. Covington's algorithm is complete but quadratic even in the best case.

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: Dependency parsing

Cited by

132 papers of our library cite it (of the 140673 whose bibliographies we read); 14 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{nivre2009non,
  title = {{Non-Projective Dependency Parsing in Expected Linear Time}},
  author = {Nivre, Joakim},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  url = {https://aclanthology.org/P09-1040/}
}

References

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

  1. Giuseppe Attardi. 2006. Experiments with a multi-language non-projective dependency parser. In Proceedings of CoNLL, pages 166–170. find
  2. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164. find our card
  3. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95– 102. find
  4. Carlos Gómez-Rodrı́guez, David Weir, and John Carroll. 2009. Parsing mildly non-projective dependency structures. In Proceedings of EACL, pages 291–299. find
  5. Keith Hall and Vaclav Novák. 2005. Corrective modeling for non-projective dependency parsing. In Proceedings of IWPT, pages 42–52. find
  6. Jiri Havelka. 2007. Beyond projectivity: Multilingual evaluation of constraints and measures on non-projective structures. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 608–615. find
  7. Richard Johansson and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of the Shared Task of EMNLP-CoNLL, pages 1134–1138. find
  8. Marco Kuhlmann and Joakim Nivre. 2006. Mildly non-projective dependency structures. In Proceedings of the COLING/ACL Main Conference Poster Sessions, pages 507–514. find
  9. Marco Kuhlmann and Giorgio Satta. 2009. Treebank grammar techniques for non-projective dependency parsing. In Proceedings of EACL, pages 478–486. find
  10. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL, pages 81–88. find our card
  11. Ryan McDonald and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of IWPT, pages 122–131. find
  12. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91– 98. find our card
  13. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLT/EMNLP, pages 523–530. find our card
  14. Ryan McDonald, Kevin Lerman, and Fernando Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings of CoNLL, pages 216–220. find
  15. Peter Neuhaus and Norbert Bröker. 1997. The complexity of recognition of linguistically adequate dependency grammars. In Proceedings of ACL/EACL, pages 337–343. find
  16. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of ACL, pages 950–958. find
  17. Joakim Nivre and Jens Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of ACL, pages 99–106. find
  18. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. find
  19. Joakim Nivre, Johan Hall, Jens Nilsson, Gülsen Eryiğit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225. find
  20. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL), pages 50–57. find our card
  21. Joakim Nivre. 2006. Constraints on non-projective dependency graphs. In Proceedings of EACL, pages 73–80. find
  22. Joakim Nivre. 2007. Incremental non-projective dependency parsing. In Proceedings of NAACL HLT, pages 396–403. find
  23. Joakim Nivre. 2008a. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. find our card
  24. Joakim Nivre. 2008b. Sorting out dependency parsing. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), pages 16–27. find
  25. Ivan Titov and James Henderson. 2007. A latent variable model for generative dependency parsing. In Proceedings of IWPT, pages 144–155. find
  26. Ivan Titov, James Henderson, Paola Merlo, and Gabriele Musillo. 2009. Online graph planarization for synchronous parsing of semantic and syntactic dependencies. In Proceedings of IJCAI. find
  27. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206. find our card