Autowarp: Learning a Warping Distance from Unlabeled Time Series Using Sequence Autoencoders

Abubakar Abid, James Y. ZouarXiv 2018 · arXiv

Introduction

Measuring similarity between time series trajectories—such as heart rate data or stock price fluctuations—is a fundamental challenge in data science. Traditional approaches often rely on hand-crafted metrics like Dynamic Time Warping (DTW) or Edit Distance. However, these metrics require significant domain expertise to select and tune, and they often struggle with the diverse noise profiles (e.g., sampling variations, outliers, Gaussian noise) found in real-world datasets.

Abid and Zou (NIPS 2018) propose Autowarp, an unsupervised framework that automatically learns an optimal similarity metric for a specific dataset. By leveraging sequence autoencoders and a differentiable family of warping distances, Autowarp "distills" complex patterns into an interpretable and robust metric without requiring labeled data.

Methodology

The Autowarp framework operates in three primary stages:

1. Learning Latent Representations

The process begins with a sequence-to-sequence LSTM autoencoder. The encoder maps an input trajectory $t$ to a fixed-length hidden representation $h$, while the decoder attempts to reconstruct the original signal. This bottleneck architecture forces the model to capture the essential "shape" of the trajectory while filtering out stochastic noise.

Figure 1: The Autowarp pipeline transforms original trajectories into a latent representation, which is then used to optimize a custom warping distance metric.

2. Metric Distillation

To move beyond the "black box" nature of the latent space, Autowarp introduces a differentiable family of warping distances. This family is parameterized by variables ($\alpha, \gamma, \epsilon$) that allow the metric to smoothly interpolate between Euclidean distance, DTW, and Edit Distance. By making the warping distance differentiable, the authors enable the use of gradient-based optimization.

3. Optimization via Latent BetaCV

The optimal parameters for the warping distance are found by minimizing a modified version of the BetaCV metric, which measures clustering quality (the ratio of intra-cluster to inter-cluster distance). Autowarp optimizes the warping distance to match the natural clusters formed in the autoencoder’s latent space. This "Latent BetaCV" approach ensures that the final metric captures the structural similarities identified by the deep learning model.

Experimental Evaluation

The authors evaluated Autowarp on synthetic data and several real-world datasets, including hand movement coordinates (Libras), GPS trajectories (Taxicab), and high-dimensional sign language data (ASL).

Key Results

  • Performance: Autowarp consistently outperformed traditional metrics like DTW and EDR, particularly in the presence of complex noise.
  • Interpretability: The learned parameters were found to be semantically meaningful. For instance, the model favored Euclidean-like metrics for regularly sampled taxi data and Edit Distance-like metrics for data with frequent outliers.
  • Validation: A critical finding is the strong correlation between the unsupervised Latent BetaCV metric and downstream classification accuracy. As shown in Figure 6, lower (better) BetaCV scores in the latent space strongly predict higher classification performance, validating the use of BetaCV as an effective unsupervised objective.
Figure 6: Correlation between the unsupervised Latent BetaCV metric and supervised classification accuracy across various datasets.

Conclusion and Future Work

Autowarp provides a robust, unsupervised method for discovering the "right" distance metric for time series data. By combining the representational power of LSTMs with the interpretability of warping distances, it bridges the gap between deep learning and classical time-series analysis. Future work aims to reduce the $O(N^2 T^2)$ computational complexity through linear-time approximations like FastDTW, potentially scaling the method to massive datasets.

Summary updated

Abstract

Measuring similarities between unlabeled time series trajectories is an important problem in domains as diverse as medicine, astronomy, finance, and computer vision. It is often unclear what is the appropriate metric to use because of the complex nature of noise in the trajectories (e.g. different sampling rates or outliers). Domain experts typically hand-craft or manually select a specific metric, such as dynamic time warping (DTW), to apply on their data. In this paper, we propose Autowarp, an end-to-end algorithm that optimizes and learns a good metric given unlabeled trajectories. We define a flexible and differentiable family of warping metrics, which encompasses common metrics such as DTW, Euclidean, and edit distance. Autowarp then leverages the representation power of sequence autoencoders to optimize for a member of this warping distance family. The output is a metric which is easy to interpret and can be robustly learned from relatively few trajectories. In systematic experiments across different domains, we show that Autowarp often outperforms hand-crafted trajectory similarity metrics.
BibTeX
@misc{abid2018autowarp,
  author = {Abubakar Abid and James Y. Zou},
  title = {{Autowarp: Learning a Warping Distance from Unlabeled Time Series Using Sequence Autoencoders}},
  year = {2018},
  eprint = {1810.10107},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.10107},
}
Figure