Amercing: An intuitive and effective constraint for dynamic time warping. (May 2023)

• Record Type: Journal Article
• Authors: Herrmann, Matthieu; Webb, Geoffrey I.
• Is Part Of: Pattern recognition. Volume 137(2023)
• Publication Date: 2023-05
• Subjects: Time series -- Dynamic time warping -- Elastic distance; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2023.109333
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A novel constraint for the dynamic time warping (DTW) elastic distance. Address pitfalls present in other DTW variants (CDTW & WDTW). Parameterized additive penalty allowing a wide range of flexibility, from none (Euclidean distance like) to complete (equivalent to DTW). On a classic classification benchmark, lead to nearest neighbor classifiers significantly more accurate than any other DTW variants. Applicable to any task where DTW and its variants are currently used. Abstract: Dynamic Time Warping (DTW) is a time series distance measure that allows non-linear alignments between series. Constraints on the alignments in the form of windows and weights have been introduced because unconstrained DTW is too permissive in its alignments. However, windowing introduces a crude step function, allowing unconstrained flexibility within the window, and none beyond it. While not entailing a step function, a multiplicative weight is relative to the distances between aligned points along a warped path, rather than being a direct function of the amount of warping that is introduced. In this paper, we introduce Amerced Dynamic Time Warping (ADTW), a new, intuitive, DTW variant that penalizes the act of warping by a fixed additive cost. Like windowing and weighting, ADTW constrains the amount of warping. However, it avoids both abrupt discontinuities in the amount of warping allowed and the limitations of a multiplicative penalty. We formally introduce ADTW, prove some of its properties, and discuss its parameterization. We show on a simple example how it can be parameterized to achieve an intuitive outcome, and demonstrate its usefulness on a standard time series classification benchmark. We provide a demonstration application in C++ Herrmann(2021)[1].