Computational Biology CB_D0003

Title : Rational Kernels
Author : Corinna Cortes Patrick Haffner Mehryar Mohri
Year : 2003
Place of publish : AT&T Labs – Research
Abstract :

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