--- kind: concept slug: dynamic-time-warping title: Dynamic time warping summary: >- Distance between two time series that stretches or squeezes the time axis to align them, so a movement done faster or slower still matches. Used as the weak-learner distance in multi-class AdaBoost on facial-landmark sequences, and as a 1-NN baseline that ranks last of nine on a 112-problem benchmark. Trade-off: each comparison is a full alignment; window and normalisation are unstated. tags: [distance, time-series, sequence-matching] papers: ["1604.03225", "2304.13029"] related: [adaboost, time-series-classification, nearest-neighbor-search] status: draft updated_at: 2026-10-18 --- ## 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 [arxiv: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 [arxiv: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](/papers/1604.03225), 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](/papers/2304.13029), 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 [arxiv:1604.03225 §3]. It also says DTW lets the two sequences differ in length [arxiv: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 [arxiv:1604.03225 §4, eq. 10, eq. 11]. A test sequence is then labelled with the class whose prototype is nearest in DTW distance [arxiv:1604.03225 §4, eq. 12]. The learner has no fitted parameters beyond these prototypes. It is used as the weak classifier inside [AdaBoost](/concepts/adaboost), and the same card is the source for both pages [arxiv:1604.03225 §4]. The paper says it uses the DTW method of its reference [32] for speed [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2304.13029 tab. 14]. It ranks ninth on every metric in that table, including negative log loss [arxiv: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 [code: tsml_eval/publications/y2023/tsc_bakeoff/set_bakeoff_classifier.py#L69-L70] [arxiv:2304.13029 §4]. The train-time table does not list 1-NN DTW [arxiv: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 [arxiv: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 [arxiv: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 | Situation | Use | Why | |---|---|---| | Sequences of the same pattern that differ in speed or timing, and you compare each one to a small set of references | DTW to the references, with the nearest reference as the label | The paper uses this to compare each landmark-motion sequence to class prototypes [arxiv:1604.03225 §4, eq. 12]. The card gives its results on one dataset only [arxiv:1604.03225 §5.2 tab. 3]. | | Many candidate series, scored against all training data in every round | Keep the candidate pool small, and budget for the cost | Each AdaBoost round scores every candidate against every training sequence with DTW [arxiv:1604.03225 alg. 1] [arxiv:1604.03225 §4]. The paper reports no run time or memory [arxiv:1604.03225 §4]. | | A classification benchmark or floor on univariate series | 1-NN DTW as the baseline to beat | It is the reference baseline in the bake off [arxiv:2304.13029 §1] and is last of nine on accuracy [arxiv:2304.13029 tab. 14]. That shows it is weak on that archive, not that it is weak everywhere. | | No prior knowledge of which time-series classifier to use on univariate data | Not DTW alone: start from the paper's suggested defaults | The authors suggest HC2 and MR-Hydra as a default starting point when no prior knowledge exists [arxiv:2304.13029 §7]. HC2 is 0.891 and MR-Hydra 0.884 mean accuracy on the 112 problems [arxiv:2304.13029 tab. 14]. Neither is a DTW method. | | Series are already aligned and of equal length | Not covered by these cards | Neither card compares DTW with a plain pointwise distance, so they cannot say when DTW is or is not needed. | | You need to reproduce the paper's number | Fix every open setting in the list above, and record your choices | The window, step pattern, local distance and normalisation are not stated [arxiv:1604.03225 §4]. Two implementations that differ on them can disagree. | The first paper reports that its DTW-based classifier reaches 95.17% on the CK+ dataset with 5-fold cross-validation [arxiv:1604.03225 §5.2 tab. 3]. These are author-reported numbers from one dataset of posed, frontal expressions [arxiv:1604.03225 §5.1]. The paper does not report variance across folds [arxiv:1604.03225 §5.1]. The second paper reports 1-NN DTW at 0.756 mean accuracy over 30 random resamples of 112 UCR problems [arxiv: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 [arxiv:1604.03225 §4, eq. 12]. Replacing the prototype loop with a loop over training series gives 1-NN DTW. ```pseudocode # 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 [arxiv:1604.03225 §5.2 tab. 3]. The second is 0.756 mean accuracy for 1-NN DTW on 112 UCR problems over 30 resamples [arxiv: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](/papers/1604.03225): 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](/papers/2304.13029): uses 1-NN with DTW distance as the baseline among nine classifiers on 112 UCR problems, where it ranks last on accuracy.