Feature Selection in Kernel Space: A Case Study on Dependency Parsing

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1180–1190, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Feature Selection in Kernel Space: A Case Study on Dependency Parsing Xian Qian and Yang Liu The University of Texas at Dallas 800 W. Campbell Rd., Richardson, TX, USA {qx,yangl}@hlt.utdallas.edu Abstract Given a set of basic binary features, we propose a new L1 norm SVM based feature selection method that explicitly selects the features in their polynomial or tree kernel spaces. The efficiency comes from the anti-monotone property of the subgradients: the subgradient with respect to a combined feature can be bounded by the subgradient with respect to each of its component features, and a feature can be pruned safely without further consideration if its corresponding subgradient is not steep enough. We conduct experiments on the English dependency parsing task with a third order graph-based parser. Benefiting from the rich features selected in the tree kernel space, our model achieved the best reported unlabeled attachment score of 93.72 without using any additional resource. 1 Introduction In Natural Language Processing (NLP) domain, existing linear models typically adopt exhaustive search to generate tons of features such that the important features are included. However, the brute-force approach will guickly run out of memory when the feature space is extremely large. Unlike linear models, kernel methods provide a powerful and unified framework for learning a large or even infinite number of features implicitly using limited memory. However, many kernel methods scale quadratically in the number of training samples, and can hardly reap the benefits of learning a large dataset. For example, the popular Penn Tree Bank (PTB) corpus for training an English part of speech (POS) tagger has approximately 1M words, thus it takes 1M 2 time to compute the kernel matrix, which is unacceptable using current hardwares. In this paper, we propose a new feature selection method that can efficiently select representative features in the kernel space to improve the quality of linear models. Specifically, given a limited number of basic features such as the commonly used unigrams and bigrams, our method performs feature selection in the space of their combinations, e.g, the concatenation of these n-grams. A sparse discriminative model is produced by training L1 norm SVMs using subgradient methods. Different from traditional training procedures, we divide the feature vector into a number of segments, and sort them in a coarse-to-fine order: the first segment includes the basic features, the second segment includes the combined features composed of two basic features, and so on. In each iteration, we calculate the subgradient segment by segment. A combined feature and all its further combinations in the following segments can be safely pruned if the absolute value of its corresponding subgradient is not sufficiently large. The algorithm stops until all features are pruned. Besides, two simple yet effective pruning strategies are proposed to filter the combinations. We conduct experiments on English …

Content truncated to 500 words