RLAD: Time Series Anomaly Detection through Reinforcement Learning and Active Learning

Tong Wu, Jorge OrtizarXiv 2021 · OpenReview

TL;DR

This paper introduces RLAD, a novel semi-supervised time series anomaly detection system that combines deep reinforcement learning (DRL) with active learning. RLAD efficiently learns to detect anomalies with minimal labeled data, adapting to changing data distributions and outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Time series anomaly detection is crucial across many domains, but existing methods often struggle with two key challenges: 1) anomalies are rare, making it difficult to train models, and 2) real-world data is often non-stationary, meaning the underlying data-generating process changes over time. Traditional supervised methods require extensive labeled data, while unsupervised methods often perform poorly and cannot adapt to these non-stationary properties. Semi-supervised methods offer a middle ground but still heavily rely on the availability of labeled anomalies, which are inherently scarce. This paper aims to develop an anomaly detection algorithm that can learn effectively with very few labels and adapt dynamically to evolving data patterns.

Methods

RLAD is built upon a combination of three core techniques:

  • Deep Reinforcement Learning (DRL): The system frames anomaly detection as a Markov Decision Process (MDP). A Deep Q-Network (DQN) is employed to learn an action-value function, where the "state" is a segment of the time series, and the "action" is the agent's prediction of whether the segment is anomalous. The agent learns by receiving rewards based on its predictions.
  • Active Learning: To address the scarcity of labeled data, RLAD incorporates an active learning strategy. Specifically, it uses "margin sampling" to identify the most uncertain data points for the model. These uncertain points are then presented to a human expert for manual labeling, allowing the model to gain the most valuable information from each query.
  • Label Propagation: Once new labels are acquired through active learning, a label propagation algorithm is used to infer pseudo-labels for similar unlabeled data points. This technique leverages the relationships within the data to expand the labeled dataset, further improving the model's learning efficiency.

The overall system involves a "warm-up" phase using an Isolation Forest to initialize a replay memory for the DRL agent, followed by iterative cycles of DRL training, active learning for new labels, and label propagation.

Datasets

The paper evaluates RLAD on two commonly used time series anomaly detection datasets:

  • Yahoo Benchmark: This dataset includes both real (A1Benchmark - login data) and synthetic (A2Benchmark) time series data.
  • KPI data set: This dataset is sourced from AIOPs competitions and comprises data from several internet companies.

Key Insights and Ideas

  • Synergy of DRL and Active Learning: The paper demonstrates that combining DRL's adaptive learning capabilities with active learning's efficient data acquisition strategy is highly effective for anomaly detection, especially in scenarios with limited labels.
  • Adaptability to Non-Stationarity: RLAD's reinforcement learning component allows it to continuously adapt its detection model as it encounters new data and anomalies, making it robust to non-stationary time series.
  • Leveraging Pseudo-Labels: The integration of label propagation to generate pseudo-labels from a small set of human-annotated data significantly amplifies the learning signal, reducing the need for extensive manual labeling.
  • Outperforming State-of-the-Art: The results highlight that RLAD can achieve superior performance compared to both unsupervised and semi-supervised methods, even with a tiny fraction of labeled data.

Key Results

RLAD demonstrates significant performance improvements across the evaluated datasets:

  • Yahoo Dataset: RLAD outperforms the best unsupervised approach by a factor of 1.58 on the F1 score with only 1% of labels. With 10% labels, it achieves nearly 0.8 F1-score on A1Benchmark and 1.0 on A2Benchmark. It also outperforms the state-of-the-art semi-supervised technique Deep-SAD by up to ~10x in some experiments.
  • KPI Dataset: RLAD achieves a 3x higher F1-score than all unsupervised methods on the KPI dataset by labeling only 0.1% of samples.

Limitations and Future Work

  • Human Expert Dependency: While RLAD significantly reduces the need for labels, it still relies on a human expert for manual labeling during the active learning phase. The efficiency and accuracy of this process are crucial.
  • Computational Cost: The paper mentions that RLAD requires 1000 episodes to converge on the Yahoo dataset, suggesting a potentially high computational cost for training.
  • Future Work: The authors plan to explore the deployment of RLAD on real-world, real-time applications, indicating a focus on scalability and practical implementation. They also suggest investigating other active learning query strategies and further optimizing the DRL components.

Summary updated

Abstract

We introduce a new semi-supervised, time series anomaly detection algorithm that uses deep reinforcement learning (DRL) and active learning to efficiently learn and adapt to anomalies in real-world time series data. Our model - called RLAD - makes no assumption about the underlying mechanism that produces the observation sequence and continuously adapts the detection model based on experience with anomalous patterns. In addition, it requires no manual tuning of parameters and outperforms all state-of-art methods we compare with, both unsupervised and semi-supervised, across several figures of merit. More specifically, we outperform the best unsupervised approach by a factor of 1.58 on the F1 score, with only 1% of labels and up to around 4.4x on another real-world dataset with only 0.1% of labels. We compare RLAD with seven deep-learning based algorithms across two common anomaly detection datasets with up to around 3M data points and between 0.28% to 2.65% anomalies.We outperform all of them across several important performance metrics.
BibTeX
@misc{wu2021rlad,
  author = {Tong Wu and Jorge Ortiz},
  title = {{RLAD: Time Series Anomaly Detection through Reinforcement Learning and Active Learning}},
  year = {2021},
  eprint = {2104.00543},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2104.00543},
}
Figure