Reverse Engineering of Tree Kernel Feature Spaces

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 111–120, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Reverse Engineering of Tree Kernel Feature Spaces 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 We present a framework to extract the most important features (tree fragments) from a Tree Kernel (TK) space according to their importance in the target kernel- based machine, e.g. Support Vector Ma- chines (SVMs). In particular, our min- ing algorithm selects the most relevant fea- tures based on SVM estimated weights and uses this information to automatically infer an explicit representation of the in- put data. The explicit features (a) improve our knowledge on the target problem do- main and (b) make large-scale learning practical, improving training and test time, while yielding accuracy in line with tradi- tional TK classifiers. Experiments on se- mantic role labeling and question classifi- cation illustrate the above claims. 1 Introduction The last decade has seen a massive use of Support Vector Machines (SVMs) for carrying out NLP tasks. Indeed, their appealing properties such as 1) solid theoretical foundations, 2) robustness to irrelevant features and 3) outperforming accuracy have been exploited to design state-of-the-art lan- guage applications. More recently, kernel functions, which im- plicitly represent data in some high dimensional space, have been employed to study and fur- ther improve many natural language systems, e.g. (Collins and Duffy, 2002), (Kudo and Matsumoto, 2003), (Cumby and Roth, 2003), (Cancedda et al., 2003), (Culotta and Sorensen, 2004), (Toutanova et al., 2004), (Kazama and Torisawa, 2005), (Shen et al., 2003), (Gliozzo et al., 2005), (Kudo et al., 2005), (Moschitti et al., 2008), (Diab et al., 2008). Unfortunately, the benefit to easily and effectively model the target linguistic phenomena is reduced by the the implicit nature of the kernel space, which prevents to directly observe the most rele- vant features. As a consequence, even very accu- rate models generally fail in providing useful feed- back for improving our understanding of the prob- lems at study. Moreover, the computational bur- den induced by high dimensional kernels makes the application of SVMs to large corpora still more problematic. In (Pighin and Moschitti, 2009), we proposed a feature extraction algorithm for Tree Kernel (TK) spaces, which selects the most relevant features (tree fragments) according to the gradient compo- nents (weight vector) of the hyperplane learnt by an SVM, in line with current research, e.g. (Rako- tomamonjy, 2003; Weston et al., 2003; Kudo and Matsumoto, 2003). In particular, we provided al- gorithmic solutions to deal with the huge dimen- sionality and, consequently, high computational complexity of the fragment space. Our experimen- tal results showed that our approach reduces learn- ing and classification processing time leaving the accuracy unchanged. In this paper, we present a new version of such algorithm which, under the same parameteriza- tion, is almost three times as fast while produc- ing the …

Content truncated to 500 words