Sketches for Time-Dependent Machine Learning

Jesus Antonanzas, Marta Arias, Albert BifetarXiv 2021 · OpenReview

TL;DR

This paper introduces a novel approach to improve machine learning models' performance on time-dependent data by incorporating statistics (mean and variance) of data distributions at various time resolutions. This method, implemented in an Exponential Histogram Recurrent Neural Network (EHRNN), significantly boosts accuracy and efficiency, especially in dynamic environments prone to concept drift.

What Problem Does This Paper Address?

Machine learning models often struggle with time-series data because the underlying processes generating the data can change over time. This phenomenon, known as "concept drift," can render previously accurate models obsolete. Traditional models trained on historical data may fail to adapt to these evolving distributions. The paper addresses this by proposing a way to equip models with an understanding of the current data distribution and its temporal evolution, making them more resilient to concept drift and improving their predictive capabilities.

Methods

The core of the proposed solution lies in efficiently maintaining descriptive statistics (mean and variance) of data features. This is achieved using sketches, specifically Exponential Histograms (EHs), which are data streaming techniques for summarizing information with sub-linear memory. The authors explore two main ways to integrate these statistics:

  1. Input Augmentation: Statistics are computed over input attributes and fed into traditional ML algorithms as additional features.
  2. Latent Representation Summarization: Statistics are computed over the latent representations (hidden states) of models like Recurrent Neural Networks (RNNs).

The paper introduces a novel architecture called the Exponential Histogram Recurrent Neural Network (EHRNN). This architecture enhances a standard Elman Network by using multi-resolution EHs to track the mean and variance of the hidden states. These statistics are then concatenated with the original hidden state vector to produce the final output. This approach leverages the temporal information already encoded in RNN hidden states and enriches it with explicit distributional statistics.

Datasets

The authors evaluated their approach using:

  • Synthetic Data (sineMixed): This dataset was generated by concatenating sampled discrete sine waves with varying parameters and offsets. It was specifically designed to simulate three types of concept drift: sudden, incremental, and reoccurring.
  • Electricity Dataset: A classical streaming benchmark dataset containing electricity market data, used for predicting price movements (UP/DOWN).

Key Insights and Ideas

  • Summaries Matter: Incorporating descriptive statistics (mean and variance) of data distributions, especially over hidden states, significantly improves model accuracy compared to using raw data alone.
  • Hidden States are Rich: Summarizing the statistics of RNN hidden states is more effective than summarizing input attributes. This is likely because hidden states already encode complex temporal patterns and interactions in a compressed form.
  • Resolution is Key: The choice of window resolution (the number of recent data points considered for statistics) is crucial for performance. There isn't a one-size-fits-all solution; finding the optimal resolution is critical.
  • Efficiency Gains: The EHRNN architecture, while incorporating additional statistics, does not introduce significant computational or memory overhead, especially when properly adjusted. This makes it suitable for streaming scenarios.

Key Results

  • Improved Accuracy: In classification tasks, the EHRNN significantly outperformed equivalent architectures without feature/latent summarizations. For the Electricity dataset, the EHRNN achieved approximately 15% higher validation accuracy compared to a vanilla RNN.
  • Effective for Concept Drift: Experiments on synthetic datasets with various drift types showed that the EHRNN's ability to track distributional changes improved its predictive performance.
  • Window Size Importance: For the Electricity dataset, a sliding window of length 48 consistently yielded the best results, aligning with known temporal correlations in the data.
  • Parameter Efficiency: When comparing EHRNN to a vanilla RNN with windowed input (mean and variance of input features), the EHRNN achieved similar accuracies with significantly fewer parameters (50% to 700% fewer).

Limitations and Future Work

  • Window Resolution Tuning: The paper acknowledges that finding the optimal window resolution is critical but currently requires manual tuning. Future work could focus on developing adaptive resolution mechanisms or end-to-end architectures that learn these resolutions.
  • Statistics Choice: While mean and variance were explored, the authors suggest that other statistics could be beneficial for different data types.
  • Model Adaptability: The authors propose adapting other common time series model architectures (e.g., CNNs) to this framework, potentially by tracking statistics along the temporal axis.
  • Sketch Types: Exploring different types of sketches, including adaptive ones like ADWIN, is suggested for future research.

Summary updated

Abstract

Time series data can be subject to changes in the underlying process that generates them and, because of these changes, models built on old samples can become obsolete or perform poorly. In this work, we present a way to incorporate information about the current data distribution and its evolution across time into machine learning algorithms. Our solution is based on efficiently maintaining statistics, particularly the mean and the variance, of data features at different time resolutions. These data summarisations can be performed over the input attributes, in which case they can then be fed into the model as additional input features, or over latent representations learned by models, such as those of Recurrent Neural Networks. In classification tasks, the proposed techniques can significantly outperform the prediction capabilities of equivalent architectures with no feature / latent summarisations. Furthermore, these modifications do not introduce notable computational and memory overhead when properly adjusted.
BibTeX
@misc{antonanzas2021sketches,
  author = {Jesus Antonanzas and Marta Arias and Albert Bifet},
  title = {{Sketches for Time-Dependent Machine Learning}},
  year = {2021},
  eprint = {2108.11923},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.11923},
}
Figure