Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering (2021)

Abstract: Discontinuous constituent parsers have always lagged behind continuous approaches in terms of accuracy and speed, as the presence of constituents with discontinuous yield introduces extra complexity to the task. However, a discontinuous tree can be converted into a continuous variant by reordering tokens. Based on that, we propose to reduce discontinuous parsing to a continuous problem, which can then be directly solved by any off-the-shelf continuous parser. To that end, we develop a Pointer Network capable of accurately generating the continuous token arrangement for a given input sentence and define a bijective function to recover the original order. Experiments on the main benchmarks with two continuous parsers prove that our approach is on par in accuracy with purely discontinuous state-of-the-art algorithms, but considerably faster.

## introduction discontinuous phrase-structure trees (with crossing branches like the one in figure 1(a) ) are crucial for fully representing the wide range of syntactic phenomena present in human languages such as long-distance extractions, dislocations or crossserial dependencies, among others. although continuous approaches ignore these linguistic phenomena by, for instance, removing them from the original treebank (a common practice in the penn treebank @xcite ), there exist different algorithms that can handle discontinuous parsing. currently, we can highlight (1) those based in linear context-free rewriting systems (lcfrs) @xcite , which allow exact cky-style parsing of discontinuous structures at a high computational cost @xcite ; (2) a variant of the former that, while still making use of lcfrs formalisms, increases parsing speed by implementing a span-based scoring algorithm @xcite and not explicitly defining a set of rules @xcite ; (3) transition-based parsers that deal with discontinuities by adding a specific transition in charge of changing token order @xcite @xcite @xcite or by designing new data structures that allow interactions between already-created non-adjacent subtrees @xcite ; and, finally, (4) several approaches that reduce discontinuous constituent parsing to a simpler problem, converting it, for instance, into a non-projective dependency parsing task @xcite or into a sequence labelling problem @xcite . in (4), we can also include the solutions proposed by @xcite and @xcite , which transform discontinuous treebanks into continuous variants where discontinuous constituents are encoded by creating additional constituent nodes and extending the original non-terminal label set (following a pseudo-projective technique @xcite ), to then be processed by continuous parsing models and discontinuities recovered in a postprocessing step. it is well known that discontinuities are inherently related to the order of tokens in the sentence, and a discontinuous tree can be transformed into a continuous one by just reordering the words and without including additional structures, an idea that has been exploited in practically all transitionbased parsers and other approaches @xcite . however, in these models the reordering process is tightly integrated and inseparable from the parsing process. likely due to the lack of accurate models to accomplish reordering in isolation, we are not aware of any approach framed in (4) that explicitly reduces discontinuous constituent parsing into a continuous problem, keeping the original set of constituent nodes and solving it with a completely independent continuous parser that does not have to deal with an extended label set. please note that existing approaches that perform discontinuous-tocontinuous conversion, such as @xcite and @xcite , not only modify the original discontinuous tree by including artificial constituent nodes and enlarging its label scheme (probably penalizing parsing performance), but they are not able to fully recover the original discontinuous tree due to limitations of the proposed encodings. in this paper, we study the (fully reversible) discontinuous-to-continuous conversion by token reordering and how any off-the-shelf continuous parser can be directly applied without any further adaptation or extended label set. to undertake the independent token reordering, we rely on a pointer network architecture @xcite that can accurately relocate those tokens causing discontinuities in the sentence to new positions, generating new sentences that can be directly parsed by any continuous parser. we test our approach foot_0 with two continuous algorithms @xcite ) on three widely-used discontinuous treebanks, obtaining remarkable accuracies and outperforming current state-of-the-art discontinuous parsers in terms of speed. ## conclusions and future work we show that, by accurately removing crossing branches from discontinuous trees, continuous parsers can perform discontinuous parsing more efficiently, achieving accuracies on par with more expensive discontinuous approaches. in addition, the proposed pointer network can be easily combined with any off-the-self continuous parser and, while barely affecting its efficiency, it can extend its coverage to fully model discontinuous phenomena. we will investigate alternatives to the inorder reordering (e.g., pre-and post-order traversal or language-specific rules to generate more continuous-friendly structures). while we think that using a different cca would have no substantial impact on pointer network reordering, it might affect continuous parsing performance (as it may be easier for the parser to process reordered constituent trees with a syntax closer to original continuous structures, and factors like the degree of left vs. right branching may also have an influence).