Accurate Evaluation of Quickest Changepoint Detectors via Non-parametric Survival Analysis

Technical Summary: Accurate Evaluation of Quickest Changepoint Detectors via Non-parametric Survival Analysis

Problem Statement

Quickest Changepoint Detection (QCD) is a critical task in fields ranging from industrial quality control to epidemiology and wireless sensor networks. The performance of QCD models is traditionally evaluated using two primary metrics: the Average Run Length (ARL), representing the average time to a false alarm, and the Average Detection Delay (ADD), representing the average time to detect a change after it occurs.

While ARL and ADD are standard optimality criteria in theoretical and simulation studies, their application to real-world datasets is significantly hindered by finite and irregular sequence lengths. In practical scenarios, sequences are often truncated before a change is detected or before a false alarm occurs. Conventional estimators, such as the Less-Biased ARL (LB-ARL) and LB-ADD, typically discard sequences where the detector fails to trigger an alarm within the observed horizon. This exclusion leads to substantial negative bias and high variance, particularly when sequence lengths are short or highly irregular, rendering reliable model evaluation and selection difficult.

Methodology

To address these limitations, the authors propose a novel framework that draws an analogy between QCD and survival analysis, specifically utilizing non-parametric methods to handle right-censored data.

1. Analogy Formulation:

   • ARL Context: A sequence is treated as a "patient," the detection point ($\tau$) as the "event time," and the minimum of the changepoint ($\nu$) and sequence length ($T$) as the "censoring time."
   • ADD Context: For sequences with a changepoint, the detection delay ($\Delta\tau = \tau - \nu$) is the event time, and the remaining sequence length after the changepoint ($T - \nu$) is the censoring time.

2. Proposed Estimators (KM-ARL and KM-ADD):
   The authors adapt the Kaplan-Meier Estimator (KME), a standard non-parametric tool for estimating survival functions under censoring, to the QCD setting.

   • Instead of discarding truncated sequences, the KME utilizes all available information up to the censoring time.
   • The KM-ARL is defined as the integral of the estimated survival function of detection points, $\hat{S}_{ARL}(t)$, over a range $[0, a]$.
   • The KM-ADD is similarly defined as the integral of the estimated survival function of detection delays, $\hat{S}_{ADD}(t)$.
   • These estimators are non-parametric, requiring no assumptions about the underlying data distribution (e.g., exponential decay), unlike previous parametric approaches.

3. Theoretical Analysis:
   The paper derives rigorous bounds for the estimation bias, decomposing it into finite-sample bias and truncation bias.

   • Finite-sample bias: Proven to decay exponentially as the dataset size ($N$) increases, provided the independent censoring assumption holds (valid for online QCD models that do not look ahead).
   • Truncation bias: The authors prove that the truncation bias of the KM estimators is strictly smaller (less negative) than that of conventional LB estimators.
   • Asymptotic Unbiasedness: The estimators are proven to be asymptotically unbiased unless extrapolation beyond the observed support is required.

Key Contributions

1. Novel Estimators: Introduction of KM-ARL and KM-ADD, non-parametric estimators enabling the evaluation of QCD models on real-world datasets with limited and irregular sequence lengths.
2. Theoretical Guarantees: Derivation of estimation bias bounds and proof of asymptotic unbiasedness (under specific conditions), establishing a theoretical foundation for using survival analysis in QCD evaluation.
3. Practical Utility: Demonstration of reduced estimation bias and enhanced robustness compared to baseline estimators (LB-ARL/ADD) through experiments on simulated (Gaussian and Poisson processes) and real-world (WISDM Actitracker) datasets.
4. Open Source Implementation: Provision of ready-to-use Python code to facilitate empirical and intuitive model selection for practitioners.

Experimental Results

The authors evaluated the proposed metrics against conventional estimators using:

• Simulated Data: Gaussian and Poisson processes with varying changepoint distributions and sequence lengths (both constant and irregular).
• Real-World Data: The WISDM Actitracker dataset, containing over 51,000 sequences of human activity with highly irregular lengths (ranging from 1 to 54,401 frames).

Findings:

• Accuracy: KM-ARL and KM-ADD provided significantly more accurate estimates of the true ARL and ADD compared to LB-ARL and LB-ADD, especially in heavy-censoring scenarios (e.g., short sequences or high detection thresholds).
• Robustness: Unlike conventional estimators, which exhibited high variance and instability when the number of valid sequences dropped (due to truncation), the KM estimators maintained stability by utilizing the full dataset via the risk set mechanism of the Kaplan-Meier estimator.
• Model Selection: The proposed metrics facilitated clearer ARL-ADD tradeoff curves, allowing for more reliable empirical model selection among various QCD algorithms (including CUSUM, EWMA, and NP-FOCuS).

Significance and Claims

The paper positions itself as a contribution to the broader goal of reproducible and interpretable evaluation in machine learning. The authors argue that without principled estimation methods for real-world constraints (like irregular sequence lengths), performance improvements may be illusory.

By bridging QCD and survival analysis, the work offers a method to:

• Eliminate the need for arbitrary assumptions about data distributions.
• Mitigate the severe bias introduced by sequence truncation.
• Enable the evaluation of QCD models on datasets that were previously considered too irregular or short for standard metrics.

The authors modestly note that while their method handles irregular lengths effectively, it still requires datasets with changepoint labels and assumes independent censoring for online models. They suggest that for scenarios with dependent censoring or extreme truncation, further extensions using copula-based methods or parametric extrapolation may be necessary.