Source-linked AI summary
Optimal detection of changepoints with a linear computational cost
R. Killick, P. Fearnhead, I. A. Eckley
TL;DR
The paper addresses exact multiple-changepoint detection as datasets grow and changepoints increase. It introduces PELT, an exact pruned search method whose computational cost can be orders of magnitude smaller than alternative exact methods while improving segmentation accuracy.
Problem
Growing datasets can contain increasing numbers of changepoints, making exact search computationally demanding.
Method
PELT adds pruning within a dynamic program to search exactly for the optimal number and locations of changepoints.
Results
PELT can have computational costs orders of magnitude smaller than alternative exact search methods and substantially improve segmentation accuracy compared with Binary Segmentation.
Takeaways & Limitations
PELT provides an exact alternative for multiple-changepoint segmentation when its computational advantages outweigh its relatively small computational costs.
Takeaways & Limitations
Binary Segmentation is not guaranteed to find the optimal number of changepoints, and the study could not compare PELT with PDPA on the change in segmentation accuracy.
Abstract
from arXiv · showhide
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 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.
1. INTRODUCTION
The paper addresses efficient multiple-changepoint search as data sets grow and changepoints increase, introducing PELT as an exact method with potentially linear computational cost. Simulations report major speed advantages over exact alternatives and more accurate segmentations than Binary Segmentation.
- Motivation: Growing data sets create a need for efficient multiple-changepoint detection, especially in genomics and longer financial time-series.The motivating setting is one where the number of changepoints increases with the amount of data.
- Motivation: This setting does not necessarily apply when data are collected at higher frequency over a fixed time period.The paper identifies this as a boundary of its motivating assumption.
- Existing methods: Exact existing methods can be computationally expensive, including O(Qn^2) for Segment Neighbourhoods and O(n^2) for Optimal Partitioning.When the number of changepoints grows linearly with n, Segment Neighbourhoods can have O(n^3) cost.
- Contribution: PELT combines optimal partitioning with pruning to retain exact segmentation while reducing computational cost under mild conditions.The method supports criteria including penalised likelihood, quasi-likelihood, and cumulative sum of squares.
- Results: PELT was orders of magnitude faster than Optimal Partitioning, particularly for long data sets.The simulations compare PELT with both Binary Segmentation and Optimal Partitioning.
- Results: Binary Segmentation was quicker in the reported examples, but PELT produced substantially more accurate segmentations.The paper attributes the accuracy advantage to PELT’s exactness relative to the approximate search method.
2. BACKGROUND
The background formulates changepoint detection as penalised cost minimisation and reviews approximate and exact search methods. It motivates PELT as a pruning-based modification of optimal partitioning that can preserve global optimality while achieving linear cost under conditions.
- Changepoint formulation: Multiple changepoints partition an ordered data sequence at integer locations into segments whose statistical properties may differ.The framework uses m changepoints and m + 1 resulting segments.
- Changepoint formulation: A common detection strategy minimises segment costs plus a penalty that guards against overfitting.The penalty is written as βf(m), with linear penalties βf(m) = βm common in practice.
- Cost functions: PELT is designed for linear cost functions and can also be applied to some alternative penalty choices.The background identifies penalised likelihood, quasi-likelihood, and cumulative-sum-based criteria among relevant cost functions.
- Binary Segmentation: Binary Segmentation iteratively splits segments and has O(n log n) computational cost, but it is not guaranteed to find the global minimum.Its efficiency therefore differs from the exhaustive exact searches reviewed in the section.
- Exact methods: Segment Neighbourhoods exhaustively search segmentations with up to Q changepoints and require O(Qn^2) computation.If Q = O(n), the resulting computational cost is O(n^3).
- PELT: PELT modifies optimal partitioning with pruning, retaining exact minimisation while allowing computational cost to be linear in n under certain conditions.The method’s exact and efficient computation combines optimal partitioning and pruning.
3. A PRUNED EXACT LINEAR TIME METHOD
PELT accelerates exact changepoint detection by pruning candidate changepoints that cannot be optimal later. Under stated stochastic and cost-function conditions, its expected computational cost is linear in the number of observations.
- Pruning: The pruning rule assumes that adding a changepoint reduces segment cost up to a constant K.For minus log-likelihood costs, K = 0; for penalised log-likelihood costs, K equals the penalisation factor.
- Pruning: PELT removes candidate changepoints that cannot be optimal last changepoints for future observations.The pruning condition eliminates computations while preserving the global minimum.
- Computational cost: The linear-cost result assumes IID segment parameters, IID observations within segments, and a stochastic model with IID segment lengths.The analysis uses minus maximum log-likelihood as the segment cost and considers penalties through the pruning condition.
- Computational cost: Under mild conditions, PELT has expected CPU cost bounded above by Ln for some finite constant L.The theorem establishes linear expected computational cost for n data points.
- Computational cost: The expected number of changepoints increases linearly with n under the condition controlling large segment probabilities.The theorem's remaining assumptions include technical controls on the estimation error and penalised likelihood.
- Computational cost: Without pruning, the algorithm's worst-case computational complexity is O(n^2).The linear result therefore depends on pruning occurring under the relevant conditions.
- Concave penalties: PELT can also minimize criteria with concave differentiable penalties by applying an appropriately chosen penalty constant γ.The paper describes an iterative procedure that updates γ using the estimated number of changepoints, though convergence to the optimum is not guaranteed.
4. SIMULATION AND DATA EXAMPLES
The simulations and data examples evaluate PELT's computational cost, fit, and changepoint accuracy against exact and approximate alternatives. PELT is linear when changepoints increase linearly with data size, while exact optimization improves segmentation accuracy over Binary Segmentation.
- Computational cost: PELT has CPU cost linear in n when the number of changepoints increases linearly with n.With slower-growing or fixed changepoint counts, PELT is no longer linear but still achieves substantial savings relative to OP.
- Parameter accuracy: PELT attains improved parameter-estimation accuracy over BS when the number of changepoints increases linearly.The difference is negligible when the number of changepoints is fixed.
- Changepoint accuracy: PELT correctly identifies more changepoints than BS as the data length increases.Qualitatively similar results hold when the distance threshold for classifying a changepoint as correct is changed.
- Wave-height application: In North Atlantic wave-height data, PELT identifies 17 changepoints versus 6 for optimal BS, with similar locations.PELT's segmentation better captures volatility regions, whereas BS misses transitions between 2008 and 2012.
- Model fit: PELT achieves lower MDL than Auto-Parm for 91% of data sets.The average MDL difference increases as the data length increases.
- Computational cost: Segment Neighbourhood takes an order of magnitude longer than PELT, with computational cost increasing cubically with data size.This makes Segment Neighbourhood impracticable for the considered problem.
5. DISCUSSION
The discussion presents PELT as an exact changepoint method that is computationally efficient when changepoint counts increase with data size. Simulations show major speed advantages over alternative exact methods and accuracy gains over Binary Segmentation, while comparisons with PDPA reveal complementary strengths and scope limitations.
- PELT is an exact multiple-changepoint method designed to be computationally efficient and versatile across applications.The authors describe PELT as an alternative exact method and emphasize its broad applicability.
- O(n) computational cost applies when the number of changepoints increases linearly with n, under stated conditions.The paper reports that its assumptions are not restrictive and that a wide class of cost functions can be implemented.
- PELT produces substantial accuracy increases compared with Binary Segmentation, whose faster practical runtime is acknowledged.The authors argue that the statistical benefits of exact segmentation outweigh its relatively small computational costs.
- PDPA complements PELT by supporting nonlinear changepoint penalties and performing best in applications with few changepoints.The methods differ in model restrictions and in the settings where they are computationally efficient.
- The PDPA comparison was limited to a change-in-mean model rather than the change-in-variance or change-in-mean-and-variance models used in the results section.The comparison included both linearly increasing and fixed changepoint scenarios.