PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Marco Cuturi, Mathieu Blondel

arXiv:1703.01541v2stat.ML

TL;DR

DTW supports time-series averaging and fitting, but its nondifferentiability and instability hamper optimization. Soft-DTW smooths the alignment minimum into a differentiable loss, and its barycenters matched or improved nearest-centroid accuracy over DBA on 75% of datasets.

  • Problem

    DTW has been used for time-series averaging and fitting, but its nondifferentiability and instability hamper its use in optimization pipelines.

    Source: §1 · p. 2

  • Method

    Soft-DTW smooths the alignment minimum and computes gradients by reverse backpropagation in quadratic time, with added quadratic storage.

    Source: §1 · p. 2, §2.2 · p. 4, §3.1 · p. 5

  • Results

    75% of datasets had better or equal nearest-centroid classification accuracy with soft-DTW barycenters than with DBA.

    Source: §4.3 · p. 7

  • Takeaways & Limitations

    Soft-DTW may suit time-series prediction settings where the desired loss is closer to DTW’s robust perspective than to Euclidean distance’s local parsing.

    Source: §5 · p. 8

    With convex substitution costs, soft-DTW is a non-convex soft minimum of convex functions.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

We propose in this paper a differentiable learning loss between time series, building upon the celebrated dynamic time warping (DTW) discrepancy. Unlike the Euclidean distance, DTW can compare time series of variable size and is robust to shifts or dilatations across the time dimension. To compute DTW, one typically solves a minimal-cost alignment problem between two time series using dynamic programming. Our work takes advantage of a smoothed formulation of DTW, called soft-DTW, that computes the soft-minimum of all alignment costs. We show in this paper that soft-DTW is a differentiable loss function, and that both its value and gradient can be computed with quadratic time/space complexity (DTW has quadratic time but linear space complexity). We show that this regularization is particularly well suited to average and cluster time series under the DTW geometry, a task for which our proposal significantly outperforms existing baselines. Next, we propose to tune the parameters of a machine that outputs time series by minimizing its fit with ground-truth labels in a soft-DTW sense.

1. Introduction

The paper introduces soft-DTW, a differentiable smoothing of DTW, to support time-series averaging, clustering, and end-to-end prediction and generation. It addresses temporal stretching, variable sequence lengths, and misalignment that make a simple Euclidean treatment inadequate.

The DTW paradigm

  • Time-series stretching, differing lengths, and lack of synchronization motivate DTW, which finds an optimal alignment by dynamic programming with quadratic cost (Sakoe & Chiba, 1971; 1978).The alignment uses pairwise distances between observations in the two series.Source: §1 · p. 1

Soft-DTW

  • Soft-DTW takes the soft-minimum over costs of all alignments and is computed by modifying Bellman’s recursion; its value has quadratic time and linear space complexity.Computing gradients adds a quadratic storage cost.Source: §1 · p. 2

Our contributions

  • Soft-DTW is differentiable in all its arguments, and its gradients can be computed alongside the discrepancy with added quadratic storage, unlike nondifferentiable, unstable DTW.The gradients are with respect to the variables of both time series.Source: §1 · p. 2
  • The proposed smoothed alternative to DBA (DTW Barycenter Averaging) for clustering significantly outperforms known baselines.The paper proposes using soft-DTW gradients for this alternative approach.Source: §1 · p. 2
  • Soft-DTW can serve as a fitting term between a machine-generated time-series segment and its ground truth, enabling differentiable end-to-end predictive and generative models.The paper illustrates prediction with a neural network architecture.Source: §1 · p. 2

Notations

  • The paper represents multivariate discrete series as variable-column matrices and alignments as binary paths from (1,1) to (n,m) using down, right, or diagonal moves.The number of such alignments grows exponentially with the two sequence lengths.Source: §1 · p. 2

2. The DTW and soft-DTW loss functions

The section unifies DTW and the Global Alignment kernel for comparing time series, then defines a smoothed alignment-cost objective and derives its gradient and algorithmic computation.

2.1. Alignment costs: optimality and sum

  • For potentially different-length series, γ-soft-DTW unifies DTW and GAK as a smoothed minimum over alignment costs; γ=0 recovers DTW and γ>0 equals −γ log k^GA_γ.The generalized formulation uses one algorithm to compute both cases, with O(nm) time and storage for the value; computing only the value can use 2n storage.Source: §2 · p. 2, §2.1 · p. 3

2.2. Differentiation of soft-DTW

  • For γ>0, soft-DTW’s gradient is the Gibbs-weighted average alignment matrix and can be computed in O(nm) complexity by reverse Bellman backpropagation.By contrast, dtw0 is differentiable only when the optimal alignment is unique, and its gradient can jump when that alignment changes.Source: §2.2 · pp. 3–4

2.3. Algorithmic differentiation

  • The algorithm stores the forward Bellman matrix R, then propagates derivatives backward through neighboring states to recover the cost-matrix gradient in O(nm) time and space.For squared Euclidean δ, the resulting gradient is 2/γ-Lipschitz continuous.Source: §2.3 · p. 4

3. Learning with the soft-DTW loss

Section 3 applies soft-DTW to average and cluster time series, construct class prototypes for classification, and train models that predict time-series outputs. These applications use soft-DTW barycenters or discrepancies to work with variable-length series and time-series predictions.

3.1. Averaging with the soft-DTW geometry

  • Soft-DTW barycenters approximate weighted averages of variable-length series, with each discrepancy normalized by the series lengths; their interpolations differ from Euclidean averages.The barycenter is defined at a fixed length, and Figure 4 illustrates interpolations for three weightings of two Gun Point series.Source: §3.1 · pp. 4–5, Figure 4 · p. 5
  • With squared-Euclidean costs, the barycenter objective is non-convex and offers no optimality guarantee; smoothing can soften local minima and ease optimization.As γ increases, soft-DTW converges to the sum of costs, which is convex when the local cost δ is convex.Source: §3.1 · p. 5

3.2. Clustering with the soft-DTW geometry

  • Time-series clustering can minimize an energy over soft-DTW centroids, using a Lloyd-style algorithm with soft-DTW for both centering and cluster assignment.The centroids are a direct extension of the approximate soft-DTW barycenters.Source: §3.2 · p. 5

3.3. Learning prototypes for time series classification

  • A nearest-centroid classifier can use soft-DTW barycenters at training time and soft-DTW discrepancies at prediction time, avoiding k-NN’s storage and prediction costs.The k-NN baseline stores the training series and compares a new series against all of them.Source: §3.3 · pp. 5–6

3.4. Multistep-ahead prediction

  • For multistep-ahead prediction, parameterized functions map observed time-series segments to predicted outputs, a setting where soft-DTW is proposed as a loss.Multi-layer perceptrons and recurrent neural networks are natural choices; they have historically been trained with Euclidean loss.Source: §3.4 · p. 6

4. Experimental results

Experiments on 79 UCR datasets evaluate soft-DTW barycenters, k-means clustering, nearest-centroid classification, and multistep-ahead prediction.

4.1. Averaging experiments

  • In averaging, decreasing γ improved DTW loss on almost all datasets, while sufficiently high γ avoided spurious barycenters and low-γ optimization could get stuck in bad local minima.With Euclidean-mean initialization, which requires equal-length series, DTW and low-γ soft-DTW often matched shapes but overfit; soft-DTW learned smoother barycenters.Source: Table 1 · p. 6, §4.1 · pp. 6–7

4.2. k-means clustering experiments

  • As γ decreased, soft-DTW k-means achieved lower DTW loss than competing methods on a large proportion of datasets; its barycenters were smoother than DBA’s.Experiments did not test γ below 0.001 because dtw0.001 was very close to dtw0 in practice.Source: §4.2 · p. 7, Figure 6 · p. 7, Table 2 · p. 8

4.3. Time-series classification experiments

  • For 75% of UCR archive datasets, using a soft-DTW barycenter rather than a DBA barycenter improved nearest-centroid classifier accuracy; soft-DTW worked better or at least as well as DBA.Source: §4.3 · p. 7, Figure 7 · p. 8

4.4. Multistep-ahead prediction experiments

  • For multistep prediction, soft-DTW training achieved lower DTW loss while Euclidean training achieved lower Euclidean loss.Predictions often agreed, but soft-DTW could predict sharp changes when a small time shift made them inexpensive under DTW.Source: Table 3 · p. 8, §4.4 · p. 8

5. Conclusion · Appendix material · A. Recursive forward computation of the average path matrix

The paper presents soft-DTW as a loss for comparing ground-truth time series with learning-machine outputs and reports benefits for barycenter and clustering tasks, plus promising multistep-ahead prediction results. Its appendix describes a recursive computation of the average alignment matrix.

5. Conclusion

  • The approach experimentally outperforms existing baselines for computing time-series barycenters and clusters.The conclusion identifies these as existing problems where the computational approach is superior.Source: §5 · p. 8
  • The paper turns the DTW discrepancy into a loss between ground-truth time series and learning-machine outputs.The authors propose this loss as a way to fit a machine’s outputs to ground-truth labels.Source: §5 · p. 8
  • The authors report promising multistep-ahead prediction results for settings where the user’s loss is closer to DTW’s robust perspective than to Euclidean distance’s local parsing.The conclusion says this could be useful in such settings.Source: §5 · p. 8

A. Recursive forward computation of the average path matrix

  • The average alignment under Gibbs distribution pγ is computed with a forward recurrence that closely mimics Bellman’s original recursion.The passage introduces the recurrence but does not provide its formula.Source: A. Recursive forward computation of… · p. 11
  • The recursion initializes border matrices to 0 except E1,1 = [1], and stores the completed average alignment matrix in En,m.The terms rij are computed following Algorithm 2.Source: A. Recursive forward computation of… · p. 11
  • Each of the nm updates sums three matrices of size (i + 1, j + 1); a careful implementation uses nm min(n, m) space but still requires (nm)^2 operations.The implementation stores only two arrays of matrices, analogous to Algorithm 1’s two arrays of values.Source: A. Recursive forward computation of… · p. 11

B. Barycenters obtained with random initialization · C. Barycenters obtained with Euclidean mean initialization

The supplied passages identify Wave Gesture Library Y in both barycenter-initialization subsections, but provide no outcomes or comparison between them.

B. Barycenters obtained with random initialization

C. Barycenters obtained with Euclidean mean initialization

D. More interpolation results · E. Clusters obtained by k-means under DTW or soft-DTW geometry

The supplied passage identifies an interpolation-results comparison between Euclidean loss and soft-DTW loss with γ = 1.

D. More interpolation results

CBF dataset

The supplied CBF dataset passages label Cluster 1 and Cluster 2 with point counts and identify two DBA initialization variants.

ECG200 dataset · F. More visualizations of time-series prediction

The merged sections provide ECG200 visualizations labeled with DBA initialization variants, followed by time-series prediction visualizations labeled for Euclidean, Soft-DTW, ground truth, and a uWaveGestureLibrary Y example.

ECG200 dataset

  • The ECG200 plots show horizontal-axis tick labels from 0 to 80 in increments of 20.Source: ECG200 dataset · p. 16
  • The ECG200 visualizations label DBA examples with random initialization and Euclidean mean initialization.The passages provide no plotted values or comparative outcomes.Source: ECG200 dataset · p. 16

F. More visualizations of time-series prediction

G. Barycenters: DTW loss (Eq. 4 with γ = 0) achieved with random init

The supplied passage identifies a barycenter comparison with Soft-DTW settings and three baseline methods, but provides no result values.

G. Barycenters: DTW loss (Eq. 4 with γ = 0) achieved with random init

  • The comparison lists Soft-DTW at γ = 1, 0.1, 0.01, and 0.001 alongside Subgradient method, DBA, and Euclidean mean.The passage contains table headings only, so it does not establish which method performs best.Source: G. Barycenters: DTW loss (Eq. 4 with γ… · p. 18

H. Barycenters: DTW loss (Eq. (4) with γ = 0) achieved with Euclidean init · K. Time-series prediction: DTW loss achieved when using random init · L. Time-series prediction: DTW loss achieved when using Euclidean init

The section reports DTW-loss results for barycenters and time-series prediction under different initialization choices. The supplied passages identify the evaluated losses, γ settings, and comparison methods, but do not provide numerical results.

H. Barycenters: DTW loss (Eq. (4) with γ = 0) achieved with Euclidean init

I. k-means clustering: DTW loss achieved (Eq. (5) with γ = 0, log-scaled) when using random initialization

J. k-means clustering: DTW loss achieved (Eq. (5) with γ = 0, log-scaled) when using Euclidean mean initialization

Related papers

Loading 1703.01541v2…