Rational Kernels
Corinna Cortes, Patrick Haffner, Mehryar Mohri · neural information processing systems · 2002
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.
Cited by 52 works.
Authors
References
- Statistical Learning Theory
- Text categorization with Support Vector Machines: Learning with many relevant features
- Combinatorial optimization: networks and matroids
- BoosTexter: A Boosting-based System for Text Categorization
- Convolution kernels on discrete structures
- Transductions and Context-Free Languages
- Harmonic Analysis on Semigroups
- Speech Recognition by Composition of Weighted Finite Automata
- Automata-Theoretic Aspects of Formal Power Series
- Text Classification using String Kernels