  We propose in this paper a new family of kernels to handle times series,
notably speech data, within the framework of kernel methods which includes
popular algorithms such as the Support Vector Machine. These kernels elaborate
on the well known Dynamic Time Warping (DTW) family of distances by considering
the same set of elementary operations, namely substitutions and repetitions of
tokens, to map a sequence onto another. Associating to each of these operations
a given score, DTW algorithms use dynamic programming techniques to compute an
optimal sequence of operations with high overall score. In this paper we
consider instead the score spanned by all possible alignments, take a smoothed
version of their maximum and derive a kernel out of this formulation. We prove
that this kernel is positive definite under favorable conditions and show how
it can be tuned effectively for practical applications as we report encouraging
results on a speech recognition task.
