Elamur Research⌕
☰
home / papers / 2013 / Finding Optimal 1-Endpoint-Crossing Trees

Finding Optimal 1-Endpoint-Crossing Trees

Paper · 2013 · Emily Pitler, Sampath Kannan and Mitchell Marcus

Summary

Dependency parsers that allow crossing arcs have usually been much slower than projective ones. The projective O(n³) algorithm misses many real sentences. Unrestricted spanning trees become NP-hard to decode once grandparent or sibling features are added. Existing mildly non-projective classes need costly algorithms, such as O(n⁷) for well-nested trees with block degree 2. The authors propose a new structural class, 1-Endpoint-Crossing trees: whenever an arc is crossed, every arc crossing it meets at a single shared vertex.

Using the CoNLL-X training treebanks for six languages, they show this class captures nearly all annotated parses. They prove that each arc, together with its shared crossing vertex, splits the tree into self-contained regions, each an interval plus one outside vertex. Based on this, they design an exact arc-factored dynamic program that finds the best such tree in O(n⁴). That is faster than any earlier mildly non-projective decoder.

The class also links to theory. It is strictly contained in 2-planar graphs, and pairs of cross-serial verbs yield trees of this type.

Key points

  • Coverage on the CoNLL-X training data (Arabic, Czech, Danish, Dutch, Portuguese, Swedish) is 95.8–99.8%. Dutch is the lowest and reaches 97.0% if arcs from the artificial root are ignored.
  • The class is compared with three others:
    • projective trees: O(n³), coverage as low as 63.6% for Dutch;
    • gap-minding trees: O(n⁵), 90.4–97.7%;
    • well-nested trees with block degree 2: O(n⁷), 95.4–99.9%.
  • The O(n⁴) algorithm combines five kinds of subproblems: plain intervals, plus four variants of interval-with-exterior-point regions. The variants differ in whether arcs from the outside vertex can be crossed by arcs at the left boundary, the right boundary, both, or neither.
  • 1-Endpoint-Crossing trees form a proper subset of 2-planar trees, a class previously handled only by a transition-based parser with no known exact algorithm. They are not a subset of the well-nested, block-degree-2 class.

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

 Institutions

🎓University of PennsylvaniaPhiladelphia · United States221 works · 63,234 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

Cite

Cite as Emily Pitler, Sampath Kannan and Mitchell Marcus. 2013. Finding Optimal 1-Endpoint-Crossing Trees. Transactions of the Association for Computational Linguistics.

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

@article{pitler2013finding,
  title = {{Finding Optimal 1-Endpoint-Crossing Trees}},
  author = {Emily Pitler, Sampath Kannan and Mitchell Marcus},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2013},
  doi = {10.1162/tacl\_a\_00206},
  url = {https://doi.org/10.1162/tacl_a_00206}
}

References

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

  1. E. Bach, C. Brown, and W. Marslen-Wilson. 1986. Crossed and nested dependencies in german and dutch: A psycholinguistic study. Language and Cognitive Processes, 1(4):249–262. find
  2. F. Bernhart and P.C. Kainen. 1979. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320 – 331. find
  3. M. Bodirsky, M. Kuhlmann, and M. Möhl. 2005. Well-nested drawings as models of syntactic structure. In In Tenth Conference on Formal Grammar and Ninth Meeting on Mathematics of Language, pages 88–1. find
  4. University Press. X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL, volume 7, pages 957–961. N. Chomsky, Massachusetts Institute of Technology. Dept. of Linguistics, and Philosophy. 1998. Minimalist inquir…
  5. N. Chomsky. 1981. Lectures on Government and Binding. find
  6. Dordrecht: Foris. F. Chung, F. Leighton, and A. Rosenberg. 1987. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic Discrete Methods, 8(1):33–58. find
  7. H. Cui, R. Sun, K. Li, M.Y. Kan, and T.S. Chua. 2005. Question answering passage retrieval using dependency relations. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 400–407. find
  8. ACM. A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, page 423. Association for Computational Linguistics.
  9. Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 541–548. Association for Computational Linguistics.
  10. J. Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. In Harry Bunt and Anton Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies, pages 29–62. find
  11. Kluwer Academic Publishers, October. S. Even and A. Itai. 1971. Queues, stacks, and graphs. In Proc. International Symp. on Theory of Machines and Computations, pages 71–86. find
  12. C. Gómez-Rodríguez and J. Nivre. 2010. A transition-based parser for 2-planar dependency structures. In Proceedings of ACL, pages 1492–1501. find
  13. C. Gómez-Rodríguez, J. Carroll, and D. Weir. 2011. Dependency parsing schemata and mildly non-projective dependency parsing. Computational Linguistics, 37(3):541–586. find
  14. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1–11. find
  15. M. Kuhlmann. 2013. Mildly non-projective dependency grammar. Computational Linguistics, 39(2). find
  16. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL, pages 81–88.
  17. R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies, pages 121–132. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005. Non-projective dependency parsing using spanning t… find
  18. E. Pitler, S. Kannan, and M. Marcus. 2012. Dynamic programming for higher order parsing of gap-minding trees. In Proceedings of EMNLP, pages 478–488. find
  19. L.A. Ringenberg. 1967. College geometry. find
  20. Wiley. A. Rush and S. Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In Proceedings of NAACL, pages 498–507. find
  21. S.M. Shieber. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8(3):333–343. find
  22. H. Zhang and R. McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proceedings of EMNLP, pages 320–331. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/pitler-2013-finding-optimal-1-endpoint-crossing/