Round Robin Active Sequential Change Detection for Dependent Multi-Channel Data

Anamitra Chaudhuri, Georgios Fellouris, Ali TajerIEEE Trans. Information Theory 2024 · DOI

TL;DR

This paper introduces a computationally efficient method for detecting changes in data streams from multiple sources, even when these sources are dependent and only a subset can be observed at any given time. The proposed "Round Robin CUSUM" policy offers a practical solution for scenarios where data acquisition is costly or constrained, achieving near-optimal performance in detecting these changes quickly while minimizing false alarms.

What Problem Does This Paper Address?

In today's data-rich world, we often deal with information coming from multiple sources simultaneously. Think of sensor networks, financial markets, or surveillance systems. The challenge arises when the underlying statistical behavior of these sources changes unexpectedly. Detecting this change quickly is crucial for making timely decisions. However, collecting data from all sources can be prohibitively expensive or even impossible due to sampling constraints (e.g., limited bandwidth, computational resources). Furthermore, these sources might not be independent; their behavior can be correlated, adding another layer of complexity. This paper tackles the problem of efficiently detecting a change in the joint distribution of multiple, potentially dependent, data sources under a strict constraint: we can only sample a fixed number of sources at each time step. The goal is to develop a method that detects the change as fast as possible while keeping the rate of false alarms low, and importantly, this method should be computationally simple and not require prior knowledge about which sources are affected.

Methods

The core of this paper is the "Round Robin CUSUM" policy. This policy is designed to be computationally simple and avoids randomization. It works by cycling through a pre-defined family of "units," where each unit is a subset of $m$ sources that can be sampled at a time. For each unit, a CUSUM-like statistic is computed. The policy dynamically decides whether to continue sampling the current unit, switch to the next unit in the cycle, or raise an alarm if the statistic exceeds a threshold.

Key aspects of the method include:

  • Round-Robin Sampling: A fixed permutation of units (subsets of $m$ sources) is used, and the policy cycles through them. This ensures that all potential combinations of $m$ sources are eventually considered.
  • CUSUM-like Statistic: For each sampled unit, a cumulative sum statistic is maintained. This statistic recursively updates based on the log-likelihood ratio of the observed data under a hypothetical post-change distribution versus the pre-change distribution.
  • Dynamic Decision Making: Based on the value of the CUSUM statistic, the policy decides to continue sampling, switch to the next unit, or declare a change.
  • Theoretical Guarantees: The paper provides theoretical analysis of the policy's performance, establishing non-asymptotic upper bounds on the detection delay and proving asymptotic optimality under certain conditions. This includes deriving a universal asymptotic lower bound for comparison.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation studies rather than evaluating on pre-existing datasets.

Key Insights and Ideas

  • The Power of Structured Sampling: Even with a fixed sampling constraint ($m$ sources out of $K$), a structured, round-robin approach can be highly effective. It avoids the need for complex adaptive sampling strategies that might be computationally intensive.
  • Dependence is Manageable: The proposed method explicitly handles dependent data streams, which is a significant advantage over many existing change detection techniques that assume independence.
  • Asymptotic Optimality Under Constraints: The paper demonstrates that even under sampling constraints, it's possible to achieve asymptotic optimality, meaning the detection delay approaches the theoretical best possible as the false alarm rate goes to zero. This is a crucial result for practical applications where perfect information is unavailable.
  • Trade-offs in Sampling: Simulations reveal interesting trade-offs. Sampling more sources at a time ($m=3$ vs. $m=2$) can improve performance, but this improvement might be offset by the complexity of the post-change distributions, suggesting a delicate balance between sampling rate and detection accuracy.

Key Results

  • False Alarm Control: The proposed Round Robin CUSUM policy is shown to effectively control the false alarm rate, ensuring the expected time to raise an alarm is at least a user-specified level $\gamma$.
  • Asymptotic Optimality: Under specific conditions (e.g., completely specified post-change distributions for affected units, or equal signal-to-noise ratios), the policy is proven to be first-order asymptotically optimal. This means its detection delay is asymptotically equivalent to the best achievable delay among all policies satisfying the same sampling and false alarm constraints.
  • Upper Bounds on Detection Delay: The paper provides non-asymptotic upper bounds on the worst-case conditional expected detection delay, which are shown to be close to the theoretical lower bounds in simulations.
  • Simulation Validation: Extensive simulations demonstrate the effectiveness of the proposed policy across various scenarios, including changes in marginal distributions and correlation structures of Gaussian data. The results align well with theoretical predictions.

Limitations and Future Work

  • Assumptions on Post-Change Distributions: The theoretical results on asymptotic optimality often rely on assumptions about the post-change distributions (e.g., being completely specified or having a specific structure). Relaxing these assumptions is a direction for future work.
  • Parametric Families: The current framework primarily deals with specified pre- and post-change distributions. Extending the analysis to parametric families of distributions would broaden its applicability.
  • Temporal Dependence: The paper assumes data streams are independent over time but can be dependent across channels at a given time. Incorporating temporal dependence within channels is another avenue for future research.
  • Alternative Error/Delay Metrics: Exploring other metrics for evaluating performance beyond the modified Lorden's criterion could lead to new insights.
  • Asymptotic Regime with Infinite Sources: Investigating an asymptotic regime where the number of sources also grows to infinity could be relevant for large-scale systems.
  • Spatial Models: Modeling data streams using spatial models, such as Markov random fields, could potentially lead to more efficient rules in practice.
  • Source Isolation: Developing procedures that can guarantee the correct isolation of affected sources is highlighted as an area of interest.

Summary updated

BibTeX
@article{chaudhuri2024round,
  author = {Anamitra Chaudhuri and Georgios Fellouris and Ali Tajer},
  title = {{Round Robin Active Sequential Change Detection for Dependent Multi-Channel Data}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3475394},
}
Figure