Supertagging-based Parsing with Linear Context-free Rewriting Systems (2021)

Abstract: We present the first supertagging-based parser for linear context-free rewriting systems (LCFRS). It utilizes neural classifiers and outperforms previous LCFRS-based parsers in both accuracy and parsing speed by a wide margin. Our results keep up with the best (general) discontinuous parsers, particularly the scores for discontinuous constituents establish a new state of the art. The heart of our approach is an efficient lexicalization procedure which induces a lexical LCFRS from any discontinuous treebank. We describe a modification to usual chart-based LCFRS parsing that accounts for supertagging and introduce a procedure that transforms lexical LCFRS derivations into equivalent parse trees of the original treebank. Our approach is evaluated on the English Discontinuous Penn Treebank and the German treebanks Negra and Tiger.

## introduction in nlp, constituency parsing is a task that assigns -usually tree-shaped -syntactic structures to sentences. formalisms such as context-free grammars (cfg) are used in this setting because they are conceptually simple, interpretable, and parsing is tractable (cubic in sentence length). discontinuous constituents span non-contiguous sets of positions in a sentence. the resulting phrase structures do not take the shape of a tree anymore, as they contain crossing branches (cf. the left of fig. 1 ), and cannot be modeled by cfg. as a countermeasure, many treebanks, e.g. the penn treebank (ptb; @xcite , denote these phrase structures as trees nevertheless and introduce designated notations for discontinuity, which is then often ignored in parsing. however, discontinuity occurs in about 20 % of the sentences in the ptb and to an even larger extent in german treebanks such as negra and tiger. for parsing discontinuous constituents, so-called mildly context-sensitive grammar formalisms have been investigated, e.g. tree-adjoining grammars @xcite and linear context-free rewriting systems (lcfrs; @xcite . an lcfrs derivation of a discontinuous phrase is shown in the right of fig. 1 . the increased expressiveness of these formalisms comes at the cost of a higher parsing complexity: given a sentence of length n, parsing is in o(n 6 ) for tag and o(n 3•fo (g) ) for a binary lcfrs g. the grammar-specific fanout fo(g) indicates that g can parse constituents spanning up to n non-contiguous sets of positions. tag have the same expressiveness as lcfrs with fanout 2 @xcite , which accounts for 96.67 % of the sentences in negra and 96.83 % of the sentences in tiger @xcite . previous publications have established mildly context-sensitive formalisms in the field of statistical constituent parsing, and found methods to tame the high parsing complexity @xcite @xcite . one approach for making parsing with mildly context-sensitive grammars tractable is supertagging, which was originally introduced for lexical tag @xcite . a tag is lexical if each rule contains exactly one lexical item, i.e. word in the parsed language. the supertagger is a (often discriminative) classifier that selects for each position of the input sentence a subset of the rules of the tag; these are the so-called supertags. parsing is then performed with the much smaller grammar of supertags. research on supertagging has also been conducted in the context of combinatory categorial grammars (ccg; @xcite , but not yet for lcfrs. the use of recurrent neural networks (rnn) as classifiers in supertagging has improved their accuracy by far @xcite @xcite . recently, mörbitz and ruprecht (2020) introduced a lexicalization procedure for probabilistic lcfrs foot_0 , paving the way to employ supertagging for parsing with this formalism. early experiments showed that the approach is infeasible in realistic settings: the set of rules explodes in a step of the construction where new rules are introduced for pairs of terminals in the grammar. to mitigate this problem, we conduct the procedure for single derivations. consequently, we only have to construct rules for pairs of terminals that occur in sibling nodes of a derivation (cf. step (4) in section 4). moreover, we consider unweighted lcfrs, as weights of underlying grammar structures are usually not considered in supertaggingbased approaches. in this paper, we present the first supertaggingbased parser for lcfrs. section 3 extends the usual chart-based parsing approach for lcfrs to account for supertagging with lexical lcfrs. section 4 adapts the lexicalization procedure by @xcite to efficiently induce a lexical lcfrs from any given treebank. we implemented and evaluated the approach. section 5 describes the experimental setups of our evaluation using three discontinuous treebanks (one english and two german). section 6 compares our results to recent lcfrs-based parsers and other state-ofthe-art parsers for discontinuous constituents. the implementation of our approach is published on github. 2 we start by introducing some basic notation that will be used throughout sections 3 and 4. the set of non-negative (resp. positive) integers is denoted by n (resp. n + ). we abbreviate {1, ..., n} by [n]; for each n n + , the set [n] is the empty set. an alphabet σ is a finite and non-empty set; the set of (finite) strings over σ is denoted by σ * . the symbol ε denotes an empty string or sequence. compositions. linear context-free rewriting systems (lcfrs) extend the rule-based string rewriting mechanism of cfg to string tuples; we describe the generation process by compositions. let @xmath0, . . . , s k , @xmath1; one can think of k as the number of arguments of a function mapping string tuples of the sizes s 1 , . . . , s k to a string tuple of size s. a σ-composition is a tuple (u 1 , . . . , u s ) where each u 1 , . . . , u s is a non-empty string over σ and variables of the form x j i with @xmath2. each of these variables must occur exactly once in u 1 • • • u s and they are ordered such that x 1 i occurs before x 1 we associate with each composition (u 1 , . . . , u s ) ∈ c σ (s 1 •••s k ,s) a function from k string tuples, where the i-th tuple is of arity s i , to a string tuple of arity s. this function is denoted by (u 1 , . . . , u s ) . intuitively, it replaces each variable of the form x i in u 1 , . . . , u s by the i-th component of the first argument, and y j by the j-th component of the second argument. the identity composition (x 1 , . . . , x s ) is denoted by id s . a hearing is scheduled on the issue today pos-tagger + supertagger (1) dt nn vbz vbn in dt nn np+nn enriched preterminals @xmath3, 4 x 2 y 1 ) (np 2 , vp| 2 -) np 2 → (x 1 , 5 y 1 ) (np, pp + ) pp + → (6 x 1 ) (np + ) np + → (7) vp| 2 -→ (8) supertags/lcfrs rules (2) parser (3) @xmath4, 4 x 2 y 1 ) (np 2 , vp| 2 -) np 2 → (x 1 , 5 y 1 ) (np, pp + ) @xmath5: an overview over the supertagging-based parsing procedure. a sequence tagger predicts k (here, @xmath6. step (4) in section 4) for each sentence position. the supertags are rules of a uni-lexical lcfrs (the annotation of the nonterminals is explained in section 4). the terminal of each rule is the sentence position it was predicted for (rather than the word at that position). the range of sentence positions is parsed and finally the resulting derivation is transformed into a parse tree. the transformation requires the predicted nonterminals, which are used as preterminals. let @xmath7,s be a composition where @xmath8, @xmath9, and @xmath10. we obtain the partial application of c to w as i-th argument, denoted by c i (w) as follows: ## supertagging-based parsing our parsing model consists of two components: a uni-lexical lcfrs and a discriminative sequence tagger which we henceforth call supertagger. the lcfrs is induced from a treebank by an adaptation of the construction of @xcite ; the interested reader may find a detailed description of this procedure in section 4. after the induction, we replace every terminal of the lcfrs by the wildcard symbol " ", and we refer to the resulting rules as supertags. our parsing pipeline is depicted in fig. 2 . as g w only resembles a fraction of all supertags, this approach shifts a huge amount of work from parsing with grammars to predicting the rules. thus its success is mainly determined by the quality of the supertagger. ## inducing lexical lcfrs our lexicalization scheme is based on @xcite . however, we ignore all weights and perform lexicalization on individual derivations rather than on a grammar induced from the entire treebank. more specifically, we directly read off a set of uni-lexical rules from each tree in the treebank; then the union of these rules forms our uni-lexical lcfrs g lex . in contrast to that, mörbitz and ruprecht (2020) first induce an lcfrs g from the entire treebank and then lexicalize g. thus g lex may have a different language than the lexicalization of g. we obtain a set of uni-lexical rules from each tree t in the treebank by the following procedure. finally, we obtain the uni-lexical lcfrs g lex by combining the rules r(t) for each tree t. the initial nonterminals of g lex are all left-hand sides of roots of d lex (t). let t be a tree in the treebank. steps (1) and ( 2 ) and their reversal are standard techniques for trees and lcfrs. after applying them to t, we obtain an lcfrs derivation in which each occurring rule is either of the form ## results we see that the parsing speed gradually drops with rising k, but for @xmath11. as expected, with rising k, the recall increases drastically. the precision, on the other hand, only changes slightly. the drop in precision using negra and tiger may be explained by a significant decrease in parse fails from @xmath12, then the effects of fewer parse fails and considering lower-scored supertags seem to balance each other out. we found @xmath13. compared to other parsing approaches, we obtain results that are on par with the state of the art; recently, this is rather unusual for grammar-based constituent parsing. we would like to especially highlight our results for discontinuous constituents, which surpass the previous state of the art by a wide margin. unfortunately, we can only compare our results to those of other supertagging-based parsers to a very limited extent, as authors seem to either report no parsing scores at all @xcite , or give attachment scores for dependency relations @xcite . however, ## conclusion we described an approach to utilize supertagging for parsing discontinuous constituents with lcfrs and evaluated it. compared to other parsers for the recent publications by @xcite and stanojević and steedman (2020) address discontinuous constituent parsing using approaches that share an algorithmic foundation with lcfrs parsing, but do not use an underlying grammar. both of them restrict constituents to two non-contiguous spans (equivalent to an lcfrs with fanout 2), we have no such limitation. considering the margin between our discontinuous f1-score and theirs, we suppose that this restriction is only benefiting the complexity, not the accuracy.