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:
- 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.
- $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.
- Global Training: The model is optimized using a structured large-margin loss, which considers the entire sequence of transitions rather than individual local moves.
- 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.
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.
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