Text Classification using String Kernels

We introduce a novel kernel for comparing two text documents. The kernel is an inner product in the feature space consisting of all subsequences of length k. A subsequence is any ordered se(cid: 173) quence of k characters occurring in the text though not necessarily contiguously. The subsequences are weighted by an exponentially decaying factor of their full length in the text, hence emphasising those occurrences which are close to contiguous. A direct compu(cid: 173) tation of this feature vector would involve a prohibitive amount of computation even for modest values of k, since the dimension of the feature space grows exponentially with k. The paper describes how despite this fact the inner product can be efficiently evaluated by a dynamic programming technique. A preliminary experimental comparison of the performance of the kernel compared with a stan(cid: 173) dard word feature space kernel results. [6] is made showing encouraging

Authors

• Huma Lodhi
• John Shawe-Taylor University College London
• Nello Cristianini
• Christopher Watkins

Keywords

No keywords are indexed for this paper.