Catching Change-points with Lasso

Zaïd Harchaoui, Céline Lévy-LeducNeurIPS 2007 · OpenReview

In signal processing, "change-point detection" involves partitioning a noisy signal into segments where the underlying value is constant. This is a critical task in various domains, from identifying sudden jumps in a patient's heart rate to detecting structural shifts in stock prices or geological formations.

The gold standard for finding these jumps is Dynamic Programming (DP). However, DP has a major flaw: its computational complexity is $O(Kn^2)$, where $n$ is the number of observations and $K$ is the number of change-points. For modern large-scale datasets, this quadratic scaling makes DP prohibitively slow. Furthermore, "raw" DP can sometimes be overly sensitive to noise in real-world data.

To address this, researchers have introduced Cachalot, a hybrid algorithm that reframes change-point detection as a sparse variable selection problem. By combining the speed of Lasso (L1-regularization) to find candidate locations with the precision of Dynamic Programming to refine them, Cachalot achieves high-accuracy signal segmentation with significantly lower computational costs.

Reframing the Problem: Change-points as Dummy Variables

The core innovation of Cachalot is treating the signal segmentation task as a linear regression problem: $Y = X\beta + \epsilon$.

  • The Trick: The matrix $X$ is defined as a lower triangular matrix of ones. In this setup, the coefficients ($\beta$) represent the magnitude of the jumps at each time step, rather than absolute values.
  • The Sparsity: Because change-points are rare relative to the length of the signal, most $eta$ values should be exactly zero. This transforms the task into a classic "variable selection" problem, allowing the authors to tap into the massive body of research on Lasso and sparse recovery.

The Cachalot algorithm executes in three stages:

  1. Lasso Selection: The Least Angle Regression (LAR) algorithm is used to solve a Lasso problem. This acts as a coarse filter, quickly identifying a small set ($K_{max}$) of candidate change-point locations and reducing the search space from $n$ (thousands) to $K_{max}$ (dozens).
  2. Reduced Dynamic Programming (rDP): Instead of running DP on every possible point in the signal, it is run only on the candidates selected by Lasso. This slashes the complexity from $O(n^2)$ to $O(K_{max}^2)$, breaking the quadratic barrier.
  3. Model Selection: A "rule of thumb" based on the ratio of empirical risks is used to decide exactly how many change-points ($K$) to keep in the final model.

Key Results and Performance

The authors evaluated Cachalot on both synthetic 1D signals with Gaussian white noise and real-world benchmark datasets.

Synthetic Data

In synthetic tests featuring 5 to 20 true change-points, Cachalot (Method A) consistently outperformed the state-of-the-art penalized least-squares method (Method B). While both methods showed comparable recall (the ability to find the true points), Cachalot exhibited superior precision and significantly lower false alarm rates, resulting in much "cleaner" detections.

Performance comparison between Cachalot (Method A) and a standard penalized least-squares method (Method B).

Real-World Application: Well-Log Data

To test practical viability, Cachalot was applied to the "well-log" dataset—a classic benchmark consisting of nuclear magnetic response measurements used to identify rock structures in geophysics. These signals are notoriously noisy and contain numerous outliers.

Raw well-log signal (left) and the processed signal with detected change-points (right).

Because the Lasso framework assumes Gaussian white noise, real-world data with heavy outliers requires pre-processing. After applying a simple median filter to handle the outliers, Cachalot successfully identified rock layer transitions that matched results from much more computationally expensive Bayesian techniques.

Limitations and Future Directions

While Cachalot offers a massive leap in efficiency—moving from $O(n^2)$ to a process dominated by the Lasso path ($O(K_{max}^2 n)$) and a very fast reduced DP ($O(K_{max}^3)$)—it does have limitations. Its sensitivity to non-Gaussian outliers necessitates careful pre-processing, and the threshold for selecting the final number of change-points still requires some domain knowledge or manual tuning.

Currently, the algorithm focuses on 1D signals. However, extending this "Lasso-then-DP" approach to 2D (such as image segmentation) or multi-variate signals remains a highly promising direction for future research.

Summary updated

Abstract

We propose a new approach for dealing with the estimation of the location of change-points in one-dimensional piecewise constant signals observed in white noise. Our approach consists in reframing this task in a variable selection context. We use a penalized least-squares criterion with a l1-type penalty for this purpose. We prove that, in an appropriate asymptotic framework, this method provides consistent estimators of the change-points. Then, we explain how to implement this method in practice by combining the LAR algorithm and a reduced version of the dynamic programming algorithm and we apply it to synthetic and real data.
BibTeX
@inproceedings{harchaoui2007catching,
  author = {Zaïd Harchaoui and Céline Lévy-Leduc},
  title = {{Catching Change-points with Lasso}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2007},
  url = {https://openreview.net/forum?id=S1bELO-_ZS},
}

Loading related content...

Figure