Non-parametric multiple change-point detection

Andreas Anastasiou, Piotr Fryzlewicz · 2025

Read Non-parametric multiple change-point detection by Andreas Anastasiou, Piotr Fryzlewicz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21379.txt.

Introduction

Andreas Anastasiou and Piotr Fryzlewicz present a new change-point method in a 2025 statistics paper. Change-point tools find the moments when a data stream's pattern shifts. Many shifts at once, of any kind, are hard to locate without assuming a model family.

Their method, NPID, isolates each stretch of data so it holds at most one change, which sharpens the search. It estimates both how many changes occurred and where, for general distribution shifts. Two stopping rules are offered: a fixed threshold and an information score. Across a wide range of test cases, the method beat current rivals. An R package ships with the paper.

Catalog record

CREATORAndreas Anastasiou, Piotr Fryzlewicz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE125 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-21379

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Non-parametric multiple change-point detection Andreas Anastasiou, Piotr Fryzlewicz Abstract We introduce a methodology, labelled Non-Parametric Isolate-Detect (NPID), for the consistent estimation of the number and locations of multiple change-points in a non-parametric setting. The method can handle general distributional changes and is based on an isolation technique preventing the consideration of intervals that contain more than one change-point, which enhances the estimation accuracy. As stopping rules, we propose both thresholding and the optimization of an information criterion. In the scenarios tested, which cover a broad range of change types, NPID outperforms the state of the art. An R implementation is provided. A Preprint Keywords Non-parametric statistics; segmentation; threshold criterion; information criterion 1 Introduction The focus of this work is on non-parametric, offline, multiple change-point detection, the aim of which is to test whether a data sequence is distributionally homogeneous, and if not, to estimate the number and locations of changes. The problem has seen a recent interest in a range of application areas; a non-exhaustive list includes social networks [ 11 ] , electrocardiography [ 21 ] and hydrology [ 25 ] . Denote by N the number of change-points and by r_{1},r_{2},\ldots,r_{N} their locations, with r_{0}=0 , r_{N+1}=T . We work in the model X_{t}\sim F_{k},\quad r_{k-1}+1\leq t\leq r_{k},\quad k=1,\ldots,N+1,\quad t=1,\ldots,T, (1) where \left\{X_{t}\right\}_{t=1,\ldots,T} is the observed univariate data sequence of serially independent observations and F_{k} is the distribution of the X_{t} ’s between the change-points r_{k-1} and r_{k} , with F_{k}\neq F_{k+1}\,\,\,\forall\,k\in\left\{1,\ldots,N\right\} . The parameters N and r_{k} , as well as the distributions F_{k} , are unknown. Our methodology can in principle be extended to variables with values in an arbitrary metric space, as long as the distributional difference is detectable on a Vapnik-Cervonenkis (VC) class. We address this briefly in Section 6 . As the choice of such a VC class in general metric spaces (a necessity for the computation of the change-point location estimator) is a difficult practical problem in itself, our literature review, which follows, does not make a distinction between non-parametric methods specifically designed for univariate data and those applicable to more general spaces. Much of the early literature on non-parametric change-point detection covers the case of a single change-point. Some authors [ 6 , 19 ] test whether there is a change-point at an unknown time point, while others [ 7 , 5 , 8 ] assume that there exists a change-point and focus on its estimation and on the construction of confidence regions. In [ 5 ] and [ 8 ] , mean-dominant norms, as defined in [ 5 ] , are employed as a measure of the difference of the empirical cumulative distribution functions before and after a change-point candidate. In multiple non-parametric change-point detection, observing a connection between multiple change-points and goodness-of-fit tests, [ 26 ] propose a non-parametric maximum likelihood approach using empirical process techniques. The number of change-points, N , is estimated via an information criterion; given an estimate of N , a non-parametric profile likelihood-based algorithm is used to recursively compute the maximizer of an objective function. In an attempt to improve on the computational cost of that method, [ 10 ] use the Pruned Exact Linear Time (PELT) method introduced in [ 13 ] in order to find the optimal segmentation. [ 17 ] propose a non-parametric approach based on Euclidean distances between sample observations, which combines binary segmentation with a divergence measure from [ 22 ] ; however, this approach departs from classical non-parametric change-point detection in the sense that it is not invariant with respect to monotone transformations of data (or in other words: does not use the ranks of the data only). Using the Kolmogorov-Smirnov (KS) statistic, [ 18 ] present two consistent procedures for univariate change point localization; one based on the standard binary segmentation algorithm of [ 24 ] and the other one on the WBS methodology of [ 9 ] . In [ 23 ] , a multiscale method is developed for detecting changes in pre-defined quantiles of the underlying distribution. Other techniques are based on the estimation of density functions [ 12 ] , or the extension of well-defined statistics, such as the Wilcoxon/Mann–Whitney rank-based criterion first employed in [ 7 ] for the detection of at most one change-point, to the multiple change-point setting [ 15 ] . Our proposed approach, labelled Non-Parametric Isolate-Detect (NPID), is a generic technique for consistent non-parametric multiple change-point detection in a data sequence. It adapts the isolate-detect principle, introduced in a parametric change-point detection context by [ 2 ] and studied also in [ 1 ] and [ 3 ] , to the non-parametric setting. NPID consists of two main stages; firstly, the isolation of each of the true change-points within subintervals of the domain [1,\ldots,T] , and secondly their detection. The isolation step ensures that, with high probability, no other change-point is present in the interval under consideration, which enhances the detection power, especially in difficult scenarios such as ones involving limited spacings between consecutive change-points or other low-signal-to-noise-ratio settings. NPID’s ability to analyse such structures accurately, with low computational cost (see Sections 3.1 and 4 ), adds to the appeal of the proposed approach. Within each interval, where, by construction, there is at most one change-point, we use the non-parametric approach of [ 5 ] to carry out detection. For the theoretical results regarding the accuracy of NPID in estimating the locations of the change-points, we show in Section 2.2 that the optimal consistency rate is attained by employing optimal rate results from [ 8 ] in our proof strategy. Section 2.2 situates our method within the existing literature. We now briefly introduce the main steps of NPID. For an observed data sequence \left\{X_{t}\right\}_{t=1,\ldots,T} , and with \lambda_{T} a suitably chosen positive integer, the method first creates a collection of right- and left-expanding intervals S_{RL}=\left\{R_{1},L_{1},R_{2},L_{2},\ldots,R_{K},L_{K}\right\} , where K=\left\lceil T/\lambda_{T}\right\rceil , R_{j}=[1,\min\left\{j{\lambda_{T}}+1,T\right\}] and L_{j}=[\max\left\{T-j\lambda_{T},1\right\},T] . A suitably chosen contrast function, whose value at location b\in\left\{s,s+1,\ldots,e-1\right\} and for an input argument u\in\mathbb{R} is denoted by \tilde{B}_{s,e}^{b}(u) (formula ( 5 )), measures the difference between the pre- b and post- b empirical distributions at u\in\mathbb{R} . NPID first works within R_{1} and calculates \tilde{B}_{1,\lambda_{T}+1}^{b}(X_{i}) , for each i\in\left\{1,2,\ldots,T\right\} and for each b\in\left\{1,2,\ldots,\lambda_{T}\right\} . This creates \lambda_{T} vectors \bm{y_{b}}=\left(\tilde{B}_{1,\lambda_{T}+1}^{b}(X_{1}),\tilde{B}_{1,\lambda_{T}+1}^{b}(X_{2}),\ldots,\tilde{B}_{1,\lambda_{T}+1}^{b}(X_{T})\right),\quad b=1,\ldots,\lambda_{T}. The next step is to aggregate the contrast function information across i\in\left\{1,2,\ldots,T\right\} by applying to each \bm{y_{b}} a mean-dominant norm L:\mathbb{R}^{T}\rightarrow\mathbb{R} ; the mean-dominance property is such for any d\in\mathbb{Z}^{+} and \forall\bm{x}\in\mathbb{R}^{d} with x_{i}\geq 0,i=1,\ldots,d , it holds that L(\bm{x})\geq\frac{1}{d}\sum_{i=1}^{d}x_{i} . The formal mathematical definition of a mean-dominant norm is given in Section 2 of [ 5 ] and examples include L_{1}(\bm{y_{b}})=\frac{1}{T}\sum_{i=1}^{T}|y_{b,i}|,\quad L_{2}(\bm{y_{b}})=\frac{1}{\sqrt{T}}\sqrt{\sum_{i=1}^{T}y_{b,i}^{2}},\quad L_{\infty}(\bm{y_{b}})=\sup_{i=1,\ldots,T}\left\{|y_{b,i}|\right\}. (2) Applying L(\cdot) to each \bm{y_{b}},b=1,\ldots,\lambda_{T} , returns a vector \bm{v} of length \lambda_{T} . With \tilde{b}_{R_{1}} := {\rm argmax}_{j}\left\{v_{j}\right\} , if v_{\tilde{b}_{R_{1}}} exceeds a certain threshold \zeta_{T} , then \tilde{b}_{R_{1}} is taken as a change-point. If not, then the process tests the next interval in S_{RL} . After detection, the algorithm makes a new start from the end-point (or start-point) of the right- (or left-) expanding interval on which the detection occurred. Given a suitable choice of the threshold \zeta_{T} (more details are provided in Section 3.2 ),

Read the complete text