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.
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.
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