A Unifying Theory of Transition-based and Sequence Labeling Parsing

Carlos Gómez-Rodríguez, Michalina Strzyz, David Vilares

In the world of Natural Language Processing (NLP), parsing—the act of determining the syntactic structure of a sentence—has long been dominated by two distinct philosophies. Transition-based parsing treats the problem like a state machine, using a stack and a buffer to build a tree step-by-step. Sequence labeling parsing, on the other hand, treats it like a tagging task, assigning a single label to every word in a sentence.

A recent paper, "A Unifying Theory of Transition-based and Sequence Labeling Parsing," finally bridges these two worlds. The authors provide a formal mathematical mapping that allows almost any standard transition-based parser to be automatically converted into a fast, simple sequence labeling model.

TL;DR

This paper introduces a theoretical framework that maps left-to-right transition-based parsing algorithms to sequence labeling encodings. This allows researchers to automatically derive simple, high-performance sequence labeling parsers from a wide variety of existing transition-based systems, simplifying the parsing architecture without sacrificing accuracy.

What Problem Does This Paper Address?

For years, transition-based parsers have been the workhorse of dependency parsing. They are powerful but complex, requiring specialized data structures like stacks and buffers to manage state. While deep learning has reduced the need for manual feature engineering, these parsers still rely on a sequence of discrete actions (like "Shift" or "Reduce") to build a tree.

Sequence labeling is the "holy grail" of simplicity in parsing: you take a sentence of length $n$ and output $n$ labels. However, creating these labels was previously an ad-hoc process. Researchers had to manually design clever encodings (like relative PoS offsets or bracketing schemes) to represent a complex tree as a flat list of tags. There was no systematic way to turn a proven transition-based algorithm into a sequence labeling one—until now.

Methods

The authors define a formal class of left-to-right transition systems. To qualify, a system must meet two main criteria:

  1. Read Transitions: For a sentence of length $n$, the parser must execute exactly $n$ "read" transitions (actions that consume a new word from the input).
  2. Incrementality: The $i$-th read transition must be the point at which the $i$-th word becomes available for building the parse.

By identifying these "read" transitions, the authors can split a full sequence of parsing actions into $n$ chunks. Each chunk starts with a read transition and includes all subsequent actions until the next read. This chunk becomes the label for that specific word.

Figure 1: Examples of label distribution based on the sequence of actions for the corresponding transition systems. LA: Left Arc, RA: Right Arc, SH: Shift, NA: No-Arc. The last shift action in the sequence (which just terminates the computation and is always present) is omitted in the Covington system.

The researchers implemented sequence labeling versions of four classic algorithms: Arc-Standard, Arc-Eager, Arc-Hybrid, and the non-projective Covington parser. They used standard neural architectures—BiLSTMs and BERT—to predict these new label sequences.

Table 1: The formal definitions of the transition systems used in the study.

Datasets

The models were evaluated on a diverse subset of Universal Dependencies (UD) v2.4 treebanks, covering various language families and levels of syntactic complexity:

  • Ancient Greek (Perseus) (Highly non-projective)
  • Chinese (GSD)
  • English (EWT)
  • Finnish (TDT)
  • Hebrew (HTB)
  • Russian (GSD)
  • Tamil (TTB)
  • Uyghur (UDT)
  • Wolof (WTB)

Key Insights and Ideas

  • Stack-less Learning: Surprisingly, neural models like BiLSTMs can learn these transition-based labels effectively without any explicit representation of a stack. The model's internal hidden states are sufficient to capture the necessary context.
  • Broad Coverage: The theory isn't just for dependency parsing. The authors show it applies to constituency parsing and even semantic parsing, potentially opening the door for the first-ever sequence labeling models for complex semantic representations.
  • PoS Independence: Some popular sequence labeling encodings (like rel-PoS) rely heavily on Part-of-Speech tags to work. The new transition-based encodings are much more robust when PoS tags are missing, which is a huge plus for real-world applications where taggers might be unreliable.

Key Results

The derived encodings achieved performance comparable to state-of-the-art custom sequence labeling models.

Table 5: Results for BiLSTM setups. The transition-based encodings (Standard, Eager, Hybrid, Covington) perform similarly to the specialized 'rel-PoS' and 'Brackets' baselines.
  • Accuracy: On the English EWT test set, the Arc-Eager encoding achieved 80.2 UAS (Unlabeled Attachment Score), very close to the 82.0 UAS of the specialized rel-PoS baseline.
  • Non-Projectivity: For highly complex languages like Ancient Greek, the Covington-based encoding (which handles crossing dependencies) significantly outperformed purely projective models.
  • Efficiency: The sequence labeling approach is inherently fast because it avoids the overhead of maintaining a state machine during inference.

Limitations and Future Work

  • Vocabulary Size: The Covington encoding, while powerful for non-projective trees, can generate a very large number of unique labels (up to thousands for some languages). This makes the classification task harder for the neural network.
  • Non-L2R Systems: Some specialized parsers, like "Easy-First" or those using "swap" transitions that move words back into the buffer, do not fit the left-to-right definition and cannot currently be mapped using this theory.
  • Next Steps: The authors suggest that applying this mapping to semantic parsing is a particularly exciting future direction, as it could simplify a notoriously difficult task into a straightforward tagging problem.

Summary updated

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.
BibTeX
@inproceedings{gomezrodriguez2020unifying,
  author = {Carlos Gómez-Rodríguez and Michalina Strzyz and David Vilares},
  title = {{A Unifying Theory of Transition-based and Sequence Labeling Parsing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2020},
}
Figure