New method finds reliable minimum number of data distribution changes
Distribution-free inference on the number of changepoints
Machine Learning
Summary
Sometimes data changes its behavior at unknown points, and it's hard to tell how many changes happen. The authors show that you can’t confidently guess an upper limit for these changes without assuming something about the data. However, they created a new tool called CLOCC that can reliably provide a lower limit on how many changes occurred, based on minimal assumptions. CLOCC works by using a statistical technique called conformal p-values and gives useful results on both fake and real data.
What this means in practice
- •For financial analysts: Identify a guaranteed minimum number of shifts in market behavior without relying on specific distribution assumptions.
- •For quality control engineers: Securely detect at least how many times a manufacturing process changes its quality distribution using only observed data.
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.