Dynamic feature selection for dependency parsing

Feature computation and exhaustive search have significantly restricted the speed of graph-based dependency parsing. We propose a faster framework of dynamic feature selec-tion, 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 dy-namic parser can achieve accuracies compara-ble or even superior to parsers using a full set of features, while computing fewer than 30% of the feature templates.