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.

• Publication year

  2019

• Venue

  IEEE Transactions on Pattern Analysis and Machine Intelligence

• Publication date

  2019-12-01

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1109/TPAMI.2018.2870154PMID 30235117
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Discriminative Dimensionality Reduction for Multi-Dimensional Sequences

  2018cited by this paper
• Heteroscedastic Max–Min Distance Analysis for Dimensionality Reduction

  2018cited by this paper
• Soft-DTW: a Differentiable Loss Function for Time-Series

  2017cited by this paper
• Discriminative Transformation for Multi-Dimensional Temporal Sequences.

  2017cited by this paper
• Optimal Mass Transport: Signal processing and machine-learning applications

  2017cited by this paper
• Order-Preserving Wasserstein Distance for Sequence Matching

  2017cited by this paper
• Hierarchical Dynamic Parsing and Encoding for Action Recognition

  2016cited by this paper
• Stochastic Optimization for Large-scale Optimal Transport

  2016cited by this paper
• Action Recognition Using Rate-Invariant Analysis of Skeletal Shape Trajectories

  2016cited by this paper
• Transport-based analysis, modeling, and learning from signal and data distributions

  2016cited by this paper
• Wasserstein discriminant analysis

  2016cited by this paper
• A Transportation Lp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L^p$$\end{document} Distance for Signal Analysis

  2016cited by this paper
• Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric

  2015cited by this paper
• Learning with a Wasserstein Loss

  2015cited by this paper
• Heteroscedastic max-min distance analysis

  2015cited by this paper
• Statistical analysis of trajectories on Riemannian manifolds: Bird migration, hurricane tracking and video surveillance

  2014cited by this paper
• Metric Learning for Temporal Sequence Alignment

  2014cited by this paper
• Optimal Transport for Domain Adaptation

  2014cited by this paper
• Fast Computation of Wasserstein Barycenters

  2013cited by this paper
• Sinkhorn Distances: Lightspeed Computation of Optimal Transport

  2013influential reference
• Learning Maximum Margin Temporal Warping for Action Recognition

  2013cited by this paper
• Multi-modal gesture recognition challenge 2013: dataset and results

  2013cited by this paper
• Linear Sequence Discriminant Analysis: A Model-Based Dimensionality Reduction Method for Vector Sequences

  2013cited by this paper
• A Model-Based Sequence Similarity with Application to Handwritten Word Spotting

  2012cited by this paper
• Generalized time warping for multi-modal alignment of human motion

  2012cited by this paper
• Mining actionlet ensemble for action recognition with depth cameras

  2012cited by this paper
• Robust hand gesture recognition based on finger-earth mover's distance with a commodity depth camera

  2011cited by this paper
• Action recognition based on a bag of 3D points

  2010cited by this paper
• SparseDTW: A Novel Approach to Speed up Dynamic Time Warping

  2009cited by this paper
• Canonical Time Warping for Alignment of Human Behavior

  2009cited by this paper
• Statistical Texture Measures Computed from Gray Level Coocurrence Matrices

  2008influential reference
• Toward accurate dynamic time warping in linear time and space

  2007cited by this paper
• An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison

  2007cited by this paper
• UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences

  2007cited by this paper
• Fast contour matching using approximate earth mover's distance

  2004cited by this paper
• Making Time-Series Classification More Accurate Using Learned Constraints

  2004cited by this paper
• Linear dimensionality reduction via a heteroscedastic extension of LDA: the Chernoff criterion

  2004cited by this paper
• Temporal classification: extending the classification paradigm to multivariate time series

  2002influential reference
• The Earth Mover's distance is the Mallows distance: some insights from statistics

  2001cited by this paper
• The Earth Mover's Distance as a Metric for Image Retrieval

  2000cited by this paper
• Matrix scaling: A geometric proof of Sinkhorn's theorem

  1998cited by this paper
• On Information and Sufficiency

  1997cited by this paper
• On the scaling of multidimensional matrices

  1989cited by this paper
• Dynamic programming algorithm optimization for spoken word recognition

  1978cited by this paper
• On information and distance measures, error bounds, and feature selection

  1976cited by this paper
• Diagonal equivalence to matrices with prescribed row and column sums. II

  1974cited by this paper
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix

  1966cited by this paper

• One-shot Humanoid Whole-body Motion Learning

  2025cites this paper
• Evaluating Text Generation Model Performance by Combining Semantic Meaning and Word Order

  2024cites this paper
• Gloss Prior Guided Visual Feature Learning for Continuous Sign Language Recognition

  2024cites this paper
• Partial ordered Wasserstein distance for sequential data

  2024cites this paper
• Explainable Legal Case Matching via Graph Optimal Transport

  2024cites this paper
• New Results on Rapid Dynamical Pattern Recognition via Deterministic Learning From Sampling Sequences

  2023cites this paper
• OTW: Optimal Transport Warping for Time Series

  2023cites this paper
• Learning With Asymmetric Kernels: Least Squares and Feature Interpretation

  2022cites this paper
• I-SEA: Importance Sampling and Expected Alignment-Based Deep Distance Metric Learning for Time Series Analysis and Embedding

  2022cites this paper
• Temporal Alignment Prediction for Supervised Representation Learning and Few-Shot Sequence Classification

  2022influential citation
• Transport-Based Anatomical-Functional Metric Learning for Liver Tumor Recognition Using Dual-View Dynamic CEUS Imaging

  2022cites this paper
• Optimal Partial Transport Based Sentence Selection for Long-form Document Matching

  2022cites this paper
• Uncertainty-DTW for Time Series and Sequences

  2022cites this paper
• Improving word mover's distance by leveraging self-attention matrix

  2022influential citation
• Application of Leading Indicator Forecasting Based on Optimal Transmission in Financial Technology

  2021cites this paper
• Linear and Deep Order-Preserving Wasserstein Discriminant Analysis

  2021influential citation
• The Novel Sequence Distance Measuring Algorithm Based on Optimal Transport and Cross-Attention Mechanism

  2021cites this paper
• Top-k Self-Adaptive Contrast Sequential Pattern Mining

  2021cites this paper
• Temporal Alignment Prediction for Few-Shot Video Classification

  2021cites this paper
• Dynamical pattern recognition for sampling sequences based on deterministic learning and structural stability

  2021cites this paper
• 2019 Index IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 41

  2020cites this paper
• Distribution Cognisant Loss for Cross-Database Facial Age Estimation With Sensitivity Analysis

  2020cites this paper
• Optimal Transport for Stationary Markov Chains via Policy Iteration

  2020cites this paper
• Improving Text Generation with Student-Forcing Optimal Transport

  2020cites this paper
• Order-Preserving Wasserstein Discriminant Analysis

  2019cites this paper
• Global Features of Fused Frame Relationships Help Video Classification

  2019cites this paper
• A Novel Radar Moving Target Classification and Recognition Technology

  2019cites this paper
• Learning Distance for Sequences by Learning a Ground Metric

  2019influential citation
• Generalized ordered Wasserstein distance for sequential data

  year unknowncites this paper