Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O (nˆ6) down to O (nˆ3) (2020)

Abstract: We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(nˆ6) down to O(nˆ3). The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and Bert-based neural networks.

## introduction syntactic parsing aims to recover the latent syntactic relations between words in a sentence, expressed in a given syntactic formalism. in this paper, we focus on constituency trees where the syntactic structure is described by the means of a hierarchical structure composed of nodes: words are leaf nodes whereas internal nodes represent labeled constituents or phrases, see figure 1 . constituency trees can broadly be classified into two categories. on the one hand, in a continuous constituent tree, each node must dominate a contiguous sequence of words. 1 on the other hand, in a discontinuous constituent tree, a node can dominate a non-contiguous sequence of words. it has been argued that modeling discontinuity is unavoidable, see for example @xcite and @xcite for english and @xcite for german. phrase-structure grammars have been proposed to parse and generate constituency trees. for ex-ample, context-free grammars (cfg) are able to process continuous constituent trees whereas multiple context free grammars @xcite and linear context-free rewriting system @xcite are able to process discontinuous constituent trees. cfgs have been widely studied for practical parsing due to the availability of time-efficient chart-based parsing algorithms based on dynamic programming: parsing a sentence of length n is a o(gn 3 ) problem where g is a grammar related constant @xcite @xcite . however, parsing algorithms for mcfgs and lcfrss are deemed to be impractical despite their polynomial-time complexity (see section 2). therefore, most of the experimental work in this field has been limited to parsing short sentences, e.g. sentences that contain less than 40 words @xcite @xcite . advances in machine learning led to the development of constituency parsers that are no longer based on phrase-structure grammars. instead, the prediction step only ensures the well-formedness of the resulting structure and does not enforce compliance of the syntactic content represented by the structure. for example, a verbal phrase is not constrained to contain a verb. as such, they can be assimilated to the mainstream approach to bi-lexical dependency parsing where one considers candidate outputs only in a restricted class of graphs: non-projective @xcite , projective @xcite or bounded block degree and wellnested spanning aborescences @xcite @xcite , among others @xcite @xcite . these approaches assume that intricate relations in the syntactic content can be implicitly learned by the scoring function. span-based parsing is a grammarless approach to constituency parsing that decomposes the score of a tree solely into the score of its constituents, originally proposed for continuous constituency parsing @xcite @xcite . 2 recovering the highest scoring tree can be done exactly using a slightly updated cyk algorithm or using inexact foot_1 methods like top-down or transition based algorithms. this approach has obtained state-of-the art results for continuous constituency parsing @xcite @xcite . in this work, we propose the first span-based parser with an exact decoding algorithm for discontinuous constituent parsing. to this end, we introduce a novel exact chart-based algorithm based on the parsing-as-deduction formalism @xcite ) that can parse constituent trees with a block degree of two, including ill-nested structures (see section 3), which have been argued to be unavoidable to model natural languages (chen-main and joshi, 2010). therefore, our constituency parser is closely related to the dependency parser of @xcite . despite its o(n 6 ) time-complexity, where n is the length of the input sentence, our algorithm is reasonably fast: in our experiments, all treebanks can be parsed without removing long sentences. moreover, we observe that several deduction rules are of little use to retrieve trees present in treebanks. therefore, we experiment with variants of the algorithm where we remove specific deduction rules. this leads to parsing algorithms with lower asymptotic complexity that experimentally produce accurate parses. importantly, we show that a specific form of discontinuity can be parsed in o(n 3 ), that is with the same asymptotic complexity as continuous constituency parsing. our main contributions can be summarized as follows: we release the c++/python implementation of the parser. foot_2 phrase-structure grammars: the lcrfs formalism has been widely used in the context of discontinuous constituency parsing, although mcfg and simple range concatenation grammars @xcite have been shown to be equivalent, see @xcite and @xcite . @xcite introduced the first practical chart-based lcfrs parser for german, which was subsequently applied to english @xcite . however, they restrict their data to sentences that contain less than 25 words. to improve parsing time, @xcite proposed an experimentally faster parser based on the a ⇤ search algorithm together with a block degree two restriction. however, they still limit the sentence size to a maximum of 40 words. a single sentence of 40 words takes around 3 minutes to be parsed, an impressive improvement over the parser of @xcite that needs several hours, but still prohibitively slow for large scale parsing. concurrently to this work, stanojević and steedman (2020) proposed a span based grammar-less lcfrs parser. they also explored the well-nested variants. graph based parsing: a different line of work proposed to explore constituency parsing as a dependency parsing problem. 5 in other words, even if it is straightforward to represent constituency trees as hierarchical phrase structures, the same syntactic content can be represented with different mathematical objects @xcite , including directed graphs commonly used for de50 100 150 0 0.5 1 1.5 sentence length seconds per sentence o(n 3 ) o(n 4 ) figure 2: execution time per sentence length of the chart-based algorithm for the o(n 3 ) (solid line) and o(n 4 ) (dashed lines) variants. transition systems: lastly, transition-based parsers have been proposed, based on the idea of the swap transition for non-projective dependency parsing @xcite , see @xcite and following work based on shift-reduce strategy @xcite @xcite ). these systems rely on the fact that a discontinuous tree can be transformed into a continuous one by changing word order in the input sentence. they do not require strong independence assumption on the scoring model which can be useful to encode richer information, especially for long-distance relationships. however, the number of transitions required to parse discontinuities can impact prediction accuracy. to alleviate this problem, two different approaches have been explored: @xcite introduced a two-stack system coupled with a gap transition and @xcite proposed the shift-i transition to access non-local elements directly, therefore reducing the number of transitions. in exchange for a rich parameterization, transition systems lose optimality guarantees with respect to the scoring model and rely on greedy or beam-search decoding. these approaches achieve state-of-theart results while being fast at test time @xcite . on the contrary, our approach is exact with respect to the scoring model, i.e. it will always return the highest scoring structure. search space restriction: previous work in constituency and dependency parsing proposed to restrict the search space to improve time complexity while at the same time ensuring a good coverage of data. @xcite proposed an al-gorithm that parses a subclass of tree adjoining grammar in o(n 5 ) instead of o(n 6 ). our parsing algorithm is highly related to the dependency parser of @xcite and the restricted variant of the latter introduce by @xcite . ## parsing algorithm we describe our algorithm using the parsing-asdeduction framework @xcite ). as such, our description is independent of the value one wants to compute, whether it be the (k-)best derivation(s), the partition function or span marginals @xcite . 7 however, we will focus on argmax decoding. we are interested in constituency trees of block degree two, including ill-nested trees. the block degree two constraint is satisfied if each node dominate at most two disjoint sequences of words. let w 1 ...w n be a sentence. a constituency tree for this sentence is ill-nested if it contains two nodes dominating disjoint sets of words w (1) and w (2) such that there exists w i , w j 2 w (1) and w k , w l 2 w (2) such that @xmath0. filtering: contrary to cfgs and lcfrs ckystyle parsers, there is no side-condition constraining allowed derivations in span-based parsers. the label of a constituent is independent of the label of its children. binarization: interestingly, span-based parsers do not require explicit binarization of the constituency structure. although grammar based parsers require binarization of the grammar production rules and therefore of the constituency structure to ensure tractable complexity, span-based parsers can take care of binarization implicitly by introducing a supplementary constituency label with a fixed null score. unary rules: we follow @xcite and merge unary chains into a single constituent with a new label, e.g. the chain sbarq ! sq will result in a single constituent labeled sbarq_sq. ## experiments we experiment on the discontinuous penn treebank @xcite with standard split, the tiger treebank @xcite with the spmrl 2014 shared task split @xcite and the negra treebank @xcite with the split proposed by @xcite . 8 without loss of generality, we assume the label d is not null. although it could be without changing the overall idea, we would just add an extra way to do implicit binarization that can already be handled with rule (a). 9 this idea of breaking up simultaneous tests in a deduction rule has been previously proposed for improving time complexity of lexicalized grammar parsers @xcite 4.1 data coverage one important question is whether our parser has a good coverage of the dataset as we can only retrieve constituents of block degree one and two. we report the maximum recall that our parser can achieve in its different variants in first, we observe that our cubic time parser can recover 98% of all constituents in the three treebanks, or around 80% of constituents of block degree of exactly two. second, the o(n 5 ) variant of the parser can recover more than 99% of all treebanks, and, interestingly, there is almost no coverage change when moving to the full deduction system. if we consider the parsers with wellnested restriction, the o(n 5 ) and o(n 6 ) variants have the same coverage in german datasets and the latter can only recover 2 additional constituents in the english treebanks. if we include ill-nested construction, the difference is either 2 (dptb and negra) or 8 (tiger) constituents. in practice, we observed that both o(n 5 ) and o(n 6 ) variants predict the same analysis. ## conclusion we proposed a novel family of algorithms for discontinuous constituency parsing achieving stateof-the art results. importantly, we showed that a specific set of discontinuous constituent trees can be parsed in cubic time while covering most of the linguistic structures observed in treebanks. despite being based on chart-based algorithms, our approach is fast at test time and we can parse all sentences without pruning or filtering long sentences. future research could explore neural architectures and training losses tailored to our approach.