A Unified Encoding of Structures in Transition Systems

Tao Ji, Yong Jiang, Tao Wang, Zhongqiang Huang, Fei Huang, Yuanbin Wu, Xiaoling WangEMNLP 2021 · DOI

Abstract

Transition-based parsing is a cornerstone of Natural Language Processing (NLP), yet it often faces a trade-off between the speed of template-based methods and the structural completeness of recurrent models. We present the Unified Structure Encoder (USE), a novel attention-based framework that captures the complete state of transition-based parsers—including stacks, buffers, and partial trees—within a single, parallelizable architecture. By decoupling an item's content from its position through structure indicators, USE achieves state-of-the-art parsing accuracy while running up to five times faster than previous transition-based models.

Introduction

Transition-based parsing builds dependency trees by performing a sequence of actions, such as pushing items to a stack or reducing them. To predict the next action, a model must understand the current configuration of its internal structures: the stack (LIFO), the buffer (FIFO), and the partial tree built so far. Historically, researchers have relied on either fast but limited template-based methods that only observe "top-k" items, or structure-based networks like Stack-LSTMs that capture the whole structure but are computationally expensive and difficult to parallelize on GPUs.

Methods

The core innovation of USE is the Two-View Representation of items within the system:

  • Structure-Invariant View: Represents the "content" of a word (embeddings, POS tags, character features) which remains constant regardless of its position in the parser.
  • Structure-Dependent View: Uses Structure Indicators—learnable vectors that specify an item's position, such as "top of the stack" or "third element in the buffer."

The Unified Structure Encoder (USE)

Instead of sequential LSTMs, USE utilizes Multi-Head Attention (MHA). Each item is represented by the sum of its content embedding and its position indicator. Each attention head is assigned to a specific structure (stack, buffer, etc.), where the query vector represents the current time step and the keys/values represent the items in that structure.

The Unified Structure Encoder (USE) architecture showing the integration of structure-invariant and structure-dependent views.

Multiple layers of USE are stacked, allowing the model to learn interactions between different structures. Crucially, this approach allows the model to track "off-structure" information—items recently removed from the stack—by using negative position indicators.

Key Results and Insights

The model was evaluated on the English Penn Treebank (PTB 3.0) and Universal Dependencies (UD 2.2) across 12 languages.

  • Accuracy: On the PTB dataset, the USE parser achieved 95.99% UAS (Unlabeled Attachment Score), matching the performance of strong graph-based parsers.
  • Efficiency: USE parsed 918 sentences per second, making it 5x faster than the strongest transition-based baseline and roughly 2x faster than popular graph-based parsers like the Dozat & Manning biaffine parser.
Comparison of USE with traditional transition-based parsing encoders, highlighting its completeness and GPU efficiency.

By treating "position in a stack" as a learnable embedding, the authors transform a dynamic, sequential problem into a set-based problem that Transformers excel at. This allows the model to process all transition states in a batch simultaneously, bypassing the sequential bottleneck of RNNs.

Conclusion

While USE slightly underperforms some "high-order" graph parsers that use complex global decoding, it provides a superior balance of speed and accuracy. Future work may involve integrating bi-directional transition systems or stronger decoding methods to bridge the remaining accuracy gap while maintaining the significant speed advantages of the USE encoder.

Summary updated

BibTeX
@inproceedings{ji2021unified,
  author = {Tao Ji and Yong Jiang and Tao Wang and Zhongqiang Huang and Fei Huang and Yuanbin Wu and Xiaoling Wang},
  title = {{A Unified Encoding of Structures in Transition Systems}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  doi = {10.18653/v1/2021.emnlp-main.339},
}
Figure