Soft-DTW Alignment Entropy

Dynamic Time Warping (DTW) computes the optimal alignment between two time series by finding a path through a cost grid that minimizes the total cost. However, DTW is not smooth and its gradients are zero almost everywhere. Soft-DTW smooths this objective by replacing the hard minimum with a continuous log-sum-exp operator, taking into account all possible alignment paths.

Theory

Given two series X of length n and Y of length m, an alignment path is a sequence of grid cells starting at (0,0) and ending at (n-1, m-1), using steps (1,0), (0,1), or (1,1). The cost of a cell is (x_i - y_j)². The cost of a path is the sum of costs over all visited cells.

Soft-DTW is defined as: softDTW_γ(X, Y) = -γ log ( \sum_π exp(-(cost(π))/(γ)) ) For numerical stability, the minimum cost is factored out using a minimum-shift log-sum-exp trick. The soft DTW value elegantly separates into the expected cost under a Gibbs distribution and an entropy term: softDTW_γ = E[cost] - γ · H

Worked Example

Let us manually calculate the components for the Warped series X=[0, 0, 1] and Y=[0, 1] with γ=0.5. The lengths are n=3, m=2. The start is (0,0) and the end is (2,1). The possible paths and their costs:

Path 1: (0,0) [cost 0] → (1,0) [cost 0] → (2,0) [cost 1] → (2,1) [cost 0]. Total Cost = 1.
Path 2: (0,0) [cost 0] → (1,0) [cost 0] → (2,1) [cost 0]. Total Cost = 0.
Path 3: (0,0) [cost 0] → (1,1) [cost 1] → (2,1) [cost 0]. Total Cost = 1.
Path 4: (0,0) [cost 0] → (0,1) [cost 1] → (1,1) [cost 1] → (2,1) [cost 0]. Total Cost = 2.
Path 5: (0,0) [cost 0] → (0,1) [cost 1] → (2,1) [cost 0]. Total Cost = 1.

Given these costs (1, 0, 1, 2, and 1), the minimum cost is 0. The sum of exponentials ∑ exp(-cost/0.5) = exp(0) + exp(-2) + exp(-2) + exp(-4) + exp(-2). Expected cost = 0.31077051847531195. Soft-DTW Cost = -0.17684777598705584. Path entropy = 0.9752365889247356.

Experiment

Observe how the Soft-DTW calculation shifts when changing the gamma smoothing factor in the Soft-DTW Alignment Entropy module:

Set the series to "Identical" and smoothing gamma to 1. Note the Soft alignment cost is negative.
Set the smoothing gamma to 0. Note that the Soft alignment cost equals the Hard DTW cost.

Limitations

Soft-DTW is not a true metric, as the soft distance between identical series may be negative due to the entropy of multiple alignments. It is also computationally expensive, maintaining an O(nm) complexity for both the forward pass and gradient calculation.

References

Cuturi, M., & Blondel, M. (2017). Soft-DTW: a Differentiable Loss Function for Time-Series. Proceedings of the 34th International Conference on Machine Learning, PMLR 70:894-903.
https://proceedings.mlr.press/v70/cuturi17a/cuturi17a.pdf

Soft-DTW Alignment Entropy