Methods to reliably estimate changepoint counts in data sequences
Distribution-free inference on the number of changepoints
Machine Learning
Summary
This paper tackles the challenge of figuring out how many times a data sequence changes its pattern without knowing where or even how many changes happened. The authors show that you cannot reliably get an upper limit on these changes without strong assumptions, but they develop a new method to find a trustworthy lower limit using something called conformal p-values. Their approach only needs the assumption that sections of data before and after changes behave consistently and independently. They also explain how to make this method work well in practice and show it gives useful results on both made-up and real-world data.
ChangepointDistribution-free inferenceConformal p-valuesLower confidence boundExchangeabilityIndependenceFinite-sample validityStatistical inferenceData segmentationConfidence interval
Authors
Rohan Hore, Aaditya Ramdas
Abstract
Suppose we are given an ordered sequence of independent data whose distribution changes $K$ times at unknown locations, for some unknown $K \geq 0$. In this paper, we study the problem of performing distribution-free inference on $K$. First, we show an impossibility result: any distribution-free upper confidence bound on $K$ must be trivial and uninformative. Then, using conformal $p$-values, and under only the assumption that the data segments induced by the changepoints are exchangeable (within themselves) and mutually independent, we construct a finite-sample valid lower confidence bound on $K$, which we call the Conformal LOwer bound on Changepoint Count (CLOCC). We show that CLOCC is the only feasible way to provide a lower bound on $K$ under the stated assumptions, a property we refer to as its universality. We provide practical guidelines for choosing score functions that yield efficient and tight lower bounds. We evaluate CLOCC in several synthetic and real-data experiments, where it provides informative lower bounds on $K$, demonstrating its practical applicability.