Rational Kernels

We introduce a general family of kernels based on weighted transducers orrational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in applications suchas computational biology or speech recognition. We show that rational kernels can be computed efficiently using a general algorithm ofcomposition of weighted transducers and a general single-source shortest-distance algorithm. We also describe several general families of positive definite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efficient and powerful techniquesfor spoken-dialog classification: highly complex kernels become easy to design and implement and lead to substantial improvements inthe classification accuracy. We also show that the string kernels considered in applications to computational biology are all specific instances ofrational kernels.