Source-linked AI summary
A computationally efficient nonparametric approach for changepoint detection
Kaylea Haynes, Paul Fearnhead, Idris A. Eckley
TL;DR
The paper addresses limited nonparametric multiple-changepoint literature and seeks a computationally efficient search approach. It develops NP-PELT and shows that it is orders of magnitude faster than NMCD, while screening can adversely affect accuracy and penalty choices motivate comparing solutions across a range.
Problem
Nonparametric multiple-changepoint detection has less literature than the extensive, often parametric, single-changepoint literature.
Method
The paper develops NP-PELT, extending the approach proposed by Zou et al. (2014) for computationally efficient multiple-changepoint search.
Results
NP-PELT is orders of magnitude faster than NMCD, while the screening approach is reported as less accurate.
Takeaways & Limitations
Comparing solutions over a range of penalty values is advantageous because individual penalty choices do not always work well.
Takeaways & Limitations
The screening step can adversely affect the accuracy of the final changepoint detection method.
Abstract
from arXiv · showhide
In this paper we build on an approach proposed by Zou et al. (2014) for nonpara- metric changepoint detection. This approach defines the best segmentation for a data set as the one which minimises a penalised cost function, with the cost function defined in term of minus a non-parametric log-likelihood for data within each segment. Min- imising this cost function is possible using dynamic programming, but their algorithm had a computational cost that is cubic in the length of the data set. To speed up computation, Zou et al. (2014) resorted to a screening procedure which means that the estimated segmentation is no longer guaranteed to be the global minimum of the cost function. We show that the screening procedure adversely affects the accuracy of the changepoint detection method, and show how a faster dynamic programming algorithm, Pruned Exact Linear Time, PELT (Killick et al., 2012), can be used to find the optimal segmentation with a computational cost that can be close to linear in the amount of data. PELT requires a penalty to avoid under/over-fitting the model which can have a detrimental effect on the quality of the detected changepoints. To overcome this issue we use a relatively new method, Changepoints Over a Range of PenaltieS (CROPS) (Haynes et al., 2015), which finds all of the optimal segmentations for multiple penalty values over a continuous range. We apply our method to detect changes in heart rate during physical activity.
1 Introduction
The paper addresses computationally expensive nonparametric multiple-changepoint detection by combining a faster segment-cost calculation with PELT and CROPS. It shows that this approach avoids the accuracy loss of screening while supporting efficient segmentation and heart-rate analysis.
- Motivation: Nonparametric multiple-changepoint methods are less developed than single-changepoint methods, which do not extend easily to multiple changes.Existing approaches include recursive testing, clustering, and approximate or exact search procedures.
- Motivation: O(Mn^2 + n^3) computation makes exact nonparametric segmentation infeasible for large data sets, especially when changepoints increase with n.Zou et al.'s screening step reduces computation but can adversely affect final changepoint accuracy.
- Method: The proposed NP-PELT simplifies segment-cost computation from O(n) to O(log n) and uses PELT instead of Segment Neighbourhood Search.For situations where the number of changepoints increases linearly with n, PELT has been proven to have computational cost linear in n.
- Method: NP-PELT requires a penalty value, and segmentation quality can be sensitive to that choice because default penalties do not always work well.CROPS is used with NP-PELT to explore optimal segmentations across a range of penalties.
- Evaluation: Simulation studies compare NP-PELT with NMCD, examine different scenarios, and apply the nonparametric method to heart-rate data from a running individual.The paper also considers settings where the underlying data distribution is unknown.
- Contribution: NP-PELT is presented as a substantially more computationally efficient nonparametric search approach for multiple changepoints.The paper's application illustrates its use for segmenting activity-related heart-rate data.
2 Nonparametric Changepoint Detection
The paper formulates nonparametric changepoint detection by penalising a segmentation cost based on empirical-CDF likelihoods. Existing exact optimisation is computationally expensive, while screening reduces computation but can remove true changepoints and lose optimality.
- 2.1 Model: The model partitions ordered data x1, ..., xn into m + 1 contiguous segments defined by integer changepoint locations.Segment i contains x_(τi−1+1):τi, with 0 = τ0 < τ1 < ... < τm < τm+1 = n.
- 2.2 Nonparametric maximum likelihood: Each segment cost is minus the maximised binomial-form log-likelihood of its empirical CDF, evaluated across threshold values t.For segment i, the cost uses its length multiplied by the empirical-CDF log-likelihood expression.
- 2.3 Nonparametric multiple changepoint detection: Integrating the single-threshold cost over t addresses the problem that choosing one CDF evaluation point can adversely affect the resulting segmentation.The full-data empirical CDF approximates the weighting distribution, and the integral is further approximated by a sum over data points.
- 2.3 Nonparametric multiple changepoint detection: For a fixed number of changepoints, dynamic programming finds the optimal segmentation, while a penalty selects the number of changepoints in practice.The penalty is based on the Schwarz Information criterion and uses a sequence ξn tending to infinity.
- 2.4 NMCD Algorithm: Exact Segment Neighbourhood Search costs O(Mn^2 + n^3) because all segment costs require O(n^3) preprocessing.M is the maximum number of changepoints searched, and each individual segment cost requires O(n) computation.
- 2.4 NMCD Algorithm: Zou et al.’s screening procedure substantially reduces candidate locations, but larger windows can remove true changepoints and require the detectable segment length to exceed the window scale.The procedure compares Cramér-von Mises statistics in overlapping windows and retains local candidate maxima.
3 NP-PELT
The paper develops NP-PELT by combining a faster approximation to the nonparametric segment cost with PELT’s pruning-based dynamic programming. Under stated conditions, this preserves optimal segmentation while reducing expected computation to linear order.
- 3 NP-PELT: NP-PELT combines an efficient approximation of the integrated nonparametric cost with the PELT dynamic programming algorithm.The approximation uses selected empirical quantiles, while PELT minimises the resulting penalised cost.
- 3.1 Improved Segment Cost: The integral approximation uses equally weighted terms whose empirical-quantile locations preferentially sample distribution tails, retaining the original tail weighting.The number of terms is K, and the approximation cost is O(K).
- 3.1 Improved Segment Cost: Choosing K = ⌈c/γ⌉ for fixed γ makes segment-cost computation O(log n), and the choice of K is investigated empirically.Here c is defined in Lemma 3.1, and the approximation uses K evenly spaced transformed x-values.
- 3.2 Use of PELT: PELT recursively minimises the penalised segmentation cost over the most recent changepoint location, jointly selecting changepoint number and positions.The recursion requires a prior penalty ξn for adding a changepoint.
- 3.2 Use of PELT: PELT prunes a candidate u when its current cost relation implies that u cannot be the optimal last changepoint at any future time.The pruning rule reduces the set of candidate previous locations considered at later times.
- 3.2 Use of PELT: Under regularity conditions and linearly increasing changepoint counts, NP-PELT has expected computational cost O(n).The result follows because substantial pruning occurs in this regime.
4 Results
The results show that screening substantially reduces computation but can reduce changepoint accuracy, whereas NP-PELT and its quantile-based variant provide faster alternatives with comparable accuracy to NMCD.
- 4.1 Performance of NMCD: NMCD+ significantly reduces computational cost, but detects fewer true positives and more false positives than unscreened NMCD across the tested cases.The screening step therefore sacrifices accuracy for speed and can prevent recovery of the true segmentation.
- 4.1 Performance of NMCD: NMCD+ usually matches NMCD while running faster, but a substantial fraction of data sets still receive nonoptimal and less accurate segmentations.This pattern persists across screening-window choices, with similar results found for the other simulation models.
- 4.2 Comparison to NMCD: NP-PELT runs at least 60 times faster than NMCD but remains an order of magnitude slower than NMCD+.The comparison uses the same segment costs, while raw timings favor NMCD because its implementation is in FORTRAN and NP-PELT is implemented in R.
- 4.2 Comparison to NMCD: With K = 4 log(n), NP-PELT+ has accuracy comparable to NMCD and is significantly faster, though it is slightly slower than NMCD+ in Models 2 and 3.The authors attribute the latter comparison to PELT tending to have lower cost when there are more changepoints, whereas Models 2 and 3 contain fewer changepoints.
5 Activity Tracking
The paper applies NP-PELT+ to raw heart-rate data, using CROPS and elbow-based selection to identify segmentations that correspond to phases and terrain-related changes during a run.
- 5 Activity Tracking: NP-PELT+ detects changes in raw heart-rate series without initially preprocessing the data, addressing the non-IID nature of heart-rate measurements.The method is intended for data recorded by commercially available devices.
- 5 Range of Penalties: CROPS finds optimal segmentations across a continuous penalty range, requiring at most mmin − mmax + 2 NP-PELT runs and allowing calculation reuse.This avoids committing to a single penalty value when different penalties yield different changepoint counts.
- 5.2.1 Nonparametric Changepoint Detection: The 10-changepoint segmentation separates the run into heart-rate zones including peak, anaerobic, aerobic, and recovery phases.Segments are colour coded by average heart rate: red for peak, orange for anaerobic, yellow for aerobic, and green for recovery.
- 5.2.1 Nonparametric Changepoint Detection: Several detected changepoints align with changes in speed and elevation, including a speed dip around 75 minutes and a sprint finish involving increased speed and elevation.The authors interpret these alignments as evidence that the segmentation reflects different phases of the run.
- 5.2.1 Nonparametric Changepoint Detection: Compared with a piecewise-linear normal-model change-in-slope method, NP-PELT+ produces segments that better correspond to differing heart-rate phases and elevation changes.The comparison method does not detect changes associated with elevation and misses segments whose average heart rate differs from surrounding segments.
6 Conclusion
The paper develops NP-PELT for nonparametric changepoint detection, combining faster segment-cost calculation with exact dynamic programming. It reports that NP-PELT is substantially faster than NMCD, more accurate than its screened variant, and useful for segmenting heart-rate activity data into meaningful regimes.
- NP-PELT detects changes without assuming the underlying data distribution and is adapted from the NMCD method.
- Reducing segment-cost computation from O(n) to O(log n) makes NP-PELT orders of magnitude faster than NMCD.
- Although screening is slightly faster, the screened method is less accurate than NP-PELT.
- NP-PELT segments run heart-rate data into meaningful segments corresponding to different phases and regimes of heart-rate activity.
SUPPLEMENTARY MATERIAL
The supplementary figures show segmentations produced by NP-PELT+ and change-in-slope methods across different numbers of changepoints. Segment colors encode average heart-rate phases, while the change-in-slope plots also show fitted segment means.
- NP-PELT+ segmentations are shown with 13, 12, and 9 changepoints, using colors for peak, anaerobic, aerobic, and recovery phases.
- Change-in-slope segmentations are shown with 12, 10, 8, and 7 changepoints, using the same heart-rate phase colors.
- The change-in-slope figures additionally display a solid black line representing the best fit for the mean within each segment.