Constrained Dynamic Time Warping

Note. This work is a part of Zheng Zhang's PhD thesis. It was performed during Zheng's stay at LETG in 2015-2016. I was not directly involved in the supervision Zheng's PhD thesis.

In this section, we present a method to regularize Dynamic Time Warping by setting constraints on the length of the admissible warping paths (Zhang et al., 2017).

Formulation and Optimization

Note. The method is available in tslearn via:

from tslearn.metrics import dtw_limited_warping_length
cost = dtw_limited_warping_length(
  x, x_prime,
  max_length
)

As discussed above, a common way to restrict the set of admissible temporal distortions for Dynamic Time Warping consists in forcing paths to stay close to the diagonal through the use of Sakoe-Chiba band or Itakura parallelogram constraints. A limitation of these global constraints is that they completely discard some regions of the alignment matrix a priori (i.e. regardless of the involved data).

To alleviate this limitation, we propose Limited warping path length DTW (LDTW) that adds a path length constraint to the DTW optimization problem such that a path is said admissible for our method iff:

it is an admissible DTW path;
its length $K$ is lower or equal to a user-defined bound $K_\text{max}$ .

We have proposed an algorithm that stores, at each step $(i, j)$ , optimal alignment scores for all admissible alignment path lengths. This gives the general LDTW algorithm:

def ldtw(x, x_prime, max_length):
  for i in range(n):
    for j in range(m):
      dist = d(x[i], x_prime[j]) ** 2
      C[i, j, :] = inf  # Set infinite cost for non-admissible lengths
      # The core difference with DTW is the following line:
      for l in admissible_lengths(i, j, max_length):
        if i == 0 and j == 0:
          C[i, j, l] = dist
        else:
          C[i, j, l] = dist + min(C[i-1, j, l-1] if i > 0
                                                 else inf,
                                  C[i, j-1, l-1] if j > 0
                                                 else inf,
                                  C[i-1, j-1, l-1] if (i > 0 and j > 0)
                                                   else inf)

  return sqrt(min(C[n-1, m-1, :]))

The question is then to compute the set admissible_lengths(i, j, max_length). We have shown that this set can be computed explicitly and that its cardinal is $O(\min(i, j))$ . Overall, we have a $O(mn^2 + nm^2)$ complexity for this exact algorithm.

Empirical Observations

First, one can see in the following figure that the resulting alignments effectively limits the number of singularities in the obtained alignments as compared to DTW:

from tslearn.metrics import dtw_path_limited_warping_length, \
    dtw_path
from tslearn.datasets import UCR_UEA_datasets

dataset = UCR_UEA_datasets().load_dataset("CBF")[0]
max_length = 150
path, cost = dtw_path_limited_warping_length(dataset[0],
                                             dataset[1],
                                             max_length)
plot_matches(dataset[0], dataset[1], path, "LDTW matches")

path, cost = dtw_path(dataset[0], dataset[1])
plot_matches(dataset[0], dataset[1], path, "DTW matches")

Moreover, our experiments on UCR Time Series Datasets (Bagnall, Lines, Vickers, & Keogh, 2018) show that this similarity measure, when used in a 1-Nearest Neighbor Classifier, leads to a higher accuracy than other constrained DTW variants (Sakoe-Chiba band and Itakura parallelogram).

References

Zhang, Z., Tavenard, R., Bailly, A., Tang, X., Tang, P., & Corpetti, T. (2017). Dynamic time warping under limited warping path length. Information Sciences, 393, 91–107.
Bagnall, A., Lines, J., Vickers, W., & Keogh, E. (2018). The UEA & UCR Time Series Classification Repository. Retrieved from www.timeseriesclassification.com