A Study on the Dynamic Time Warping in Kernel Machines
Authors:
- Hansheng LeiHLHansheng Lei
- Bingyu SunBSBingyu Sun
- 1 December 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 839-845
Abstract
The dynamic time warping (DTW) is state-of-the-art distance measure widely used in sequential pattern matching and it outperforms Euclidean distance in most cases because its matching is elastic and robust. It is tempting to substitute DTW distance for Euclidean distance in the Gaussian RBF kernel and plug it into the state-of-the art classifier support vector machines (SVMs) for sequence classification. However, it is not straightforward that DTW also outperforms Euclidean distance in kernel machines. While counter-examples can be found to numerically prove that DTW is not positive definite symmetric (PDS)acceptable by SVM, little is known why it can not be PDS theoretically. We analyze the DTW kernel and complete a theoretical proof via the connection between PDS kernel and reproducing kernel Hilbert space (RKHS). Our analysis leads to a better understanding that all Hilbertian metrics can be be converted to a PDS kernel in the Gaussian form, while the reverse is not true. The proof can be extended to conclude that elastic matching distance is not eligible to construct PDS kernels (e.g., Edit distance). Experiments were conducted to compare the RBF-kernel and DTW kernel in SVM classifications and the results show that simple Euclidean distance outperforms DTW in kernel machines.Keywords
This publication has 11 references indexed in Scilit:
- An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF KernelsIEEE Transactions on Information Theory, 2006
- Distance measures for effective clustering of ARIMA time-series2002
- On the need for time series data mining benchmarks2002
- Tangent distance kernels for support vector machines2002
- Segment-based approach for subsequence searches in sequence databases2001
- Bounds on Error Expectation for Support Vector MachinesNeural Computation, 2000
- Adaptive query processing for time-series data1999
- Algebraic aspects of interpolation1986
- Theory of reproducing kernelsTransactions of the American Mathematical Society, 1950
- Metric spaces and positive definite functionsTransactions of the American Mathematical Society, 1938