Rational Kernels: Theory and Algorithms

Corinna Cortes, Patrick Haffner, Mehryar MohriJMLR 2004 · OpenReview

Introduction

Classical machine learning algorithms, such as Support Vector Machines (SVMs), typically require fixed-length feature vectors. However, real-world data—including speech, natural language, and biological sequences—is inherently sequential and variable in length. In fields like Automatic Speech Recognition (ASR), the challenge is compounded: systems often produce "word lattices"—weighted directed graphs representing multiple possible transcriptions—rather than a single string.

Examples of weighted automata (a, b) and a more complex lattice (c) representing multiple sequence hypotheses.

Standard approaches often discard this rich information, relying on the "one-best" hypothesis. This paper introduces rational kernels, a unified framework that allows SVMs to operate directly on these weighted automata and variable-length sequences, significantly improving classification robustness.

The Rational Kernel Framework

Rational kernels are defined using the machinery of weighted finite-state transducers (WFSTs). A rational kernel $K(x, y)$ is defined by a weighted transducer $T$ that maps an input sequence $x$ to an output $y$ with a specific weight. The kernel value is the sum of weights of all paths transforming $x$ into $y$.

The computation of these kernels relies on the concept of semirings, which define the algebraic operations for addition ($\oplus$) and multiplication ($\otimes$) within the transducer framework.

Common semirings used in rational kernels, defining the operations for different types of sequence weights.

The authors demonstrate that calculating the kernel between two weighted automata $A$ and $B$ is equivalent to finding the "shortest distance" through a composed network $A \circ T \circ B$. This framework provides a "Grand Unified Theory" for sequence-based kernels, showing that n-gram, mismatch, and convolution kernels are all specific instances of rational kernels.

Computational Efficiency and PDS Properties

For a kernel to be valid for SVMs, it must be Positive Definite Symmetric (PDS). The authors provide a general recipe for constructing PDS kernels by composing any transducer $T$ with its inverse ($T \circ T^{-1}$). They also prove closure properties: the sum, product, or Kleene-closure of PDS rational kernels remains PDS.

Crucially, the authors prove that the classic edit-distance is not negative definite over non-trivial alphabets, cautioning against its naive use in Gaussian-style kernels. This theoretical result highlights the importance of the PDS properties ensured by the rational kernel framework.

Experimental Evaluation

The framework was evaluated on three large-scale spoken-dialog datasets from AT&T (HMIHY 0300, VoiceTone1, and VoiceTone2). These datasets contain noisy, real-world speech with numerous call-type categories.

The results demonstrate that SVMs using rational kernels on full lattices consistently outperform those using only the "one-best" ASR output. On the HMIHY task, the lattice-based approach reduced the error rate by 1% absolute. The advantage was even more significant on the noisier VoiceTone2 dataset, showing up to a 6% absolute improvement. Despite the mathematical complexity, these kernels are computable in quadratic time relative to the automata size, making them suitable for real-time applications.

Conclusion

Rational kernels bridge the gap between structured sequential data and powerful discriminative classifiers like SVMs. By leveraging the full information contained in weighted lattices, this framework provides a robust and theoretically sound method for sequence classification. Future work includes extending these methods to non-PDS kernels and exploring higher-order "moment kernels" for even more descriptive feature spaces.

Summary updated

BibTeX
@article{cortes2004rational,
  author = {Corinna Cortes and Patrick Haffner and Mehryar Mohri},
  title = {{Rational Kernels: Theory and Algorithms}},
  journal = {J. Mach. Learn. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=P4HF3xA_BwJ},
}
Figure