Source-linked AI summary
On Optimal Multiple Changepoint Algorithms for Large Data
Robert Maidstone, Toby Hocking, Guillem Rigaill, Paul Fearnhead
TL;DR
Exact dynamic programming methods for changepoint detection can be computationally expensive on large time series, while faster approaches may not guarantee an optimal segmentation. This paper extends pruning methods and introduces FPOP and SNIP; empirical results show FPOP is efficient, robust to the number of changepoints, and competitive with Binary Segmentation.
Problem
Large time-series changepoint detection requires methods that account for multiple abrupt structural changes while addressing the computational cost of exact dynamic programming.
Method
The paper extends pruning methods for dynamic programming and introduces two changepoint algorithms, FPOP and SNIP.
Results
FPOP’s computational speed was robust to changes in the number of changepoints and was competitive with, and sometimes faster than, Binary Segmentation.
Takeaways & Limitations
FPOP provides an efficient option for large-data changepoint detection while retaining the dynamic-programming pruning framework.
Takeaways & Limitations
SNIP requires a stronger condition on the cost functions, and its implementation is currently restricted.
Abstract
from arXiv · showhide
There is an increasing need for algorithms that can accurately detect changepoints in long time-series, or equivalent, data. Many common approaches to detecting changepoints, for example based on penalised likelihood or minimum description length, can be formulated in terms of minimising a cost over segmentations. Dynamic programming methods exist to solve this minimisation problem exactly, but these tend to scale at least quadratically in the length of the time-series. Algorithms, such as Binary Segmentation, exist that have a computational cost that is close to linear in the length of the time-series, but these are not guaranteed to find the optimal segmentation. Recently pruning ideas have been suggested that can speed up the dynamic programming algorithms, whilst still being guaranteed to find true minimum of the cost function. Here we extend these pruning methods, and introduce two new algorithms for segmenting data, FPOP and SNIP. Empirical results show that FPOP is substantially faster than existing dynamic programming methods, and unlike the existing methods its computational efficiency is robust to the number of changepoints in the data. We evaluate the method at detecting Copy Number Variations and observe that FPOP has a computational cost that is competitive with that of Binary Segmentation.
1 Introduction
Changepoint detection can be posed as an exact segmentation-cost minimisation problem, but conventional dynamic programming is costly for large datasets. The paper develops FPOP and SNIP by combining pruning ideas to retain optimality while improving computational efficiency.
- Multiple abrupt structural changes in time-series and equivalent data motivate detecting both changepoint number and locations.
- Penalised and constrained changepoint problems formulate segmentation as minimising a cost, with dynamic programming providing exact solutions when costs are additive across segments.
- Dynamic programming costs increase at least quadratically with data size, creating a major challenge for increasingly large datasets.
- Binary Segmentation is roughly linear but approximate, and can estimate changepoint numbers and positions poorly.
- PELT and pDPA are exact pruning algorithms with different strengths: PELT is most efficient with many changepoints, whereas pDPA performs better when there are fewer.
- The paper introduces FPOP and SNIP, combining functional and inequality-based pruning, and reports FPOP as robust to changepoint count and competitive with Binary Segmentation.
2 Model Definition
The paper defines changepoint detection through segment costs and optimisation over segmentations. It distinguishes constrained and penalised formulations and specifies cost conditions enabling pruning methods.
- The statistical task is to infer the number and locations of changepoints in ordered data.
- A segmentation cost is formed by summing segment-specific costs, which may be based on minus maximum log-likelihood under a segment model.
- The constrained formulation minimises cost for a fixed changepoint count, while the penalised formulation adds a penalty and can estimate the count directly.
- Dynamic programming solves both formulations exactly through Segment Neighbourhood Search and Optimal Partitioning.
- Pruning requires one of two segment-cost conditions: C1 supports functional pruning, while C2 supports inequality-based pruning and is weaker than C1.
- For many practical cost functions, including negative log-likelihood costs, the pruning conditions hold.
3 Solving the Penalised Optimisation Problem
The penalised problem is solved by Optimal Partitioning, which recursively optimises the last changepoint but has O(n^2) cost without pruning. PELT reduces candidates through inequality-based pruning while preserving exactness.
- Optimal Partitioning recursively splits the penalised segmentation problem at the last changepoint and recovers optimal changepoints from minimising arguments.
- The basic Optimal Partitioning computation takes O(n^2) time because each time step minimises over all earlier candidate changepoints.
- PELT is at least as efficient as Optimal Partitioning, with cost bounded above by O(n^2), and under conditions expected cost bounded by Ln.
- PELT limits the set of potential previous changepoints using inequality-based pruning, eliminating candidates that cannot be optimal at future times.
- PELT updates its retained candidate set by applying an inequality involving prior optimal costs, segment costs, and κ.
- The expected linear-time bound requires conditions including an expected changepoint count that increases linearly with data length.
4 Solving the Constrained Optimisation Problem
The constrained optimisation problem finds minimum-cost segmentations for specified changepoint counts using dynamic programming. Segment Neighbourhood Search is exact but can require O(Kn^2) computation, motivating pruning through functional representations.
- Segment Neighbourhood Search: Segment Neighbourhood Search solves the constrained problem for all changepoint counts up to K using dynamic programming.It recursively computes the minimum cost for each number of segments and time point, then recovers changepoint locations recursively.
- Computational cost: O(n^2) calculations are required for each fixed changepoint count because every time point evaluates all earlier candidate locations.Repeating this for k = 1, ..., K increases the total computational cost with K.
- Pruned Segment Neighbourhood Search: pDPA accelerates Segment Neighbourhood Search by representing cost functions over scalar segment parameters and pruning candidates that are never optimal.For a change in mean with least-squares cost, candidate functions can be partitioned into parameter intervals and updated recursively.
- Pruned Segment Neighbourhood Search: At each update, pDPA adds a new candidate function, updates existing functions, and removes functions that are not optimal for any parameter value.In the illustrated example, the candidate at τ = 43 is pruned after the new candidate is added.
- Pruned Segment Neighbourhood Search: pDPA has a worst-case time bound of O(Kn^2), while empirical analysis reports O(Kn log n).The method nevertheless incurs computational overhead and has mainly been implemented for scalar parameters and exponential-family log-likelihood costs.
5 New Changepoint Algorithms
The paper introduces FPOP and SNIP by combining functional and inequality-based pruning with the two principal dynamic programming formulations. FPOP applies functional pruning to Optimal Partitioning, while SNIP applies inequality pruning to Segment Neighbourhood Search.
- New algorithms: The paper extends pruning in two directions: functional pruning for Optimal Partitioning and inequality pruning for Segment Neighbourhood Search.These extensions produce Functional Pruning Optimal Partitioning (FPOP) and Segment Neighbourhood with Inequality Pruning (SNIP).
- Functional Pruning Optimal Partitioning: FPOP recursively updates cost functions conditional on the last segment parameter and minimizes over parameter values to solve the penalised problem.Potential last changepoints are retained only when their associated parameter sets are non-empty.
- Functional Pruning Optimal Partitioning: FPOP prunes candidate functions that are no longer optimal for any parameter value after each new time point is incorporated.The candidate set is updated by restricting recursions to surviving potential last changepoints.
- Segment Neighbourhood with Inequality Pruning: SNIP applies inequality-based pruning to Segment Neighbourhood Search and removes candidate last changepoints that cannot be optimal at future times.Its pruning rule is justified under condition C2 and updates the reduced candidate set recursively.
- Segment Neighbourhood with Inequality Pruning: SNIP returns minimum-fit segmentations and changepoint locations for all k = 0, ..., K under its constrained formulation.The algorithm uses a maximum changepoint count K, a fit measure, and a constant κ satisfying the stated cost condition.
6 Comparisons Between Pruning Methods
The comparisons show that functional pruning generally removes candidates more aggressively than inequality-based pruning. The methods differ in assumptions, computational overhead, and behavior as the number of changepoints varies.
- Assumptions and limitations: Inequality-based pruning requires condition C2, while functional pruning requires the stronger condition C1.Both methods depend on assumptions about the segment cost function.
- Assumptions and limitations: Inequality-based pruning has substantial computational overhead and is currently feasible only for detecting changes in a univariate parameter.These constraints limit the settings in which the method can be applied.
- Penalised optimisation: PELT prunes very rarely, whereas FPOP prunes more frequently and keeps its candidate set small throughout the illustrated analysis.Figure 4 compares the number of stored candidate changepoints over time for the two methods.
- Constrained optimisation: pDPA prunes continuously in the constrained problem, while SNIP prunes sporadically and prunes little for low values of k.The comparison concerns candidate counts stored over time under the constrained formulation.
- Pruning comparison: Functional pruning keeps fewer candidates than inequality-based pruning in the penalised and constrained optimisation problems.The paper states that every candidate pruned by inequality-based pruning is also pruned by functional pruning at the same time step.
7 Empirical evaluation of FPOP
The evaluation compares FPOP with exact dynamic-programming methods and Binary Segmentation on synthetic and microarray data. FPOP is generally faster than PELT and pDPA, remains efficient as changepoints increase, and matches PELT's segmentation accuracy on the neuroblastoma benchmark.
- Experimental setup: FPOP was implemented for quadratic loss and evaluated against PELT, pDPA, and Binary Segmentation on synthetic and real microarray data.The evaluation used C++ implementations and included 4467 segmentation problems from tumour microarrays.
- Microarray benchmark: FPOP is generally faster than PELT and pDPA on the tumour microarray benchmark, but about two times slower than Binary Segmentation.The benchmark covered profiles ranging from 25 to 153662 data points.
- Microarray benchmark: For small profiles, microbenchmarking confirmed that FPOP is faster than PELT and about as fast as Binary Segmentation.The authors used a separate microbenchmark because system.time is inaccurate for very small runtimes.
- Simulated speed benchmark: FPOP's computational efficiency is intended to remain effective across the range of maximum changepoint counts K, unlike methods whose runtime depends more strongly on K or the underlying number of changes.The expected fixed-size runtime dependence is O(log K) for Binary Segmentation and O(K) for pDPA; PELT is expected to benefit from more changepoints.
- Simulated speed benchmark: FPOP is always faster than pDPA and PELT in simulations, and becomes faster than Binary Segmentation when the true number of changepoints exceeds 500.This pattern was observed for signals with n = 2 × 10^5 and n = 10^7.
- Accuracy benchmark: FPOP obtains the same segmentation error rate as PELT on the neuroblastoma benchmark and achieves 2.2% test error.The reported 2.2% test error was the smallest among tested algorithms.
8 Discussion
The discussion frames algorithm choice around the optimisation formulation and pruning strategy, balancing segmentation coverage, computational efficiency, and applicability. FPOP is preferred where functional pruning applies, while its speed remains competitive with Binary Segmentation.
- Choosing the optimisation problem: The paper introduces FPOP and SNIP to combine the two optimisation formulations with functional and inequality-based pruning.FPOP solves the penalised problem with functional pruning, while SNIP solves the constrained problem with inequality-based pruning.
- Choosing the optimisation problem: Constrained optimisation provides optimal segmentations for a range of changepoint counts, whereas penalised optimisation is faster when its penalty is known.The constrained approach is particularly useful for interactive exploration, while penalised optimisation suits non-interactive settings with a known penalty parameter.
- Choosing the pruning method: Functional pruning always prunes more than inequality-based pruning, with the difference potentially large when few changepoints are present.The authors recommend functional pruning where applicable because its greater pruning can improve computational efficiency.
- Choosing the pruning method: Functional pruning has narrower applicability because it requires a stronger cost-function condition and is implemented for univariate exponential-family parameters.Even when applicable, it has higher computational overhead per non-pruned candidate.
- Empirical comparison: FPOP was always faster than PELT for detecting a change in mean, with especially large speed differences when few changepoints were present.Its computational speed was robust to the number of changepoints and was competitive with, and sometimes faster than, Binary Segmentation.