Dynamic time warping

Overview

Dynamic time warping (DTW) measures how far apart two sequences are after letting the time axis bend. Each sample of one sequence may be matched to one or more samples of the other, so the total cost is the smallest sum of local differences over all such matchings 1604.03225 §4. The effect is that two sequences with the same shape but different timing can still look close.

The invariant shared by the uses is that the result is a single non-negative score per pair of sequences, and that a smaller score means a better match 1604.03225 §4, eq. 12. Everything else, such as the local distance, the allowed warping paths and any normalisation, is a choice the sources do not fully state (see Variants).

This page is compiled from two cards. In the first, Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines, DTW compares a landmark-motion sequence with a class prototype. In the second, Bake off redux: a review and experimental evaluation of recent time series classification algorithms, DTW is the distance inside the 1-nearest-neighbour baseline on the UCR archive. Neither card describes DTW variants (window constraints, step patterns, lower bounds), so those are not covered here.

Two points in the first source are unclear and matter for an implementation. The paper resamples every sequence to 15 frames by linear interpolation before the features are built 1604.03225 §3. It also says DTW lets the two sequences differ in length 1604.03225 §5.2. The card does not say whether the sequences reaching DTW are still at 15 frames, so an implementer should decide this explicitly.

Variants

Nearest prototype under DTW (the weak learner)

Each candidate feature is a sequence per video. For each class, the paper builds one prototype: the element-wise median of that feature's training sequences of that class 1604.03225 §4, eq. 10, eq. 11. A test sequence is then labelled with the class whose prototype is nearest in DTW distance 1604.03225 §4, eq. 12. The learner has no fitted parameters beyond these prototypes. It is used as the weak classifier inside AdaBoost, and the same card is the source for both pages 1604.03225 §4.

The paper says it uses the DTW method of its reference [32] for speed 1604.03225 §4. The card does not say what that method does to the computation, so the speed claim cannot be checked from this card alone.

1-nearest-neighbour DTW (the benchmark baseline)

The distance-based family of time-series classifiers is usually a nearest neighbour rule on a whole-series distance 2304.13029 §4 item 1. In this benchmark, 1-NN DTW is the distance-based baseline. The 2017 bake off compared 18 algorithms and found only nine significantly better than 1-NN DTW and Rotation Forest 2304.13029 §1. In the 2023 re-run, on 112 equal-length univariate UCR problems, 1-NN DTW has the lowest mean accuracy of the nine classifiers compared, 0.756 against 0.891 for the best 2304.13029 tab. 14. It ranks ninth on every metric in that table, including negative log loss 2304.13029 tab. 14.

The code passes no window argument to its 1-NN DTW classifier, so the benchmark uses the library's default window, which the paper does not state set_bakeoff_classifier.py 2304.13029 §4. The train-time table does not list 1-NN DTW 2304.13029 tab. 19, so the card gives no run-time figure for it.

Settings the sources leave open

The cards do not state the following, and a reimplementation must choose them itself 1604.03225 §4, §5.2:

• the local distance between two samples, which matters here because each sample is a vector of landmark coordinates or of distance and angle;
• the window constraint, which limits how far the warping path may drift from the diagonal;
• the step pattern, which sets which moves through the alignment grid are allowed and at what cost;
• whether the final distance is normalised by sequence length or path length;
• any lower-bound pruning, and whether it changes the result.

Because these are not stated, the 95.17% reported for the DTW-based classifier is tied to the authors' unstated choices 1604.03225 §5.2 tab. 3. The bake off leaves the window unset in code as well (see above), so its 0.756 is also tied to a setting the paper does not name.

When to use which

The first paper reports that its DTW-based classifier reaches 95.17% on the CK+ dataset with 5-fold cross-validation 1604.03225 §5.2 tab. 3. These are author-reported numbers from one dataset of posed, frontal expressions 1604.03225 §5.1. The paper does not report variance across folds 1604.03225 §5.1.

The second paper reports 1-NN DTW at 0.756 mean accuracy over 30 random resamples of 112 UCR problems 2304.13029 tab. 14. These are author-reported averages over a benchmark archive.

Implementation sketch

The sources do not give the DTW recurrence, so the sketch below is ours. It uses an unconstrained step pattern and no normalisation; both are choices, not the papers' settings. The outer loop is the nearest-prototype rule of the first paper 1604.03225 §4, eq. 12. Replacing the prototype loop with a loop over training series gives 1-NN DTW.

# Classic DTW cost between sequences a (n samples) and b (m samples).
# Window, step pattern and normalisation are NOT stated in the cards;
# this sketch uses an unconstrained pattern and no normalisation (our choice).
def dtw_distance(a, b):
    # Cost table with a border row and column set to infinity
    cost = full((n + 1, m + 1), inf)
    cost[0][0] = 0
    for i in 1..n:
        for j in 1..m:
            # Local distance between two samples; a vector norm here (our choice)
            d = norm(a[i] - b[j])
            # Cheapest of the three allowed predecessor moves (our choice)
            cost[i][j] = d + min(cost[i-1][j],
                                 cost[i][j-1],
                                 cost[i-1][j-1])
    return cost[n][m]

# Nearest-prototype labelling for one feature f  [arxiv:1604.03225 §4, eq. 12]
def classify_feature(x_f, prototypes_f):
    # Score the test sequence against each class prototype with DTW
    dists = [dtw_distance(x_f, p) for p in prototypes_f]
    # Return the class index with the smallest distance
    return argmin(dists)

Contradictions

None between the two cards: they report DTW in different roles and do not make the same claim. Their numbers are not comparable. The first is 95.17% accuracy on CK+ with 5-fold cross-validation, for a DTW prototype classifier inside AdaBoost 1604.03225 §5.2 tab. 3. The second is 0.756 mean accuracy for 1-NN DTW on 112 UCR problems over 30 resamples 2304.13029 tab. 14. The datasets, protocols and classifiers all differ, so the two figures should not be read as one scale.

Papers

• Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines: uses DTW distance to per-class median prototypes as the weak learner in multi-class AdaBoost on landmark-motion sequences, with author-reported CK+ results.
• Bake off redux: a review and experimental evaluation of recent time series classification algorithms: uses 1-NN with DTW distance as the baseline among nine classifiers on 112 UCR problems, where it ranks last on accuracy.