A Unifying Theory of Transition-based and Sequence Labeling Parsing (2020)

Abstract: We define a mapping from transition-based parsing algorithms that read sentences from left to right to sequence labeling encodings of syntactic trees. This not only establishes a theoretical relation between transition-based parsing and sequence-labeling parsing, but also provides a method to obtain new encodings for fast and simple sequence labeling parsing from the many existing transition-based parsers for different formalisms. Applying it to dependency parsing, we implement sequence labeling versions of four algorithms, showing that they are learnable and obtain comparable performance to existing encodings.

## introduction transition-based parsing algorithms compute the syntax or semantics of sentences as graphs; for instance in the form of dependency @xcite @xcite , phrasestructure @xcite @xcite or meaning representations @xcite @xcite . these algorithms define an abstract state machine where each state (configuration) holds a structured representation, as well as auxiliary data structures (often, but not always, a buffer and a stack of tokens). shift-reduce actions (transitions) are defined to move the system between states until a full parse is found. the transition to take at each state was traditionally predicted by data-driven classifiers based on local decisions and rich feature representations @xcite . with the adoption of deep learning, which can globally contextualize word representations, the dependency on hand-crafted features has been drastically reduced @xcite ; and it has also been shown that alternative ways to attack the problem can be practical. more particularly, several parsing problems have been cast as a machine translation task, where a sequence-to-sequence (seq2seq) network maps the sentence into a string of arbitrary length that encodes a linearized graph @xcite @xcite . to a certain extent, the attention mechanism in these seq2seq models can be seen as an abstraction of the stack and buffer in transition-based parsers, where the attention weights mark the relevant words to generate the next component of the output string. alternatively, some authors have reduced constituent and dependency parsing to sequence labeling, where given an input sentence of length n, the output has length n too, assigning one label to each word @xcite . however, these reductions have consisted in defining custom encodings for the output structure, which cannot be automatically derived. in this context, some studies have linked transition-based parsers to seq2seq architectures, as in @xcite , but to the best of our knowledge there is no unified framework or theory for transition-based and sequence labeling parsing. contribution (i) our first contribution is theoretical, connecting the transition-based and sequence labeling parsing paradigms. we give a broad definition of a left-to-right transition system, covering the majority of transition-based parsers, and prove that the transitions produced by such systems for a sentence of length n can be mapped to a sequence of n labels, hence providing a mapping from transition-based parsers to sequence labeling parsers. (ii) the second contribution is empirical, applied to dependency parsing. we implement projective and non-projective transition-based algorithms, cast them in a sequence labeling setup and show that they are learnable, and even outperform some existing custom encodings for parsing as labeling. the source code is available at https://github.com/mstrise/dep2label . ## preliminaries let @xmath0. . . w n be an input sentence. we will denote by p w the set of possible well-formed parses for w in the relevant parsing formalism (e.g. in projective dependency parsing, p w is the set of projective dependency trees of n nodes). following @xcite , with some adaptations to generalize the notions beyond dependency parsing, we can define a transition system as a quadruple @xmath1, t, c s , c t ) where: a transition system parses an input sentence w by starting in the initial configuration c s (w), and applying a sequence of transitions until a final configuration c @xmath2. at that point, the parse p c @xmath3. thus, for a transition system @xmath4, t, c s , c t ), we can define a computation of s on w as a sequence of configurations c 0 , c 1 , . . . , c m such that each c i is obtained from c i-1 by applying a transition t i . such a computation is complete for w if c 0 = c s (w) and c @xmath5. we denote by c s w the set of complete computations of s on w. note that a computation is uniquely determined by its starting configuration and the sequence of transitions t 1 , . . . , t m applied to it. a complete computation is uniquely determined by the sequence of transitions t 1 , . . . , t m , as the initial configuration is fixed. finally, we define a static oracle for a transition system @xmath6, t, c s , c t ) as a function ω : p @xmath7, the parse associated with the final configuration in ω(p ) is p . that is, given a gold parse for the sentence w, a static oracle returns a (canonical) computation of s that produces that gold parse on w. note that a correct transition system should be able to produce all the possible well-formed parses in p w , and hence, a static oracle must exist. foot_0 ## mapping transition-based parsers to sequence labeling parsers we first formally define our mapping from transition systems to sequence labeling parsers, to then explain it in detail, provide examples, and analyze how it applies to different transition systems: definition 1. let @xmath8, t, c s , c t ) be a transition system. we say that s is a left-to-right transition system if there is a subset of transitions t s ⊆ t , called the read transitions, which satisfy the following conditions: such parsers can be mapped into a sequence labeling encoding as follows: definition 2. let @xmath9, t, c s , c t ) be a left-to-right transition system. let γ = c 0 , . . . , c m be a complete computation of s on a sentence w 1 . . . w n . by the first condition of a left-to-right transition system, we know that the sequence of transitions of γ is of the form definition 3. let @xmath10, t, c s , c t ) be a left-to-right transition system, @xmath11. . . w n a sentence of length n, and ω a static oracle for s. then, we define the sequence labeling encoding associated to s as the mapping κ : p @xmath12, κ(p ) = l(ω(p )). ## experiments to test the practical applicability of our theoretical contribution, we implement sequence labeling versions, obtained using the mapping in section 3, of various syntactic dependency parsers. we include three wellknown projective parsers: arc-standard @xcite , arc-eager @xcite and arc-hybrid @xcite ; and one parser with full coverage of non-projective trees: the covington non-projective parser @xcite . the transition systems for all of these parsers are shown in ## conclusion this paper has established a theoretical relationship between transition-based and sequence labeling parsing valid for a broad definition of left-to-right transition-based algorithms. it also provides a new set of encodings for sequence labeling parsing which are automatically derived, in contrast to existing ones which were created ad-hoc for this purpose. to test the practical utility, we ran experiments on dependency parsing for a diverse set of languages. interestingly, the mapping is meaningful and learnable, despite not using any representation of stack nodes. while our experiments focused on dependency parsing as we only aimed to validate the theory, an obvious avenue for future work is to implement and test the sequence-labeling encodings derived from the constituent and semantic parsers in tables 3 and 4 . the latter are particularly relevant in the sense that, to our knowledge, there is no previous work on semantic parsing as sequence labeling; so our method provides the first encodings for this purpose. in