Source-linked AI summary
Nonparametric maximum likelihood approach to multiple change-point problems
Changliang Zou, Guosheng Yin, Long Feng, Zhaojun Wang
TL;DR
Multiple change-point methods often rely on restrictive distributional assumptions, despite unknown segment distributions and deterioration of least-squares performance with heavy tails or outliers. The paper proposes NMCD, a nonparametric likelihood method using BIC, dynamic programming, and screening. Under mild conditions it achieves optimal-rate estimation without distributional assumptions and detects changes in location, scale, or shape, while its scope is limited by an assumption of at least one change-point and its omnibus design.
Problem
Unknown segment distributions and least-squares sensitivity to heavy tails or outliers motivate multiple change-point detection without parametric assumptions.
Method
NMCD uses nonparametric maximum likelihood, BIC for the number of change-points, dynamic programming for locations, and screening to reduce computation.
Results
Under mild conditions, NMCD achieves the optimal Op(1) change-point estimation rate without distributional assumptions and detects location, scale, or shape changes.
Takeaways & Limitations
NMCD provides a nonparametric approach for identifying multiple change-points across varied distributional differences, including when the number of changes grows with sample size.
Takeaways & Limitations
NMCD assumes at least one change-point, cannot diagnose whether changes involve location, scale, or shape, and requires extensions for autocorrelated or multivariate data.
Abstract
from arXiv · showhide
In multiple change-point problems, different data segments often follow different distributions, for which the changes may occur in the mean, scale or the entire distribution from one segment to another. Without the need to know the number of change-points in advance, we propose a nonparametric maximum likelihood approach to detecting multiple change-points. Our method does not impose any parametric assumption on the underlying distributions of the data sequence, which is thus suitable for detection of any changes in the distributions. The number of change-points is determined by the Bayesian information criterion and the locations of the change-points can be estimated via the dynamic programming algorithm and the use of the intrinsic order structure of the likelihood function. Under some mild conditions, we show that the new method provides consistent estimation with an optimal rate. We also suggest a prescreening procedure to exclude most of the irrelevant points prior to the implementation of the nonparametric likelihood method. Simulation studies show that the proposed method has satisfactory performance of identifying multiple change-points in terms of estimation accuracy and computation time.
1. Introduction.
The paper develops a nonparametric method for multiple change-point detection when segment distributions are unknown and may differ in diverse ways. It combines nonparametric likelihood estimation with BIC, dynamic programming, and screening to support consistent and efficient estimation.
- Unknown segment distributions can make parametric modeling misspecified, while least-squares performance often deteriorates for heavy-tailed errors or outliers.
- The authors target multiple change-point detection without parametric structure, allowing salient differences between successive distributions to signal changes asymptotically.
- The proposed NMCD procedure is a nonparametric maximum likelihood counterpart to classical least-squares multiple change-point methods.
- Under mild conditions, NMCD estimates change-point locations at the optimal Op(1) rate without distributional assumptions, including settings where the number of change-points diverges with sample size.
- BIC selects the number of change-points, while dynamic programming exploits the likelihood’s intrinsic order structure to compute the maximizer.
- The method is designed to detect changes in location, scale, or shape and uses screening to reduce the dimensionality before nonparametric likelihood optimization.
2. Nonparametric multiple change-point detection.
The NMCD models multiple change-points without parametric distributional assumptions, using a nonparametric likelihood linked to goodness-of-fit testing. Under stated conditions, it consistently estimates change-point locations and can consistently select their number with BIC.
- Nonparametric likelihood: The method treats each observation as binary at threshold u, yielding a nonparametric likelihood based on empirical distribution functions.For fixed u, the empirical count follows a binomial distribution, and the likelihood integrates information across u using a weight function.
- Nonparametric likelihood: The integrated likelihood criterion is maximized at the true change-point location in the one-change-point population analysis.The limiting objective has a local maximum at the true location q1.
- Model selection: BIC selects the number of change-points by balancing the likelihood against a penalty for larger models.The penalty sequence must diverge, and the proposed setting differs from the traditional least-squares choice because spurious change-points can otherwise be selected.
- Asymptotic theory: Under assumptions including continuous successive distributions, diverging minimum segment length, and uniform empirical-CDF convergence, the theory establishes consistency.The assumptions allow change-points to become asymptotically distinguishable and support the required empirical-process control.
- Asymptotic theory: Op(1) is achieved for change-point location estimation under fixed change-point count and suitable signal conditions, without specifying the distributions.The same optimal rate is stated for the nonparametric approach when the number of change-points is known.
- Model selection: The BIC consistently estimates the number of change-points when its penalty and the upper bound on candidate change-points satisfy the stated growth conditions.The result gives Pr( bKn = Kn) →1 as n →∞ under the theorem’s assumptions.
3. Implementation of NMCD.
NMCD exploits separability of the likelihood objective to compute optimal segmentations recursively with dynamic programming. This makes fitting straightforward, although the O(n^2) dependence can become costly for very long sequences.
- Dynamic programming: Bellman’s principle of optimality makes the segmentation objective separable into a rightmost change-point and an optimal preceding segmentation.This recursive structure enables dynamic programming to maximize the nonparametric likelihood.
- Computational cost: The dynamic-programming implementation is fast for ordinary sequences but can be computationally intensive when n is very large.The stated computational complexity is O(n^2), motivating a preliminary screening step for long sequences.
- Computational cost: Preliminary screening reduces the dimension before NMCD optimization by excluding most irrelevant points.This is intended to alleviate the computational burden of optimal segmentation for very long data sequences.
Screening algorithm.
The screening algorithm uses local two-sample Cramér–von Mises statistics to retain influential candidate change-points before running NMCD. Its weighting scheme emphasizes tail differences, while the reduced candidate set lowers computation.
- Candidate screening: The algorithm computes local Cramér–von Mises statistics on adjacent subsequences and retains local maxima as candidate change-points.For each index, it compares two windows of length nI and adds the index when it is the strongest local statistic.
- Candidate screening: The resulting candidate set usually has cardinality much smaller than n, reducing the dimension of the subsequent NMCD computation.With a candidate set O, the computation for a given L reduces to O(L|O|n).
- Screening consistency: The screening procedure is designed to retain at least one neighborhood of each true change-point with probability tending to one under its stated conditions.The tuning length nI must satisfy the growth conditions in Proposition 1.
- Weight selection: The proposed weight dw(u) = { bFn(u)(1−bFn(u))}−1 d bFn(u) gives greater emphasis to observations in the tails than the unweighted choice.This is intended to improve sensitivity when adjacent distributions differ mainly in their tails rather than centers.
4. Simulation studies.
The simulations evaluate NMCD across error distributions, change patterns, tuning choices, competing methods, and increasing numbers of change-points. NMCD generally provides accurate and computationally efficient detection, with performance that remains stable under nonnormal errors and diverging change-point counts.
- Simulation designs: The simulations cover location, scale, skewness, and kurtosis changes under several error distributions and sample-size settings.Models (I)–(III) include location changes, combined location and scale changes, and distributional differences involving skewness and kurtosis.
- NMCD versus PL: NMCD and PL perform comparably under normal errors, while NMCD generally improves location estimation under t(3) and χ2(1) errors.For nonnormal errors, NMCD has smaller distance values and standard deviations than PL in the reported known-change-point comparisons.
- NMCD versus PL: When the number of change-points is unknown, NMCD significantly outperforms PL on selected distance and change-point-count measures for the two nonnormal cases.Both procedures use BIC to select the number of change-points; estimating that number increases variability in the distance measures.
- Comparisons with nonparametric methods: Across nonparametric comparisons, NMCD remains effective for higher-order distributional changes, while ECP has advantages in some location-and-scale settings.Under model (III), NMCD produces reasonable results when ECP and Lee’s method perform poorly; NMCD is also reported as faster than ECP because of dynamic programming.
- Comparison with LSTV: NMCD and LSTV* substantially outperform LSTV, and NMCD is uniformly better than LSTV* while becoming much faster at large sample sizes.The reported explanation attributes LSTV’s weaker location estimation partly to LASSO-induced shrinkage bias.
- Diverging change-point counts: Across increasing sample sizes and diverging numbers of change-points, NMCD’s distance measures remain reasonably small and generally stable.The simulations support satisfactory detection performance when the number of change-points grows with the sample size.
5. Example.
The example applies NMCD to a challenging large dataset with outliers, using screening and BIC to obtain a computationally manageable segmentation. The results indicate reasonable detection of both sharp local features and long unchanged segments, including distributional changes beyond location or scale.
- The dataset has n = 8811 observations, appears patternless and complicated, and contains quite a few outliers.These features make identifying multiple change-points challenging and motivate a robust nonparametric procedure.
- The initial screening leaves 305 candidate points, dramatically reducing the dimensionality of change-point detection.The procedure sets nI = 14 and ζn ≈41 before screening.
- BIC selects bKn = 43 change-points, and the entire procedure completes in 54 seconds.The reported computation used an Intel Core 2.2 MHz CPU.
- NMCD detects local sharp features and long unchanged data segments, with generally reasonable change-point estimates.The example compares NMCD with LSTV* on the same dataset.
- Among 44 NMCD-identified segments, 34 reject normality at the 0.01 nominal level, while consecutive segments differ in location, scale, and shape.The fifth segment is far from normal according to its normal QQ-plot, and the fifth and sixth density estimates show multiple distributional differences.
6. Concluding remarks.
The paper concludes that NMCD consistently detects multiple change-points without parametric distributional assumptions, combining BIC, dynamic programming, and screening. It is fast and competitive, with stronger balance between over- and under-segmentation on nonnormal data, but its scope has explicit limitations.
- NMCD is a nonparametric likelihood-based method whose consistency is established under mild conditions.The true number of change-points is unknown and selected using BIC.
- Dynamic programming combined with screening facilitates implementation, particularly for large datasets.The computational scheme is reported to be fast and competitive with existing methods.
- Numerical comparisons show better balance between over- and under-segmentation errors with nonnormal data, while matching parametric performance under correct specification.
- NMCD assumes at least one change-point and cannot diagnose whether a detected change concerns location, scale, or shape.Additional nonparametric tests are needed to verify the assumption and identify which parameter changes.
- Extensions remain warranted for autocorrelated observations, multivariate data, and multiple structural changes in linear models.
APPENDIX
The appendix develops probability bounds and BIC arguments supporting NMCD’s asymptotic behavior. It establishes control of likelihood fluctuations and shows that the selected segmentation contains, and ultimately estimates, the true number and locations of change-points.
- Under assumptions (A1)–(A2) and Kn(log n)/n → 0, the appendix derives a bound involving un ≡CǫKn(log Kn)2(log(nKn))2.
- The global BIC minimum includes at least Kn change-point estimators asymptotically: Pr{ b Kn ≥Kn} →1.
- The appendix separately analyzes under-segmentation and over-segmentation through propositions concerning BIC minima with different numbers of candidate change-points.These arguments support consistency of the selected number of change-points under assumptions (A1)–(A4).