Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)
Alex Smola, S.v.n. Vishwanathan
In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynarrtic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the se(cid:173) quence to be classified, regardless of the number of support vectors. This improvement on the currently available algorithms makes string kernels a viable alternative for the practitioner.