PaperlayerView exact revision on arXiv

Source-linked AI summary

Wild binary segmentation for multiple change-point detection

Piotr Fryzlewicz

arXiv:1411.0858v1math.ST

TL;DR

Multiple change-point detection must estimate unknown change counts and locations while existing procedures can be computationally expensive or fail under difficult configurations. The paper introduces WBS, which uses randomised interval-based CUSUM localisation with recursive segmentation, and reports consistency, fast computation, and improved performance over standard binary segmentation, including for short spacings and increasing change-point counts.

  • Problem

    The paper addresses estimation of unknown change-point counts and locations in piecewise-constant signals, where existing approaches can be computationally expensive or binary segmentation can be unsuitable for some configurations.

  • Method

    WBS randomly samples intervals, computes CUSUM statistics, selects the largest maximiser, and recursively applies the procedure to segments on either side.

  • Results

    WBS is computationally fast, consistent, easy to code, and provably better than binary segmentation for very short spacings and increasing numbers of change-points.

  • Takeaways & Limitations

    WBS offers a practical multiple change-point procedure that avoids span or window selection while retaining binary segmentation’s main strengths.

  • Takeaways & Limitations

    The paper studies a univariate model with a deterministic one-dimensional piecewise-constant signal, so it does not cover many multivariate segmentation settings directly.

Abstract

from arXiv · show

We propose a new technique, called wild binary segmentation (WBS), for consistent estimation of the number and locations of multiple change-points in data. We assume that the number of change-points can increase to infinity with the sample size. Due to a certain random localisation mechanism, WBS works even for very short spacings between the change-points and/or very small jump magnitudes, unlike standard binary segmentation. On the other hand, despite its use of localisation, WBS does not require the choice of a window or span parameter, and does not lead to a significant increase in computational complexity. WBS is also easy to code. We propose two stopping criteria for WBS: one based on thresholding and the other based on what we term the `strengthened Schwarz information criterion'. We provide default recommended values of the parameters of the procedure and show that it offers very good practical performance in comparison with the state of the art. The WBS methodology is implemented in the R package wbs, available on CRAN. In addition, we provide a new proof of consistency of binary segmentation with improved rates of convergence, as well as a corresponding result for WBS.

1. Introduction.

Multiple change-point detection seeks the number and locations of changes in piecewise-stationary data, but existing approaches face computational or statistical limitations. The paper proposes WBS, which randomises CUSUM localisation to retain binary segmentation’s simplicity while addressing weaknesses of global searches.

  • Motivation: Multiple change-point detection estimates the number and locations of changes in time-evolving quantities whose parameters are piecewise constant.Such segmentation can support flexible modelling and exploratory analysis.
  • Existing methods: Multivariate optimisation methods such as penalised least squares or likelihood fits typically require O(T^2) computation, creating difficulties for large datasets.Alternative linear-time methods rely on assumptions that can preclude statistical consistency.
  • Existing methods: Binary segmentation is simple, easy to code, and typically has computational complexity O(T log T), but its sequential greedy searches may fail when multiple changes occur in certain configurations.Each stage searches for one change-point and never revisits earlier decisions.
  • Wild binary segmentation: WBS randomly draws subintervals, computes a CUSUM statistic on each, selects the largest maximiser, and recursively searches the resulting left and right segments.Random intervals may isolate a single change-point away from the interval boundaries, improving localisation.
  • Wild binary segmentation: By randomising localisation and using intervals of different lengths, WBS addresses global-CUSUM weaknesses, reduces required spacing and jump-size conditions, and avoids span selection.The procedure is intended to preserve binary segmentation’s main strengths without substantial additional computational complexity.
  • Contributions: WBS is presented as computationally fast, consistent, easy to code, and provably better than binary segmentation for short spacings and increasing numbers of change-points.An implementation is available in the R package wbs on CRAN.

2. Motivation.

The motivation contrasts standard binary segmentation's global search with a localized random-interval strategy designed to reveal change-points that can cancel under global aggregation. WBS randomly samples intervals, maximizing a CUSUM statistic on each, so favorable intervals can isolate individual changes without exhaustively testing all endpoints.

  • Binary segmentation: Binary segmentation recursively searches the full interval and then splits at the largest CUSUM candidate deemed significant.The procedure starts on [1,T], then recursively searches the left and right subintervals created by each accepted candidate.
  • CUSUM interpretation: The absolute CUSUM maximizer on an interval is equivalent to the least-squares one-change-point estimator, and under Gaussian noise also to the maximum-likelihood estimator.For a single true change-point, this explains why the first BS estimate can perform well.
  • Binary segmentation: When multiple change-points are present, the first global BS step fits a one-change-point model to data generated by several changes.This model mismatch can make the global maximum miss every true change-point.
  • Failure of global search: Three concentrated changes at t = 130,150,170 produce a global maximum around b = 100, completely missing all of them.The middle jump is offset by the two outer jumps in the example configuration.
  • Localized search: A localized interval [101,200] successfully identifies the middle change because its signal contrast is much higher than on [1,300].The contrast becomes strongest when interval endpoints approach the two outer change-points, isolating the middle change.
  • Wild binary segmentation: WBS randomly draws endpoint pairs (s,e) and maximizes the absolute CUSUM statistic over b for each sampled interval.With sufficiently many draws, at least one interval is likely to be long enough while containing one change-point away from its endpoints.

3. Methodology and theory of wild binary segmentation.

WBS combines random interval localisation with binary segmentation to estimate multiple change-points under weaker spacing and jump-size conditions than standard BS. Its theory covers increasing numbers of change-points, improved location rates, thresholding and sSIC stopping, while random designs support short-interval detection without a fixed design choice.

  • Assumptions: The number of change-points may increase to infinity with the sample size, subject only to constraints implied by the minimum spacing.This removes any separate upper-bound assumption on N beyond the spacing condition.
  • Theory: The authors provide improved convergence rates and consistency proofs for both standard binary segmentation and WBS.For standard BS, the improved rates inform the admissible threshold choice rather than only quantifying performance.
  • WBS procedure: WBS randomly samples subintervals and applies CUSUM statistics, increasing the chance of isolating individual change-points in suitably narrow intervals.The random design also avoids choosing a subjective fixed interval design and permits additional intervals to be added easily.
  • Theoretical advantages: WBS remains consistent when the minimum spacing is logarithmic in T, whereas standard BS requires spacing larger than O(T^3/4) in the stated comparison.For fixed spacing and minimum jump height, WBS also has a wider admissible threshold-rate range than BS.
  • Theoretical advantages: The WBS location-error rate does not depend on the spacing δT, provided the spacing satisfies the WBS assumption, but depends on the minimum jump height.The result applies even when the number of change-points is unbounded and spacings are much shorter than T.
  • Stopping criteria: WBS supports thresholding and strengthened SIC stopping criteria, with sSIC selecting among candidate models generated by the algorithm.The sSIC theory requires N ≤ K for finite K and a condition involving the smallest admissible δT fT.

4. Parameter choice and simulation study.

The paper recommends practical defaults for WBS and compares thresholding and sSIC against competing change-point methods in simulations. WBS sSIC performs best overall, while thresholded WBS performance depends on the constant C.

  • Parameter choice: M = 5000 is recommended for datasets with T up to a few thousand, and larger M makes results less dependent on the random draw.For M = 5000, dependence on the particular random draw was observed to be very minimal.
  • Parameter choice: The default threshold constant is C = 1, selected because it minimized |N̂ − N| closely enough in extensive simulations.The simulations varied average change-point counts, jump variances, sample sizes, and Gaussian noise.
  • Simulation results: Several competitors exhibit systematic errors: PELT tends to overestimate, while cumSeg and SMUCE tend to underestimate the number of change-points.S3IB also underestimates substantially for mix and performs poorly for stairs10.
  • Simulation results: Classical binary segmentation shows clear shortcomings, with poor or average performance on several signals under both tested threshold constants.For C = 1 it performs poorly for teeth10, while for C = 1.3 it is poor except on stairs10.
  • Simulation results: Thresholded WBS performs well across signals but changes behavior with C: C = 1 excels for mix and teeth10, whereas C = 1.3 excels for fms and stairs10.With C = 1, WBS slightly overestimates fms; with C = 1.3, it underestimates other signals, though generally not by many.
  • Simulation results: WBS sSIC performs best or nearly best across all test signals except stairs10, where any overestimation is usually by only one change-point.The authors recommend using WBS sSIC first, followed by thresholded WBS with C = 1.3 and then C = 1 if residual patterns remain.

5. Real data example.

The paper applies WBS to volatility-adjusted S&P 500 log-returns over approximately eight trading years. Threshold maps and sSIC identify a small number of estimated trend changes, with the interpretation depending on the threshold scale.

  • Data and procedure: The analysis uses 2,000 daily S&P 500 log-returns ending 26 October 2012, removes volatility with a Gaussian GARCH(1,1) fit, and applies WBS to residuals.Both thresholding and sSIC stopping criteria are applied.
  • Thresholding: At threshold ζT ≈ 3.83, WBS estimates five change-points concentrated in or around three separate locations.The time-threshold map represents estimated locations by vertical lines and thresholds by their y-axis ranges.
  • Interpretation and caveat: The number of estimated financial-data change-points is scale-dependent, because different traders may focus on trend changes over weeks, months, or years.A lower threshold may therefore be more suitable for more frequent trading horizons.

APPENDIX A: PROOFS

The appendix proves consistency properties for binary segmentation and WBS by controlling empirical CUSUM statistics on high-probability events. The argument shows that detected change-points localize near true changes, recursion continues while changes remain, and thresholding stops after all are detected.

  • Proof strategy: The proof works on high-probability events where empirical CUSUM statistics are uniformly close to their unobserved signal counterparts.The appendix introduces events A_T and B_T to control the innovations and empirical CUSUM behavior.
  • Localization: When an interval contains undetected change-points and satisfies the required spacing conditions, the largest CUSUM statistic lies within Cε_T of one true change-point.Lemma A.3 gives |b−η|≤Cε_T under the stated assumptions.
  • Recursive detection: After detecting a change-point, the procedure recurses on the two resulting subintervals, and the spacing conditions remain valid for intervals containing undetected changes.The proof uses the separation assumptions to preserve the conditions needed for subsequent detections.
  • Stopping: For sufficiently large T, all change-points are detected one by one, after which the CUSUM statistics fall uniformly below the threshold and the algorithm stops.This establishes the intended stopping behavior once no true change-points remain.
  • Proof bounds: The appendix notes that sharper constants may be possible, but the existing bounds are already rate-optimal and would not improve practical stopping-criterion choices.The stated limitation concerns multiplicative constants in the theoretical bounds, not their convergence rates.

APPENDIX B: TEST MODELS AND METHODS USED IN THE SIMULATION STUDY

This appendix specifies the simulated signals, noise levels, competing methods, and execution settings used to evaluate change-point procedures. The test suite includes standard, short-spacing, frequent-change, and gradually increasing signals, while comparison methods retain stated defaults unless otherwise noted.

  • Test models: The simulation study uses five test signals: blocks, fms, mix, teeth10, and stairs10, with their lengths, change-points, signal values, and noise standard deviations specified.The signals range from a standard piecewise-constant benchmark to frequent changes every 10 observations and alternating or increasing levels.
  • Test models: The mix signal combines prominent short-spaced changes with less prominent changes separated by longer constant intervals.Its length is 560 and its noise standard deviation is σ = 4.
  • Test models: The teeth10 and stairs10 signals contain frequent change-points every 10 observations, with alternating and increasing segment levels respectively.Their noise standard deviations are σ = 0.4 for teeth10 and σ = 0.3 for stairs10.
  • Comparison methods: Competing procedures include strucchange, Segmentor3IsBack, changepoint, cumSeg, and stepR, with their principal routines and selection settings described.The appendix identifies these methods respectively with breakpoints, Segmentor, cpt.mean, jumpoints, and smuceR.
  • Comparison methods: The Segmentor routine requires a maximum number of segments, set to 15 by default, and none of the test signals exceeds that limit.The resulting comparison is referred to as S3IB.
  • Simulation design: Figure 5 evaluates WBS under linear-trend misspecification using threshold constant C = 1.3 over 1000 realisations of each model.The figure pairs trend-containing signals and typical noisy realizations with detection-frequency bar plots.

APPENDIX C: PERFORMANCE OF WBS IN THE PRESENCE OF LINEAR TRENDS

This appendix examines WBS when the true signal contains linear trends rather than only piecewise-constant sections. The simulations show that trend strength affects whether WBS ignores trends or produces separated spurious change-points.

  • Simulation scope: Figure 5 studies WBS performance under model misspecification in which the true function contains linear trends.The study is intended to provide insight into behavior outside the piecewise-constant signal assumption.
  • Trend strength: When linear trends are very flat, WBS almost completely ignores them.This behavior is reported for the example in the figure’s top row.
  • Trend strength: With more pronounced trends, WBS tends to detect spurious change-points toward trend-section middles, while the main change-point remains correctly detected.The middle locations can represent the piecewise-constant approximation of a trend and remain separated from the main central change-point.
  • Trend approximation: In the bottom examples, spurious detections occur toward trend-section middles and edges, producing more widely spaced piecewise-constant approximations.The appendix interprets this spacing as potentially visually attractive.
Loading 1411.0858v1…