Score-based Quickest Change Detection for Unnormalized Models

Suya Wu, Enmao Diao, Taposh Banerjee, Jie Ding, Vahid TarokhAISTATS 2023 · OpenReview

Abstract

Quickest Change Detection (QCD) is a critical task in signal processing, traditionally addressed by the Cumulative Sum (CUSUM) algorithm. However, CUSUM's reliance on normalized probability density functions presents a significant computational bottleneck for modern unnormalized models, such as Energy-Based Models (EBMs), where calculating the partition function is often intractable. This paper introduces SCUSUM (Score-based CUSUM), a novel algorithm that replaces the log-likelihood ratio with a weighted difference of Hyvärinen scores. This approach eliminates the need for normalization constants while maintaining theoretical parity with CUSUM. Experimental results across various synthetic datasets demonstrate that SCUSUM offers massive computational speedups—up to 1,700x—and superior robustness compared to non-parametric methods.

Introduction

The goal of Quickest Change Detection is to identify an abrupt change in the underlying distribution of a data stream as quickly as possible while minimizing false alarms. The CUSUM algorithm is the optimal solution when pre- and post-change distributions are fully known. However, in high-dimensional settings or complex generative models, we often only have access to unnormalized densities. The required normalization constant (the partition function) involves integration that is typically computationally prohibitive.

While non-parametric methods like Maximum Mean Discrepancy (MMD) avoid explicit distribution modeling, they often lack the sensitivity and theoretical guarantees of likelihood-based approaches. This work bridges the gap by leveraging score-based methods to enable efficient QCD for unnormalized models.

Methodology: The SCUSUM Algorithm

The core innovation of SCUSUM is the substitution of the traditional log-likelihood ratio with the Hyvärinen score. The Hyvärinen score depends only on the derivatives of the log-density, causing the unknown normalization constant to vanish during calculation.

The algorithm maintains a detection score $Z(n)$. Under the pre-change distribution, the score exhibits a negative drift, remaining near zero. Upon a change, the score gains a positive drift and increases monotonically. A change is declared when $Z(n)$ exceeds a threshold $\tau$.

Comparison of detection score trajectories for CUSUM, SCUSUM, Scan B-statistic, and CALM-MMD.

As shown in the figure above, both CUSUM and SCUSUM exhibit a clear, monotonic increase in detection score following the change point (at time step 500). In contrast, kernel-based methods like the Scan B-statistic and CALM-MMD often plateau or show higher variance, which can lead to delayed detection or increased false alarms in noisy environments.

Experimental Evaluation

The authors evaluated SCUSUM against CUSUM and MMD-based baselines (Scan B-statistic and CALM-MMD) using three synthetic data streams where normalization is difficult:

  • Multivariate Normal (MVN): Used as a baseline to prove asymptotic optimality.
  • Exponential Family (EXP): A pairwise interaction graphical model where the partition function requires numerical integration.
  • Gauss-Bernoulli Restricted Boltzmann Machine (GB-RBM): A complex generative model where exact likelihoods are notoriously hard to compute.

Key Results and Discussion

SCUSUM demonstrates exceptional performance in both speed and accuracy. In the 4-dimensional Exponential Family experiment, the classic CUSUM took 66,409 seconds per trial due to numerical integration, while SCUSUM achieved similar performance in just 38.4 seconds—a speedup of over 1,700x.

Quantitative performance comparison (CADD and ARL) across MVN, EXP, and GB-RBM datasets.

The quantitative results in the figure above highlight several key findings:

  • Theoretical Parity: SCUSUM's trade-off between the Average Run Length (ARL) until a false alarm and the Conditional Average Detection Delay (CADD) is nearly identical to the computationally expensive CUSUM.
  • Superiority over Non-Parametric Methods: SCUSUM consistently outperforms MMD-based methods, particularly in non-Gaussian scenarios (EXP and GB-RBM), where MMD methods struggle to control false alarms effectively.

Conclusion

SCUSUM provides a powerful framework for quickest change detection in unnormalized models, offering the theoretical strengths of CUSUM without its computational burdens. While it currently requires knowledge of the model forms, future work could extend this to scenarios with unknown post-change distributions or temporally correlated data. This work significantly advances the applicability of QCD to modern, high-dimensional machine learning models.

Summary updated

Abstract

Classical change detection algorithms typically require modeling pre-change and post-change distributions. The calculations may not be feasible for various machine learning models because of the co...
BibTeX
@inproceedings{wu2023score,
  author = {Suya Wu and Enmao Diao and Taposh Banerjee and Jie Ding and Vahid Tarokh},
  title = {{Score-based Quickest Change Detection for Unnormalized Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=B1T6tWyZfI1},
}
Figure