Differentiable Divergences Between Time Series (2020-10-16T00:00:00.000000Z)

TL;DR

A new divergence is proposed, dubbed soft-DTW divergence, which is non-negative and minimized when the time series are equal, under conditions on the ground cost and also proposes a new "sharp" variant by further removing entropic bias.

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 non-negative and minimized when the 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.

Authors

Jean-Philippe Vert

1 papers

Mathieu Blondel

3 papers

Arthur Mensch

1 papers

TL;DR

Abstract

Authors

References32 items

End-to-End Adversarial Text-to-Speech

Spatio-Temporal Alignments: Optimal transport through space and time

D3TW: Discriminative Differentiable Dynamic Time Warping for Weakly Supervised Action Alignment and Segmentation

Interpolating between Optimal Transport and MMD using Sinkhorn Divergences

Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance

Computational Optimal Transport

Differentiable Dynamic Programming for Structured Prediction and Attention

Learning Generative Models with Sinkhorn Divergences

Soft-DTW: a Differentiable Loss Function for Time-Series

On Wasserstein Two-Sample Testing and Related Families of Nonparametric Tests

Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification

Ion transport in porous media: derivation of the macroscopic equations using upscaling and properties of the effective coefficients

A global averaging method for dynamic time warping, with applications to clustering

Stochastic modeling of particle movement with application to marine biology and oceanography

Graphical Models, Exponential Families, and Variational Inference

A Kernel for Time Series Based on Global Alignments

Optimizing amino acid substitution matrices with a local alignment kernel

A Conditional Random Field for Discriminatively-trained Finite-state String Edit Distance

Why Delannoy numbers?

OBJECTS COUNTED BY THE CENTRAL DELANNOY NUMBERS

On the limited memory BFGS method for large scale optimization

Dynamic programming algorithm optimization for spoken word recognition

Tslearn, A Machine Learning Toolkit for Time Series Data

Miko(cid:32)laj

Comparing Time-Series Clustering Algorithms in R Using the dtwclust Package

The ucr time series classification

On a new multivariate two-sample test

TESTING FOR EQUAL DISTRIBUTIONS IN HIGH DIMENSION

The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Les éléments aléatoires de nature quelconque dans un espace distancié

Connectionist Temporal Classiﬁcation: Labelling Unsegmented Sequence Data with Recurrent Neural Networks

Connectionist Temporal Classiﬁcation: Labelling Unsegmented Sequences with Recurrent Neural Networks

Field of Study

Venue Information

Name

Type

URL

Alternate Names