Global Transition-based Non-projective Dependency Parsing

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

In ACL (2018)

Abstract
Shi, Huang, and Lee (2017) obtained state-of-the-art results for English and Chinese dependency parsing by combining dynamic-programming implementations of transition-based dependency parsers with a minimal set of bidirectional LSTM features. However, their results were limited to projective parsing. In this paper, we extend their approach to support non-projectivity by providing the first practical implementation of the MH4 algorithm, an O(n^4) mildly nonprojective dynamic-programming parser with very high coverage on non-projective treebanks. To make MH4 compatible with minimal transition-based feature sets, we introduce a transition-based interpretation of it in which parser items are mapped to sequences of transitions. We thus obtain the first implementation of global decoding for non-projective transition-based parsing, and demonstrate empirically that it is more effective than its projective counterpart in parsing a number of highly non-projective languages.

Bibtex

@InProceedings{gomez+shi+lee2018,
    author      = "G{\'o}mez-Rodr{\'i}guez, Carlos
                and Shi, Tianze
                and Lee, Lillian",
    title       = "Global Transition-based Non-projective Dependency Parsing",
    booktitle   = "Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    year        = "2018",
    publisher   = "Association for Computational Linguistics",
    pages       = "2664--2675",
    location    = "Melbourne, Australia",
    url         = "http://aclweb.org/anthology/P18-1248"
}

Tianze Shi @ Cornell University. Built with jekyll