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$.
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.
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