Making Tree Kernels Practical for Natural Language Learning

Making Tree Kernels practical for Natural Language Learning Alessandro Moschitti Department of Computer Science University of Rome ”Tor Vergata” Rome, Italy moschitti@info.uniroma2.it Abstract In recent years tree kernels have been pro- posed for the automatic learning of natural language applications. Unfortunately, they show (a) an inherent super linear complex- ity and (b) a lower accuracy than tradi- tional attribute/value methods. In this paper, we show that tree kernels are very helpful in the processing of nat- ural language as (a) we provide a simple algorithm to compute tree kernels in linear average running time and (b) our study on the classification properties of diverse tree kernels show that kernel combinations al- ways improve the traditional methods. Ex- periments with Support Vector Machines on the predicate argument classification task provide empirical support to our the- sis. 1 Introduction In recent years tree kernels have been shown to be interesting approaches for the modeling of syn- tactic information in natural language tasks, e.g. syntactic parsing (Collins and Duffy, 2002), rela- tion extraction (Zelenko et al., 2003), Named En- tity recognition (Cumby and Roth, 2003; Culotta and Sorensen, 2004) and Semantic Parsing (Mos- chitti, 2004). The main tree kernel advantage is the possibility to generate a high number of syntactic features and let the learning algorithm to select those most rel- evant for a specific application. In contrast, their major drawback are (a) the computational time complexity which is superlinear in the number of tree nodes and (b) the accuracy that they produce is often lower than the one provided by linear models on manually designed features. To solve problem (a), a linear complexity al- gorithm for the subtree (ST) kernel computation, was designed in (Vishwanathan and Smola, 2002). Unfortunately, the ST set is rather poorer than the one generated by the subset tree (SST) kernel de- signed in (Collins and Duffy, 2002). Intuitively, an ST rooted in a node n of the target tree always contains all n’s descendants until the leaves. This does not hold for the SSTs whose leaves can be internal nodes. To solve the problem (b), a study on different tree substructure spaces should be carried out to derive the tree kernel that provide the highest ac- curacy. On the one hand, SSTs provide learn- ing algorithms with richer information which may be critical to capture syntactic properties of parse trees as shown, for example, in (Zelenko et al., 2003; Moschitti, 2004). On the other hand, if the SST space contains too many irrelevant features, overfitting may occur and decrease the classifica- tion accuracy (Cumby and Roth, 2003). As a con- sequence, the fewer features of the ST approach may be more appropriate. In this paper, we aim to solve the above prob- lems. We present (a) an algorithm for the eval- uation of the ST and SST kernels which runs in linear average time and (b) a study of the impact of diverse tree kernels on the accuracy of Support Vector Machines (SVMs). Our fast algorithm computes …

Content truncated to 500 words