Efficient Linearization of Tree Kernel Functions

Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL), pages 30–38, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Efficient Linearization of Tree Kernel Functions Daniele Pighin FBK-Irst, HLT Via di Sommarive, 18 I-38100 Povo (TN) Italy pighin@fbk.eu Alessandro Moschitti University of Trento, DISI Via di Sommarive, 14 I-38100 Povo (TN) Italy moschitti@disi.unitn.it Abstract The combination of Support Vector Machines with very high dimensional kernels, such as string or tree kernels, suffers from two ma- jor drawbacks: first, the implicit representa- tion of feature spaces does not allow us to un- derstand which features actually triggered the generalization; second, the resulting compu- tational burden may in some cases render un- feasible to use large data sets for training. We propose an approach based on feature space reverse engineering to tackle both problems. Our experiments with Tree Kernels on a Se- mantic Role Labeling data set show that the proposed approach can drastically reduce the computational footprint while yielding almost unaffected accuracy. 1 Introduction The use of Support Vector Machines (SVMs) in supervised learning frameworks is spreading across different communities, including Computa- tional Linguistics and Natural Language Processing, thanks to their solid mathematical foundations, ef- ficiency and accuracy. Another important reason for their success is the possibility of using kernel functions to implicitly represent examples in some high dimensional kernel space, where their similar- ity is evaluated. Kernel functions can generate a very large number of features, which are then weighted by the SVM optimization algorithm obtaining a fea- ture selection side-effect. Indeed, the weights en- coded by the gradient of the separating hyperplane learnt by the SVM implicitly establish a ranking be- tween features in the kernel space. This property has been exploited in feature selection models based on approximations or transformations of the gradient, e.g. (Rakotomamonjy, 2003), (Weston et al., 2003) or (Kudo and Matsumoto, 2003). However, kernel based systems have two major drawbacks: first, new features may be discovered in the implicit space but they cannot be directly ob- served. Second, since learning is carried out in the dual space, it is not possible to use the faster SVM or perceptron algorithms optimized for linear spaces. Consequently, the processing of large data sets can be computationally very expensive, limiting the use of large amounts of data for our research or applica- tions. We propose an approach that tries to fill in the gap between explicit and implicit feature represen- tations by 1) selecting the most relevant features in accordance with the weights estimated by the SVM and 2) using these features to build an explicit rep- resentation of the kernel space. The most innovative aspect of our work is the attempt to model and im- plement a solution in the context of structural ker- nels. In particular we focus on Tree Kernel (TK) functions, which are especially interesting for the Computational Linguistics community as they can effectively encode rich syntactic data into a kernel- based learning algorithm. The high dimensionality of a TK feature space …

Content truncated to 500 words