Don’t Parse, Choose Spans! Continuous and Discontinuous Constituency Parsing via Autoregressive Span Selection (2023)

Abstract: We present a simple and unified approach for both continuous and discontinuous constituency parsing via autoregressive span selection. Constituency parsing aims to produce a set of non-crossing spans so that they can form a constituency parse tree. We sort gold spans using a predefined order and leverage a pointer network to autoregressively select spans by that order. To deal with discontinuous spans, we consecutively select their subspans from left to right, label all but last subspans with special discontinuous labels and the last subspan as the whole discontinuous spans’ labels. We use simple heuristic to output valid trees so that our approach is able to predict all possible continuous and discontinuous constituency trees without sacrificing data coverage and without the need to use expensive chart-based parsing algorithms. Experiments on multiple continuous and discontinuous benchmarks show that our model achieves state-of-the-art or competitive performance.

## introduction constituency parsing is a fundamental task in natural language processing, having many applications in downstream tasks such as language modeling @xcite and machine translation @xcite . continuous constituency parsing is not capable of capturing discontinuous language phenomena, such as wh-movements and extraposition, which are deemed unavoidable in syntactic analysis @xcite @xcite . discontinuous constituency parsing enables modeling these phenomena by allowing each constituent node governing nonadjacent strings in the yields, resulting in discontinuous parse trees as exemplified in fig. 1 we study both continuous and discontinuous constituency parsing under a unified framework. both continuous and discontinuous parsing can be framed as span prediction problems. in continuous parsing, each span corresponds to a single interval (of the observed sentence), while in discontinuous parsing a discontinuous span could correspond to multiple nonadjacent intervals, the number of which we refer to as fan-out. fig. 1 shows the span representations of both types of parse trees. based on span representations, span-based methods decompose the score of a parse tree into scores of spans, scoring all possible spans and finding the best parse with dynamic programming algorithms. they have achieved high accuracy in both continuous parsing @xcite @xcite and discontinuous parsing @xcite . however, they have several issues: • their strong conditional independence assumption is problematic. span-based methods score each span independently for global training and decoding, hoping that powerful neural encoders could capture sufficient contextual information for parsing. however, @xcite show that independent local span scoring is suboptimal and they propose auxiliary training objectives to inject non-local features into neural span-based continuous parsing. in discontinuous parsing, span-based parsers impose even stronger conditional independence assumptions when scoring discontinuous spans to alleviate high space and time complexities, 2 which exacerbates the issue of insufficient modeling of non-local contextual information. current span-based discontinuous parsers can only deal with discontinuous spans of fan-out of at most two due to high parsing time complexity, thereby having limited data coverage. for instance, the most expressive variant of lcfrs-2 @xcite can only cover up to 87% discontinuous spans in the negra treebank, greatly upper-bounding the prediction performance on discontinuous constituents. in this work, we present a simple yet effective approach to address all aforementioned problems via autogressive span selection. 4 to solve the first issue, we sort gold spans by a predefined order and train a pointer network @xcite to autoregressively choose spans by that order. as such, the independence assumption of span-based parsing is weakened due to the existence of the autoregressive neural decoder, which captures span correlations in a similar way to @xcite and yang and tu (2022) (but see section 4 for how our method differs from theirs). to solve the second issue, we devise a simple strategy of decoding discontinuous spans that consecutively selects all continuous subspans of a discontinuous span from left to right and labels all but the last subspans with a special discontinuous label and the last subspan with the label of the entire discontinuous span. as such, we can connect an arbitrary number of subspans to obtain a discontinuous span, so we can decode discontinuous spans of arbitrary fanout and thus arbitrary discontinuous constituency parse trees, enjoying perfect data coverage. for the third issue, we find a frustratingly simple and fairly fast strategy that works quite well. concretely, we use greedy decoding to output spans in an unconstrained manner and use a heuristic to resolve possible inconsistency (i.e., two spans crossing each other) afterwards by simply discarding conflicting spans. since o(n) spans are needed to decode, our method needs linear steps for parsing, thus is efficient. in continuous parsing, this simple strategy combined with our autoregressive neural decoder works even better than global cky decoding in our experiments. in discontinuous parsing, it removes the need to use expensive chart-based algorithms for decoding, greatly reducing the computational complexity. we conduct extensive experiments on benchmarks, achieving state-of-the-art performance on ptb and competitive performance on ctb for continuous parsing; and state-of-the-art performance on three benchmarks: tiger, negra, and dptb for discontinuous parsing. ## conclusion in this work, we have presented a simple yet effective method for both continuous and discontinuous constituency parsing. we showed that an autoregressive decoder is more desirable than global cky decoding in span-based continuous parsing, and with a simple labeling mechanism, we obtained state-of-the-art performance in discontinuous parsing.