Speeding up Training with Tree Kernels for Node Relation Labeling

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 137–144, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Speeding up Training with Tree Kernels for Node Relation Labeling Jun’ichi Kazama and Kentaro Torisawa Japan Advanced Institute of Science and Technology (JAIST) Asahidai 1-1, Nomi, Ishikawa, 923-1292 Japan {kazama, torisawa}@jaist.ac.jp Abstract We present a method for speeding up the calculation of tree kernels during train- ing. The calculation of tree kernels is still heavy even with efficient dynamic pro- gramming (DP) procedures. Our method maps trees into a small feature space where the inner product, which can be cal- culated much faster, yields the same value as the tree kernel for most tree pairs. The training is sped up by using the DP pro- cedure only for the exceptional pairs. We describe an algorithm that detects such ex- ceptional pairs and converts trees into vec- tors in a feature space. We propose tree kernels on marked labeled ordered trees and show that the training of SVMs for semantic role labeling using these kernels can be sped up by a factor of several tens. 1 Introduction Many NLP tasks such as parse selection and tag- ging can be posed as the classification of labeled ordered trees. Several tree kernels have been pro- posed for building accurate kernel-based classifiers (Collins and Duffy, 2001; Kashima and Koyanagi, 2002). They have the following form in common. K(T1, T2) = � Si W(Si) · #Si(T1) · #Si(T2), (1) where Si is a possible subtree, #Si(Tj) is the num- ber of times Si is included in Tj, and W(Si) is the weight of Si. That is, tree kernels are inner products in a subtree feature space where a tree is mapped to vector V (Tj) = �� W(Si)#Si(Tj) � With tree kernels we can take global structures intoi. account, while alleviating overfitting with kernel- based learning methods such as support vector ma- chines (SVMs) (Vapnik, 1995). Previous studies (Collins and Duffy, 2001; Kashima and Koyanagi, 2002) showed that although it is difficult to explicitly calculate the inner product in Eq. (1) because we need to consider an exponen- tial number of possible subtrees, the tree kernels can be computed in O(|T1||T2|) time by using dynamic programming (DP) procedures. However, these DP procedures are time-consuming in practice. In this paper, we present a method for speeding up the training with tree kernels. Our target ap- plication is node relation labeling, which includes NLP tasks such as semantic role labeling (SRL) (Gildea and Jurafsky, 2002; Moschitti, 2004; Ha- cioglu et al., 2004). For this purpose, we designed kernels on marked labeled ordered trees and derived O(|T1||T2|) procedures. However, the lengthy train- ing due to the cost of kernel calculation prevented us from assessing the performance of these kernels and motivated us to make the training practically fast. Our speed-up method is based on the observation that very few pairs in the training set have a great many common subtrees (we call …

Content truncated to 500 words