Global Transition-based Non-projective Dependency Parsing

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


Abstract
Shi, Huang, and Lee (2017a) 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 MH₄ algorithm, an O(n4) mildly nonprojective dynamic-programming parser with very high coverage on non-projective treebanks. To make MH₄ 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 effective than its projective counterpart in parsing a number of highly non-projective languages.
Anthology ID:
P18-1248
Volume:
Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Month:
July
Year:
2018
Address:
Melbourne, Australia
Editors:
Iryna Gurevych, Yusuke Miyao
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
2664–2675
Language:
URL:
https://aclanthology.org/P18-1248
DOI:
10.18653/v1/P18-1248
Bibkey:
Cite (ACL):
Carlos Gómez-Rodríguez, Tianze Shi, and Lillian Lee. 2018. Global Transition-based Non-projective Dependency Parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2664–2675, Melbourne, Australia. Association for Computational Linguistics.
Cite (Informal):
Global Transition-based Non-projective Dependency Parsing (Gómez-Rodríguez et al., ACL 2018)
Copy Citation:
PDF:
https://aclanthology.org/P18-1248.pdf
Note:
 P18-1248.Notes.pdf
Code
 tzshi/mh4-parser-acl18