Partially Observable Multi-Sensor Sequential Change Detection: A Combinatorial Multi-Armed Bandit Approach

Chen Zhang, Steven C. H. Hoi

Abstract

In modern industrial monitoring, the volume of sensor data often exceeds the capacity for full real-time observability due to bandwidth and computational constraints. This paper presents a novel approach to Partially Observable Multi-sensor Sequential Change Detection (POMSCD) by integrating Bayesian inference with a Combinatorial Multi-Armed Bandit (CMAB) framework. Our method leverages inter-sensor correlations to infer the state of unobserved variables and employs an adaptive sampling strategy to prioritize sensors that maximize detection power. Experimental results on synthetic and real-world semiconductor manufacturing data demonstrate that our CMAB-based approach significantly reduces the Average Detection Delay (ADD) compared to standard sampling heuristics.

Introduction

The rapid growth of the Internet of Things (IoT) and complex industrial systems, such as power grids and semiconductor fabrication lines, has led to environments monitored by hundreds or thousands of sensors. The primary goal is sequential change detection: identifying an anomaly or "change-point" as quickly as possible after it occurs. However, full observability is frequently unattainable due to limited battery life in wireless nodes, restricted communication bandwidth, or processing bottlenecks.

The challenge lies in determining which subset of $m$ sensors to monitor out of $p$ total sensors at each time step to minimize detection delay. This paper addresses this "Partially Observable" challenge by treating sensor selection as an online optimization problem.

Methodology

Online Weighted Bayesian Change Detection

A key innovation of this work is the move away from treating sensors as independent entities. By exploiting the underlying correlation structure of the system, the proposed model can update the posterior probability of a change even for sensors that are not currently being sampled.

The system utilizes a Bayesian posterior estimator with time-decayed weights, ensuring that recent observations have a greater impact on the test statistic, $\Lambda(n)$. This statistic is derived from a confidence region of the system's state; when it exceeds a predefined threshold, an alarm is triggered.

Figure 1: Correlation matrix of the variables in the SECOM dataset, illustrating the complex inter-dependencies that the Bayesian model exploits to infer unobserved states.

Adaptive Sampling via CMAB

To solve the selection problem, the authors formulate it as a Combinatorial Multi-Armed Bandit (CMAB). In this setup:

  • Arms: Each sensor represents an "arm" that can be pulled.
  • Reward: The reward is defined as the "detection power"—specifically, the non-centrality parameter of the test statistic's distribution.
  • Strategy: A Upper Confidence Bound (UCB) algorithm is employed to balance exploration and exploitation. Exploitation focuses on sensors showing signs of deviation, while exploration ensures that no part of the system remains unmonitored for too long, preventing "blind spots."

Experimental Results

Synthetic Data Performance

The researchers conducted extensive simulations with $p=10$ and $p=100$ sensors to evaluate the Average Detection Delay (ADD). The CMAB approach was compared against several baselines, including Random sampling (RAND), Top-r Adaptive Sampling (TRAS), and Numerical Adaptive Sampling (NAS).

Figure 2: Comparison of Average Detection Delay (ADD) for synthetic datasets ($p=10, 100$). The CMAB approach consistently achieves lower delays across various change magnitudes ($\delta$) compared to heuristic methods.

As shown in the results, the CMAB strategy significantly outperforms traditional methods. For instance, in a 100-sensor environment with a change magnitude of $\delta=1$, the CMAB approach achieved an ADD of approximately 8.91, while random sampling lagged behind at 190. This highlights the efficiency of the UCB-based exploration strategy in high-dimensional spaces.

Real-World Application: SECOM Dataset

The framework was also validated using the SECOM dataset from the UCI Machine Learning Repository, which contains 1,567 samples with 31 variables from a semiconductor process. The CMAB strategy maintained its superior performance even under tight sensing constraints (e.g., monitoring only 3 or 5 variables), demonstrating its practical utility in real-world industrial settings.

Conclusion

This research demonstrates that modeling sensor selection as a CMAB problem, combined with Bayesian correlation modeling, provides a robust solution for anomaly detection in partially observable systems. By mathematically balancing the need to investigate suspicious signals with the need to maintain global awareness, the proposed method achieves near-optimal detection speeds. Future work will focus on reducing the computational complexity for extremely large-scale systems and extending the framework to non-Gaussian data distributions.

Summary updated

Abstract

This paper explores machine learning to address a problem of Partially Observable Multi-sensor Sequential Change Detection (POMSCD), where only a subset of sensors can be observed to monitor a target system for change-point detection at each online learning round. In contrast to traditional Multisensor Sequential Change Detection tasks where all the sensors are observable, POMSCD is much more challenging because the learner not only needs to detect on-the-fly whether a change occurs based on partially observed multi-sensor data streams, but also needs to cleverly choose a subset of informative sensors to be observed in the next learning round, in order to maximize the overall sequential change detection performance. In this paper, we present the first online learning study to tackle POMSCD in a systemic and rigorous way. Our approach has twofold novelties: (i) we attempt to detect changepoints from partial observations effectively by exploiting potential correlations between sensors, and (ii) we formulate the sensor subset selection task as a Multi-Armed Bandit (MAB) problem and develop an effective adaptive sampling strategy using MAB algorithms. We offer theoretical analysis for the proposed online learning solution, and further validate its empirical performance via an extensive set of numerical studies together with a case study on real-world data sets.
BibTeX
@inproceedings{zhang2019partially,
  author = {Chen Zhang and Steven C. H. Hoi},
  title = {{Partially Observable Multi-Sensor Sequential Change Detection: A Combinatorial Multi-Armed Bandit Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33015733},
}
Figure