Reorder and then Parse, Fast and Accurate Discontinuous Constituency Parsing

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 10575 - 10588 December 7-11, 2022 ©2022 Association for Computational Linguistics Reorder and then Parse, Fast and Accurate Discontinuous Constituency Parsing Kailai Sun1,2, Zuchao Li3,∗, and Hai Zhao1,2,∗ 1Department of Computer Science and Engineering, Shanghai Jiao Tong University 2MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University 3School of Computer Science, Wuhan University kaishu2.0@sjtu.edu.cn, zcli.charlie@gmail.com, zhaohai@cs.sjtu.edu.cn Abstract Discontinuous constituency parsing is still kept developing for its efficiency and accuracy are far behind its continuous counterparts. Moti- vated by the observation that a discontinuous constituent tree can be simply transformed into a pseudo-continuous one by artificially reorder- ing words in the sentence, we propose a novel reordering method, thereby construct fast and accurate discontinuous constituency parsing systems working in continuous way. Specif- ically, we model the relative position changes of words as a list of actions. By parsing and per- forming this actions, the corresponding pseudo- continuous sequence is derived. Discontinuous parse tree can be further inferred via integrat- ing a high-performance pseudo-continuous con- stituency parser. Our systems are evaluated on three classical discontinuous constituency tree- banks, achieving new state-of-the-art on two treebanks and showing a distinct advantage in speed. 1 Introduction Constituency parses represent the syntactic struc- ture by hierarchical constituent trees, which de- compose the sentence into constituents and estab- lish hierarchical relations between constituents and words (Corro, 2020). In continuous constituent trees, the sequence of words that compose the con- stituent must be contiguous. This type of structure is enough for representing most of the syntactic structure (Fernández-González et al., 2021a) and has been extensively studied. Nevertheless, some syntactic phenomena, such as long-distance dependencies and extractions, re- quire discontinuous words to form a constituent, which have been argued to be unavoidable (Mc- Cawley, 1982; Bunt et al., 1987; Müller, 2004). Thus, discontinuous constituent trees with crossing ∗Corresponding author. This work was supported by Key Projects of National Natural Science Foundation of China (U1836222 and 61733011). So what is a parent to do ? RB WP VBZ DT NN TO VB . WHNP NP VP VP SQ So what do to is a parent ? RB WP VB TO VBZ DT NN . WHNP NP VP VP SQ SBARQ SBARQ Figure 1: An example of converting a discontinuous tree into a pseudo-continuous one. branches are introduced to describe all the syntactic phenomena present in human language. Compared to continuous constituency parsing, discontinuous parsing is a more complicated prob- lem, so that the high computational cost is par- ticularly prominent. Many researches (Ruprecht and Mörbitz, 2021; Coavoux and Crabbé, 2017; Coavoux et al., 2019) have focused on how to re- duce the time complexity of discontinuous parsing algorithm to reduce or get rid of the constraint of sentence length. Based on the observation that a discontinuous tree can be converted into a pseudo-continuous one by simply reordering the words in the sentence, as an example in Figure 1, and the advantage that parsing a …

Content truncated to 500 words