Efficient Second-Order TreeCRF for Neural Dependency Parsing

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3295–3305 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 3295 Efficient Second-Order TreeCRF for Neural Dependency Parsing Yu Zhang, Zhenghua Li∗, Min Zhang Institute of Artificial Intelligence, School of Computer Science and Technology, Soochow University, Suzhou, China yzhang.cs@outlook.com, {zhli13,minzhang}@suda.edu.cn Abstract In the deep learning (DL) era, parsing mod- els are extremely simplified with little hurt on performance, thanks to the remarkable ca- pability of multi-layer BiLSTMs in context representation. As the most popular graph- based dependency parser due to its high ef- ficiency and performance, the biaffine parser directly scores single dependencies under the arc-factorization assumption, and adopts a very simple local token-wise cross-entropy training loss. This paper for the first time presents a second-order TreeCRF extension to the biaffine parser. For a long time, the com- plexity and inefficiency of the inside-outside algorithm hinder the popularity of TreeCRF. To address this issue, we propose an effec- tive way to batchify the inside and Viterbi al- gorithms for direct large matrix operation on GPUs, and to avoid the complex outside algo- rithm via efficient back-propagation. Experi- ments and analysis on 27 datasets from 13 lan- guages clearly show that techniques developed before the DL era, such as structural learning (global TreeCRF loss) and high-order model- ing are still useful, and can further boost pars- ing performance over the state-of-the-art bi- affine parser, especially for partially annotated training data. We release our code at https: //github.com/yzhangcs/crfpar. 1 Introduction As a fundamental task in NLP, dependency pars- ing has attracted a lot of research interest due to its simplicity and multilingual applicability in capturing both syntactic and semantic informa- tion (Nivre et al., 2016). Given an input sentence x = w0w1 . . . wn, a dependency tree, as depicted in Figure 1, is defined as y = {(i, j, l), 0 ≤ i ≤ n, 1 ≤ j ≤ n, l ∈ L}, where (i, j, l) is a depen- dency from the head word wi to the modifier word ∗Corresponding author $0 I1 saw2 Sarah3 with4 a5 telescope6 nsubj dobj pobj det root prep Figure 1: An example full dependency tree. In the case of partial annotation, only some (not all) dependencies are annotated, for example, the two thick (blue) arcs. wj with the relation label l ∈ L. Between two mainstream approaches, this work focuses on the graph-based paradigm (vs. transition-based). Before the deep learning (DL) era, graph-based parsing relies on many hand-crafted features and differs from its neural counterpart in two major aspects. First, structural learning, i.e., explicit awareness of tree structure constraints during train- ing, is indispensable. Most non-neural graph-based parsers adopt the max-margin training algorithm, which first predicts a highest-scoring tree with the current model, and then updates feature weights so that the correct tree has a higher score than the predicted tree. Second, high-order modeling brings significant accuracy gains. The basic first-order model fac- tors the score of a tree …

Content truncated to 500 words