Dynamic Feature Selection for Dependency Parsing

He He, Hal Daumé Iii, Jason Eisner

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:

  1. Feature Grouping: Templates are ranked by their contribution to accuracy and partitioned into groups.
  2. 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.
  3. 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.
  4. Constraint Propagation: Once an edge is locked, the search space is dynamically reduced by enforcing tree and projectivity constraints.
The dynamic parsing process: (a) initial state, (b-d) iterative feature addition and edge locking/pruning, (e-f) final decoding.

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.

Performance metrics across feature selection stages: UAS increases while the percentage of remaining edges decreases significantly.

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

Abstract

Feature computation and exhaustive search have significantly restricted the speed of graph-based dependency parsing. We propose a faster framework of dynamic feature selection, where features are added sequentially as needed, edges are pruned early, and decisions are made online for each sentence. We model this as a sequential decision-making problem and solve it by imitation learning techniques. We test our method on 7 languages. Our dynamic parser can achieve accuracies comparable or even superior to parsers using a full set of features, while computing fewer than 30% of the feature templates.
BibTeX
@inproceedings{he2013dynamic,
  author = {He He and Hal Daumé III and Jason Eisner},
  title = {{Dynamic Feature Selection for Dependency Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
  doi = {10.18653/v1/d13-1152},
}
Figure