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

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 2753–2764, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 2753 Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n6) down to O(n3) Caio Corro⇤ Université Paris-Saclay, CNRS, LIMSI, 91400, Orsay, France. caio.corro@limsi.fr Abstract We introduce a novel chart-based algorithm for span-based parsing of discontinuous con- stituency 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(n6) down to O(n3). The cu- bic time variant covers 98% of constituents ob- served in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on Ger- man 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. 1 Introduction Syntactic parsing aims to recover the latent syn- tactic relations between words in a sentence, ex- pressed 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. Con- stituency trees can broadly be classified into two categories. On the one hand, in a continuous con- stituent tree, each node must dominate a contiguous sequence of words.1 On the other hand, in a dis- continuous constituent tree, a node can dominate a non-contiguous sequence of words. It has been argued that modeling discontinuity is unavoidable, see for example McCawley (1982) and Bunt et al. (1987) for English and Müller (2004) for German. Phrase-structure grammars have been proposed to parse and generate constituency trees. For ex- ⇤Work partially done while the author was a postdoc at University of Amsterdam with Ivan Titov. 1The set of words that a node dominates is the set of leaf nodes in the subtree for which this node is the root. ample, Context-Free Grammars (CFG) are able to process continuous constituent trees whereas Mul- tiple Context Free Grammars (Seki et al., 1991, MCFG) and Linear Context-Free Rewriting Sys- tem (Vijay-Shanker et al., 1987, LCFRS) 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 al- gorithms based on dynamic programming: parsing a sentence of length n is a O(gn3) problem where g is a grammar related constant (Kasami, 1966; Younger, 1967; Cocke, 1969). However, parsing algorithms for MCFGs and LCFRSs are deemed to be impractical despite their polynomial-time com- plexity (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 (Kallmeyer and Maier, 2010; Evang and Kallmeyer, 2011; Maier et al., 2012; Kuhlmann and Nivre, 2006). Advances in machine learning led to the devel- opment …

Content truncated to 500 words