Large-Scale Multi-Stream Quickest Change Detection via Shrinkage Post-Change Estimation

Yuan Wang, Yajun MeiIEEE Trans. Information Theory 2015 · DOI

TL;DR

This paper tackles the challenge of quickly detecting changes in the means of many independent data streams simultaneously. The authors propose a novel approach using shrinkage estimators to improve detection speed, especially when the number of affected streams is large, by balancing detection delay trade-offs.

What Problem Does This Paper Address?

Monitoring large numbers of data streams in real-time is crucial for applications like biosurveillance, quality control, and finance. A key problem is "quickest change detection," which aims to raise an alarm as soon as a change occurs in the data's underlying distribution, while minimizing false alarms. While this problem is well-studied for a single data stream, extending it to a large number of streams (K) presents significant challenges. Classical methods, even when adapted, suffer from a "curse of dimensionality," where their performance degrades rapidly as K increases. Specifically, the detection delay can become comparable to the first-order term, rendering their theoretical optimality practically meaningless. This paper addresses the open problem of developing efficient methods for large-scale, multi-stream change detection that can mitigate these dimension-related issues.

Methods

The core of the proposed methodology lies in combining "hard thresholding" and "linear shrinkage" estimators with the classical Shiryaev-Roberts procedure for quickest change detection.

  • Shiryaev-Roberts Procedure: This is a standard framework for quickest change detection. The paper adapts it to a multi-stream setting.
  • Shrinkage Estimators: These are a class of statistical estimators that "shrink" estimates towards a central value. The paper explores two types:
  • Hard-thresholding: This method sets estimates to zero if they fall below a certain threshold, effectively assuming only a sparse subset of streams are affected.
  • Linear Shrinkage: This method shrinks estimates towards a pre-specified value, balancing the influence of individual stream data with prior information.
  • Post-Change Hypothesis: The paper assumes that for each stream, either there's no change or a "big" change (larger than a pre-specified bound). This assumption is crucial for the shrinkage approach.
  • Two Scenarios: The methods are analyzed under two scenarios:
  • Sparse Post-Change: Only a small, unknown subset of streams are affected.
  • Simultaneous Change: All streams are affected, potentially with different mean shifts.

The paper proposes plugging these shrinkage-based estimators into the Shiryaev-Roberts framework to create new monitoring schemes.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulated data.

Key Insights and Ideas

  • Shrinkage for High Dimensions: The paper demonstrates that shrinkage estimation, a technique well-established in offline statistics, can be effectively adapted to online quickest change detection in high-dimensional settings.
  • Balancing Trade-offs: Shrinkage estimators are shown to balance the trade-off between the first-order and second-order terms of the detection delay, which is critical for large K.
  • Sparse vs. Simultaneous Changes: The paper highlights that different shrinkage strategies (hard-thresholding vs. linear shrinkage) are more effective for different post-change scenarios (sparse vs. simultaneous changes). Hard-thresholding excels in sparse cases, while linear shrinkage is beneficial when all streams change.
  • Curse of Dimensionality in Simulation: The paper emphasizes the significant challenge of accurately simulating the Average Run Length (ARL) to false alarm for large K due to the "curse of dimensionality," suggesting that standard Monte Carlo methods may be insufficient.
  • New Information Measure: A new "information number" is introduced, which is a shrinkage approximation of the Kullback-Leibler divergence, better reflecting the complexities of large-scale, uncertain data streams.

Key Results

  • Theoretical Guarantees: The paper provides theoretical results on the asymptotic properties of the proposed shrinkage-based schemes, including bounds on detection delay and ARL to false alarm.
  • Hard-thresholding for Sparse Changes: For the sparse post-change case (few affected streams), hard-thresholding estimators can significantly reduce the detection delay compared to baseline methods, with the reduction proportional to the number of affected streams (r).
  • Linear Shrinkage for Simultaneous Changes: For the case where all streams are affected, linear shrinkage estimators can also reduce detection delay, with the optimal shrinkage factor depending on parameters like the number of streams (K) and the overall information content.
  • Simulation Challenges: Numerical simulations illustrate the difficulty of accurately estimating ARL for large K, showing that standard Monte Carlo simulations can be highly biased and require an exponentially increasing number of runs.

Limitations and Future Work

  • Gaussian Model Assumption: The current work focuses on Gaussian data streams with known variances. Extending the methods to more general distributions (e.g., Poisson) or to handle unknown and different variances across streams is a significant future direction.
  • Monte Carlo Simulation: Overcoming the "curse of dimensionality" for efficient and accurate Monte Carlo simulation of ARL in high-dimensional settings remains an open problem.
  • Optimal Parameter Choice: While the paper provides guidance on choosing shrinkage parameters (a, b, c), further research could explore more adaptive or data-driven methods for parameter selection.
  • Theoretical Analysis for Other Distributions: The theoretical analysis for other distributions, like Poisson, will likely require modifications to the definition of "r" and other key components.

Summary updated

BibTeX
@article{wang2015large,
  author = {Yuan Wang and Yajun Mei},
  title = {{Large-Scale Multi-Stream Quickest Change Detection via Shrinkage Post-Change Estimation}},
  journal = {IEEE Trans. Information Theory},
  year = {2015},
  doi = {10.1109/tit.2015.2495361},
}
Figure