Optimal detection of changepoints with a linear computational cost

By Rebecca Killick, Paul Fearnhead, Idris Arthur Eckley. 2011

2,451 citations recorded by the source corpus.

We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse larger regions of the genome, or in finance as we observe time-series over longer periods. We consider the common approach of detecting changepoints through minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised likelihood and minimum description length. We introduce a new ∗R. Killick is Senior Research Associate, Department of Mathematics & Statistics, Lancaster University, Lancaster, UK (E-mail: r.killick@lancs.ac.uk). P. Fearnhead is Professor, Department of Mathematics & Statistics, Lancaster University, Lancaster, UK (E-mail: p.fearnhead@lancs.ac.uk). I.A. Eckley is Senior Lecturer, Department of Mathematics & Statistics, Lancaster University, Lancaster, UK (E-mail: i.eckley@lancs.ac.uk). The authors are grateful to Richard Davis and Alice Cleynen for providing the Auto-PARM and PDPA software respectively. Part of this research was conducted whilst R. Killick was a jointly funded Engineering and Physical Sciences Research Council (EPSRC) / Shell Research Ltd graduate student at Lancaster University. Both I.A. Eckley and R. Killick also gratefully acknowledge the financial support of the EPSRC grant number EP/I016368/1. 1 ar X iv :1 10 1. 14 38 v3 [ st at .M E ] 9 O ct 2 01 2 method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost which, under mild conditions, is linear in the number of observations. This compares favourably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the Binary Segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/1619f2d3c69bc2d2b1510c2c668b20e892a70cb1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

A MOSUM procedure for the estimation of multiple random change points (2018, methodology): “Precisely, the methods are: Segmentor from the Segmentor3IsBack-R-Package, CumSeg as described in [33], SMUCE as described in [17] as well as PELT as described in [22].”
Inference for single and multiple change‐points in time series (2013, methodology): “While expressing the criterion function in its general form, we find it convenient to adapt the notation introduced by Killick et al. (2012).”
WEAK SINDY FOR PARTIAL DIFFERENTIAL EQUATIONS (2020, methodology): “An algorithm for this is given in [17] and implemented in MATLAB using the function findchangepts .”
changepoint: An R Package for Changepoint Analysis (2014, methodology): “The changepoint package implements three multiple changepoint algorithms that minimise (2); Binary Segmentation (Edwards and Cavalli-Sforza, 1965), Segment Neighbourhoods (Auger and Lawrence, 1989) and the recently proposed Pruned Exact Linear Time (PELT) (Killick et al., 2012).”
Detecting Changes in Slope With an L0 Penalty (2017, methodology): “There are two ways in which this can be achieved: functional pruning and inequality-based pruning (Killick, Fearnhead, and Eckley 2012; Rigaill 2015; Maidstone et al. 2017).”
Selective review of offline change point detection methods (2020, methodology): “) The algorithm Pelt (for “Pruned Exact Linear Time”) [113] was introduced to find the exact solution of (P2), when the penalty is linear (22).”
A review of change point detection methods (2018, methodology): “Nevertheless, in practice, this method is orders of magnitude faster than the naive heuristics previously described [69, 81].”
ecp: An R Package for Nonparametric Multiple Change Point Analysis of Multivariate Data (2013, methodology): “Although the package only considers the case of independent observations, the theory behind the implemented methods allows for certain types of serial dependence (Killick et al., 2012).”
A robust approach for estimating change-points in the mean of an AR(1) process (2014, positive): “oduced by [2]. The computational complexity of this algorithms is quadratic relatively to the length of the series. Only this algorithm and some of its improvements (such as these proposed by [28] or [15]) provide exactly the optimal change-point location estimators. However, the dynamic programming”
Wild binary segmentation for multiple change-point detection (2014, methodology): “Killick, Fearnhead and Eckley (2012) propose an algorithm, called PELT, that reduces the complexity to O ( T ) but under the assumption of change-points being separated by time intervals drawn independently from a probability distribution, a set-up under which considerations of statistical…”
A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data (2013, methodology): “, 2011), which is based on a generalization of a Wilcoxon/Mann-Whitney (marginal) rank based approach, the parametric Pruned Exact Linear Time (PELT) procedure (Killick et al., 2012), and the nonparametric Kernel Change Point (KCP) procedure (Arlot et al.”
Heterogeneous change point inference (2015, methodology): “and Knott, 1974; Vostrikova, 1981) (if the corresponding single change-point detection method takes the heterogeneous variance into account), but also global methods can achieve this goal, e.g. PELT (Killick et al., 2012). For a Bayesian approach in this context see (Du et al., 2015) and the referen”
Univariate mean change point detection: Penalization, CUSUM and optimality (2018, methodology): “Killick et al. (2012) introduced the pruned exact linear time (PELT) method, which has the worst case computational cost of order O ( n 2 ); while in the situations where the number of change points increases linearly with n , the expected time of PELT is of order O ( n ).”
Is Textual Similarity Invariant under Machine Translation? Evidence Based on the Political Manifesto Corpus (2026, unknown): “For that purpose, we use linearly penalized segmentation ( PELT ) algorithm by Killick et al. [30].”