Source-linked AI summary
Soft-DTW: a Differentiable Loss Function for Time-Series
Marco Cuturi, Mathieu Blondel
TL;DR
Time-series learning needs a loss that tolerates variable lengths and temporal misalignment while remaining usable for optimization. The paper smooths DTW into soft-DTW, making the discrepancy differentiable and enabling gradient-based time-series averaging, clustering, and prediction. Experiments report superior barycenter and clustering performance over existing baselines, with promising multistep-ahead prediction results.
Problem
Time-series outputs may differ in length, temporal pacing, and synchronization, while DTW-based averaging and clustering are limited by DTW’s nondifferentiability and optimization instability.
Method
Soft-DTW replaces DTW’s minimum alignment cost with a soft minimum over all alignments and computes gradients through dynamic programming for learning-machine outputs.
Results
Soft-DTW significantly outperforms known baselines for time-series barycenters and clusters, while also producing promising multistep-ahead prediction results.
Takeaways & Limitations
Soft-DTW provides a differentiable end-to-end fitting loss for predictive and generative time-series models when the desired loss is closer to DTW than Euclidean distance.
Takeaways & Limitations
With squared-Euclidean substitution costs, the soft-DTW objective remains non-convex, and gradients can be discontinuous near alignment changes.
Abstract
from arXiv · showhide
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
Time-series learning requires representations that handle variable lengths, temporal shifts, stretching, and imperfect synchronization. The paper builds a differentiable soft-DTW loss from DTW’s alignment geometry and applies it to averaging, clustering, and prediction.
- Motivation: Time series can vary in length and exhibit temporal stretching or desynchronization, making simple vector concatenation inadequate.These effects can occur without changing the underlying phenomenon, such as speech produced at different rates.
- DTW geometry: DTW addresses these invariances by finding the best alignment between two time series.Its alignment is computed through a dynamic-programming formulation.
- DTW geometry: Although DTW supports time-series averaging and clustering, its nondifferentiability and optimization instability limit its use in learning pipelines.These limitations are especially relevant when a model must directly output an entire time series.
- Soft-DTW: Soft-DTW replaces DTW’s minimum over alignments with a soft minimum over all alignment costs.The resulting discrepancy is computed by a smoothed modification of Bellman’s dynamic-programming recursion.
- Contributions: Soft-DTW is differentiable, and its gradients can be computed with added quadratic storage cost, enabling end-to-end time-series models.The paper applies this property to barycenter computation, clustering, and fitting predictive or generative machines.
2. The DTW and soft-DTW loss functions
Soft-DTW unifies DTW and alignment-based formulations by replacing the hard minimum over alignment costs with a smoothing operator. The resulting objective remains computable by dynamic programming and supports differentiable gradient computation through forward and backward recursions.
- Alignment costs: DTW and GAK both aggregate alignment costs, but DTW selects an optimal alignment while GAK integrates over all alignments.The unified formulation expresses both behaviors through different operations on alignment costs.
- Soft-DTW formulation: Soft-DTW applies a generalized minimum with smoothing parameter γ ≥ 0 to the costs of all possible alignment matrices.At γ = 0 it recovers the original DTW score; for γ > 0 it is related to the global-alignment kernel through a logarithmic transformation.
- Dynamic programming: The soft-DTW value is computed with a Bellman-style recursion requiring O(nm) time and O(nm) storage, while the value alone can use linear storage.The full intermediary-cost matrix is needed for the backward pass.
- Differentiation limits: Unlike soft-DTW, DTW’s gradient can be discontinuous when small input changes switch the unique optimal alignment, which may hinder gradient descent.For continuous data, the optimal alignment is likely unique almost everywhere, but the associated gradient changes discontinuously near alignment switches.
- Differentiation: For γ > 0, the gradient is obtained by differentiating through the recursion and can be expressed using an average alignment matrix under a Gibbs distribution over alignments.The backward recursion computes sensitivities of the final cost to intermediary costs, which then yields derivatives with respect to the cost matrix and time-series inputs.
- Differentiation: The gradient algorithm remains quadratic in time and space, and with squared Euclidean substitution costs the gradient is 2/γ-Lipschitz continuous.The method reverses Bellman’s recursion using the chain rule and backpropagation.
3. Learning with the soft-DTW loss
Soft-DTW supports time-series averaging, clustering, classification, and prediction by providing a differentiable DTW-based objective, while its smoothing can improve optimization but does not guarantee barycenter optimality.
- Averaging with the soft-DTW geometry: Soft-DTW barycenters minimize a weighted sum of normalized discrepancies between a candidate series and variable-length input series.Each discrepancy is divided by the corresponding input length because DTW grows roughly linearly with both series lengths.
- Averaging with the soft-DTW geometry: Averaging under soft-DTW produces substantially different interpolations from Euclidean averaging, including for unequal-length series.Figure 4 illustrates this behavior on Gun Point using weights (0.25, 0.75), (0.5, 0.5), and (0.75, 0.25).
- Differentiable optimization: The soft-DTW computational graph uses a forward recursion to compute the discrepancy and a backward recursion to compute its gradient.The backward pass tracks how changes in each recursion value affect its three successor cells.
- Limitations: Barycenter optimization remains non-convex with squared-Euclidean substitution costs, so approximate solutions provide no guarantee of optimality.The authors caution that computations involving barycenters should therefore be interpreted carefully.
- Differentiable optimization: Smoothing can improve optimization by reducing local minima and making the objective increasingly convex as γ grows when the substitution cost is convex.The paper presents this as an explanation for better results than DBA and other minimization approaches, with evidence deferred to experiments.
- Clustering and classification: Soft-DTW barycenters form a basis for clustering with a generalized Lloyd algorithm, while nearest-centroid classification reduces storage and prediction costs relative to DTW k-NN.The clustering procedure uses soft-DTW for both centroid updates and allocation, whereas nearest-centroid classification compares inputs with class barycenters.
- Multistep-ahead prediction: Soft-DTW can also serve as a loss for predicting future time-series observations with parameterized models such as multilayer perceptrons or recurrent neural networks.The prediction task maps an observed prefix to the remaining segment and can replace the historically used Euclidean loss.
4. Experimental results
Experiments evaluate soft-DTW barycenters, clustering, classification, and prediction across time-series datasets. Smoothing generally yields smoother, better-optimized representations and improves or matches baselines on many datasets.
- Averaging: With Euclidean initialization, low-γ methods often overfit data idiosyncrasies, whereas soft-DTW learns much smoother barycenters.Euclidean initialization is possible only when time series have equal lengths.
- Averaging: As γ decreases, soft-DTW achieves lower DTW loss than competing barycenter methods on almost all datasets.Table 1 reports the percentage of datasets where soft-DTW achieves lower DTW loss.
- k-means clustering: In CBF clustering, soft-DTW learns much smoother barycenters than DBA, which absorbs tiny data details.The clustering procedure uses Lloyd’s algorithm with barycenter computation and assignment steps.
- Classification: Soft-DTW performed better or at least as well as DBA on 75% of datasets for nearest-centroid classification.The comparison uses barycenters computed with soft-DTW versus DBA.
- Prediction: Under prediction experiments, soft-DTW training achieved lower DTW loss, while Euclidean training achieved lower Euclidean loss.Soft-DTW predictions can represent sharp changes when similarly shifted changes occur in the ground truth.
5. Conclusion
The paper turns DTW into a loss for comparing ground-truth time series with learned outputs and reports superiority over baselines for barycenter and clustering tasks. It also presents preliminary multistep-ahead prediction results under the DTW perspective.
- The proposed approach turns the DTW discrepancy into a full-fledged loss between ground-truth time series and outputs from a learning machine.
- Experiments found the computational approach superior to existing baselines for computing time-series barycenters and clusters.
- The paper reports promising preliminary results for multistep-ahead prediction when the relevant loss is closer to DTW than Euclidean distance.
B. Barycenters obtained with random initialization
The section identifies Wave Gesture Library Y in the results for barycenters obtained with random initialization.
- The results concern Wave Gesture Library Y.
- No quantitative outcome or comparison is specified in the supplied passage text.
- Wave Gesture Library Y is represented again in the section’s extracted results text.
D. More interpolation results
The section compares interpolation results under Euclidean loss with those under soft-DTW (γ = 1) loss, using extracted numeric axes.
- The left results use Euclidean loss, while the right results use soft-DTW (γ = 1) loss.
- The extracted result displays include an axis labeled from 0 to 20.
- A second extracted display also includes an axis labeled from 0 to 20.
- The extracted displays include axes labeled from 0 to 80 in increments of 20.
CBF dataset
The CBF dataset results identify Cluster 1 and Cluster 2 configurations by point count and include DBA baselines with two initialization strategies.
- Cluster 1 is represented with 8 points.
- A second Cluster 1 entry also uses 8 points.
- DBA is evaluated with random initialization and Euclidean mean initialization.
ECG200 dataset
The ECG200 dataset material presents plots with a 0–80 horizontal scale, compares Euclidean, Soft-DTW, and ground truth, and includes DBA baselines.
- The plotted horizontal scale is labeled from 0 to 80.
- DBA appears with random initialization as one plotted baseline.
- DBA also appears with Euclidean mean initialization.
- The comparison legend includes Euclidean, Soft-DTW, and Ground truth.
G. Barycenters: DTW loss (Eq. 4 with γ = 0) achieved with random init
The barycenter results are tabulated across datasets and Soft-DTW smoothing values, alongside subgradient, DBA, and Euclidean-mean methods.
- The table compares datasets across Soft-DTW values γ = 1, 0.1, 0.01, and 0.001.
- The listed comparison methods are Subgradient method, DBA, and Euclidean mean.
H. Barycenters: DTW loss (Eq. (4) with γ = 0) achieved with Euclidean init
The Euclidean-initialization barycenter results compare DTW and Soft-DTW losses across smoothing values, with Euclidean loss included as a baseline.
- The table compares Soft-DTW values γ = 1, 0.1, 0.01, and 0.001 across datasets.
- The comparison includes Soft-DTW and Euclidean mean methods.
- The Euclidean-initialization section reports DTW loss achieved for barycenters.
- The results also include Soft-DTW loss and Euclidean loss columns.
- The listed smoothing values are γ = 1, 0.1, 0.01, and 0.001.