On Reverse Feature Engineering of Syntactic Tree Kernels

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 223–233, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics On Reverse Feature Engineering of Syntactic Tree Kernels Daniele Pighin FBK-irst, DISI, University of Trento Via di Sommarive, 14 I-38123 Povo (TN) Italy daniele.pighin@gmail.com Alessandro Moschitti DISI, University of Trento Via di Sommarive, 14 I-38123 Povo (TN) Italy moschitti@disi.unitn.it Abstract In this paper, we provide a theoretical framework for feature selection in tree ker- nel spaces based on gradient-vector com- ponents of kernel-based machines. We show that a huge number of features can be discarded without a significant decrease in accuracy. Our selection algorithm is as accurate as and much more efficient than those proposed in previous work. Com- parative experiments on three interesting and very diverse classification tasks, i.e. Question Classification, Relation Extrac- tion and Semantic Role Labeling, support our theoretical findings and demonstrate the algorithm performance. 1 Introduction Kernel functions are very effective at modeling diverse linguistic phenomena by implicitly rep- resenting data in high dimensional spaces, e.g. (Cumby and Roth, 2003; Culotta and Sorensen, 2004; Kudo et al., 2005; Moschitti et al., 2008). However, the implicit nature of the kernel space causes two major drawbacks: (1) high computa- tional costs for learning and classification, and (2) the impossibility to identify the most important features. A solution to both problems is the ap- plication of feature selection techniques. In particular, the problem of feature selection in Tree Kernel (TK) spaces has already been ad- dressed by previous work in NLP, e.g. (Kudo and Matsumoto, 2003; Suzuki and Isozaki, 2005). However, these approaches lack a theoretical char- acterization of the problem that could support and justify the design of more effective algorithms. In (Pighin and Moschitti, 2009a) and (Pighin and Moschitti, 2009b) (P&M), we presented a heuristic framework for feature selection in kernel spaces that selects features based on the compo- nents of the weight vector, ⃗w, optimized by Sup- port Vector Machines (SVMs). This method ap- pears to be very effective, as the model accuracy does not significantly decrease even when a large number of features are filtered out. Unfortunately, we could not provide theoretical or intuitive moti- vations to justify our proposed apporach. In this paper, we present and empirically val- idate a theory which aims at filling the above- mentioned gaps. In particular we provide: (i) a proof of the equation for the exact computation of feature weights induced by TK functions (Collins and Duffy, 2002); (ii) a theoretical characteriza- tion of feature selection based on ∥⃗w∥. We show that if feature selection does not sensibly reduces ∥⃗w∥, the margin associated with ⃗w does not sen- sibly decrease as well. Consequently, the theoret- ical upperbound to the probability error does not sensibly increases; (iii) a proof that the convolu- tive nature of TK allows for filtering out an expo- nential number of features with a small ∥⃗w∥ de- crease. The combination of (ii) with (iii) suggests that an extremely aggressive feature selection can be …

Content truncated to 500 words