Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control

Wanrong Zhang, Yajun Mei

TL;DR

This paper introduces a novel algorithm, Thompson-Sampling-Shiryaev-Roberts-Pollak (TSSRP), for detecting changes in high-dimensional data streams in real-time, even when only a subset of data can be observed at any given time. TSSRP effectively balances exploring new data sources with exploiting known ones, leading to significantly faster and more efficient change detection compared to existing methods.

What Problem Does This Paper Address?

In many real-world applications, such as network security, manufacturing quality control, or disease outbreak monitoring, we need to detect anomalies or "change-points" in high-dimensional data streams as quickly as possible. However, a significant challenge arises from "sampling control constraints." This means we can't always observe all dimensions of the data at every time step due to limitations in data acquisition, transmission, or processing power. For instance, sensors might have limited battery life, or network bandwidth might be restricted. This forces us to make decisions about which data components to observe, creating a trade-off between gathering information for immediate detection and exploring potentially informative but currently unobserved data sources. Existing change-point detection methods often assume full data availability, making them unsuitable for these resource-constrained scenarios.

Methods

The core of the proposed solution is the Thompson-Sampling-Shiryaev-Roberts-Pollak (TSSRP) algorithm. It combines two key ideas:

  • Multi-Armed Bandit (MAB) Approach (Thompson Sampling): This is used for the "adaptive sampling policy." Imagine each data stream as an "arm" of a bandit machine. Thompson Sampling is a Bayesian approach that intelligently decides which arms (data streams) to "pull" (observe) at each time step. It balances "exploration" (sampling less-observed streams to gain new knowledge) and "exploitation" (sampling streams that have historically shown signs of change to maximize immediate detection). This is achieved by sampling from the posterior distribution of potential changes for each stream.
  • Bayesian Change-Point Detection (Shiryaev-Roberts Procedure): This forms the basis of the "statistical decision policy." The Shiryaev-Roberts procedure is a Bayesian method for detecting changes in data streams. TSSRP adapts this by using local Shiryaev-Roberts statistics for each data stream and then combining them to make a global alarm decision.

The novelty lies in integrating these two frameworks. TSSRP recursively computes two-dimensional local statistics (Rk,t and Lk,t) for each data stream. Rk,t mimics the Shiryaev-Roberts statistic, providing evidence of a local change, while Lk,t relates to the number of observations. The adaptive sampling policy then uses a randomized version of Rk,t to select the top q data streams to observe, balancing exploration and exploitation. The global decision is made by summing the top r of these randomized local statistics and comparing it to a threshold.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation studies using synthetic data.

Key Insights and Ideas

  • Bridging MAB and Change-Point Detection: The paper successfully integrates the adaptive sampling capabilities of MAB (specifically Thompson Sampling) with the robust change-point detection framework of Shiryaev-Roberts. This is a significant step for real-time monitoring under sampling constraints.
  • Balancing Exploration and Exploitation: The Thompson Sampling component is crucial for efficiently allocating limited observation resources. It ensures that the algorithm doesn't just focus on streams that have already shown changes but also explores others that might provide early warnings.
  • Computational Scalability: Despite using Bayesian methods, the TSSRP algorithm is designed to be computationally efficient, with a cost linear to the number of data streams. This is achieved through recursive updates and a limiting Bayesian approach.
  • Prior Knowledge Integration: The algorithm can incorporate prior knowledge about which data streams are more likely to be affected by a change, leading to improved detection performance.
  • Robustness to Distributional Assumptions: The simulation studies suggest that TSSRP performs well even when the assumed data distributions are slightly violated, highlighting its practical utility.

Key Results

  • Significant Reduction in Detection Delay: Numerical simulations consistently show that TSSRP significantly reduces the average detection delay compared to existing methods like TRAS (Top-r Based Adaptive Sampling). For instance, in Table 1, TSSRP variants achieve detection delays around 5.8-6.7, while TRAS is around 11.8-22.8 for 10 changed streams.
  • Improved Performance with Correct Priors: When the prior information about the location of changes is accurate (e.g., using priors Go and G1), TSSRP achieves the smallest average detection delays.
  • Efficient Sensor Allocation: Theorems 3 and 4 demonstrate that in the in-control state, the algorithm samples data streams somewhat randomly, ensuring all have a chance to be observed. In the out-of-control state, it greedily focuses on the affected streams, efficiently allocating resources.
  • Case Study Success: In a hot forming process case study, TSSRP outperformed the TRAS algorithm in detecting anomalies. A solar flare detection case study also showed comparable or better performance than existing methods.

Limitations and Future Work

  • Theoretical Proofs for Optimal Delay: While the paper provides theoretical properties, deriving exact bounds on the average detection delay remains an open problem.
  • Fixed Number of Active Sensors: The current TSSRP algorithm uses a fixed number of q active sensors per time step. The authors suggest future work could explore dynamically changing this number based on the likelihood of a change.
  • Extension to Unknown Post-Change Parameters: The current framework assumes known post-change parameters. Extending it to handle unknown parameters by introducing prior distributions on them is a promising direction.
  • Handling Complex Data Structures: For data streams with spatial or temporal correlation, the Bayesian and Thompson sampling framework could still be applicable if posterior updates can be done efficiently (e.g., via MCMC). This opens new research avenues.
  • Robustness to Significant Mis-specification: While robust to minor distributional violations, the paper notes that significant mis-specification of underlying models can lead to less efficient performance. Exploring more robust variants, perhaps based on ranks, is suggested.

Summary updated

Abstract

In many real-world problems of real-time monitoring high-dimensional streaming data, one wants to detect an undesired event or change quickly once it occurs, but under the sampling control constraint in the sense that one might be able to only observe or use selected components data for decision-making per time step in the resource-constrained environments. In this paper, we propose to incorporate multi-armed bandit approaches into sequential change-point detection to develop an efficient bandit change-point detection algorithm based on the limiting Bayesian approach to incorporate a prior knowledge of potential changes. Our proposed algorithm, termed Thompson-Sampling-Shiryaev-Roberts-Pollak (TSSRP), consists of two policies per time step: the adaptive sampling policy applies the Thompson Sampling algorithm to balance between exploration for acquiring long-term knowledge and exploitation for immediate reward gain, and the statistical decision policy fuses the local Shiryaev-Roberts-Pollak statistics to determine whether to raise a global alarm by sum shrinkage techniques. Extensive numerical simulations and case studies demonstrate the statistical and computational efficiency of our proposed TSSRP algorithm.
BibTeX
@article{zhang2020bandit,
  author = {Wanrong Zhang and Yajun Mei},
  title = {{Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control}},
  journal = {Technometrics},
  year = {2020},
}
Figure