Source-linked AI summary
Selective review of offline change point detection methods
Charles Truong, Laurent Oudre, Nicolas Vayatis
TL;DR
The paper addresses offline detection of multiple change points in settings involving industrial systems, physical phenomena, or human activity. It surveys methods through a framework of cost functions, search methods, and constraints on the number of changes, reporting faster computation with Pelt and providing implementations in ruptures.
Problem
The paper addresses offline detection of multiple change points in settings involving industrial systems, physical phenomena, or human activity.
Method
The paper organizes detection algorithms as combinations of a cost function, a search method, and a constraint on the number of changes.
Results
The review reports that the same results can be obtained faster with Pelt.
Takeaways & Limitations
Implementations of the main surveyed algorithms are provided in the ruptures Python package to facilitate prototyping.
Takeaways & Limitations
The framework does not encompass all published methods, including methods excluded from the remainder of the article.
Abstract
from arXiv · showhide
This article presents a selective survey of algorithms for the offline detection of multiple change points in multivariate time series. A general yet structuring methodological strategy is adopted to organize this vast body of work. More precisely, detection algorithms considered in this review are characterized by three elements: a cost function, a search method and a constraint on the number of changes. Each of those elements is described, reviewed and discussed separately. Implementations of the main algorithms described in this article are provided within a Python package called ruptures.
1. Introduction
The introduction frames offline change point detection as retrospective segmentation of multivariate time series whose underlying states may change repeatedly. It surveys methods to help practitioners choose and apply suitable algorithms, emphasizing a common methodological structure, mathematical properties, evaluation metrics, and implementations.
- Change point detection identifies changes in the underlying state or model of signals and time series.
- In gait analysis, segmentation boundaries enable extraction of informative features from homogeneous activity phases.
- Offline methods retrospectively detect changes after all samples have been collected, unlike online methods operating in real time.
- The article surveys algorithms for detecting multiple change points in multivariate time series.
- The review supports method selection through practical implementation and calibration guidance, mathematical properties, and evaluation metrics.
- The main reviewed methods are implemented modularly in the Python scientific library ruptures.
2. Background
The review formulates offline multiple change point detection as a segmentation and model-selection problem, then organizes methods by cost function, search method, and change-number constraint. It surveys exact and approximate solutions for known or unknown numbers of changes while acknowledging scope limitations.
- Problem formulation: Change point detection estimates unknown instants where characteristics of a multivariate, piecewise-stationary process change abruptly.The number of changes may be known beforehand or estimated from the data.
- Problem formulation: A segmentation minimizes a criterion V(T, y), whose cost-function choice depends on the task and measures segment goodness-of-fit.The criterion is assumed to sum the costs of all segments, with c(·) measuring sub-signal fit to a specific model.
- Review typology: The typology defines each reviewed algorithm by a cost function, a search method, and a constraint on the number of change points.The cost function encodes detectable change types; the search method resolves the associated discrete optimization problems.
- Problem formulation: Known-K detection solves a discrete optimization over segmentations with a fixed number of changes, whereas unknown-K detection adds a complexity penalty.The penalty balances goodness-of-fit against segmentation complexity in the unknown-number formulation.
- Search methods: Search methods provide exact or approximate solutions and trade computational complexity against accuracy.The review covers methods for both fixed- and unknown-change optimization problems.
- Constraints: For unknown change counts, too-small penalties detect noise-related changes, while excessive penalties detect only the most significant changes or none.Penalty choice is related to the amplitude of the changes to detect.
- Scope and organization: The framework does not encompass all published methods, and Bayesian approaches are excluded despite state-of-the-art results in some speech and sound-processing domains.The article instead reviews selected cost functions, search methods, constraints, theoretical results where possible, and a modular Python implementation.
3. Evaluation
Evaluation combines general consistency analysis with empirical metrics for comparing estimated and true segmentations. The reviewed metrics assess breakpoint-count error, temporal robustness, segmentation agreement, and detection accuracy under a matching tolerance.
- 3.1. Consistency: Consistency is evaluated mathematically or empirically through metrics computed on segmentation performance.The asymptotic setting treats the signal as sampled from a continuous-time process on an increasingly fine grid.
- 3.1. Consistency: Asymptotic consistency requires the estimated breakpoint count to match the true count and estimated change point fractions to converge to the true fractions.The definition concerns convergence of fractions rather than exact convergence of breakpoint indexes.
- 3.1. Consistency: Exact breakpoint-index distances generally do not converge to zero, so consistency results address change point fractions instead.This limitation holds even for simple models.
- 3.2.2. Hausdorff: Hausdorff measures the greatest temporal distance between a change point and its prediction, penalizing both over-segmentation and under-segmentation.A value of zero means the predicted and true breakpoint sets are equal.
- 3.2.3. RandIndex: RandIndex measures average segmentation similarity by counting pairs assigned to the same or different segments in both segmentations.It ranges from 0 for total disagreement to 1 for total agreement.
4. Models and cost functions
The survey organizes change detection models through their associated cost functions. It separates costs into parametric and non-parametric categories, presenting general formulations before special cases and summarizing the reviewed costs.
- 4. Models and cost functions: Cost functions are the first defining element of change detection methods and are usually derived from a signal model.
- 4. Models and cost functions: The reviewed models and costs are organized into parametric and non-parametric categories.This typology is shown schematically in Figure 6.
- 4. Models and cost functions: For each model, the survey gives the most general formulation first and then describes special cases when applicable.
- 4. Models and cost functions: A summary table of all reviewed cost functions appears at the end of the section.
4.1. Parametric models
Parametric change point models specify a distribution family and detect changes in its parameters, often through maximum-likelihood costs. The reviewed theory establishes asymptotic consistency for several single- and multiple-change settings, while applications include mean, scale, count-rate, and piecewise-linear changes.
- General model: Parametric methods model changes in a finite-dimensional parameter vector, with the distribution family typically known before detection.The literature historically began with Gaussian mean and scale shifts and later expanded to exponential-family distributions.
- Maximum likelihood estimation: When the summed cost equals negative log-likelihood, change point detection is equivalent to maximum-likelihood estimation.The cost c_i.i.d. is defined for a parametric density family over a compact parameter space.
- Theoretical results: Asymptotic consistency has been demonstrated for single changes across Gaussian, discrete, and other specific distributions, and later for multiple changes.For generic distribution families, known-number multiple-change solutions are consistent under regularity and technical cost-function assumptions.
- Related costs: The mean-shift model uses independent Gaussian variables with piecewise-constant means and common variance, yielding the quadratic-error cost c_L2.The mean-shift cost uses the empirical mean of each sub-signal.
- Related costs: Allowing variance changes yields c_Σ, which can detect shifts in the first two moments even for non-Gaussian variables.The cost has applications in stock-market, biomedical, and electric-power data.
- Related costs: Other reviewed parametric costs include Poisson rate changes and piecewise-linear regression models with abruptly changing relationships.Piecewise-linear formulations include partial and pure structural-change models and generalize to autoregressive and multiple-regression settings.
4.2. Non-parametric models
Non-parametric methods address settings where the distribution family is unknown or unsuitable, using empirical distribution, rank, or kernel-based statistics. The review reports consistency results, computational costs, invariance properties, and competitive applications across several data types.
- Motivation: Non-parametric detection is motivated when parametric assumptions do not fit the data or the distribution family is unknown beforehand.Such methods can be more robust in these settings.
- Empirical-cdf methods: The empirical-cdf cost c_F uses distribution-free likelihood construction and has asymptotically consistent estimates for known or unknown change counts.Its total detection complexity is O(T^3) because evaluating a sub-signal cost requires summing T terms.
- Rank-based methods: Rank-based c_rank measures changes in the joint behavior of marginal ranks and is invariant under monotonic transformations of the data.Its preprocessing requires O(dT log T) operations for ranks and O(d^2T + d^3) operations for the rank covariance matrix.
- Kernel-based detection: Kernel costs detect mean shifts in a transformed signal, and characteristic kernels can make distribution changes coincide with transformed mean shifts.The mapping is injective for characteristic kernels, including commonly used Gaussian kernels under stated conditions.
- Kernel-based detection: Kernel change point estimates are asymptotically consistent for known and unknown change counts, with an oracle inequality also holding non-asymptotically.Experiments found kernel detection competitive in many settings, unsupervised, and requiring few manually calibrated parameters.
4.3. Summary table
The review summarizes its parametric and non-parametric cost functions in a table, listing each cost’s name, expression, and parameters of interest.
- Summary table: Table 1 organizes the reviewed costs by name, mathematical expression, and parameters of interest.Referenced quantities include empirical means, empirical cumulative distribution functions, and positive semi-definite matrices in feature space H.
- Summary table: The table covers both parametric and non-parametric cost functions.It is presented as a summary of the cost functions reviewed in the section.
5. Search methods
Search methods are organized into exact optimal procedures and approximate sequential procedures, which can be combined with the reviewed costs. Dynamic programming and pruning provide exact solutions, while window-based, binary, and bottom-up methods trade precision for speed.
- Method typology: Search methods fall into optimal methods yielding exact solutions and approximate methods yielding approximate solutions to the segmentation problems.Complexity depends on the selected cost function; the review often assumes O(1) cost evaluation on a sub-signal.
- Optimal methods: For a known number K of changes, Opt uses dynamic programming to find the exact solution with complexity O(KT^2).It recursively combines optimal sub-signal partitions and reconstructs the breakpoint set by backtracking.
- Optimal methods: Forward dynamic programming computes the L lowest-cost partitions in O(LKT^2), using recurring change points diagnostically to trim insignificant changes.The method can correct overestimation of the number of change points, at higher computational cost.
- PELT: PELT solves the unknown-count problem exactly under a linear penalty and can achieve O(T) complexity when regime lengths are uniformly distributed.Its sequential pruning rule discards indexes that cannot be the last change point before the current endpoint.
- Approximate methods: Approximate procedures include window-based, binary, and bottom-up segmentation, returning one estimated change point per sequential iteration.The window-sliding method compares adjacent windows, has linear complexity in the number of samples, and is easy to implement.
6. Estimating the number of changes
The review organizes unknown-change-point procedures by their penalty functions and describes how smoothing parameters balance segmentation complexity against goodness-of-fit.
- Penalty-based procedures: Unknown change-point procedures are organized by the penalty functions on which they are based.The section also describes common heuristics for selecting among these procedures.
- Linear penalties: The linear l0 penalty encompasses criteria including BIC and AIC, with specialized forms for Gaussian mean-shift signals.The review gives explicit penalty formulations and relates BIC penalties to constrained likelihood under the iid piecewise-constant model.
- Penalty calibration: Low smoothing-parameter values favor segmentations with many regimes, whereas high values discard most changes.The smoothing parameter controls the trade-off between complexity and goodness-of-fit measured by the sum of costs.
- Penalty calibration: Model-selection approaches calibrate the smoothing parameter using criteria such as BIC, while model-free approaches use cross-validation or slope heuristics.Supervised procedures can instead choose β by minimizing an approximation of segmentation error on annotated signals.
- Fused lasso: Relaxing the l0 penalty to l1 yields a convex optimization problem solvable efficiently with Lars, with complexity of order O(T log T).Under a Gaussian mean-shift model, estimated change-point fractions are asymptotically consistent for an appropriately converging sequence of β values, even without the irrepresentable condition.
7. Summary table
The summary table categorizes reviewed methods by search method and whether the number of change points is known or unknown, while also indicating computational complexity.
- Organization: Methods are classified according to search procedures such as Opt, Pelt, BinSeg, and Win, although the categorization is approximate rather than implementation-exact.The table also distinguishes methods requiring known K from methods that operate when K is unknown.
- Computational complexity: Quadratic methods receive one star and linear methods receive three stars in the computational-complexity guide.The review notes that newer Pelt implementations can obtain results faster than earlier quadratic approaches for linear penalties.
- Summary resources: Table 2 summarizes the literature review, and Figure 12 schematically presents the ruptures package.
8. Presentation of the Python package
The ruptures package provides a modular Python interface for multivariate change-point detection, combining cost functions, search methods, constraints, evaluation, and visualization.
- Search methods: Ruptures includes major algorithm families such as dynamic programming, l0-constrained detection, binary segmentation, bottom-up segmentation, and window-based segmentation.The selection favors algorithms used across several settings rather than exhaustive coverage of all procedures.
- Cost functions: Parametric costs detect shifts in means, scale, relationships between dimensions, or autoregressive coefficients, while nonparametric costs detect distribution changes.The nonparametric options include kernel-based and Mahalanobis-type metrics.
- Constraints: All methods can be used whether the number of change points is known or unknown, including cost-budget and linear-penalty formulations.
- Modularity: A consistent interface makes optimization methods and cost functions composable, allowing new contributions to be integrated when they follow the interface guidelines.
- Scalability: Caching intermediate results reduces the cost of rerunning the same algorithm on the same signal with different parameter sets.Users can also subsample signals and impose a minimum distance between changes when speed constraints apply.
9. Conclusion
The article reviews offline multiple-change-point methods within a common framework of cost functions, search methods, and constraints. This framework supports method selection for particular segmentation tasks and is implemented in ruptures.
- Conclusion: Each reviewed detection method is described through a cost function, a search method, and a constraint on the number of changes.
- Conclusion: The framework lets users select components to design an algorithm suited to a given segmentation task.
- Conclusion: Most procedures discussed are available in the Python package ruptures, whose consistent interface supports comparison and integration of new contributions.