Dependency Parsing as MRC -based Span-Span Prediction (2022)

Abstract: Higher-order methods for dependency parsing can partially but not fully address the issue that edges in dependency trees should be constructed at the text span/subtree level rather than word level. In this paper, we propose a new method for dependency parsing to address this issue. The proposed method constructs dependency trees by directly modeling span-span (in other words, subtree-subtree) relations. It consists of two modules: the text span proposal module which proposes candidate text spans, each of which represents a subtree in the dependency tree denoted by (root, start, end); and the span linking module , which constructs links between proposed spans. We use the machine reading comprehension (MRC) framework as the backbone to formalize the span linking module, where one span is used as query to extract the text span/subtree it should be linked to. The proposed method has the following merits: (1) it addresses the fundamental problem that edges in a dependency tree should be constructed between subtrees; (2) the MRC framework allows the method to retrieve missing spans in the span proposal stage, which leads to higher recall for eligible spans. Extensive experiments on the PTB, CTB and Universal Dependencies (UD) benchmarks demonstrate the effectiveness of the proposed method. The code is available at https://github.com/ShannonAI/mrc-for-dependency-parsing

## introduction dependency parsing is a basic and fundamental task in natural language processing (nlp) @xcite @xcite . among existing efforts for dependency parsers, graph-based models @xcite are a widely used category of models, which cast the task as finding the optimal maximum spanning tree in the directed graph. graph-1 chun fan is the corresponding author. 2 the code is available at https://github.com/ shannonai/mrc-for-dependency-parsing i love tim's cat nsubj nmod obj root i love tim's cat nsubj obj obj root figure 1: two possible dependency trees for sentence "i love tim's cat". for the tree on the right hand side, if we look at the token-token level, 'love" being linked to "cat" is correct. but at the subtree-subtree level, the linking is incorrect since the span/subtree behind "cat" is incorrect. to address this challenge, in this work, we propose a model for dependency parsing that directly operates at the span-span relation level. the proposed model consists of two modules: (1) the text span proposal module which proposes eligible candidate text spans, each of which represents a subtree in the dependency tree denoted by (root, start, end); (2) and the span linking module, which constructs links between proposed spans to form the final dependency tree. we use the machine reading comprehension (mrc) framework as the backbone to formalize the span linking module in an mrc setup, where one span is used as a query to extract the text span/subtree it should be linked to. in this way, the proposed model is able to directly model span-span relations and build the complete dependency tree in a bottom-up recursive manner. the proposed model provides benefits in the following three aspects: (1) firstly, it naturally addresses the shortcoming of token-token modeling in vanilla graph-based approaches and directly performs at the span level; (2) with the mrc framework, the left-out spans in the span proposal stage can still be retrieved at the span linking stage, and thus the negative effect of unextracted spans can be alleviated; and (3) the mrc formalization allows us to take advantage of existing state-of-the-art mrc models, with which the model expressivity can be enhanced, leading to better performances. we are able to achieve new sota performances on ptb, ctb and ud benchmarks, which demonstrate the effectiveness of the proposed method. ## related work transition-based dependency parsing incrementally constructs a dependency tree from input words through a sequence of shift-reduce actions @xcite @xcite @xcite @xcite . graph-based dependency parsing searches through the space of all possible dependency trees for a tree that maximizes a specific score @xcite @xcite . graph-based dependency parsing is first introduced by @xcite . they formalized the task of dependency parsing as finding the maximum spanning tree (mst) in directed graphs and used the large margin objective @xcite to efficiently train the model. @xcite introduced a probabilistic convolutional neural network (cnn) for graph-based dependency parsing to model third-order dependency informa-tion @xcite ; @xcite proposed to employ lstms as an encoder to extract features, which are then used to score dependencies between words. @xcite ; @xcite ; wang and tu (2020) integrated higher-order features across adjacent dependency edges to build the dependency tree. @xcite captured high-order dependency information by using graph neural networks. the biaffine approach @xcite is a particular kind of graph-based method improving upon vanilla scoring functions in graph-based dependency parsing. @xcite combined biaffine classifiers and pointer networks to build dependency trees in a top-down manner. jia et al. (2020); zhang et al. (2020) extended the biaffine approach to the conditional random field (crf) framework. mrini et al. (2020) incorporated label information into the self-attention structure @xcite for biaffine dependency parsing. ## ablation study and analysis we use ptb to understand behaviors of the proposed model. as projective decoding works best for ptb, scores reported in this section are all from projective decoding.