On Recursive Edit Distance Kernels with Application to Time Series Classification

Abstract

This paper proposes some extensions to the work on kernels dedicated to string or time series global alignment based on the aggregation of scores obtained by local alignments. The extensions we propose allow to construct, from classical recursive definition of elastic distances, recursive edit distance (or time-warp) kernels that are positive definite if some sufficient conditions are satisfied. The sufficient conditions we end-up with are original and weaker than those proposed in earlier works, although a recursive regularizing term is required to get the proof of the positive definiteness as a direct consequence of the Haussler's convolution theorem. The classification experiment we conducted on three classical time warp distances (two of which being metrics), using Support Vector Machine classifier, leads to conclude that, when the pairwise distance matrix obtained from the training data is \textit{far} from definiteness, the positive definite recursive elastic kernels outperform in general the distance substituting kernels for the classical elastic distances we have tested.

14 pages

References in corpus (3)

• Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching
• A kernel for time series based on global alignments
• Discrete Elastic Inner Vector Spaces with Application in Time Series and Sequence Mining

Cited by in corpus (11)

• Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
• Sparsification of the Alignment Path Search Space in Dynamic Time Warping
• Times series averaging from a probabilistic interpretation of time-elastic kernel
• Times series averaging and denoising from a probabilistic perspective on time-elastic kernels
• Correlative Channel-Aware Fusion for Multi-View Time Series Classification
• An Unsupervised Multivariate Time Series Kernel Approach for Identifying Patients with Surgical Site Infection from Blood Samples
• Time Series Cluster Kernel for Learning Similarities between Multivariate Time Series with Missing Data
• An Empirical Approach For Probing the Definiteness of Kernels
• Efficient Kernel-based Subsequence Search for User Identification from Walking Activity
• On the separation of shape and temporal patterns in time series -Application to signature authentication-
• Adaptive Down-Sampling and Dimension Reduction in Time Elastic Kernel Machines for Efficient Recognition of Isolated Gestures