Sequential data classification by dynamic state warping

Abstract

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 comparisons 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 may be sensitive to noise and poorly interpretable. This paper proposes an improved alignment method, dynamic state warping (DSW). DSW integrates the dynamic information of sequences into DTW by converting each time point into a latent state. 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 neighbour classifier, DSW shows significant improvement on classification accuracy in comparison with Euclidean distance (68/85 wins), DTW (70/85 wins) and its variants. We also empirically demonstrate that DSW is more robust and scales better to long sequences than Euclidean distance and DTW.