Discontinuous Combinatory Constituency Parsing (2023)

Abstract: We extend a pair of continuous combinator-based constituency parsers (one binary and one multi-branching) into a discontinuous pair. Our parsers iteratively compose constituent vectors from word embeddings without any grammar constraints. Their empirical complexities are subquadratic. Our extension includes 1) a swap action for the orientation-based binary model and 2) biaffine attention for the chunker-based multi-branching model. In tests conducted with the Discontinuous Penn Treebank and TIGER Treebank, we achieved state-of-the-art discontinuous accuracy with a significant speed advantage.

## introduction discontinuity is common in natural languages, as illustrated in figure 1 . children from a discontinuous constituent are not necessarily consecutive because each can group with its syntactic cousins in the sentence rather than its two adjacent neighbors. although this relaxation makes discontinuous parsing more challenging than continuous parsing, it becomes more valuable for studies and applications in non-configurational languages @xcite , where word order does not determine grammatical function. with gradually saturated continuous parsing accuracy @xcite @xcite , discontinuous parsing has started gaining more attention @xcite @xcite . typically, constituency parsers are divided into two genres (not including methods employing dependency parsing, e.g., @xcite ): 1) global parsers use a fixed chart to search through all parsing possibilities for a global optimum. 2) local parsers rely on fewer local decisions, which leads to lower complexities. the global parser complexi-ties start at least from binary o(n 3 ) @xcite ) or m-ary o(n 4 ) @xcite , resulting in low speeds for long parses. global parsers introduce numerous hypotheses, whereas a local shift-reduce process or incremental parse exhibits more linguistic interests with fewer outputs @xcite . neural global parsers dominate both continuous and discontinuous parsing @xcite in terms of f1 score, but they do not exhibit a strong accuracy advantage over other parsers. although local parsers may in some cases produce ill-formed trees, global parsers do not guarantee the selection of gold-standard answers from their charts. we propose extending a pair of local parsers to achieve high speed, accuracy, and convenient investigation for both binary and multi-branching parses. @xcite proposed a pair of continuous parsers employing bottom-up vector compositionality. we dub these as neural combinatory constituency parsers (nccp) with binary cb and multi-branching cm. to the best of our knowledge, they possess the top parsing speeds for continuous constituency. cb reflects a linguistic branching tendency, whereas cm represents unsupervised grammatical headedness through composition weight. cm is among the few parsers that do not require preprocessing binarization @xcite but possess a high parsing speed. we dub our extension as dccp with binary db and multi-branching dm. the mechanisms with neural discontinuous combinators are shown in figure 2 . specifically, our combinators take a sentencerepresenting vector sequence as input and predict layers of concurrent tree-constructing actions. two mechanisms are employed. db triggers an action if the orientations of two neighboring vectors agree. a swap action exchanges the vectors; figure 1 : @xcite recover discontinuity from continuous penn treebank @xcite with trace nodes (blue). a joint action composes a new vector with them. cb only possesses a joint action. meanwhile, dm takes discontinuous vectors to form biaffine attention matrices and decides their groups collectively; the remaining continuous vectors resort to chunking decisions, as with cm. nccp and dccp are unlexicalized supervised greedy parsers. the contributions of our study are as follows: in m-ary and/or discontinuous cases (i.e., for multi-branching arity m and/or fan-out k of each constituent), the chart is superior to that of binary continuous parsing in terms of complexity. both horizontal and vertical axes expand to diversify the combination of discrete bits of each lexical node. because of the expansion, m-ary continuous global parsing @xcite has o(n 4 ) complexity, whereas binary discontinuous parsing has exponential complexity at o(n 3k ) @xcite ), where @xmath0, 2} are special cases for binary cfg (likely in chomsky normal form @xcite ) and binary linear context-free rewriting systems with maximum fan-out 2 (stanojevic and steedman, 2020, lcfrs-2). m -ary discontinuous parsing, which certainly has a higher complexity, is not yet available for global parsing. for efficiency, expensive rules are commonly restricted by lcfrs-2 parsers @xcite @xcite . a tricky o(n 3 ) variant of @xcite covering major rules has produced the best results. however, the variant excludes 2% sophisticated discontinuous rules on tiger treebank. limited by the simplified grammar, their discontinuous scores are low, especially for recalls. a global optimum does not guarantee a gold parse, leaving room for local parsing. local parsing. local parsers do not observe the chart framework and only consider one greedy or a few hypotheses. transition-based parsers with a swap or gap action have sequential actions and low complexities @xcite . multiple swaps or gaps combine to construct a large discontinuous constituent. in contrast, stack-free parsing can directly pick up a distant component with one attachment search @xcite . easy-first @xcite and chunker-based @xcite run rapidly. fernández-gonzález and gómez-rodríguez (2020a) redirected discontinuity to dependency parsing via pointer networks and obtained significant accuracy improvement among greedy parsers. however, it is difficult to determine whether such improvement originates from the model or the extra head information. in contrast, fernándezgonzález and gómez-rodríguez (2020b) reordered input words in at most o(n 2 ) complexity and redirected to various continuous parsers. ## discontinuous combinatory parsing we call a level of partial derivations or subtrees a ply @xcite , as depicted in figure 4 . similar to the state of a transition-based parser, each of which leads to an action, ply is the state for dccp, each of which leads to a sequence of concurrent actions for itself. starting with a sequence of words (x 1 , • • • , x n ) as an initial ply, we assemble an unlabeled discontinuous parse tree in a bottom-up manner by applying concurrent actions to the roots of subtrees in the ply and iterating until sequence length @xmath1. ## sample analysis continuous vs. discontinuous parsing. figure 13 highlights the value of discontinuous parsing by demonstrating the respective cm parse. conspicuously, the branching tendency of the continuous parse is to the right, while it is not obvious for the discontinuous parsing. meanwhile, we observed instances of similar unsupervised headedness weights. this sample is not trivial, which challenges our plm dccp models. parsing process of dccp. in figure 13 , db shows sinuous travel traces of ''i,'' ''was,'' and larger ∅-subtree nodes that involve the turning of orientations. the varying context leads them to achieve complex movement. db also created some grammatical substructures for ''how, @xcite meanwhile, the dm parse is more dramatic. the formation of the lower discontinuous vp involves five nodes, two of which are irrelevant words ''how'' and ''referred'' triggered by incorrect discontinuity signals. they are discontinuous but for the higher vp. the two nodes create a noisy biaffine attention matrix because their grammatical roles are compatible with the lower vp. trained for extra robustness, the matrix decomposition with five tries found the right θ to identify the correct vp members excluding ''how'' and ''referred.'' the interply loss and the decoding process gave this parse a chance for perfection. in figure 14 for german, db achieved a long distant constituent in a more subtle way. the word ''zwar'' joins ''registriert'' as an ∅-subtree when the formation of intermediate np shortens their distance and prevents a travel through. ''gegenwärtig'' follows and forms a vp. however, dm failed. the ρ ∅ > 0 matters. the above failure explains why dm is inferior to db with ρ ∅ = 0. db's orientation system allows some free travel before joining with correct mates. the constituent formation through steps of accumulation creates copula ''were'' has less affinity than ''when'' and ''due.'' a more stable context. however, dm's group action happens all at once. an incorrect composition might create a quite different context, which leads to unseen reaction chains. the strange unsupervised headedness weights reflect the issue. on the other side, with ρ ∅ > 0, dm can also gradually build and discover some semantic substructures, as shown in figure 15 . in contrast, db is not sensitive to ρ ∅ because of its nature, in agreement with ## conclusion we proposed a pair of efficient and effective discontinuous combinatory constituency parsers and extended the neural combinator family of nccp. a binary combinator db is based on orientation extended into a joint-swap system. a multi-branching combinator dm leverages biaffine attention adapted for constituency. our models (as in in the future, we will aim to extend dccp into a multilingual tool for directed acyclic graph (dag) parsing with function tag prediction for predicate-argument structure.