Related papers: Differentiable Divergences Between Time Series

Differentiable Divergences Between Time Series

URL: http://arxiv.org/abs/2010.08354v3
Date: Thu, 25 Feb 2021 23:13:18 GMT
Title: Differentiable Divergences Between Time Series
Authors: Mathieu Blondel and Arthur Mensch and Jean-Philippe Vert
Abstract summary: 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.
Score: 34.60983018798683
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Computing the discrepancy between time series of variable sizes is notoriously challenging. While dynamic time warping (DTW) is popularly used for this purpose, it is not differentiable everywhere and is known to lead to bad local optima when used as a "loss". Soft-DTW addresses these issues, but it is not a positive definite divergence: due to the bias introduced by entropic regularization, it can be negative and it is not minimized when the time series are equal. We propose in this paper a new divergence, dubbed soft-DTW divergence, which aims to correct these issues. We study its properties; in particular, under conditions on the ground cost, we show that it is a valid divergence: 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. We showcase our divergences on time series averaging and demonstrate significant accuracy improvements compared to both DTW and soft-DTW on 84 time series classification datasets.

Related papers

Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
arXiv Detail & Related papers (2023-10-02T08:15:52Z)
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)
Approximating DTW with a convolutional neural network on EEG data [9.409281517596396]
We propose a fast and differentiable approximation of Dynamic Time Wrapping (DTW) We show that our methods achieve at least the same level of accuracy as other DTW main approximations with higher computational efficiency.
arXiv Detail & Related papers (2023-01-30T13:27:47Z)
Uncertainty-DTW for Time Series and Sequences [38.27785891922479]
We propose to model the so-called aleatoric uncertainty of a differentiable (soft) version of Dynamic Time Warping. Our uncertainty-DTW is the smallest weighted path distance among all paths. We showcase forecasting the evolution of time series, estimating the Fr'echet mean of time series, and supervised/unsupervised few-shot action recognition of the articulated human 3D body joints.
arXiv Detail & Related papers (2022-10-30T17:06:55Z)
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)
Optimization Variance: Exploring Generalization Properties of DNNs [83.78477167211315]
The test error of a deep neural network (DNN) often demonstrates double descent. We propose a novel metric, optimization variance (OV), to measure the diversity of model updates.
arXiv Detail & Related papers (2021-06-03T09:34:17Z)
A Case-Study on the Impact of Dynamic Time Warping in Time Series Regression [2.639737913330821]
We show that Dynamic Time Warping (DTW) is effective in improving accuracy on a regression task when only a single wavelength is considered. When combined with k-Nearest Neighbour, DTW has the added advantage that it can reveal similarities and differences between samples at the level of the time-series. However, in the problem, we consider here data is available across a spectrum of wavelengths.
arXiv Detail & Related papers (2020-10-11T15:21:21Z)
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.