A Bayesian Partially Observable Online Change Detection Approach with Thompson Sampling

Abstract

This article proposes a Bayesian learning framework for online change detection of high-dimensional data streams where only a subset of variables can be observed at each time point due to limited sensing capacities. On the one hand, we need to build a change detection scheme based on partial observations. On the other, the scheme should be able to adaptively and actively select the most critical sensing variables to observe to maximize the detection power. To address these two points, in this article, first, a novel Bayesian Spike-Slab Composite Decomposition (BSSCD) is proposed to decompose the high-dimensional signals onto normal and abnormal bases, where the projection coefficients are efficiently estimated via variational Bayesian inference. Built upon it, the posterior Bayes factor is constructed as the detection statistic. Second, by further formulating the detection statistic as the reward function of combinatorial multi-armed bandit (CMAB), a Thompson sampling strategy is proposed for selecting the potential changed variables with the balance of exploration and exploitation. The efficacy and applicability of our method are demonstrated in practice with numerical studies and a real case study.

Keywords:

• Adaptive sampling
• Combinatorial multi-armed bandit
• Composite decomposition
• Posterior Bayes Factor
• Sparse change detection
• Variational Bayesian inference

Supplementary Materials

In the supplementary materials, we provide derivation of variational Bayesian inference, deviation of the detection statistic, verification of Proposition 2, proof of Theorems 1 and 2, simulation results for 1D and 2D cases, as well as sensitivity analysis of parameters.

Code_and_Data: Zip file containing the Matlab code for implementing TS-BSSCD method as well as the real-world data used in case study in.mat form.

Additional information

Funding

This article was supported by the NSFC grant 71901131 and 71932006, the BNSF grant 9222014, the NSF grant DMS 1830363 and CMMI 1922739, the ASFC grant 2020Z063058001, and the Tsinghua University Intelligent Logistics & Supply Chain Research Center grant THUCSL20182911756-001.