Generalised Interpretable Shapelets for Irregular Time Series

Patrick Kidger, James Morrill, Terry LyonsarXiv 2020 · arXiv

TL;DR

This paper introduces a continuous-time framework for "shapelets"—small, representative patterns used to classify time series. By moving from discrete to continuous time, the authors enable shapelets to handle messy, irregularly sampled data, learn their own optimal lengths through gradient descent, and remain highly interpretable thanks to a novel regularization penalty.

What Problem Does This Paper Address?

Time series data in the real world is rarely perfect. Sensors fail (missing data), and observations often happen at irregular intervals. Traditional shapelet transforms—which classify a signal based on how closely it matches a set of "template" patterns—struggle here because they typically require regularly spaced, fully observed data.

Furthermore, classical shapelet methods face a frustrating trade-off: you can either search the dataset for patterns (which is interpretable but computationally expensive) or learn them via gradient descent (which is fast but often results in "noisy" shapelets that don't look like real data). Finally, the length of a shapelet has traditionally been a fixed hyperparameter, requiring a tedious and expensive grid search to optimize.

Methods

The authors propose a Generalised Shapelet Transform that re-imagines shapelets as continuous-time objects.

  1. Continuous-Time Interpolation: Discrete time series are converted into continuous paths using piecewise linear interpolation. This naturally handles irregular sampling and missing values.
  2. Differentiable Lengths: Because the framework is continuous, the length of each shapelet ($S_k$) becomes a continuous parameter. The model can now "stretch" or "shrink" shapelets during training using standard backpropagation.
  3. Interpretable Regularization: To ensure learned shapelets remain meaningful to humans, the authors add a penalty term that forces each shapelet to stay similar to at least one actual segment from the training data.
  4. Generalised Discrepancy: Instead of relying solely on standard Euclidean distance ($L^2$), the framework allows for learned pseudometrics. This includes advanced tools like Logsignatures (which capture the geometric "essence" of a path) and Mel-frequency cepstrums (MFC) for audio data.

Datasets

The method was evaluated on a broad range of challenges:

  • UEA Multivariate Time Series Archive: A benchmark of 30 datasets. The authors selected 9 representative ones, including Handwriting, Epilepsy, and LSST (astronomical data).
  • Irregularly Sampled UEA: Modified versions of the above where 10%, 30%, or 50% of data points were randomly dropped to test robustness.
  • Speech Commands: A large-scale audio dataset consisting of one-second clips of spoken words like "yes," "no," "left," and "right."

Key Insights and Ideas

  • Chirality Matters: In the PenDigits dataset (handwritten digits), the model discovered that the digits 5 and 6 are best distinguished not just by their static shape, but by the chirality (direction) of their bottom loops.
  • Automatic Feature Weighting: By learning a diagonal matrix $A$ within the discrepancy function, the model automatically learns which channels (or frequencies) are most important.
  • Discovering the Spectral Gap: When applied to audio, the learned pseudometric assigned high weights to lower frequencies and very low weights to higher ones. It essentially "discovered" the spectral gap in human speech—the fact that lower frequencies carry more linguistic information—purely from the data.
Figure 1: The most significant shapelet for each class (blue, solid), overlaid with the most similar training example (orange, dashed). Similarity is measured with respect to the (learnt) discrepancy function.

Key Results

  • Superior Accuracy: On the UEA archive, the generalised shapelet transform ($L^2$) outperformed the classical approach, achieving "wins" (top performance within one standard deviation) on 7 out of 9 datasets, compared to just 3 for the classical method.
  • Audio Performance: On the Speech Commands dataset, the generalised method achieved 91.9% accuracy, dwarfing the classical shapelet's 44.8%.
  • Efficiency in Length Learning: The authors showed that learning shapelet lengths differentiably is just as effective as performing an exhaustive hyperparameter search, but significantly faster and less labor-intensive.
Table 1: Test accuracy (mean ± std, computed over three runs) on UEA. A ‘win’ is the number of times each algorithm was within 1 standard deviation of the top performer for each dataset.

Limitations and Future Work

  • Computational Complexity: While more efficient than brute-force searching, training differentiable shapelets still scales with the square of the time series length ($O(N \cdot T^2)$), which could be a bottleneck for very long sequences.
  • Interpolation Choice: The study primarily uses piecewise linear interpolation. The authors note that while other methods like splines or Gaussian Processes are possible, their impact on performance wasn't the primary focus of this work.
  • Domain Expertise: While the framework supports complex discrepancies like Logsignatures, choosing the right one still requires some domain knowledge of the data's underlying structure.

Summary updated

Abstract

The shapelet transform is a form of feature extraction for time series, in which a time series is described by its similarity to each of a collection of `shapelets'. However it has previously suffered from a number of limitations, such as being limited to regularly-spaced fully-observed time series, and having to choose between efficient training and interpretability. Here, we extend the method to continuous time, and in doing so handle the general case of irregularly-sampled partially-observed multivariate time series. Furthermore, we show that a simple regularisation penalty may be used to train efficiently without sacrificing interpretability. The continuous-time formulation additionally allows for learning the length of each shapelet (previously a discrete object) in a differentiable manner. Finally, we demonstrate that the measure of similarity between time series may be generalised to a learnt pseudometric. We validate our method by demonstrating its performance and interpretability on several datasets; for example we discover (purely from data) that the digits 5 and 6 may be distinguished by the chirality of their bottom loop, and that a kind of spectral gap exists in spoken audio classification.
BibTeX
@misc{kidger2020generalised,
  author = {Patrick Kidger and James Morrill and Terry Lyons},
  title = {{Generalised Interpretable Shapelets for Irregular Time Series}},
  year = {2020},
  eprint = {2005.13948},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.13948},
}

Loading related content...

Figure