Abstract
Constituency parsing has traditionally been a computationally intensive task. Recent advancements have proposed "parsing-as-tagging" methods to leverage the speed and parallelization of neural sequence models. However, the theoretical underpinnings and the reasons for the varying performance of different tagging schemes remained unclear. This paper introduces a unifying framework that decomposes parsing-as-tagging into linearization, learning, and decoding. We identify "deviation"—the alignment distance between words and tags—as a critical factor for accuracy. Our findings reveal that in-order linearization, which minimizes deviation, consistently achieves superior results across multiple languages.
Introduction
Constituency parsing involves decomposing sentences into recursive syntactic structures. While accurate, traditional methods often suffer from high computational costs. The emergence of parsing-as-tagging offers a faster alternative by reducing the problem to sequence labeling, compatible with architectures like BERT. Despite its promise, the field lacked a systematic comparison of tagging schemes. This work provides a taxonomy for these methods and explores the relationship between modern tagging and classical transition-based parsing.
The Parsing-as-Tagging Framework
The authors propose a three-stage pipeline to unify disparate tagging approaches:
- Linearization: This step converts a derivation tree into a sequence of tags. Three primary orders are analyzed: pre-order (top-down), post-order (bottom-up), and in-order (tetratagging).
- Learning: A neural model, such as BERT, is trained to predict tag probabilities. The framework allows for varying degrees of dependency modeling between tags, from independent predictions to structured approaches like CRFs.
- Decoding: Predicted tag sequences are transformed back into valid trees. To ensure structural validity, dynamic programming or beam search is employed to find the most probable legal tree.
Theoretical Insights: Alignment and Deviation
A significant contribution of this research is the formal proof that tetratagging is mathematically equivalent to a shift-reduce parser performing a right-corner transformation. Central to the success of these models is the concept of deviation—the spatial distance between a word and the tag responsible for shifting it onto the parser's stack.
Neural models exhibit a strong preference for locality. When a tag's information is closely aligned with its corresponding word (low deviation), prediction accuracy improves. In-order linearization (tetratagging) is shown to have zero deviation, perfectly aligning tags with words. This alignment is the "secret sauce" behind its high performance.
Evaluation and Results
The framework was tested on the English Penn Treebank and the SPMRL dataset, covering eight morphologically rich languages. In-order linearization achieved an F1 score of 95.15 in English, significantly outperforming pre-order (94.56) and post-order (89.23) schemes. This trend held across most languages, with in-order being the top performer in 7 out of 9 cases.
A strong negative correlation (-0.77) was observed between mean deviation and F1 score, confirming that schemes which "scramble" word order perform worse. While right-branching languages like English favor in-order schemes, left-branching languages like Korean show better alignment with post-order linearization than English does, though in-order remains highly competitive.
Conclusion
This study clarifies the mechanics of parsing-as-tagging, highlighting the importance of word-tag alignment. While focused on constituency parsing, the principles of deviation and locality likely extend to other structured prediction tasks. Future work should explore these principles in a wider variety of left-branching languages and more complex formalisms like Combinatory Categorial Grammar (CCG).
Summary updated