Abstract
Graph-based dependency parsing traditionally suffers from high computational costs due to the exhaustive scoring of all possible edges using hundreds of feature templates. We present a dynamic feature selection framework that treats parsing as a sequential decision-making problem. By adaptively adding feature groups and utilizing a "lock or add" policy trained via imitation learning (DAgger), our approach achieves state-of-the-art accuracy while computing fewer than 30% of total feature templates. Evaluation across seven languages demonstrates significant speedups, with a 5.5x improvement on the English Penn Treebank.
Introduction
In graph-based dependency parsing, the objective is to identify the highest-scoring tree structure representing grammatical relationships within a sentence. While decoding algorithms are mathematically complex, the primary computational bottleneck is feature scoring. Modern parsers employ hundreds of feature templates to evaluate every $O(n^2)$ possible edge, a process that accounts for over 80% of total parsing time. Much of this effort is redundant, as many edges can be correctly identified or dismissed using only a small fraction of available information.
Methodology
This paper proposes a framework where feature selection is handled as a sequential decision-making task. Instead of a one-shot scoring process, the parser proceeds through several stages:
- Feature Grouping: Templates are ranked by their contribution to accuracy and partitioned into groups.
- The "Lock or Add" Policy: At each stage, a fast first-order parser suggests a tree. A learned policy (binary classifier) then decides for each edge whether to Lock it (committing to the edge and pruning competitors) or Add more complex feature groups to resolve uncertainty.
- Imitation Learning (DAgger): To ensure robustness against early errors, the policy is trained using Dataset Aggregation (DAgger). This allows the model to learn from an expert while also learning to recover from its own past mistakes.
- Constraint Propagation: Once an edge is locked, the search space is dynamically reduced by enforcing tree and projectivity constraints.
Experimental Evaluation
The approach was evaluated on the English Penn Treebank (PTB) and the CoNLL-X Shared Task datasets, covering six additional languages: Bulgarian, Chinese, German, Japanese, Portuguese, and Swedish. The primary metrics were Unlabeled Attachment Score (UAS) and parsing speedup.
Results and Discussion
The dynamic parser demonstrated remarkable efficiency, achieving comparable or superior accuracy to full-feature baselines while computing fewer than 30% of the feature templates. On the English PTB, the first-order dynamic parser achieved a 5.5x speedup.
As shown in the figure above, the Unlabeled Attachment Score (UAS) rises rapidly in early stages, while the percentage of remaining edges to be scored drops sharply. This confirms the "80/20 rule" of features: most grammatical dependencies can be resolved with minimal information. Interestingly, in languages like Chinese and Japanese, dynamic selection actually improved UAS, suggesting that pruning low-value features acts as a form of regularization.
Conclusion
Dynamic feature selection offers a powerful alternative to static pruning methods in dependency parsing. By leveraging structural context and sequential decision-making, the framework significantly reduces the computational burden of feature scoring without sacrificing accuracy. Future work may involve optimizing parser weights specifically for the dynamic setting to further enhance robustness when only partial features are available.
Summary updated