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

Abstract: In this paper, we propose second-order graph-based neural dependency parsing using message 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 dependency parsers and have significantly faster speed in both training and testing. We also empirically show the advantage of second-order parsing over first-order parsing and observe that the usefulness of the head-selection structured constraint vanishes when using BERT embedding.

## introduction graph-based dependency parsing is a popular approach to dependency parsing that scores parse components of a sentence and then finds the highest scoring tree through inference. first-order graphbased dependency parsing takes individual dependency 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 @xcite @xcite and approximate inference algorithms @xcite @xcite to find the best parse tree. recent work focused on neural network based graph dependency parsers @xcite @xcite @xcite . @xcite proposed a first-order graph-based neural dependency parsing approach with a simple headselection training objective. it uses a biaffine function to score dependency edges and has high efficiency and good performance. subsequent work * kewei tu is the corresponding author. in this paper, we first show how a previously proposed second-order semantic dependency parser @xcite can be applied to syntactic dependency 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 problem. 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 approaches and the first-order baselines on english penn tree bank 3.0 (ptb), chinese penn tree bank 5.1 (ctb) and datasets of 12 languages in universal dependencies (ud). we show that our approaches achieve state-of-the-art performance on both ptb and ctb and our approaches are significantly faster than recently proposed second-order parsers. we also make two interesting observations from our empirical study. first, it is a common belief that contextual word embeddings such as elmo @xcite and bert @xcite already conveys sufficient high-order information that renders high-order parsing less useful, but we find that second-order decoding is still helpful even with strong contextual embeddings like bert. second, while @xcite previously found that incoperating the head-selection constraint is helpful in first-order parsing, we find that with a better loss function design and hyper-parameter tun-ing both first-and second-order parsers without the head-selection constraint can match the accuracy of parsers with the head-selection constraint and can even outperform the latter when using bert embedding. our approaches are closely related to the work of @xcite , which proposed a nonneural second-order parser based on loopy belief propagation (lbp). our work differs from theirs in that: 1) we use mean field variational inference (mfvi) instead of lbp, which @xcite found is faster and equally accurate in practice; 2) we add the head-selection constraint and do not include the global tree constraint that is shown to produce only slight improvement @xcite but would complicate our neural network design and implementation; 3) we employ modern neural encoders and achieve much better parsing accuracy. our approaches are also closely related to the very recent work of @xcite . the main difference is that we use mfvi while they use the dual decomposition algorithm ad 3 @xcite for approximate inference. the second-order semantic dependency parser of @xcite is an end-to-end neural network derived from message passing inference on a conditional random field that encodes the second-order parsing problem. it is clearly a single approach because of the lack of structured constraints in semantic dependency parsing. we can apply this approach to syntactic dependency parsing with two minor modifications. first, co-parents, one of the three types of second-order parts, become invalid and hence are removed. second, for the approach to output valid parse trees during testing, we run maximum spanning tree (mst) @xcite based on the posterior edge probabilities predicted by the approach. inspired by @xcite , below we propose a local second-order parsing approach. while the single approach uses boolean random variables to represent existence of possible dependency edges, our local approach defines a discrete random variable for each word specifying its dependency head, thus enforcing the head-selection constraint and leading to different formulation of the message passing inference steps. ## conclusion we propose second-order graph-based dependency parsing based on message passing and end-toend neural networks. we modify a previous approach that predicts dependency edges independently and also design a new approach that incorporates the head-selection structured constraint. our experiments show that our second-order approaches have better overall performance than the first-order baselines; they achieve competitive accuracy with very recent start-of-the-art second-order graph-based parsers and are significantly faster. our empirical comparisons also show that secondorder decoders still outperform first-order decoders even with bert embeddings, and that the usefulness of the head-selection constraint is limited, especially when using bert embeddings. our code is publicly avilable at https://github.com/ wangxinyu0922/second_order_parsing .