Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers

Tianze Shi, Carlos Gómez-Rodríguez, Lillian Lee


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
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/N18-2067.pdf
Code
 tzshi/nonproj-dp-variants-naacl2018