Statistical Parsing of Tree Wrapping Grammars (2020)

Abstract: We describe an approach to statistical parsing with Tree-Wrapping Grammars (TWG). TWG is a tree-rewriting formalism which includes the tree-combination operations of substitution, sister-adjunction and tree-wrapping substitution. TWGs can be extracted from constituency treebanks and aim at representing long distance dependencies (LDDs) in a linguistically adequate way. We present a parsing algorithm for TWGs based on neural supertagging and A* parsing. We extract a TWG for English from the treebanks for Role and Reference Grammar and discuss first parsing results with this grammar.

## introduction we present a statistical parsing approach for tree-wrapping grammar (twg) @xcite . twg is a grammar formalism closely related to tree-adjoining grammar (tag) @xcite , which was originally developed with regard to the formalization of the typologically oriented role and reference grammar (rrg) @xcite . twg allows for, among others, a more linguistically adequate representation of long distance dependencies (ldds) in sentences, such as topicalization or long distance wh-movement. in the present paper we show a grammar extraction algorithm for twg, propose a twg parser, and discuss parsing results for the grammar extracted from the rrg treebanks rrgbank and rrgparbank 1 @xcite . similarly to tag, twg has the elementary tree combination operations of substitution and sisteradjunction. additionally, twg includes the operation of tree-wrapping substitution, which accounts for preserving the connection between the parts of the discontinuous constituents. operations similar to tree-wrapping substitution were proposed by @xcite as subsertion in d-tree grammars (dtg) and by @xcite as generalized substitution in d-tree substitution grammar (dsg). to our best knowledge, no statistical parsing approach was proposed for dtg or dsg. an approach to symbolic parsing for twgs with edge features was proposed in @xcite . in this work, we propose a statistical parsing approach for twg and extend the pipeline based on supertagging and a * algorithm @xcite originally developed for tag to be applied to twg. the contributions of the paper are the following: 1) we present the first approach to statistical parsing for tree-wrapping grammars. 2) we propose an extraction algorithm for twgs based on the algorithm developed for tag by (xia, 1999). 3) we extend and modify the neural a tag-parser @xcite @xcite to handle the operation of tree-wrapping substitution. clause core nuc v remember np pro you prcs npwh prowh what clause core core do you think clause core core nuc v remember np pro you do you think prcs npwh prowh what rrg categories: @xmath0. @xmath1. linguistic phenomena leading to ldd differ across languages. among ldds in english are some cases of extraction of a phrase to a non-canonical position with respect to its head, which is typically fronting in english @xcite . we identified the following ldd variants in our data which can be captured with tree-wrapping substitution: long-distance relativization, long-distance wh-movement, and long-distance topicalization, which we discuss in section 6. foot_0 ldd cases are rather rare in the data, which is partly due to the rrg analysis of operators such as modals, which do not embed core constituents (in contrast to, for example, the analyses in the penn treebank). only 0,11 % of tokens in our experiment data (including punctuation) are dislocated from their canonical position in sentence to form an ldd. this number is on a par with 0,16 % of tokens reported by @xcite for french data. ## statistical parsing with twgs the proposed a twg parser foot_1 is a direct extension of the simpler a tag parser described in @xcite . the parser is specified in terms of weighted deduction rules @xcite and can be also seen as a weighted variant of the symbolic twg parser @xcite . as in @xcite , both twg elementary trees (supertags) and dependency links are weighted, a schema also used in a ccg parsing @xcite . these weights come directly from a neural supertagger and dependency parser, similar to the one proposed by @xcite . parsing consists then in finding a best-weight derivation among the derivations that can be constructed based on the deduction rules for a given sentence. the supertagger takes on input a sequence of word embeddings 4 (x i ) n @xmath2, to which a 2-layer bilstm transducer is applied to provide the contextualized word representations (h i ) n @xmath3, common to all subsequent tasks: pos tagging, twg supertagging, and dependency parsing. on top of that, we apply two additional 2-layer bilstm transducers in order to obtain the supertag-and dependency-specific word representations: the supertag-specific representations are used to predict both supertags and pos tags (pos tagging is a purely auxiliary task, since pos tags are fully determined by the supertags): finally, the dependency parsing component is based on biaffine scoring @xcite , in which the head and dependent representations are obtained by applying two feed-forward networks to the dependency-specific word representations, ## twg extraction to extract a twg from rrgbank and rrgparbank, we adapt the top-down grammar extraction algorithm developed by (xia, 1999) for tag. while inital and sister-adjoining trees can be extracted following this algorithm, we added a new procedure to extract d-edge trees for wrapping substitution operation. extraction of initial and sister-adjoining elementary trees requires manually defined percolation tables for marking head and modifier nodes. in order to extract d-edge elementary trees for ldds, dependent constituents need to be marked prior to twg extraction. in rrgbank and rrgparbank the constituents belonging to ldds are indicated with features pred-id and nuc-id and an index. these indicated parts alongside with the mother node are extracted to form a single tree with a dominance link (d-edge) (see for instance the elementary tree for "what to say" in fig. 3 ). the remaining nodes plus the duplicated mother node and a substitution slot form the target tree, for example the tree for "i'm trying" in fig. 3 . please find a more detailed formal description of our extraction algorithm along with a link to the percolation tables in appendix b. we have taken the gold and silver data from rrgbank and the english part of rrgparbank foot_5 . the data is split in a train and a test set. we have taken 10 % of the sentences from the train set to create a dev. set. thus, our train, dev. and test sets include 4960, 551, and 2145 trees, respectively. there are 46 constituents with ldds in the train set, 5 in the dev. set and 27 in the test set. we extracted a twg from this data and present in ## error analysis for ldd prediction we evaluated the performance of our parsing architecture with regard to the labeled f1-score and we also focused on prediction of the ldds (see tables 2 and 3 ). the results show that partage predicted the ldds in the test data more accurately than the compared parsers. please note that ldds are generally rare in the corpus data and that we also had only about 5000 sentences in the training data. some mistakes resulted from the wrong prediction of a pos tag which leads to the parser confusing an ldd constituent with a construction without ldd. for example, in (1), the word "is" should have pos tag v, but the parsing system erroneously labels it as aux (= auxiliary) and thus interprets the wh-element as a predicate. in order to check our assumption about pos tags as a source of error, we have run an experiment in which we presented the parser with gold pos tags. although this additional information helped to rule out the ldd errors in (1), restriction of the available supertags introduced new errors in ldd predictions (see a. what is one to think of all this? (is tagged aux instead of v) b. [. . . ] which he told her to place on her tongue (which tagged clm instead of @xcite in some cases where the relative or wh phrase of the ldd is an adjunct, as in (2), the parser incorrectly attaches it higher, taking it to be a modifier of the embedding verb. and why do you imagine that we bring people to this place? cases where the embedding verb also has a strong tendency to take a wh-element as argument sometimes get parsed incorrectly: in (3), which is analysed as an argument of said. ## conclusions and outlook we have presented a statistical parsing algorithm for parsing tree-wrapping grammar -a grammar formalism inspired by tag which aims at linguistically better representations of long distance dependencies. the ldds in twg are represented in a single elementary tree called d-edge tree which is combined with the target tree using tree-wrapping substitution. this operation allows to simultaneously put both parts of a discontinuous constituent to the corresponding slots of the target tree. we have extracted a twg for english from two rrg treebanks and have compared our parsing experiments with the parser discodop based on the dop parsing model and with the transition-based parser discoparset. we have evaluated our parser on prediction of ldds and could achieve more accurate results than the compared parsers. in our future work we plan to explore twg extraction and parsing for different languages, since the linguistic phenomena leading to ldds vary across the languages. in particular, we have already started to work on extraction of twgs for german and french. we plan to apply our twg extraction and parsing algorithm to other constituency treebanks, for example french treebank @xcite . we also plan to implement a slightly extended version of tree wrapping substitution which would allow to place the parts of discontinuous constituents in various slots between the nodes of the target tree. su: weights. a pair (w, m) is assigned to each chart item via deduction rules, where w is the inside weight, i.e., the weight of the inside derivation, and m is a map assigning weights to the individual gaps in the corresponding gap list γ. since each gap in γ can be uniquely identified by its starting position, we use the starting positions as keys in m. the need to use a map (dictionary) data structure instead of a single scalar value, as in the tag parser, stems from the cw rule (complete wrapping), in which the calculation of the resulting weight map requires removing the weight corresponding to the gap (f 1 , f 2 , y). we use ∅ to denote an empty map, m[x ⇒ y] to denote m with y assigned to x, m[x ⇒ ⊥] to denote m with x removed from the set of keys (together with the corresponding value), and sum(m) to denote the sum of values (weights) in the map m. we also re-use the concatenation operator ⊕ to represent map union. whenever map union is used (m 1 ⊕ m 2 ), the sets of keys of the two map arguments (m 1 and m 2 ) are guaranteed to be disjoint (an invariant which can be proved by induction over the deduction rules). heuristic. given a chart item η = (x, i, j, γ) with the corresponding weights (w, m), the twg a heuristic (which provides a lower-bound estimate on the cost of parsing the remaining part of the sentence) is a straightforward generalization of the tag a heuristic used by @xcite . in particular, it accounts for the total minimal cost of scanning each word outside the span (i, j), as well as the words remaining in the gaps in γ. thus, in constrast with the tag heuristic, since there can be many gaps in γ, the sum of the weights in the map m has to be accounted for.