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

April 27, 2018 · Entered Twilight · 🏛 North American Chapter of the Association for Computational Linguistics

"Last commit was 7.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: .gitignore, LICENSE, README.md, check_oracle.py, compute_coverage.py, nonproj

Authors Tianze Shi, Carlos Gómez-Rodríguez, Lillian Lee arXiv ID 1804.10615 Category cs.CL: Computation & Language Citations 1 Venue North American Chapter of the Association for Computational Linguistics Repository https://github.com/tzshi/nonproj-dp-variants-naacl2018 ⭐ 1 Last Checked 1 month ago

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(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