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

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

In NAACL (2018)

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 on prior bounds. We hope that this piece of theoretical work inspires design of novel transition systems with better coverage and better run-time guarantees.

Bibtex

@InProceedings{shi+gomez+lee2018,
    author    = {Tianze Shi and Carlos G{\'o}mez-Rodr{\'i}guez and Lillian Lee},
    title     = {Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers},
    booktitle = {Proceedings of NAACL},
    month     = {June},
    year      = {2018},
    address   = {New Orleans, Louisiana},
    publisher = {Association for Computational Linguistics},
    pages     = {420--425}
}

Tianze Shi @ Cornell University. Built with jekyll