On Parsing as Tagging (2022)

Abstract: There are many proposals to reduce constituency parsing to tagging. To figure out what these approaches have in common, we offer a unifying pipeline, which consists of three steps: linearization, learning, and decoding. We prove that classic shift–reduce parsing can be reduced to tetratagging—the state-of-the-art constituency tagger—under two assumptions: right-corner transformation in the linearization step and factored scoring in the learning step. We ask what is the most critical factor that makes parsing-as-tagging methods accurate while being efficient. To answer this question, we empirically evaluate a taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders. Based on the results in English as well as a set of 8 typologically diverse languages, we conclude that the linearization of the derivation tree and its alignment with the input sequence is the most critical factor in achieving accurate parsers as taggers.

## introduction the automatic syntactic analysis of natural language text is an important problem in natural language processing (nlp). due to the ambiguity present in natural language, many parsers for natural language are statistical in nature, i.e., they provide a probability distribution over syntactic analyses for a given input sequence. a common design pattern for natural language parsers is to re-purpose tools from formal language theory that were often designed for compiler construction @xcite , to construct probability distributions over derivation trees (syntactic analyses). indeed, one of the most commonly deployed parsers in nlp is a statistical version of the classic shift-reduce parser, which has been widely applied in constituency parsing @xcite @xcite , dependency parsing @xcite ; yamada and @xcite , and even for the parsing of more exotic formalisms, e.g., ccg parsing @xcite . another relatively recent trend in statistical parsing is the idea of reducing parsing to tagging @xcite @xcite @xcite . there are a number of motivations behind this reduction. for instance, kitaev and klein (2020) motivate tetratagging, their novel constituency parsing-as-tagging scheme, by its ability to parallelize the computation during training and to minimize task-specific modeling. the proposed taggers in the literature are argued to exhibit the right balance in the trade-off between accuracy and efficiency. nevertheless, there are several ways to cast parsing as a tagging problem, and the relationship of each of these ways to transition-based parsing remains underdeveloped. to better understand the relationship between parsing as tagging and transition-based parsing, we identify a common pipeline that many parsing-astagging approaches seem to follow. this pipeline, as shown in fig. 1 , consists of three steps: linearization, learning, and decoding. furthermore, we demonstrate that @xcite tetratagging may be derived under two additional assumptions on a classic shift-reduce parser: (i) a right-corner transform in the linearization step and (ii) factored scoring of the rules in the learning step. we find that (i) leads to better alignment with the input sequence, while (ii) leads to parallel execution. in light of these findings, we propose a taxonomy of parsing-as-tagging schemes based on different choices of linearizations, learners, and decoders. furthermore, we empirically evaluate the effect that the different choice points have on the performance of the resulting model. based on experimental results, one of the most important factors in achieving the best-performing tagger is the order in which the linearizer enumerates the tree and the alignment between the tags and the input sequence. we show that taggers with in-order linearization are the most accurate parsers, followed by their pre-order and post-order counterparts, respectively. finally, we argue that the effect of the linearization step on parsing performance can be explained by the deviation between the resulting tag sequence and the input sequence, which should be minimized. we theoretically show that in-order linearizers always generate tag sequences with zero deviation. on the other hand, the deviation of pre-and post-order linearizations in the worst case grows in order of sentence length. empirically, experiments on a set of 9 typologically diverse languages show that the deviation varies across languages and negatively correlates with parsing performance. indeed, we find that the deviation appears to be the most important factor in predicting parser performance. ## preliminaries before diving into the details of parsing as tagging, we introduce the notation that is used throughout the paper. we assume that we have a weighted grammar in chomsky normal form @xmath0, s, σ, r where n is a finite set of nonterminal symbols, @xmath1, σ is an alphabet of terminal symbols, and r is a set of productions. each production can take on two forms, either @xmath2, where x, y, @xmath3, or @xmath4, where @xmath5. foot_0 let @xmath6, where w @xmath7. next, we give a definition of a derivation tree d w that yields w. ## linearization in this and the following two sections, we go through the parsing-as-tagging pipeline and discuss the choice points at each step. we start with the first step, which is to design a linearizer. the goal of this step is to efficiently encode all we need to know about the parse tree in a sequence of tags. definition 2 @xcite ). a linearizer is a function φ w : d @xmath8, where d w is the set of derivation trees with yield w, t is the set of tags, m is o(n ), and n is the length of w. we further require that φ w is a total and injective function. this means that each derivation tree d w in d w is mapped to a unique tagging sequence t, but that some tagging sequences do not map back to derivation trees. we wish to contextualize def. 2 by contrasting parsing-as-tagging schemes, as formalized in def. 2, with classical transition-based parsers. as written, def. 2 subsumes many transition-based parsers, e.g., @xcite arc-standard and arc-eager parsers. 3 however, in the case of most transition-based parsers, the linearizer φ w is a bijection between the set of derivation trees d w and the set of valid tagging sequences, which we denote as t w ⊂ t m . the reason for this is that most transition-based parsers require a global constraint to ensure that the resulting tag sequence corresponds to a valid parse. in contrast, in def. 2, we require a looser condition-namely, that φ w : d @xmath9. therefore, tagging-based parsers allow the prediction of invalid linearizations, i.e., sequences of tags that cannot be mapped back to a valid derivation tree. more formally, the model can place non-zero score on elements in t m \ t w . however, the hope is that the model learns to place zero score on elements in t m \ t w , and, thus, enforces a hard constraint. therefore, parsing-astagging schemes come with the advantage that they make use of a simpler structure prediction framework, i.e., tagging. nevertheless, in practice, they still learn a useful parser that only predicts valid sequences of tags due to the expressive power of the neural network backbone. ## learning in this section, we focus on the second step in a parsing-as-tagging pipeline, which is to score a tag sequence. the parsers-as-taggers proposed in the literature often simplify the probability distribution over derivation trees, as defined in eq. ( 1 ). we first discuss various approximations we can make to the score function score(@xmath10. the three approximations we identify each make the model less expressive, but allow for more efficient decoding algorithms (see §5). then, we exhibit how the crudest approximation allows for a fully parallelized tagger. ## decoding in this section, we focus on the last step in a parsingas-tagging pipeline, which is to decode a tag sequence into a tree. the goal of the decoding step is to find a valid sequence of tags t * that are assigned the highest probability under the model for a given sentence, i.e., ## experiments in our experimental section we aim to answer two questions: (i) what is the effect of each design decision on the efficiency and accuracy of a tagger, and which design decisions have the greatest effect? (ii) are the best design choices consistent across languages? data. we use two data sources: the penn treebank @xcite for english constituency parsing and statistical parsing of morphologically rich languages (spmrl) 2013/2014 shared tasks @xcite for 8 languages: basque, french, german, hebrew, hungarian, korean, polish, and swedish. we provide the dataset statistics in learning schema. second, we measure the effect of the independence assumption in scoring tagging sequences. we slightly change the scoring mechanism by training a crf foot_10 and an lstm layer foot_11 to make scoring over tags left-or rightdependent. we expect to see improvements with φ pre w and φ post w , since in these two cases, creating such dependencies gives us more expressive power in terms of the distributions over trees that can be modeled. however, we only observe marginal improvements when we add left and right dependencies (see decoding schema. third, we assess the tradeoff between accuracy and efficiency caused by using beam search versus exact decoding. we take @xmath11. as shown in ## conclusion in this paper, we analyze parsing as tagging, a relatively new paradigm for developing statistical parsers of natural language. we show many parsing-as-tagging schemes are actually closely related to the well-studied shift-reduce parsers. we also show that kitaev and klein's (2020) tetratagging scheme is, in fact, an in-order shift-reduce parser, which can be derived from bottom-up or top-down shift-reduce parsing on the right or left-cornered grammars, respectively. we further identify three common steps in parsing-as-tagging pipelines and explore various design decisions at each step. empirically, we evaluate the effect of such design decisions on the speed and accuracy of the resulting parser. our results suggest that there is a strong negative correlation between the deviation metric and the accuracy of constituency parsers. proof sketch. we give an outline of the construction. first, consider a grammar in chomsky normal form g. next, apply the standard shift-reduce transformation to g in order to construct a pushdown automaton (pda). finally, note that under the independence assumption score(@xmath12. note that @xmath13. this can be viewed as using algorithm 1 to find the valid tagging sequence with the highest score in a directed acyclic graph, as shown in fig. 2 . proof sketch. we give an outline of the construction. first, consider a grammar in chomsky normal form g. next, apply the standard shift-reduce transformation to g in order to construct a pushdown automaton (pda). finally, note that under the left-or right-dependent approximation, score(