Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers
This work addresses a theoretical bottleneck in computational linguistics for researchers and practitioners, offering incremental improvements in coverage and runtime for non-projective parsing.
The authors tackled the problem of exact inference in non-projective transition-based dependency parsers by generalizing an existing parser to a family of parsers, achieving polynomial-time exact inference with improved coverage and a variant reducing time complexity to O(n^6).
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(n^6)$, 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. Code available at https://github.com/tzshi/nonproj-dp-variants-naacl2018