Reorder and then Parse, Fast and Accurate Discontinuous Constituency Parsing (2022)

Abstract: Discontinuous constituency parsing is still kept developing for its efficiency and accuracy are far behind its continuous counterparts. Motivated by the observation that a discontinuous constituent tree can be simply transformed into a pseudo-continuous one by artificially reordering words in the sentence, we propose a novel reordering method, thereby construct fast and accurate discontinuous constituency parsing systems working in continuous way. Specifically, we model the relative position changes of words as a list of actions. By parsing and performing this actions, the corresponding pseudo-continuous sequence is derived. Discontinuous parse tree can be further inferred via integrating a high-performance pseudo-continuous constituency parser. Our systems are evaluated on three classical discontinuous constituency treebanks, achieving new state-of-the-art on two treebanks and showing a distinct advantage in speed.

## introduction constituency parses represent the syntactic structure by hierarchical constituent trees, which decompose the sentence into constituents and establish hierarchical relations between constituents and words @xcite . in continuous constituent trees, the sequence of words that compose the constituent must be contiguous. this type of structure is enough for representing most of the syntactic structure @xcite and has been extensively studied. nevertheless, some syntactic phenomena, such as long-distance dependencies and extractions, require discontinuous words to form a constituent, which have been argued to be unavoidable @xcite @xcite . ## related work syntax shows its effect in language understanding @xcite @xcite @xcite . discontinuous constituency parsing, as a special constituency parsing form has drawn much attention. grammar-based method inheriting and expanding the grammar-based methods of continuous constituency parsing, mildly context-sensitive grammar such as linear context-free rewriting systems (lcfrs) @xcite and multiple context-free grammars (mcfgs) @xcite has been applied for discontinuous parsing, which has higher parsing complexity than its continuous counterpart. for example, the complexity of accurate cky-style lcfrs is o(n 3•fan-out ), where grammar-specific fan-out is greater than 1 @xcite . to reduce the limit on the sentence length, @xcite proposes a supertagging-based parser for lcfrs. however, there is still a considerable gap in speed and accuracy between discontinuous parsing and continuous parsing. span-based method in continuous constituency parsing, span-based methods generally excel in both speed and accuracy @xcite @xcite . spanbased methods are also proposed for discontinuous constituency parsing @xcite , but their discontinuous accuracy is not good enough. through error analysis, @xcite concludes that compared to transition-based parser, span-based parser has less fine-grained features which are particularly helpful for predicting discontinuous constituents. thus, first converting the discontinuous tree into a pseudocontinuous one and then utilizing span-based parser may be a better choice. transition-based method in continuous constituency parsing, transition-based methods based on shift-reduce strategy @xcite are widely used. some works propose to add specific transition actions to change the order of words @xcite for discontinuous parsing. however, this type of extension may make transition sequences so long that affecting efficiency and accuracy. to alleviate this problem, methods of dealing directly with discontinuous sequences @xcite and designing new data structures and corresponding actions @xcite al., pseudo-continuous constituency parser action graph parser original sentence 𝑋 = 𝑤 ! , 𝑤 " , 𝑤 # , 𝑤 @xmath0 , @xmath1, 𝑤 # , 𝑤 $ , 𝑤 " pseudo-continuous constituent tree ' 𝑌 id list @xmath2, 3, 4, 2] discontinuous constituent tree 𝑌 reorder discontinuous constituency treebank {𝑋 : 𝑌} pseudo-continuous constituency treebank { ' 𝑋 : ' 𝑌} action graph dataset {𝑋 : 𝐺} model the relative word position changes between 𝑋 and " 𝑋 train train restore order by id list 2019; @xcite are used to reduce the length of the transition sequence. these methods are indeed effective, but there is still room for improvement in terms of speed and accuracy. conversion-based method several works also aim to convert discontinuous constituency parsing to a simpler task. for example, some works reduce discontinuous constituency parsing to nonprojective dependency parsing by encoding the constituents to arc labels @xcite , while vilares and gómez-rodríguez (2020) converts the task to sequence tagging by representing the discontinuous tree as a sequence of tag. in this work, we convert the discontinuous parsing task into continuous parsing task by modeling, parsing and presenting the words relocating actions, and thus reduce the complexity of the problem. ## method the flow of our system foot_0 is shown in figure 2 . in data pre-processing stage, we first build a pseudocontinuous constituency treebank based on discontinuous treebank by reordering the words in the sentences. the reordering strategy is consistent with @xcite and is described in detail in appendix a. then, we construct an action graph dataset based on our action schema by modeling the relative position changes of words as action edges. in training stage, we train an action graph parser on the action graph dataset and a pseudo-continuous constituency parser on the pseudo-continuous treebank. in prediction stage, we first parse the original sentence: x into action graph: g. then, we propose an algorithm which derives the reordered sequence: x and the id list: orders from x by performing actions in g. x is then used as input to the pseudo-continuous constituency parser for pseudo-continuous tree ŷ pars-ing. finally, orders which indicates the original positions of the words in x, is used for discontinuous tree y restoration. ## conclusion in this work, we build fast and accurate discontinuous constituency parsing systems working in continuous way by innovatively propose a novel reordering method. results show that our method is able to preserve the high performance of the pseudo-continuous constituency parser with high efficiency. we not only achieve state-of-the-art results on two treebanks, but also demonstrate that the bottleneck of discontinuous constituency parsing is reordering.