Abstract
We generalize Cohen, Gómez-Rodríguez, and Satta’s (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference. This includes novel parsers with better coverage than Cohen et al. (2011), and even a variant that reduces time complexity to O(n6), improving over the known bounds in exact inference for non-projective transition-based parsing. We hope that this piece of theoretical work inspires design of novel transition systems with better coverage and better run-time guarantees.- Anthology ID:
- N18-2067
- Volume:
- Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)
- Month:
- June
- Year:
- 2018
- Address:
- New Orleans, Louisiana
- Editors:
- Marilyn Walker, Heng Ji, Amanda Stent
- Venue:
- NAACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 420–425
- Language:
- URL:
- https://aclanthology.org/N18-2067
- DOI:
- 10.18653/v1/N18-2067
- Cite (ACL):
- Tianze Shi, Carlos Gómez-Rodríguez, and Lillian Lee. 2018. Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 420–425, New Orleans, Louisiana. Association for Computational Linguistics.
- Cite (Informal):
- Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers (Shi et al., NAACL 2018)
- PDF:
- https://preview.aclanthology.org/emnlp22-frontmatter/N18-2067.pdf
- Code
- tzshi/nonproj-dp-variants-naacl2018