Discontinuous Constituent Parsing as Sequence Labeling (2020)

Abstract: This paper reduces discontinuous parsing to sequence labeling. It first shows that existing reductions for constituent parsing as labeling do not support discontinuities. Second, it fills this gap and proposes to encode tree discontinuities as nearly ordered permutations of the input sequence. Third, it studies whether such discontinuous representations are learnable. The experiments show that despite the architectural simplicity, under the right representation, the models are fast and accurate.

## introduction discontinuous constituent parsing studies how to generate phrase-structure trees of sentences coming from non-configurational languages @xcite , where non-consecutive tokens can be part of the same grammatical function (e.g. nonconsecutive terms belonging to the same verb phrase). figure 1 shows a german sentence exhibiting this phenomenon. discontinuities happen in languages that exhibit free word order such as german or guugu yimidhirr @xcite , but also in those with high rigidity, e.g. english, whose grammar allows certain discontinuous expressions, such as wh-movement or extraposition @xcite . this makes discontinuous parsing a core computational linguistics problem that affects a wide spectrum of languages. there are different paradigms for discontinuous phrase-structure parsing, such as chart-based parsers @xcite , transitionbased algorithms @xcite or reductions to a problem of a different nature, such as dependency parsing @xcite . however, many of these approaches come either at a high complexity or low figure 1 : an example of a german sentence exhibiting discontinuous structures, extracted from the negra treebank @xcite . a valid english translation is: 'never before i have chosen so much.' related to these research aspects, this work explores the feasibility of discontinuous parsing under the sequence labeling paradigm, inspired by @xcite 's work on fast and simple continuous constituent parsing. we will focus on tackling the limitations of their encoding functions when it comes to analyzing discontinuous structures, and include an empirical comparison against existing parsers. contribution (i) the first contribution is theoretical: to reduce constituent parsing of free word order languages to a sequence labeling problem. this is done by encoding the order of the sentence as (nearly ordered) permutations. we present various ways of doing so, which can be naturally combined with the labels produced by existing reductions for continuous constituent parsing. (ii) the second contribution is a practical one: to show how these representations can be learned by neural transducers. we also shed light on whether general-purpose architectures for nlp tasks @xcite can effectively parse free word order languages, and be used as an alternative to adhoc algorithms and architectures for discontinuous constituent parsing. ## related work discontinuous phrase-structure trees can be derived by expressive formalisms such as multiple context free grammmars @xcite (mcfgs) or linear context-free rewriting systems (lcfrs) @xcite . mcfgs and lcfrs are essentially an extension of context-free grammars (cfgs) such that non-terminals can link to non-consecutive spans. traditionally, chart-based parsers relying on this paradigm commonly suffer from high complexity @xcite @xcite . let k be the block degree, i.e. the number of nonconsecutive spans than can be attached to a single non-terminal; the complexity of applying cyk (after binarizing the grammar) would be o(n 3k ) @xcite , which can be improved to o(n 2k+2 ) if the parser is restricted to well-nested lcfrs @xcite , and @xcite discusses how for a standard discontinuous treebank, k ≈ 3 (in contrast to @xmath0. recently, corro (2020) presents a chart-based parser for @xmath1, which is equivalent to the running time of a continuous chart parser, while covering 98% of the discontinuities. also recently, @xcite present an lcfrs parser with @xmath2, where l is the number of unique non-terminal symbols, but in practice they show that the empirical running time is among the best chart-based parsers. differently, it is possible to rely on the idea that discontinuities are inherently related to the location of the token in the sentence. in this sense, it is possible to reorder the tokens while still obtaining a grammatical sentence that could be parsed by a continuous algorithm. this is usually achieved with transition-based parsing algorithms and the swap transition @xcite which switches the topmost elements in the stack. for instance, versley (2014) uses this transition to adapt an easy-first strategy @xcite for dependency parsing to discontinuous constituent parsing. in a similar vein, @xcite builds on top of a fast continuous shift-reduce constituent parser @xcite , and incorporates both standard and bundled swap transitions in order to analyze discontinuous constituents. maier's system produces derivations of up to a length of n foot_0 -n + 1 given a sentence of length n. more efficiently, @xcite present a transition system which replaces swap with a gap transition. the intuition is that a reduction does not need to be always applied locally to the two topmost elements in the stack, and that those two items can be connected, despite the existence of a gap between them, using non-local reductions. their algorithm ensures an upper-bound of n(n-1) 2 transitions. 2 with a different optimization goal, @xcite removed the traditional reliance of discontinuous parsers on averaged perceptrons and hand-crafted features for a recursive neural network approach that guides a swap-based system, with the capacity to generate contextualized representations. @xcite replace the stack used in transition-based systems with a memory set containing the created constituents. this model allows interactions between elements that are not adjacent, without the swap transition, to create a new (discontinuous) constituent. trained on a 2 stacked bilstm transducer, the model is guaranteed to build a tree with in 4n-2 transitions, given a sentence of length n. a middle ground between explicit constituent parsing algorithms and this paper is the work based on transformations. for instance, @xcite convert constituent trees into a nonlinguistic dependency representation that is learned by a transition-based dependency parser, to then map its output back to a constituent tree. a similar approach is taken by @xcite , but they proposed a more compact representation that leads to a much reduced set of output labels. other authors such as @xcite propose a two-step approach that approximates discontinuous structure trees by parsing context-free grammars with generative probabilistic models and transforming them to discontinuous ones. @xcite cast discontinuous phrase-structure parsing into a framework that jointly performs supertagging and non-projective dependency parsing by a reduction to the generalized maximum spanning arborescence problem @xcite . the recent work by @xcite can be also framed within this paradigm. they essentially adapt the work by @xcite and replace the averaged perceptron classifier with pointer networks @xcite , adressing the problem as a sequence-to-sequence task (for dependency parsing) whose output is then mapped back to the constituent tree. and next, fernández-gonzález and gómez-rodríguez (2020b) extended pointer networks with multitask learning to jointly predict constituent and dependency outputs. in this context, the closest work to ours is the reduction proposed by @xcite , who cast continuous constituent parsing as sequence labeling. 3 in the next sections we build on top of their work and: (i) analyze why their approach cannot handle discontinuous phrases, (ii) extend it to handle such phenomena, and (iii) train functional sequence labeling discontinuous parsers. ## preliminaries let @xmath3, w 1 , ..., w |w|-1 ] be an input sequence of tokens, and t |w| the set of (continuous) constituent trees for sequences of length |w|; @xcite define an encoding function φ : t |w| → l |w| to map continuous constituent trees into a sequence of labels of the same length as the input. each label, l @xmath4, is composed of three components l @xmath5, x i , u i ): figure 2 illustrates the encoding on a continuous example. john likes the movie . noun verb det noun punct s vp np np (1,s,np) (1,vp,) (1,np,) (-2,s,) () (1,s,np) (2,vp,) (3,np,) (1,s,) () with n i with abs(n i ) figure 2 : an example of a continuous tree encoded according to @xcite . incompleteness for discontinuous phrase structures gómez-rodríguez and vilares proved that φ is complete and injective for continuous trees. however, it is easy to prove that its validity does not extend to discontinuous trees, by using a counterexample. figure 3 shows a minimal discontinuous tree that cannot be correctly decoded. the inability to encode discontinuities lies on the assumption that w i+1 will always be attached to a node belonging to the path from the root to w i (n i is then used to specify the location of that node in the path). this is always true in continuous trees, but not in discontinuous trees, as can be seen in figure 3 where c is the child of a constituent that does not lie in the path from s to b. figure 3 : a minimal discontinuous constituent tree that cannot be decoded correctly if we rely on the @xcite linearization. ## encoding nearly ordered permutations next, we fill this gap to address discontinuous parsing as sequence labeling. we will extend the encoding φ to the set of discontinuous constituent trees, which we will call t |w| . the key to do this relies on a well-known property: a discontinuous tree @xmath6.g. the trees at the left and the right in figure 4 ). 5 we will call this tree the (canonical) continuous arrangement of t, ω(t) ∈ t |w| . thus, if given an input sentence we can generate the position of every word as a terminal in ω(t), the existing encodings to predict continuous trees as sequence labeling could be applied on ω(t). in essence, this is learning to predict a permutation of w. as introduced in §2, the concept of location of a token is not a stranger in transition-based discontinuous parsing, where actions such as swap switch the position of two elements in order to create a discontinuous phrase. we instead propose to explore how to handle this problem in end-to-end sequence labeling fashion, without relying on any parsing structure nor a set of transitions. to do so, first we denote by τ : {0, . . . , |w| -1} → {0, . . . , |w| -1} the permutation that maps the position i of a given w i in w into its position as a terminal node in ω(t). 6 from this, one can derive π : w @xmath7, a function that encodes a permutation of w in such way that its phrase structure does not have crossing branches. for continuous trees, τ and π are identity permutations. then, we extend the tree encoding function φ to φ : the crux of defining a viable encoding for discontinuous parsing is then in how we encode τ as a sequence of values p i , for @xmath8. . . |w| -1. while the naive approach would be the identity encoding (p @xmath9, we ideally want an encoding that balances minimizing sparsity (by minimizing infrequently-used values) and maximizing learnability (by being predictable). to do so, we will look for encodings that take advantage of the fact that discontinuities in attested syntactic structures are mild @xcite , i.e., in most cases, τ (i + 1) = τ (i) + 1. in other words, permutations τ corresponding to real syntactic trees tend to be nearly ordered permutations. based on these principles, we propose below a set of concrete encodings, which are also depicted on an example in figure 4 . all of them handle multiple gaps (a discontinuity inside a discontinuity) and cover 100% of the discontinuities. even if this has little effect in practice, it is an interesting property compared to algorithms that limit the number of gaps they can address @xcite . absolute-position for every token w i , p @xmath10. otherwise, we use a special label inv, which represents that the word is a fixed point in the permutation, i.e., it occupies the same place in the sentence and in the continuous arrangement. relative-position if @xmath11, then p @xmath12; otherwise, we again use the inv label. lehmer code @xcite in combinatorics, let @xmath13, ..., n -1] be a sorted sequence of objects, a lehmer code is a sequence σ = [σ 0 , ...σ n-1 ] that encodes one of the n! permutations of n, namely α. the idea is intuitive: let n i+1 be the subsequence of objects from n that remain available after we have permuted the first i objects to achieve the permutation α, then σ i+1 equals the (zero-based) position in n i+1 of the next object to be selected. for instance, given @xmath14, 1, 2, 3, 4] and a valid permutation α = [0, 1, 3, 4, 2], then σ = [0, 0, 1, 1, 0]. note that the identity permutation would be encoded as a sequence of zeros. in the context of discontinuous parsing and encoding p i , n can be seen as the input sentence w where π(w) is encoded by σ. the lehmer code is particularly suitable for this task in terms of compression, as in most of the cases we expect (nearly) ordered permutations, which translates into the majority of elements of σ being zero. 7 however, this encoding poses some potential learnability problems. the root of the problem is that σ i does not necessarily encode τ (i), but τ (j) where j is the index of the word that occupies the ith position in the continuous arrangement (i.e., @xmath15. in other words, this encoding is expressed following the order of words in the continuous arrangement rather than the input order, causing a non-straightforward mapping between input words and labels. for instance, in the previous example, σ 2 does not encode the location of the object n 2 =2 but that of n 3 =3. ## sequence labeling frameworks to test whether these encoding functions are learnable by parametrizable functions, we consider different sequence labeling architectures. we will be denoting by encoder a generic, contextualized encoder that for every word w i generates a hidden vector h i conditioned on the sentence, i.e. encoder(w i |w)=h i . we use a hard-sharing multitask learning architecture @xcite to map every h i to four 1-layered feedforward networks, followed by softmaxes, that predict each of the components of l i . each task's loss is optimized using categorical cross-entropy l @xmath16. we test four en-coders, which we briefly review but treat as black boxes. their number of parameters and the training hyper-parameters are listed in appendix a.4. ## conclusion we reduced discontinuous parsing to sequence labeling. the key contribution consisted in predicting a continuous tree with a rearrangement of the leaf nodes to shape discontinuities, and defining various ways to encode such a rearrangement as a sequence of labels associated to each word, taking advantage of the fact that in practice they are nearly ordered permutations. we tested whether those encodings are learnable by neural models and saw that the choice of permutation encoding is not trivial, and there are interactions between encodings and models (i.e., a given architecture may be better at learning a given encoding than another). overall, the models achieve a good trade-off speed/accuracy without the need of any parsing algorithm or auxiliary structures, while being easily parallelizable.