Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training

Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, pages 93–99 December 4 - 7, 2020. c⃝2020 Association for Computational Linguistics 93 Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training Xinyu Wang and Kewei Tu∗ School of Information Science and Technology, ShanghaiTech University Shanghai Engineering Research Center of Intelligent Vision and Imaging Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences {wangxy1,tukw}@shanghaitech.edu.cn Abstract In this paper, we propose second-order graph- based neural dependency parsing using mes- sage passing and end-to-end neural networks. We empirically show that our approaches match the accuracy of very recent state-of- the-art second-order graph-based neural de- pendency parsers and have significantly faster speed in both training and testing. We also em- pirically show the advantage of second-order parsing over first-order parsing and observe that the usefulness of the head-selection struc- tured constraint vanishes when using BERT embedding. 1 Introduction Graph-based dependency parsing is a popular ap- proach to dependency parsing that scores parse components of a sentence and then finds the highest scoring tree through inference. First-order graph- based dependency parsing takes individual depen- dency edges as the components of a parse tree, while higher-order dependency parsing considers more complex components consisting of multiple edges. There exist both exact inference algorithms (Carreras, 2007; Koo and Collins, 2010; Ma and Zhao, 2012) and approximate inference algorithms (McDonald and Pereira, 2006; Smith and Eisner, 2008; Gormley et al., 2015) to find the best parse tree. Recent work focused on neural network based graph dependency parsers (Kiperwasser and Gold- berg, 2016; Wang and Chang, 2016; Cheng et al., 2016; Kuncoro et al., 2016; Ma and Hovy, 2017; Dozat and Manning, 2017). Dozat and Manning (2017) proposed a first-order graph-based neural dependency parsing approach with a simple head- selection training objective. It uses a biaffine func- tion to score dependency edges and has high effi- ciency and good performance. Subsequent work ∗Kewei Tu is the corresponding author. introduced second-order inference into their parser. Ji et al. (2019) proposed a graph neural network that captures second-order information in token representations, which are then used for first-order parsing. Very recently, Zhang et al. (2020) pro- posed an efficient second-order tree CRF model for dependency parsing and achieved state-of-the-art performance. In this paper, we first show how a previously pro- posed second-order semantic dependency parser (Wang et al., 2019) can be applied to syntactic de- pendency parsing with simple modifications. The parser is an end-to-end neural network derived from message passing inference on a conditional random field that encodes the second-order parsing prob- lem. We then propose an alternative conditional random field that incorporates the head-selection constraint of syntactic dependency parsing, and derive a novel second-order dependency parser. We empirically compare the two second-order ap- proaches and the first-order baselines on English Penn Tree Bank 3.0 (PTB), Chinese Penn Tree Bank 5.1 (CTB) and datasets of 12 …

Content truncated to 500 words