Efficient Second-Order T ree CRF for Neural Dependency Parsing (2020)

Abstract: In the deep learning (DL) era, parsing models are extremely simplified with little hurt on performance, thanks to the remarkable capability of multi-layer BiLSTMs in context representation. As the most popular graph-based dependency parser due to its high efficiency 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 complexity and inefficiency of the inside-outside algorithm hinder the popularity of TreeCRF. To address this issue, we propose an effective way to batchify the inside and Viterbi algorithms for direct large matrix operation on GPUs, and to avoid the complex outside algorithm via efficient back-propagation. Experiments and analysis on 27 datasets from 13 languages clearly show that techniques developed before the DL era, such as structural learning (global TreeCRF loss) and high-order modeling are still useful, and can further boost parsing performance over the state-of-the-art biaffine parser, especially for partially annotated training data. We release our code at https://github.com/yzhangcs/crfpar .

## introduction as a fundamental task in nlp, dependency parsing has attracted a lot of research interest due to its simplicity and multilingual applicability in capturing both syntactic and semantic information @xcite . given an input sentence @xmath0. . . w n , a dependency tree, as depicted in figure 1 , is defined as @xmath1, j, l), 0 ≤ @xmath2, 1 ≤ @xmath3, @xmath4, where (i, j, l) is a dependency from the head word w i to the modifier word * corresponding author $ 0 i 1 saw 2 sarah 3 with 4 a 5 telescope 6 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. second, high-order modeling brings significant accuracy gains. the basic first-order model factors the score of a tree into independent scores of single dependencies @xcite . second-order models were soon propose to incorporate scores of dependency pairs, such as adjacent-siblings @xcite and grand-parent-child @xcite , showing significant accuracy improvement yet with the cost of lower efficiency and more complex decoding algorithms. 1 in contrast, neural graph-based dependency parsing exhibits an opposite development trend. @xcite propose to use feed-forward neural networks for automatically learning combinations of dozens of atomic features similar to @xcite , and for computing subtree scores. they show that incorporating second-order scores of adjacent-sibling subtrees significantly improved performance. then, both @xcite and @xcite propose to utilize bilstm as an encoder and use minimal feature sets for scoring single dependencies in a first-order parser. these three representative works all employ global max-margin training. @xcite propose a strong and efficient biaffine parser and obtain state-of-the-art accuracy on a variety of datasets and languages. the biaffine parser is also first-order and employs simpler and more efficient non-structural training via local head selection for each token @xcite . observing such contrasting development, we try to make a connection between pre-dl and dl techniques for graph-based parsing. specifically, the first question to be addressed in this work is: can previously useful techniques such as structural learning and high-order modeling further improve the state-of-the-art foot_2 biaffine parser, and if so, in which aspects are they helpful? for structural learning, we focus on the more complex and less popular treecrf instead of maxmargin training. the reason is two-fold. first, estimating probability distribution is the core issue in modern data-driven nlp methods @xcite . the probability of a tree, i.e., p(y | x), is potentially more useful than an unbounded score s(x, y) for high-level nlp tasks when utilizing parsing outputs. second, as a theoretically sound way to measure model confidence of subtrees, marginal probabilities can support minimum bayes risk (mbr) decoding @xcite , and are also proven to be crucial for the important research line of token-level active learning based on partial trees @xcite . one probable reason for the less popularity of treecrf, despite its usefulness, is due to the complexity and inefficiency of the inside-outside algorithm, especially the outside algorithm. as far as we know, all existing works compute the inside and outside algorithms on cpus. the inefficiency issue becomes more severe in the dl era, due to the unmatched speed of cpu and gpu computation. this leads to the second question: can we batchify the inside-outside algorithm and perform computation directly on gpus? in that case, we can employ efficient treecrf as a built-in component in dl toolkits such as pytorch for wider applications @xcite . overall, targeted at the above two questions, this work makes the following contributions. ## the basic biaffine parser we re-implement the state-of-the-art biaffine parser @xcite with two modifications, i.e., using charlstm word representation vectors instead of pos tag embeddings, and the first-order eisner algorithm @xcite for projective decoding instead of the non-projective mst algorithm. scoring architecture. figure 2 shows the scoring architecture, consisting of four components. input vectors. the ith input vector is composed of two parts: the word embedding and the charlstm word representation vector of w i . figure 2: scoring architecture with second-order extension. charlstm(w i ) leads to consistent improvement, and also simplifies the multilingual experiments by avoiding pos tag generation (especially n-fold jackknifing on training data). ## second-order treecrf this work substantially extends the biaffine parser in two closely related aspects: using probabilistic treecrf for structural training and explicitly incorporating high-order subtree scores. specifically, we further incorporate adjacent-sibling subtree scores into the basic first-order model: 3 s(x, y) = @xmath5, j)+ @xmath6,j}∈y s(i, k, j) (6) figure 3: diagrams of the second-order inside algorithm based on bottom-up dynamic programming. ## related works batchification has been widely used in linear-chain crf, but is rather complicated for tree structures. @xcite presents a theoretical proof on the equivalence of outside and back-propagation for constituent tree parsing, and also briefly discusses other formalisms such as dependency grammar. unfortunately, we were unaware of eisner's great work until we were surveying the literature for paper writing. as an empirical study, we believe this work is valuable and makes it practical to deploy treecrf models in real-life systems. @xcite present a nice analytical work on dependency parsing, similar to @xcite on constituency parsing. by extending the first-order graph-based parser of @xcite into second-order, they try to find out how much structural context is implicitly captured by the bilstm encoder. they concatenate three bilstm output vectors (i, k, j) for scoring adjacent-sibling subtrees, and adopt maxmargin loss and the second-order eisner decoding algorithm @xcite . based on their negative results and analysis, they draw the conclusion that high-order modeling is redundant because bilstm can implicitly and effectively encode enough structural context. they also present a nice survey on the relationship between rnns and syntax. in this work, we use a much stronger basic parser and observe more significant uas/las improvement than theirs. particularly, we present an in-depth analysis showing that explicitly highorder modeling certainly helps the parsing model and thus is complementary to the bilstm encoder. @xcite employ graph neural networks to incorporate high-order structural information into the biaffine parser implicitly. they add a threelayer graph attention network (gat) component @xcite between the mlp and biaffine layers. the first gat layer takes r h i and r m i from mlps as inputs and produces new representation r h1 ## conclusions this paper for the first time presents second-order treecrf for neural dependency parsing using triaffine for explicitly scoring second-order subtrees. we propose to batchify the inside algorithm to accommodate gpus. we also empirically verify that the complex outside algorithm can be implicitly performed via efficient back-propagation, which naturally produces gradients and marginal probabilities. we conduct experiments and detailed analysis on 27 datasets from 13 languages, and find that structural learning and high-order modeling can further enhance the state-of-the-art biaffine parser in various aspects: 1) better convergence behavior; 2) higher performance on sub-and full-tree levels; 3) better utilization of partially annotated data.