Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming

Vo Nguyen Le Duy, Hiroki Toda, Ryota Sugiyama, Ichiro Takeuchi

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.

Conceptual diagram of the proposed Selective Inference method, showing the conditioning on the data space to identify valid p-values.

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:

  1. Reliability: In null-hypothesis tests, OptSeg-SI correctly controlled the false positive rate at 5%, whereas "naive" methods were wildly over-optimistic.
  2. 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.
  3. Efficiency: Computing time scales almost linearly with the number of data points, making it practical for real-world applications.
Comparison of p-values for detected changepoints (A-F) using Naive, BinSeg-SI, and the proposed OptSeg-SI methods. OptSeg-SI provides valid p-values with higher power for true changes.

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

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.
BibTeX
@inproceedings{duy2020computing,
  author = {Vo Nguyen Le Duy and Hiroki Toda and Ryota Sugiyama and Ichiro Takeuchi},
  title = {{Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=h8wt7BtoXt},
}
Figure