OTW: Optimal Transport Warping for Time Series
Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. However, it suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed exactly. This hinders its use in deep learning architectures, where layers involving DTW computations cause severe bottlenecks. To alleviate these issues, we introduce a new metric for time series data based on the Optimal Transport (OT) framework, called Optimal Transport Warping (OTW). OTW enjoys linear time/space complexity, is differentiable and can be parallelized. OTW enjoys a moderate sensitivity to time and shape distortions, making it ideal for time series. We show the efficacy and efficiency of OTW on 1-Nearest Neighbor Classification and Hierarchical Clustering, as well as in the case of using OTW instead of DTW in Deep Learning architectures.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringDeep LearningDynamic Time WarpingTime SeriesMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
An Efficient Transport-Based Dissimilarity Measure for Time Series Classification under Warping Distortions
Time Series Classification (TSC) is an important problem with numerous applications in science and technology. Dissimilarity-based approaches, such as Dynamic Time Warping (DTW), are classical methods for distinguishing …
ClassificationDynamic Time WarpingTime SeriesTime Series ClassificationMulti-task learning of time series and its application to the travel demand
We address the problem of modeling and prediction of a set of temporal events in the context of intelligent transportation systems. To leverage the information shared by different events, we propose a multi-task learning…
Dynamic Time WarpingMulti-Task LearningTime SeriesTime Series AnalysisOptimal Warping Paths are unique for almost every Pair of Time Series
Update rules for learning in dynamic time warping spaces are based on optimal warping paths between parameter and input time series. In general, optimal warping paths are not unique resulting in adverse effects in theory…
Dynamic Time WarpingTime SeriesTime Series AnalysisMatch-And-Deform: Time Series Domain Adaptation through Optimal Transport and Temporal Alignment
While large volumes of unlabeled data are usually available, associated labels are often scarce. The unsupervised domain adaptation problem aims at exploiting labels from a source domain to classify data from a related, …
Domain AdaptationDynamic Time WarpingTime SeriesUnsupervised Domain AdaptationA Survey on Algorithmic Developments in Optimal Transport Problem with Applications
Optimal Transport (OT) has established itself as a robust framework for quantifying differences between distributions, with applications that span fields such as machine learning, data science, and computer vision. This …
Dynamic Time Warping