Abstract
There is a vast body of literature related to methods for detecting changepoints (CP). However, less attention has been paid to assessing the statistical reliability of the detected CPs. In this paper, we introduce a novel method to perform statistical inference on the significance of the CPs, estimated by a Dynamic Programming (DP)-based optimal CP detection algorithm. Based on the selective inference (SI) framework, we propose an exact (non-asymptotic) approach to compute valid p-values for testing the significance of the CPs. Although it is well-known that SI has low statistical power because of over-conditioning, we address this disadvantage by introducing parametric programming techniques. Then, we propose an efficient method to conduct SI with the minimum amount of conditioning, leading to high statistical power. We conduct experiments on both synthetic and real-world datasets, through which we offer evidence that our proposed method is more powerful than existing methods, has decent performance in terms of computational efficiency, and provides good results in many practical applications.
Introduction
In fields ranging from bioinformatics to finance, identifying "changepoints"—sudden shifts in the underlying mechanism of sequential data—is a critical task. While many algorithms can find the optimal locations for these markers, they rarely assess whether these detections represent a real physical change or merely stochastic noise.
The core challenge is a phenomenon known as "double dipping." In standard statistics, using the same data to both identify a pattern and test its significance leads to biased p-values, often resulting in a high rate of false discoveries. Existing solutions for changepoint (CP) detection have significant drawbacks. Asymptotic methods often fail with small or highly correlated datasets, while standard Selective Inference (SI) methods tend to "over-condition," making the tests so conservative that they lack the statistical power to detect real changes.
Methodology: OptSeg-SI
The proposed method, OptSeg-SI, bridges the gap between Dynamic Programming (DP)—the gold standard for finding optimal changepoints—and Selective Inference.
Selective Inference Framework
The SI framework calculates p-values by conditioning the test on the "selection event"—the fact that the algorithm chose these specific points. To avoid the low power associated with over-conditioning, the authors introduce parametric Dynamic Programming. Instead of conditioning on the entire decision path of the algorithm, they characterize the entire subspace of data that would result in the same optimal changepoints.
The Line Approach and Pruning
The data is represented as a function of a single scalar $z$, effectively a line in high-dimensional space. A modified DP algorithm identifies the specific intervals of $z$ where the detected changepoints remain the "optimal" choice. To maintain computational efficiency, the authors introduce pruning lemmas that discard candidate changepoint vectors that could never be optimal, preventing exponential complexity.
Experimental Evaluation
The researchers evaluated OptSeg-SI on a variety of datasets, including synthetic 1D sequences with various noise distributions, DNA Copy Number Profiles, Array CGH data, and the historical Nile River Dataset.
Key Results
OptSeg-SI demonstrated several key advantages over existing methods:
- Reliability: In null-hypothesis tests, OptSeg-SI correctly controlled the false positive rate at 5%, whereas "naive" methods were wildly over-optimistic.
- Superior Power: OptSeg-SI consistently outperformed Binary Segmentation (BinSeg-SI) and over-conditioned DP methods. It successfully identified real changes that other valid methods missed.
- Efficiency: Computing time scales almost linearly with the number of data points, making it practical for real-world applications.
As shown in the figure above, OptSeg-SI provides much smaller p-values for true changepoints (like B and D) compared to BinSeg-SI, while correctly identifying noise-induced points (like C and F) with high p-values.
Conclusion
OptSeg-SI provides a robust framework for validating changepoint detections with exact p-values. By minimizing conditioning through parametric programming, it achieves high statistical power without compromising the false discovery rate. While currently optimized for 1D sequences, future work aims to extend this approach to multivariate data and further improve computational efficiency for high-stakes decision-making environments.
Summary updated