Abstract
Transition-based dependency parsers are valued for their efficiency but often struggle with error propagation. Recent advancements have integrated global learning and beam search to achieve state-of-the-art accuracy. This paper explores the underlying reasons for this success, demonstrating that global learning and beam search are synergistic. Together, they allow parsers to utilize complex, non-local features that would lead to overfitting in traditional greedy systems.
Introduction
Dependency parsing involves mapping the grammatical structure of sentences by identifying relationships between words. Transition-based parsers typically use a sequence of local actions (e.g., "shift" or "reduce") to build these structures. While fast, a single incorrect early decision can lead to significant downstream errors. To mitigate this, researchers introduced beam search to track multiple hypotheses and global learning to optimize the entire action sequence. This study investigates whether these improvements stem solely from reduced search errors or if there is a deeper interaction with feature representation.
Methodology
The researchers utilized ZPar, a transition-based parser, to conduct controlled experiments isolating three key variables:
- Learning Method: Local Learning (multi-class classification per action) vs. Global Learning (structured perceptron for the entire sequence).
- Search Strategy: Beam sizes ranging from 1 (greedy) to 64.
- Feature Sets: "Base" features vs. "Rich" non-local features (e.g., word valency, distance, and third-order dependencies).
Performance was evaluated on the Penn Treebank (PTB) and the CoNLL-X Shared Task data across 13 languages.
The Synergy of Global Learning and Beam Search
A critical finding is that global learning and beam search must be paired to be effective. As illustrated in Figure 1, increasing the beam size significantly improves the Unlabeled Attached Score (UAS) for globally-trained models but drastically degrades performance for locally-trained ones.
This phenomenon is attributed to "label bias" or a training-test mismatch. A locally-trained model is not optimized to distinguish between the numerous high-scoring but incorrect paths exposed during a beam search, leading it to choose erroneous structures that it was never trained to reject.
Feature Accommodation and Error Analysis
The combination of global learning and beam search acts as a regularizer, allowing the parser to "accommodate" rich, non-local features. In a greedy parser, these complex features often lead to overfitting, providing little to no accuracy gain. However, in the global beam-search framework, rich features provided a substantial 0.89% UAS improvement.
Furthermore, this combination allows transition-based parsers to bridge the gap with graph-based parsers. Error analysis shows that ZPar maintains high precision on long-distance dependencies, a traditional weakness of transition-based systems.
As shown in Figure 6, ZPar's precision for long-distance arcs (length > 8) remains stable and competitive with the global MSTParser, whereas the greedy MaltParser's performance drops significantly.
Conclusion
The study concludes that the success of modern transition-based parsers is not just due to better search, but to the synergistic interaction between global learning and beam search. This pairing enables the effective use of non-local features, making the parsers robust across varying dependency lengths. While challenges remain for exceptionally long sentences, the global/beam-search paradigm represents a fundamental shift in transition-based parsing capabilities.
Summary updated