Dynamic Feature Selection for Dependency Parsing

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1455–1464, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Dynamic Feature Selection for Dependency Parsing He He Hal Daum´e III Department of Computer Science University of Maryland College Park, MD 20740 {hhe,hal}@cs.umd.edu Jason Eisner Department of Computer Science Johns Hopkins University Baltimore, MD 21218 jason@cs.jhu.edu Abstract 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. 1 Introduction Graph-based dependency parsing usually consists of two stages. In the scoring stage, we score all pos- sible edges (or other small substructures) using a learned function; in the decoding stage, we use com- binatorial optimization to find the dependency tree with the highest total score. Generally linear edge-scoring functions are used for speed. But they use a large set of features, de- rived from feature templates that consider different conjunctions of the edge’s attributes. As a result, parsing time is dominated by the scoring stage— computing edge attributes, using them to instanti- ate feature templates, and looking up the weights of the resulting features in a hash table. For example, McDonald et al. (2005a) used on average about 120 first-order feature templates on each edge, built from attributes such as the edge direction and length, the two words connected by the edge, and the parts of speech of these and nearby words. We therefore ask the question: can we use fewer features to score the edges, while maintaining the ef- fect that the true dependency tree still gets a higher score? Motivated by recent progress on dynamic feature selection (Benbouzid et al., 2012; He et al., 2012), we propose to add features one group at a time to the dependency graph, and to use these fea- tures together with interactions among edges (as de- termined by intermediate parsing results) to make hard decisions on some edges before all their fea- tures have been seen. Our approach has a similar flavor to cascaded classifiers (Viola and Jones, 2004; Weiss and Taskar, 2010) in that we make decisions for each edge at every stage. However, in place of relatively simple heuristics such as a global relative pruning threshold, we learn a featurized decision- making policy of a more complex form. Since each decision can affect later stages, or later decisions in the same stage, we model this problem as a sequen- tial decision-making process and solve it by Dataset Aggregation (DAgger) (Ross et al., 2011), a recent iterative imitation learning technique for structured prediction. …

Content truncated to 500 words