Classification of Time Sequences using Graphs of Temporal Constraints

Mathieu Guillame-Bert, Artur DubrawskiJMLR 2017 · OpenReview

TL;DR

This paper introduces a novel representation called Graphs of Temporal Constraints (GTCs) for classifying complex time-series data (Symbolic and Scalar Time Sequences - SSTS). Two algorithms, GTC-Set and GTC-DF, leverage GTCs to achieve state-of-the-art accuracy on a wide range of benchmark datasets, often outperforming existing methods in both speed and classification performance.

What Problem Does This Paper Address?

Traditional machine learning often struggles with the inherent temporal nature of time-series data. Existing methods typically "flatten" this data into a tabular format by extracting features like moving window statistics or signal projections, which can lose crucial temporal relationships. This paper addresses the need for classification algorithms that can natively handle and exploit the temporal dependencies within time sequences, especially for complex data types like Symbolic and Scalar Time Sequences (SSTS), which combine discrete events with continuous scalar values.

Methods

The core of this work is the Graph of Temporal Constraints (GTC). A GTC is a directed graph where nodes represent events (with optional scalar constraints) and edges represent temporal relationships between these events (e.g., "event A must occur within 5 seconds of event B"). The authors propose two algorithms that learn GTCs for classification:

  • GTC-Set: This algorithm extracts a set of GTCs that act as individual "voters." A new time sequence is classified based on the majority vote of the GTCs that are true for it.
  • GTC-DF (Decision Forest): This algorithm builds a decision forest where each node in the decision trees is a GTC. The path through the tree is determined by whether the input sequence satisfies the GTC at each node.

Both algorithms employ a constructive learning approach, recursively building GTCs by applying operations that maximize information gain. This is a key novelty, as it directly builds the model rather than relying on pre-extracted patterns and subsequent selection. The learning process is interleaved with model building, leading to efficient and interpretable models.

Datasets

The authors evaluated their algorithms on a diverse collection of datasets:

  • 59 Benchmark Datasets: This includes a broad range of temporal sequence classification tasks.
  • Synthetic Data (1 set): A generated dataset of 200 purely symbolic SSTSs designed to test the ability to learn explicit temporal patterns.
  • UCR Time Series Classification Repository (41 datasets): A standard benchmark for time series classification. These datasets are "aligned," meaning observations at the same time index across different series correspond to the same phenomenon.
  • 16 Rotated UCR Data Sets: A novel benchmark created by breaking the alignment of the UCR datasets. This was done by randomly shifting time series, making them "non-aligned" and more challenging, simulating scenarios where the starting point of observation is arbitrary.
  • Internal Bleeding Detection Data Set (1 set): A multivariate time series dataset collected from vital signs of pigs, designed to detect internal bleeding. This dataset is also non-aligned.

Key Insights and Ideas

  • GTCs as a Powerful Representation: The GTC framework effectively captures complex temporal relationships, including event order, time differences, and scalar value constraints, which are crucial for accurate time-series classification.
  • Direct Model Building is Efficient: Instead of a two-stage process of pattern extraction followed by selection, the proposed algorithms build GTCs directly, leading to more efficient learning and often smaller, more interpretable models.
  • Information Gain Drives Learning: Maximizing information gain is a robust criterion for selecting the most discriminative GTCs and operations, leading to high classification accuracy.
  • GTC-DF vs. GTC-Set Trade-offs: GTC-DF is generally faster and produces slightly better models, while GTC-Set offers easier interpretability due to its independent voter structure.
  • Interpretability is Achievable: The GTC representation, especially when simplified, allows for human understanding of the learned patterns, which is a significant advantage over black-box models.
  • Handling Non-Aligned Data: The proposed methods show particular strength in classifying non-aligned time series, a common and challenging real-world scenario.

Key Results

  • State-of-the-Art Accuracy: On the UCR datasets, GTC-DF and GTC-Set achieved the highest average and median ranks for accuracy, outperforming 13 other algorithms.
  • Superior Performance on Non-Aligned Data: The algorithms demonstrated significantly better performance on the "Rotated UCR" datasets and the "Bleeding Detection Data Set," where temporal alignment is broken.
  • Competitive Computational Speed: While not always the fastest, the algorithms were often competitive in terms of computation time, especially when compared to their accuracy. For example, on the Yoga dataset, their computation was significantly faster than other high-accuracy methods.
  • High Accuracy on Synthetic Data: Achieved 100% accuracy on synthetic data, validating their ability to learn explicit temporal patterns.
  • Effective Interpretability: Experiments showed that even a small number of selected GTCs could achieve substantial classification performance and provide meaningful insights into the data.

Limitations and Future Work

  • Approximate Negation: The algorithms use an approximate negation for GTC operations, which is a simplification that might not be exact in all cases.
  • Complexity of Large Models: While individual GTCs are manageable, large GTC-DF or GTC-Set models can still be complex to fully comprehend. The paper proposes methods to extract smaller, interpretable subsets of GTCs.
  • Parameter Tuning: While default parameters were used for most algorithms to ensure fair comparison, optimizing parameters for specific datasets could potentially improve results further.
  • Future Work: The paper suggests that the GTC framework could be extended to other temporal pattern mining tasks and that further research into efficient GTC learning and interpretation methods is warranted. The authors also highlight the potential for developing effective cardio-respiratory monitors using their methods for detecting specific conditions.

Summary updated

Abstract

We introduce two algorithms that learn to classify Symbolic and Scalar Time Sequences (SSTS); an extension of multivariate time series. An SSTS is a set of \emph{events} and a set of scalars. An event is defined by a symbol and a time-stamp. A scalar is defined by a symbol and a function mapping a number for each possible time stamp of the data. The proposed algorithms rely on temporal patterns called Graph of Temporal Constraints (GTC). A GTC is a directed graph in which vertices express occurrences of specific events, and edges express temporal constraints between occurrences of pairs of events. Additionally, each vertex of a GTC can be augmented with numeric constraints on scalar values. We allow GTCs to be cyclic and/or disconnected. The first of the introduced algorithms extracts sets of co-dependent GTCs to be used in a voting mechanism. The second algorithm builds decision forest like representations where each node is a GTC. In both algorithms, extraction of GTCs and model building are interleaved. Both algorithms are closely related to each other and they exhibit complementary properties including complexity, performance, and interpretability. The main novelties of this work reside in direct building of the model and efficient learning of GTC structures. We explain the proposed algorithms and evaluate their performance against a diverse collection of 59 benchmark data sets. In these experiments, our algorithms come across as highly competitive and in most cases closely match or outperform state-of-the-art alternatives in terms of the computational speed while dominating in terms of the accuracy of classification of time sequences.
BibTeX
@article{guillamebert2017classification,
  author = {Mathieu Guillame-Bert and Artur Dubrawski},
  title = {{Classification of Time Sequences using Graphs of Temporal Constraints}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=Qq2uec1eM8M},
}
Figure