Source-linked AI summary
Changepoint Detection in the Presence of Outliers
Paul Fearnhead, Guillem Rigaill
TL;DR
Traditional changepoint methods can confuse outliers with genuine changes, especially under heavy-tailed noise, often motivating preprocessing that is difficult online. The paper combines penalised costs with less outlier-sensitive bounded losses, particularly the biweight loss, and an efficient dynamic-programming algorithm for online use. It reports consistent estimation of changepoint numbers and accurate location estimates, with applications to well-log data, copy number variation, and wireless-device tampering.
Problem
Existing changepoint methods can infer extra changes to fit outliers, while preprocessing them is difficult for online analysis.
Method
The approach replaces L2 loss in penalised changepoint costs with less outlier-sensitive bounded loss functions and solves the resulting optimisation by dynamic programming.
Results
Using biweight loss, the method consistently estimates the number of changepoints and accurately estimates their locations under weak conditions on the noise distribution.
Takeaways & Limitations
The method supports online changepoint analysis and is demonstrated on well-log data, copy number variation, and wireless-device tampering.
Takeaways & Limitations
The approach requires care when the noise violates the IID assumption, where the penalty may need inflation.
Abstract
from arXiv · showhide
Many traditional methods for identifying changepoints can struggle in the presence of outliers, or when the noise is heavy-tailed. Often they will infer additional changepoints in order to fit the outliers. To overcome this problem, data often needs to be pre-processed to remove outliers, though this is difficult for applications where the data needs to be analysed online. We present an approach to changepoint detection that is robust to the presence of outliers. The idea is to adapt existing penalised cost approaches for detecting changes so that they use loss functions that are less sensitive to outliers. We argue that loss functions that are bounded, such as the classical biweight loss, are particularly suitable -- as we show that only bounded loss functions are robust to arbitrarily extreme outliers. We present an efficient dynamic programming algorithm that can find the optimal segmentation under our penalised cost criteria. Importantly, this algorithm can be used in settings where the data needs to be analysed online. We show that we can consistently estimate the number of changepoints, and accurately estimate their locations, using the biweight loss function. We demonstrate the usefulness of our approach for applications such as analysing well-log data, detecting copy number variation, and detecting tampering of wireless devices.
d’Evry Val d’Essonne, UMR CNRS 8071, ENSIIE, USC INRA
The paper concerns robust changepoint detection, including binary segmentation and biweight loss.
- The paper’s keywords include Binary Segmentation, Biweight loss, Cusum, M-estimation, and Penalised likelihood.
1 Introduction
The introduction frames changepoint detection as difficult when outliers can be mistaken for genuine changes. It proposes replacing square-error loss with a robust bounded loss, supported by dynamic programming, theoretical guarantees, and applications across online well-log analysis, copy number variation, and wireless-device tampering.
- Changepoint detection seeks changes in data ordered by time or position, with applications including bioinformatics, climate records, oceanographic data, and finance.
- A central challenge is distinguishing genuine changepoints from outliers, which many existing methods cannot reliably do.Square-error segmentation performs well on cleaned well-log data but cannot distinguish changes from outliers in the real data.
- Gaussian-related assumptions can make changepoint methods seriously over-estimate the number of changes when outliers are present.
- The proposed approach replaces L2 loss with a less outlier-sensitive loss inside a penalised cost method for multiple changepoints.
- Efficient dynamic programming algorithms can solve the penalised-cost minimisation exactly and support sequential online analysis.
- Bounded loss functions are required for robustness to any single arbitrarily extreme outlier, and the paper uses the biweight loss as a simple example.The biweight loss is the pointwise minimum of an L2 loss and a constant.
- Under mild conditions, the biweight penalised-cost approach consistently estimates changepoint numbers and accurately estimates their locations.
- Applications cover online well-log analysis, copy number variation, and wireless-device tampering, including performance against existing and preprocessing-based methods.The approach is reported to outperform existing methods for copy number variation, avoid preprocessing, and distinguish tampering from short-term environmental effects.
2 Model Definition
The paper formulates changepoint detection as minimising a penalised cost over segmentations, using loss functions chosen to detect changes in location while limiting sensitivity to outliers. It develops conditions under which bounded losses, especially the biweight loss, yield robust and consistent inference.
- A segmentation partitions ordered observations into k + 1 segments determined by changepoints τ1:k, with τ0 = 0 and τk+1 = n.
- Changepoint detection estimates both the number and locations of abrupt changes in a location parameter such as the mean, median, or another quantile.
- The penalised cost minimises within-segment loss over segment-specific parameters and adds a penalty β for each introduced changepoint.
- Squared-error loss is highly sensitive to outliers and can fail to distinguish isolated outliers from genuine changes, motivating slower-growing or bounded losses.
- For bounded losses satisfying 0 ≤ γ(y; θ) ≤ K, every inferred segment has length greater than β/K, so segments shorter than this threshold may be treated as outliers.
- With biweight loss and a penalty βn satisfying βn > C1 log(n) and βn = o(n), the estimated changepoint number is consistent and location errors are bounded by C2 log(n) with probability tending to one.
3 Minimising the Penalised Cost
R-FPOP minimizes the penalized segmentation cost exactly by recursively representing parameter-dependent costs as piecewise quadratics over intervals. It then recovers the optimal changepoints by storing interval-specific solutions and backtracking.
- Algorithm: R-FPOP extends pruned dynamic programming and FPOP to robust loss functions for exact penalized-cost minimization.The algorithm is designed to minimize the segmentation criterion over all possible segmentations.
- Dynamic programming recursion: At each time t, the recursion considers segmentations ending at t with or without a changepoint at t−1.The resulting update depends on the previous cost function Qt−1(θ), its minimum Qt−1, and the new observation loss γ(y_t; θ).
- Piecewise-quadratic representation: Because the loss is piecewise quadratic and piecewise quadratics are closed under addition and minimization, Qt(θ) remains piecewise quadratic.The representation uses intervals with associated quadratics, including linear and constant special cases.
- Piecewise-quadratic representation: Each iteration minimizes competing quadratic functions on intervals, splits intervals at solution changes or loss breakpoints, and merges adjacent equivalent intervals.The new observation loss is then added to form the next interval-quadratic representation.
- Recovering the segmentation: After processing all observations, R-FPOP extracts the optimal segmentation by backtracking through stored most-recent-changepoint values.Figure 3 illustrates one iteration, including pointwise minimization, interval splitting, merging, and addition of the new loss.
4 Computational Cost of R-FPOP
R-FPOP has complexity bounds that depend on the loss geometry. Convex piecewise losses admit lower worst-case bounds, while the nonconvex biweight loss has quadratic space and cubic time worst-case complexity.
- Convex losses: For convex losses defined in L pieces, R-FPOP stores at most 2t − 1 + t(L − 1) quadratics and intervals at step t.This bound applies to the convex case, which excludes the biweight loss considered separately.
- Convex losses: For convex piecewise losses, R-FPOP has O(n) space complexity and O(n^2) time complexity.These are the resulting overall complexity bounds from the per-step storage bound.
- Biweight loss: For the biweight loss, R-FPOP stores O(t^2) intervals at step t.The biweight loss is nonconvex, producing worse bounds than the convex case.
- Biweight loss: For the biweight loss, R-FPOP has worst-case space complexity O(n^2) and time complexity O(n^3).These are worst-case bounds on storage and computation.
- Empirical cost: Empirically, average computational cost is linear in n when the number of changepoints is large and less than quadratic when there are no changepoints.The empirical behavior is better than the biweight worst-case bounds in the investigated settings.
5 Results
The experiments evaluate runtime, accuracy under heavy-tailed noise, and applications to well-log, copy-number, and wireless-tampering data. The biweight loss generally improves robustness to outliers, while performance depends on the segmentation scenario and loss choice.
- Computational cost: For profiles of length n = 10^6 without true changes, biweight runtime is around 4 seconds, slightly larger than FPOP using L2 loss.The comparison was conducted on a standard laptop and concerns the reported runtime experiment.
- Computational cost: With many changepoints, average CPU cost of all penalized-cost approaches increases linearly with the number of data points.With no changepoints, cost increases faster, but remains less than quadratic; L1 and Huber are particularly slower.
- Simulation study: For almost all scenarios with small degrees of freedom, the biweight loss gives the best mean square error and loses little accuracy near Gaussian noise.The robust cusum method also performs well for small degrees of freedom but often drops relative to alternatives near Gaussian noise.
- Simulation study: Biweight performs poorly in one near-Gaussian scenario with very short segments and repeated segment means because distinguishing changes from outliers is difficult.The stated problem concerns segments only slightly longer than the biweight loss's minimum segment length.
- Simulation study: For segmentation quality, biweight is clearly best in scenarios 1 and 2, whereas Huber appears best across scenarios and biweight performs poorly in scenario 3.The L2 approaches perform poorly when the noise has few degrees of freedom.
- Applications: In well-log data with substantial outliers, the biweight penalty detects all obvious changes without detecting changes at outlier locations.The online analysis quickly detects changes, with reported detection lags between 21 and 27 observations in the relevant case.
- Applications: Across copy-number-variation cases, the robust biweight loss outperforms L2 after outlier removal and the robust Cusum approach.The reported advantage is slight in some low-tumor-fraction cases and clearer in others.
6 Discussion
The discussion presents a penalised-cost changepoint algorithm using bounded loss, particularly the biweight loss, to remain robust to extreme outliers. It reports consistent changepoint-number estimation and accurate location estimation, while identifying tuning and noise-dependence caveats.
- The proposed algorithm detects changepoints by minimising a penalised cost and gains robustness to extreme outliers.
- Bounded loss functions enable robustness to arbitrarily large outliers, motivating the recommended use of the biweight loss.
- The biweight loss can also yield accurate changepoint locations under weak conditions on the noise distribution.
- Choosing K around 2 to 3 times the noise standard deviation makes the biweight loss perform similarly to square-error loss for most observations.
- Using biweight loss with a C1 log(n) changepoint penalty can consistently estimate the number of changepoints.
- Consistency is not guaranteed when constants similar to square-error choices are used, so strengthened penalties or penalty-range exploration may be needed.
Appendix A Proof of Theorem 2.3
The appendix establishes properties of the biweight loss and sets up the consistency proof. It states that the estimator recovers the changepoint count asymptotically and estimates locations within a logarithmic accuracy bound.
- The biweight loss is bounded by 0 ≤ γ(y) ≤ K2 and satisfies a Lipschitz property.
- The consistency result states that the estimated number of changepoints is asymptotically correct and each location is estimated within a specified accuracy.
- The proof uses preliminary bounds controlling cost reductions from extra changepoints and cost increases when true changepoints are missed.
- The asymptotic analysis allows the penalty for adding a changepoint, βn, to depend on n.
Proof of Theorem 2.3
The proof compares penalised costs of candidate segmentations with the true segmentation to rule out bad segmentations. It relies on bounded-loss cost control and the fact that adding changepoints cannot increase unpenalised cost.
- The proof partitions bad segmentations into cases and shows their probability goes to 0 as n increases.
- Candidate segmentations are compared with the true segmentation or with adaptations that add one or more true changepoints.
- The correct segmentation’s unpenalised cost is upper-bounded by fixing each segment parameter at its true value.
- Adding changepoints cannot increase the unpenalised cost, a fact repeatedly used in the proof.
Appendix B Proofs from Section 2
The appendix proves consistency by separately excluding overestimation, underestimation, and inaccurate locations. The resulting bounds show that the estimated changepoint count converges to the true count and locations achieve logarithmic accuracy.
- Overestimation: If βn > C1 log(n), the probability of overestimating the true changepoint count tends to 0 as n →∞.
- Underestimation: If βn = o(n), the probability of underestimating the changepoint count tends to 0 as n →∞.
- Changepoint count: Together, the first two proof parts imply Pr(ˆkn = k0) →1.
- Location accuracy: A segmentation with k0 changepoints is disfavoured when at least one estimated location has error greater than C2 log(n).
- Proof bounds: The proof bounds lower-tail probabilities using the bounded and Lipschitz properties of the loss, including discretisation over parameter intervals.
Appendix C Proofs from Section 4
The proofs bound R-FPOP’s interval counts and show that its operations require quadratic total complexity. These bounds follow from convex loss structure and the number of interval breakpoints.
- General piecewise losses: For piecewise loss functions with L intervals, each term contributes L − 1 internal breakpoints, whose total distribution across disjoint intervals controls the interval count.The proof defines N_k as the number of breakpoints inside interval I_k and uses disjointness to bound their sum.
- Complexity bounds: R-FPOP processes O(t) intervals at step t, so each iteration costs O(t) and the total complexity is quadratic.Operations on each interval cost O(1), while roots, fusions, updates, and minima are all handled in O(t) time per step.
- Interval structure: The biweight loss creates at most 2t + 1 intervals separated by its nondifferentiability points y_i − K and y_i + K.These breakpoints partition the parameter space into intervals used by R-FPOP.
- Interval structure: On each loss-defined interval, R-FPOP needs at most 2t − 1 intervals to describe Q_t(θ), yielding a quadratic bound after summing across intervals.The proof associates interval descriptions with a single best time of the most recent changepoint.
- General piecewise losses: The corresponding space and time proofs replace the O(n) interval bound with an O(n^2) bound when required by the loss structure.The corollary explicitly derives its complexity by substituting the larger interval bound.
Appendix D Pseudo Code for R-FPOP
The pseudo-code organizes R-FPOP around interval-based dynamic programming. It updates the cost function, recovers the best changepoint, compares against a penalized constant, and outputs the recorded changepoints.
- Sub-routines: R-FPOP manipulates piecewise functions through three sub-routines: updating Q_t, recovering its minimum and best change, and constructing Q*_{t+1}.These sub-routines provide the algorithm’s core interval operations.
- Algorithm inputs: R-FPOP takes data y_1:n, a data-and-mean fit measure γ, and a penalty β independent of changepoint number or location.These are the algorithm’s stated inputs.
- Main procedure: The main algorithm computes Q_t and its minimizer, compares Q_t(θ) with Q_t + β, and outputs the changepoints stored in cp(n).The pseudo-code identifies these operations as the main control flow.
- Implementation flow: The algorithm initializes the interval representation, creates new intervals, and applies minimum-recovery and comparison routines at each update.The pseudo-code includes explicit interval initialization and sub-routine calls.
- Sub-routines: The comparison sub-routine sorts roots, partitions the parameter domain into intervals, and assigns either a constant or Q_t(θ) on each interval.The pseudo-code records the associated candidate changepoint for each resulting interval.