Parameterizing the cost function of Dynamic Time Warping with application to time series classification

• URL: http://arxiv.org/abs/2301.10350v2
• Date: Wed, 29 Mar 2023 03:16:44 GMT
• Title: Parameterizing the cost function of Dynamic Time Warping with application to time series classification
• Authors: Matthieu Herrmann, Chang Wei Tan, Geoffrey I. Webb
• Abstract summary: We show that higher values of gamma place greater weight on larger pairwise differences, while lower values place greater weight on smaller pairwise differences. We demonstrate that training gamma significantly improves the accuracy of both the DTW nearest neighbor and Proximity Forest classifiers.
• Score: 4.752559512511424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic Time Warping (DTW) is a popular time series distance measure that aligns the points in two series with one another. These alignments support warping of the time dimension to allow for processes that unfold at differing rates. The distance is the minimum sum of costs of the resulting alignments over any allowable warping of the time dimension. The cost of an alignment of two points is a function of the difference in the values of those points. The original cost function was the absolute value of this difference. Other cost functions have been proposed. A popular alternative is the square of the difference. However, to our knowledge, this is the first investigation of both the relative impacts of using different cost functions and the potential to tune cost functions to different tasks. We do so in this paper by using a tunable cost function {\lambda}{\gamma} with parameter {\gamma}. We show that higher values of {\gamma} place greater weight on larger pairwise differences, while lower values place greater weight on smaller pairwise differences. We demonstrate that training {\gamma} significantly improves the accuracy of both the DTW nearest neighbor and Proximity Forest classifiers.

Related papers

• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Deep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths [54.53208538517505]
  This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW) We propose a DTW layer based around bi-level optimisation and deep declarative networks, which we name DecDTW. We show that this property is particularly useful for applications where downstream loss functions are defined on the optimal alignment path itself.
  arXiv  Detail & Related papers  (2023-03-19T21:58:37Z)
• Asynchronous Training Schemes in Distributed Learning with Time Delay [17.259708772713164]
  In the context of distributed deep learning, the issue of stale weights or gradients could result in poor algorithmic performance. In this paper, we propose a different approach to tackle the issue of stale weights or gradients. One practical variant of PC-ASGD is also proposed by adopting a condition to help with the determination of the tradeoff parameter.
  arXiv  Detail & Related papers  (2022-08-28T07:14:59Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Amercing: An Intuitive, Elegant and Effective Constraint for Dynamic Time Warping [6.063782572064742]
  We introduce Amerced Dynamic Time Warping (ADTW), a new, intuitive, DTW variant that penalizes the act of warping by a fixed additive cost. We show how it can be parameterized to achieve an intuitive outcome, and demonstrate its usefulness on a standard time series classification benchmark.
  arXiv  Detail & Related papers  (2021-11-26T05:11:04Z)
• Two-phase Optimization of Binary Sequences with Low Peak Sidelobe Level Value [1.5990720051907859]
  Two fitness functions are used to find sequences with low peak sidelobe level value. The proposed algorithm was tested on sequences with lengths $L = 2m - 1$, for $14 le m le 20$.
  arXiv  Detail & Related papers  (2021-06-30T13:59:55Z)
• Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
  Generalized self-concordance is a key property present in the objective function of many learning problems. We show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.
  arXiv  Detail & Related papers  (2021-05-28T15:26:36Z)
• Temporal Difference Learning as Gradient Splitting [15.321579527891457]
  We show that convergence proofs for gradient descent can be applied almost verbatim to temporal difference learning. We show that a minor variation on TD learning which estimates the mean of the value function separately has a convergence time where $1/(1-gamma)$ only multiplies anally negligible term.
  arXiv  Detail & Related papers  (2020-10-27T22:50:39Z)
• Differentiable Divergences Between Time Series [34.60983018798683]
  We propose a new divergence, dubbed soft-DTW divergence, to solve the discrepancy between time series of variable sizes. We show that it is non-negative and minimized if and only if the two time series are equal. We also propose a new "sharp" variant by further removing entropic bias.
  arXiv  Detail & Related papers  (2020-10-16T12:45:13Z)
• Aligning Time Series on Incomparable Spaces [83.8261699057419]
  We propose Gromov dynamic time warping (GDTW), a distance between time series on potentially incomparable spaces. We demonstrate its effectiveness at aligning, combining and comparing time series living on incomparable spaces.
  arXiv  Detail & Related papers  (2020-06-22T22:19:28Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
  arXiv  Detail & Related papers  (2020-02-05T03:09:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.