A Dependency-based Word Subsequence Kernel

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 400–409, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics A Dependency-based Word Subsequence Kernel Rohit J. Kate Department of Computer Sciences The University of Texas at Austin 1 University Station C0500 Austin, TX 78712-0233, USA rjkate@cs.utexas.edu Abstract This paper introduces a new kernel which computes similarity between two natural lan- guage sentences as the number of paths shared by their dependency trees. The paper gives a very efficient algorithm to compute it. This kernel is also an improvement over the word subsequence kernel because it only counts linguistically meaningful word subsequences which are based on word dependencies. overcomes some of the difficulties encoun-It tered by syntactic tree kernels as well. Ex- perimental results demonstrate the advantage of this kernel over word subsequence and syn- tactic tree kernels. 1 Introduction Kernel-based learning methods (Vapnik, 1998) are becoming increasingly popular in natural language processing (NLP) because they allow one to work with potentially infinite number of features with- out explicitly constructing or manipulating them. In most NLP problems, the data is present in structured forms, like strings or trees, and this structural infor- mation can be effectively passed to a kernel-based learning algorithm using an appropriate kernel, like a string kernel (Lodhi et al., 2002) or a tree kernel (Collins and Duffy, 2001). In contrast, feature-based methods require reducing the data to a pre-defined set of features often leading to some loss of the use- ful structural information present in the data. A kernel is a measure of similarity between ev- ery pair of examples in the data and a kernel-based machine learning algorithm accesses the data only through these kernel values. For example, the string kernel (Lodhi et al., 2002; Cancedda et al., 2003) computes the similarity between two natural lan- guage strings as the number of common word sub- sequences between them. A subsequence allows gaps between the common words which are penal- ized according to a parameter. Each word subse- quence hence becomes an implicit feature used by the kernel-based machine learning algorithm. problem with this kernel is that many of these wordA subsequences common between two strings may not be semantically expressive or linguistically mean- ingful1. Another problem with this kernel is that if there are long-range dependencies between the words in a common word subsequence, then they will unfairly get heavily penalized because of the presence of word gaps. The syntactic tree kernel presented in (Collins and Duffy, 2001) captures the structural similarity be- tween two syntactic trees as the number of syntac- tic subtrees common between them. However, of- ten syntactic parse trees may share syntactic sub- trees which correspond to very different semantics based on what words they represent in the sentence. On the other hand, some subtrees may differ syn- tactically but may represent similar underlying se- mantics. These differences can become particularly problematic if the tree kernel is to be used for tasks which require semantic processing. This paper presents …

Content truncated to 500 words