Amercing: An Intuitive, Elegant and Effective Constraint for Dynamic Time Warping

• URL: http://arxiv.org/abs/2111.13314v1
• Date: Fri, 26 Nov 2021 05:11:04 GMT
• Title: Amercing: An Intuitive, Elegant and Effective Constraint for Dynamic Time Warping
• Authors: Matthieu Herrmann, Geoffrey I. Webb
• Abstract summary: 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.
• Score: 6.063782572064742
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic Time Warping (DTW), and its constrained (CDTW) and weighted (WDTW) variants, are time series distances with a wide range of applications. They minimize the cost of non-linear alignments between series. CDTW and WDTW have been introduced because DTW is too permissive in its alignments. However, CDTW uses a crude step function, allowing unconstrained flexibility within the window, and none beyond it. WDTW's multiplicative weight is relative to the distances between aligned points along a warped path, rather than being a direct function of the amount of warping that is introduced. In this paper, we introduce Amerced Dynamic Time Warping (ADTW), a new, intuitive, DTW variant that penalizes the act of warping by a fixed additive cost. Like CDTW and WDTW, ADTW constrains the amount of warping. However, it avoids both abrupt discontinuities in the amount of warping allowed and the limitations of a multiplicative penalty. We formally introduce ADTW, prove some of its properties, and discuss its parameterization. We show on a simple example how it can be parameterized to achieve an intuitive outcome, and demonstrate its usefulness on a standard time series classification benchmark. We provide a demonstration application in C++.

Related papers

• FinePseudo: Improving Pseudo-Labelling through Temporal-Alignablity for Semi-Supervised Fine-Grained Action Recognition [57.17966905865054]
  Real-life applications of action recognition often require a fine-grained understanding of subtle movements. Existing semi-supervised action recognition has mainly focused on coarse-grained action recognition. We propose an Alignability-Verification-based Metric learning technique to effectively discriminate between fine-grained action pairs.
  arXiv  Detail & Related papers  (2024-09-02T20:08:06Z)
• OTW: Optimal Transport Warping for Time Series [75.69837166816501]
  Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. It suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed exactly. We introduce a new metric for time series data based on the Optimal Transport framework, called Optimal Transport Warping (OTW)
  arXiv  Detail & Related papers  (2023-06-01T12:45:00Z)
• 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)
• Parameterizing the cost function of Dynamic Time Warping with application to time series classification [4.752559512511424]
  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.
  arXiv  Detail & Related papers  (2023-01-24T23:34:13Z)
• End-to-end Temporal Action Detection with Transformer [86.80289146697788]
  Temporal action detection (TAD) aims to determine the semantic label and the boundaries of every action instance in an untrimmed video. Here, we construct an end-to-end framework for TAD upon Transformer, termed textitTadTR. Our method achieves state-of-the-art performance on HACS Segments and THUMOS14 and competitive performance on ActivityNet-1.3.
  arXiv  Detail & Related papers  (2021-06-18T17:58:34Z)
• 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)
• Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
  We present the first scalable exact method to discover time series motifs under Dynamic Time Warping. Our algorithm can admissibly prune up to 99.99% of the DTW computations.
  arXiv  Detail & Related papers  (2020-09-16T19:35:43Z)
• Approximated Bilinear Modules for Temporal Modeling [116.6506871576514]
  Two-layers in CNNs can be converted to temporal bilinear modules by adding an auxiliary-branch sampling. Our models can outperform most state-of-the-art methods on SomethingSomething v1 and v2 datasets without pretraining.
  arXiv  Detail & Related papers  (2020-07-25T09:07:35Z)
• 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)

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.