Rational Kernels: Theory and Algorithms
Corinna Cortes, Patrick Haffner, Mehryar Mohri · 2004
Many classification algorithms were originally designed for fixed-size vectors. Recent applications in text and speech processing and computational biology require however the analysis of variablelength sequences and more generally weighted automata. An approach widely used in statistical learning techniques such as Support Vector Machines (SVMs) is that of kernel methods, due to their computational efficiency in high-dimensional feature spaces. We introduce a general family of kernels based on weighted transducers or rational relations, rational kernels, that extend kernel methods to the analysis of variable-length sequences or more generally weighted automata. 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. Not all rational kernels are positive definite and symmetric (PDS), or equivalently verify the Mercer condition, a condition that guarantees the convergence of training for discriminant classification algorithms such as SVMs. We present several theoretical results related to PDS rational kernels. We show that under some general conditions these kernels are closed under sum, product, or Kleene-closure and give a general method for constructing a PDS rational kernel from an
Cited by 153 works.
Authors
References
- Support-Vector Networks
- Statistical Learning Theory
- A training algorithm for optimal margin classifiers
- Combinatorial optimization: networks and matroids
- Binary codes capable of correcting deletions, insertions and reversals
- Biological sequence analysis probabilistic models of proteins and nucleic acids
- BoosTexter: A Boosting-based System for Text Categorization
- LINPACK User's Guide.
- Convolution kernels on discrete structures
- Transductions and Context-Free Languages