Order-Preserving Optimal Transport for Distances between Sequences

We present new distance measures between sequences that can tackle local temporal distortion and periodic sequences with arbitrary starting points. Through viewing the instances of each sequence as empirical samples of an unknown distribution, we cast the calculations of distances between sequences as optimal transport problems. To preserve the inherent temporal relationships of the instances in sequences, we propose two methods through incorporating the temporal information into the spatial ground metric and concentrating the transport with two novel temporal regularization terms, respectively. The inverse difference moment regularization enforces local homogeneous structures in the transport, and the KL-divergence with a prior distribution regularization prevents transport between instances with far temporal positions. We show that the resulting problems can be efficiently solved by the matrix scaling algorithm. Extensive experiments on eight datasets with different classifiers and performance measures show the effectiveness and generality of the proposed distances.