Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set

Tianze Shi, Liang Huang, Lillian Lee

Abstract

This paper demonstrates that transition-based dependency parsers can achieve state-of-the-art accuracy using a minimal set of only two positional features by leveraging bi-directional LSTM (bi-LSTM) representations. This radical simplification enables efficient $O(n^3)$ exact decoding and global training, effectively bridging the performance gap between fast transition-based systems and globally optimized graph-based parsers.

Introduction

Dependency parsing—the task of mapping grammatical structures in sentences—has traditionally faced a trade-off between speed and global optimality. Transition-based parsers are efficient but often rely on greedy, local decisions and complex feature engineering to maintain accuracy. Historically, consulting numerous stack and buffer positions made exact decoding (finding the globally optimal sequence of moves) computationally prohibitive, often reaching complexities of $O(n^6)$ or $O(n^7)$. This research explores how minimal feature sets, empowered by modern deep learning, can make exact global decoding practical.

Methodology

The authors combine bi-directional LSTM (bi-LSTM) representations with traditional dynamic programming (DP) frameworks to simplify the parsing process:

  1. Minimal Feature Set: By using bi-LSTMs to encode the entire sentence, the model captures surrounding context within individual vectors. The researchers found that for arc-hybrid and arc-eager systems, only two positional features—the top of the stack ($s_0$) and the front of the buffer ($b_0$)—are necessary to maintain high performance.
  2. $O(n^3)$ Exact Decoding: Reducing the state signature to just two positions allows the use of DP frameworks with $O(n^3)$ complexity, matching the efficiency of standard graph-based parsers.
  3. Global Training: The model is optimized using a structured large-margin loss, which considers the entire sequence of transitions rather than individual local moves.
  4. Theoretical Unification: The paper proves that the arc-eager transition-based model is more expressive than the standard edge-factored graph-based model, providing a theoretical bridge between the two paradigms.
Inference rules for Arc-standard, Arc-hybrid, Arc-eager, and Edge-factored graph-based parsing systems.

Evaluation and Results

The proposed systems were evaluated on the English Penn Treebank (PTB) and the Chinese Treebank 5.1 (CTB). The results confirm that global training and exact decoding provide a significant and consistent performance boost over greedy, local strategies.

  • Accuracy: On the Chinese Treebank, the system achieved a state-of-the-art Unlabeled Attachment Score (UAS) of 88.62% for a single model and 90.22% for an ensemble. On the English PTB, it reached a competitive 95.33% with an ensemble.
  • Efficiency: The study produced the first practical $O(n^3)$ exact decoders for arc-hybrid and arc-eager systems. While the arc-standard system still requires $O(n^4)$ complexity due to needing three features ($s_1, s_0, b_0$), the other variants offer significant speedups.
Comparison of Unlabeled Attachment Scores (UAS) on PTB and CTB datasets, highlighting the superior performance of the proposed global training and exact decoding methods.

Conclusion

The integration of bi-LSTM contextual embeddings renders most traditional, manually engineered features redundant. This allows for a minimal feature approach that enables efficient, globally optimized transition-based parsing. Future work may explore even more refined training methods and further investigate the narrowing gap between transition-based and graph-based parsing architectures.

Summary updated

Abstract

We first present a minimal feature set for transition-based dependency parsing, continuing a recent trend started by Kiperwasser and Goldberg (2016a) and Cross and Huang (2016a) of using bi-directional LSTM features. We plug our minimal feature set into the dynamic-programming framework of Huang and Sagae (2010) and Kuhlmann et al. (2011) to produce the first implementation of worst-case O(n^3) exact decoders for arc-hybrid and arc-eager transition systems. With our minimal features, we also present O(n^3) global training methods. Finally, using ensembles including our new parsers, we achieve the best unlabeled attachment score reported (to our knowledge) on the Chinese Treebank and the "second-best-in-class" result on the English Penn Treebank.
BibTeX
@inproceedings{shi2017fast,
  author = {Tianze Shi and Liang Huang and Lillian Lee},
  title = {{Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  doi = {10.18653/v1/d17-1002},
}
Figure