Abstract. We present a general study of learning and linear separability with rational kernels, the sequence kernels commonly used in computational biology and natural language processing. We give a characterization of the class of all languages linearly separable with rational kernels and prove several properties of the class of languages linearly separable with a fixed rational kernel. In particular, we show that for kernels with finite range, these languages are necessarily finite Boolean combinations of preimages by a transducer of a single sequence. We also analyze the margin properties of linear separation with rational kernels and show that kernels with finite range guarantee a positive margin and lead to better learning guarantees. Creating a finite range rational kernel is often non-trivial even for relatively simple cases. However, we present a novel and general algorithm, doubletape disambiguation, that takes as input an arbitrary transducer mapping sequences to sequence features, and yields an associated transducer that defines a finite range rational kernel. We describe the algorithm in detail and show its application to several cases of interest. In previous work, we introduced a paradigm for learning languages that consists of mapping strings to an appropriate high-dimensional feature space and learning a separating hyperplane in that space [13] . We proved that the rich class of piecewise-testable languages [21] can be linearly separated using a high-dimensional feature mapping based on subsequences. We also showed that the positive definite kernel associated to this embedding, the subsequence kernel, can be efficiently computed. Support vector machines can be used in combination with this kernel to determine a separating hyperplane for piecewise-testable languages. We further proved that the languages linearly separable with this kernel are exactly the piecewise-testable languages. The subsequence kernel is a rational kernel -that is, a kernel that can be represented by weighted finite-state transducers [5, 12] . Most sequence kernels successfully used in computational biology and natural language processing, including mismatch kernels [15], gappy n-gram kernels [16] , locality-improved kernels [24] , convolutions kernels for strings [11] , tree kernels [4], n-gram kernels [5] , and moment kernels [6] , are special instances of rational kernels. Rational kernels can be computed in quadratic time using a single general algorithm [5] . This motivates our study of learning with rational kernels, in particular the question of determining the class of languages that can be linearly separated with a given rational kernel, thereby generalizing the result relating to subsequence kernels and piecewise-testable languages, and also analyzing their generalization properties based on the margin. It is also natural to ask which languages are separable with rational kernels in general.
This line of research is continued in REF , where linear separability properties of rational kernels are investigated.
Learning Languages with Rational Kernels
In Proceedings of The 20th Annual Conference on Learning Theory (COLT 2007
Computer Science