Rational Kernels

Abstract

We introduce a general family of kernels based on weighted transduc- ers or rational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in appli- cations such as computational biology or speech recognition. We show that rational kernels can be computed efficiently using a general algo- rithm of composition 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 power- ful techniques for spoken-dialog classification: highly complex kernels become easy to design and implement and lead to substantial improve- ments in the classification accuracy. We also show that the string kernels considered in applications to computational biology are all specific in- stances of rational kernels.