Dynamic State Warping
This is an incremental improvement for sequence learning applications like video and image analysis, offering more interpretable and robust alignment.
The paper tackles the problem of measuring distance between sequences by addressing DTW's limitations in handling autocorrelation and semantic mismatches, proposing DSW which improves classification accuracy over ED and DTW with 70/85 and 74/85 wins respectively.
The ubiquity of sequences in many domains enhances significant recent interest in sequence learning, for which a basic problem is how to measure the distance between sequences. Dynamic time warping (DTW) aligns two sequences by nonlinear local warping and returns a distance value. DTW shows superior ability in many applications, e.g. video, image, etc. However, in DTW, two points are paired essentially based on point-to-point Euclidean distance (ED) without considering the autocorrelation of sequences. Thus, points with different semantic meanings, e.g. peaks and valleys, may be matched providing their coordinate values are similar. As a result, DTW is sensitive to noise and poorly interpretable. This paper proposes an efficient and flexible sequence alignment algorithm, dynamic state warping (DSW). DSW converts each time point into a latent state, which endows point-wise autocorrelation information. Alignment is performed by using the state sequences. Thus DSW is able to yield alignment that is semantically more interpretable than that of DTW. Using one nearest neighbor classifier, DSW shows significant improvement on classification accuracy in comparison to ED (70/85 wins) and DTW (74/85 wins). We also empirically demonstrate that DSW is more robust and scales better to long sequences than ED and DTW.