On Parsing as Tagging

Afra Amini, Ryan Cotterell

Abstract

There have been many proposals to reduce constituency parsing to tagging in the literature. To better understand what these approaches have in common, we cast several existing proposals into a unifying pipeline consisting of three steps: linearization, learning, and decoding. In particular, we show how to reduce tetratagging, a state-of-the-art constituency tagger, to shift--reduce parsing by performing a right-corner transformation on the grammar and making a specific independence assumption. Furthermore, we empirically evaluate our taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders. Based on the results in English and 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 taggers.

Introduction

Constituency parsing—the process of identifying nested syntactic structures like noun and verb phrases—is a fundamental task in natural language processing. Traditionally, this task has been computationally intensive, requiring complex algorithms to navigate the hierarchical nature of language. Recently, a paradigm shift has occurred: researchers are increasingly "reducing" parsing to a sequence tagging task. By representing a tree as a sequence of tags, models can leverage fast, parallelizable architectures like BERT to predict syntactic structure efficiently.

However, the literature has become fragmented with various methods of "linearization" (turning a tree into tags). This research provides a unifying framework to understand these methods, revealing that the success of parsing-as-tagging depends less on the complexity of the learner and more on how well the tag sequence aligns with the input words.

A Unified Framework for Parsing-as-Tagging

The authors propose that all parsing-as-tagging schemes can be decomposed into a three-step pipeline:

  1. Linearization: The process of converting a derivation tree into a sequence of tags. The study compares three primary strategies: Pre-order, Post-order, and In-order. The latter serves as the foundation for "tetratagging."
  2. Learning: Training a model to predict these tags. The researchers explored various scoring approximations, ranging from independent tag prediction using BERT to more complex sequence modeling with CRFs or LSTMs to capture inter-tag dependencies.
  3. Decoding: The process of reconstructing a valid tree from predicted tags. Because raw tag sequences may not naturally form a valid tree, the authors utilize dynamic programming (DP) and beam search to ensure structural integrity.

A significant theoretical contribution of this work is the proof that tetratagging is mathematically equivalent to a shift-reduce parser that has undergone a "right-corner transformation" on its grammar, combined with specific independence assumptions.

The Importance of Alignment and "Deviation"

To explain why certain linearization methods outperform others, the authors introduce the concept of deviation. Deviation measures the distance between a word and the tags that describe its structural role in the tree. The hypothesis is simple: the lower the deviation, the easier it is for a neural model to learn the relationship between a word and its syntactic function.

The study theoretically proves that in-order linearization (tetratagging) results in zero deviation. This means the information the model needs to predict is always local to the word being processed. In contrast, pre-order and post-order linearizations introduce higher deviation, forcing the model to capture longer-range dependencies.

Experimental Results

The framework was evaluated on the Penn Treebank (English) and the SPMRL shared tasks, which include eight typologically diverse languages: Basque, French, German, Hebrew, Hungarian, Korean, Polish, and Swedish.

Accuracy and Consistency

In English, the in-order tagger achieved a state-of-the-art F-measure of 95.15, significantly outperforming pre-order (94.56) and post-order (89.23) methods. This performance was consistent across the multilingual dataset. Regardless of whether a language was primarily right-branching (like English or French) or left-branching (like Korean), the in-order approach remained the most robust and accurate choice.

The Role of the Learner

One of the more surprising findings was that adding complex sequence modeling layers—such as a CRF or LSTM—on top of a BERT-large encoder provided only marginal improvements. This suggests that modern transformer-based models are already highly capable of capturing the necessary structural dependencies, provided the linearization scheme is well-aligned with the input.

Efficiency in Decoding

While exact decoding via dynamic programming yields the highest accuracy, the authors found that beam search (with a beam size of 10) offers a significant speed advantage with a negligible impact on accuracy (less than 1 point). This makes the parsing-as-tagging approach highly viable for real-world, high-throughput applications.

Conclusion

The success of parsing-as-tagging models is fundamentally tied to the alignment between words and their structural tags. By minimizing "deviation" through in-order linearization, researchers can achieve state-of-the-art parsing accuracy with relatively simple tagging architectures. Future work may extend this "deviation" insight to other structured prediction tasks, such as dependency parsing or semantic role labeling, to further optimize the efficiency of deep learning models in NLP.

Summary updated

Abstract

There have been many proposals to reduce constituency parsing to tagging in the literature. To better understand what these approaches have in common, we cast several existing proposals into a unifying pipeline consisting of three steps: linearization, learning, and decoding. In particular, we show how to reduce tetratagging, a state-of-the-art constituency tagger, to shift--reduce parsing by performing a right-corner transformation on the grammar and making a specific independence assumption. Furthermore, we empirically evaluate our taxonomy of tagging pipelines with different choices of linearizers, learners, and decoders. Based on the results in English and 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 taggers.
BibTeX
@inproceedings{amini2022parsing,
  author = {Afra Amini and Ryan Cotterell},
  title = {{On Parsing as Tagging}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=hVEFVjTcgIy},
}
Figure