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

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.

arXiv commentSpotlight Presentation at NeurIPS 2020

References in corpus (12)

• Optimal detection of changepoints with a linear computational cost
• Selective review of offline change point detection methods
• Optimal Inference After Model Selection
• An Evaluation of Change Point Detection Algorithms
• Selective Sequential Model Selection
• A significance test for forward stepwise model selection
• Performance evaluation of DNA copy number segmentation methods
• More powerful post-selection inference, with application to the Lasso
• Selective inference after cross-validation
• On the Post Selection Inference constant under Restricted Isometry Properties
• Parametric Programming Approach for More Powerful and General Lasso Selective Inference
• Selective Inference for Change Point Detection in Multi-dimensional Sequences

Cited by in corpus (3)

• More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming
• Parametric Programming Approach for More Powerful and General Lasso Selective Inference
• More Powerful and General Selective Inference for Stepwise Feature Selection using the Homotopy Continuation Approach