Corinna Cortes, Patrick Haffner, Mehryar Mohri
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 efﬁciently 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 deﬁnite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efﬁcient and power- ful techniques for spoken-dialog classiﬁcation: highly complex kernels become easy to design and implement and lead to substantial improve- ments in the classiﬁcation accuracy. We also show that the string kernels considered in applications to computational biology are all speciﬁc in- stances of rational kernels.