Improved identification of breakpoints in piecewise regression and its applications

This paper proposes a novel, fast-converging greedy algorithm that accurately identifies the optimal number and locations of breakpoints in piecewise polynomial regression, demonstrating superior accuracy and interpretability over existing methods on both synthetic and real-world datasets.

The Gist

The Big Picture: Drawing a Line Through a Wiggly Path

Imagine you are trying to draw a single line through a bunch of scattered dots on a piece of paper.

• Traditional Regression is like trying to force a single, straight ruler through all the dots. If the dots curve up and down, your straight line will miss a lot of them. It's too rigid.
• Piecewise Regression is smarter. It says, "Okay, the path goes up for a while, then flattens out, then drops down." So, instead of one straight line, we draw several straight lines connected end-to-end, like a折 (zig-zag) path that follows the dots much better.

The "breakpoints" are the specific spots where you stop one line and start the next. The big challenge in this paper is: How do you find the exact perfect spot to switch lines?

The Problem: Finding the "Sweet Spot"

In the past, finding these switch-points (breakpoints) was like trying to find a needle in a haystack while blindfolded.

• Old methods were like guessing randomly or checking every single inch of the paper. This took forever (computationally expensive) or got stuck in a "local trap" (thinking a small dip was the bottom of the valley when it wasn't).
• Gradient methods (used by some recent tools) are like a hiker trying to walk down a mountain in thick fog. They take small steps based on which way feels "down." But if the fog is thick (noise in the data), they might get stuck in a small hole and think they've reached the bottom, even though the real bottom is far away. They also require tuning "step size" (how big a step to take), which is tricky.

The Solution: The "Smart Greedy" Hiker

The authors propose a new method that acts like a smart, cautious hiker who doesn't need a compass or a step-size setting.

1. The "Candidate Set" (The Map)

Instead of checking every possible spot on the map, the algorithm creates a specific list of "candidate spots" to check.

• The Analogy: Imagine you are looking for a lost key in a garden. Instead of digging up the whole garden, you only check the spots halfway between two flowers. These are your "candidates." It's a finite, manageable list that covers the most likely places.

2. The "Greedy" Move (The Local Check)

The algorithm picks one "switch point" and looks at its three neighbors:

• Stay: Keep the switch point exactly where it is.
• Move Left: Shift the switch point to the candidate spot just before it.
• Move Right: Shift the switch point to the candidate spot just after it.

It solves a tiny math puzzle for each of these three options to see which one makes the line fit the dots best. It picks the winner.

• The Analogy: Imagine you are adjusting a shelf. You nudge it left, nudge it right, and leave it alone. You measure which position holds the most books without falling. You pick the best one. You do this for every shelf (breakpoint) one by one.

Why is this better?

• No Step-Size Tuning: You don't have to guess how far to move. You just check the immediate neighbors.
• No Getting Stuck: Because it checks specific candidates and compares them directly, it avoids the "foggy mountain" problem of gradient descent. It guarantees the error (the distance between the line and the dots) gets smaller or stays the same every time.

3. The "Backward Elimination" (The Pruning Shears)

Sometimes, you might start with too many switch points (overfitting). The model becomes too wiggly and starts memorizing the noise instead of the trend.

• The Analogy: Imagine you have a hedge with too many branches. You don't know which ones to cut. So, you try cutting one branch at a time.
  • If you cut Branch A, the hedge looks almost the same. (Cut it!)
  • If you cut Branch B, the hedge looks terrible and loses its shape. (Keep it!)
• The algorithm does this automatically. It starts with many breakpoints, finds the one that matters the least, removes it, and repeats until the model is just right—simple but accurate.

The Results: Why It Matters

The authors tested this on:

1. Fake Data: They created computer-generated wiggly lines with noise. Their method found the true shape better and faster than other popular methods (like Decision Trees or Gradient Boosting).
2. Real Data:
   • Stock Market (S&P 500): It successfully identified the major turning points in the stock market history, fitting the curve better than the competition.
   • COVID-19 Cases: It tracked the rise and fall of infection rates, identifying exactly when government policies (like lockdowns) changed the trend, without getting confused by daily fluctuations.

Summary in One Sentence

This paper introduces a new, stable way to draw lines through messy data by checking specific "neighborhood" spots to find the perfect turning points, and then trimming away the unnecessary ones, resulting in a model that is both highly accurate and easy to understand.

Technical Summary

1. Problem Statement

Piecewise regression (or segmented regression) is a statistical technique used to model data where the relationship between variables changes at specific points, known as breakpoints or change points. While effective, two major challenges exist:

1. Breakpoint Identification: Accurately locating the breakpoints is critical. Traditional methods often rely on grid searches, dynamic programming, or gradient-based optimization (like Adaptive Piecewise Linear Regression, APLR). Gradient-based methods suffer from hyperparameter tuning (e.g., learning rates), sensitivity to initialization, and the risk of converging to poor local minima.
2. Model Complexity vs. Fit: Determining the optimal number of breakpoints is difficult. Too few lead to underfitting; too many lead to overfitting. Existing methods often require manual specification of the number of segments or rely on complex penalty terms.

The paper addresses the need for a stable, derivative-free method to identify breakpoint locations and an automated scheme to determine the optimal number of breakpoints for continuous piecewise polynomial regression.

2. Methodology

The authors propose a two-stage approach combining a greedy location update algorithm with a backward elimination scheme.

A. Continuous Piecewise Polynomial Formulation

The problem is formulated as a constrained least-squares optimization. Given data $\{(x_i, y_i)\}$, the goal is to fit a continuous function $f(x)$ composed of $k$ polynomial segments of degree $d$.

• Objective: Minimize the sum of squared residuals $\sum (f(x_i) - y_i)^2$.
• Constraint: Continuity at breakpoints $\xi_j$, i.e., $p_j(\xi_j) = p_{j+1}(\xi_j)$.
• Solution: This is solved using the Karush-Kuhn-Tucker (KKT) conditions, resulting in a linear system involving a block-diagonal design matrix and a continuity constraint matrix.

B. Greedy Breakpoint Location Update (Algorithm 3)

Instead of optimizing over a continuous space, the method searches over a finite, data-adaptive candidate set $\mathcal{X} = \{ \frac{x_i + x_{i+1}}{2} \mid i=1,\dots,n-1 \}$.

• Local Search: For a fixed number of segments $k$, the algorithm iteratively updates each interior breakpoint $\xi_j$.
• Three-Point Comparison: For a specific breakpoint $\xi_j$, the algorithm considers three candidates:
  1. Stay: Current position $\xi_j$.
  2. Move Left: The midpoint between the data point immediately to the left of $\xi_j$ and the one before it ($\xi_j^-$).
  3. Move Right: The midpoint between the data point immediately to the right and the one after it ($\xi_j^+$).
• Constrained Subproblems: For each candidate, the algorithm solves a small, local constrained least-squares problem (involving only the two adjacent segments) to compute the Mean Squared Error (MSE).
• Update Rule: The candidate yielding the lowest MSE is selected. This process repeats for all breakpoints until a stopping criterion is met (either no change occurs or a cycle is detected).
• Advantages: This derivative-free approach avoids step-size tuning, ensures monotonic decrease in MSE, and guarantees termination in finite iterations due to the finite candidate set.

C. Backward Elimination for Optimal Number of Breakpoints (Algorithm 4)

To determine the optimal number of breakpoints without pre-specifying it:

1. Initialization: Start with a large number of breakpoints (e.g., $p_{max}$).
2. Refinement: Run the greedy location update (Algorithm 3) to optimize positions.
3. Elimination: Systematically test removing one interior breakpoint at a time. For each removal, re-optimize the remaining breakpoints and calculate the new MSE.
4. Selection: Identify the breakpoint whose removal results in the smallest increase in MSE (i.e., the most redundant breakpoint).
5. Stopping Criteria: The process stops if:
   • The relative increase in MSE exceeds a tolerance parameter $\tau$ (indicating the removed breakpoint was critical).
   • The number of remaining breakpoints falls below a user-defined upper bound $p$.

3. Key Contributions

1. Derivative-Free Greedy Algorithm: A novel method for updating breakpoint locations using a finite candidate set and local constrained least-squares (KKT) problems. It eliminates the need for learning rate tuning and avoids local minima associated with gradient descent.
2. Finite Termination Guarantee: Theoretical proof that the algorithm terminates in finite iterations due to the finite nature of the candidate set and the use of fixed-point/cycle detection.
3. Data-Driven Model Selection: A backward elimination scheme that automatically selects the number of breakpoints based on a relative MSE tolerance ($\tau$) and an upper bound ($p$), balancing model complexity and fit.
4. Continuity Enforcement: The method explicitly enforces continuity constraints at breakpoints, ensuring realistic and interpretable models for structural changes.

4. Experimental Results

The authors evaluated the method on synthetic and real-world datasets, comparing it against Polynomial Regression, Spline Regression, SVR, Decision Trees, Gradient Boosting, Random Forests, $\ell_1$ Trend Filter, APLR, and PELT.

• Synthetic Data:

  • The proposed method achieved the lowest MSE (3.94) and highest $R^2$ (0.8545) among all competitors.
  • It successfully identified the correct number of breakpoints (5), avoiding the overfitting seen in tree-based methods (which used 10–39 breakpoints) and the underfitting of global polynomial/spline models.
  • Robustness: In repeated experiments with varying noise levels and sample sizes, the proposed method consistently outperformed APLR and PELT, showing approximately 15% improvement in MSE over APLR.

• Real-World Data:

  • S&P 500 Index: The method achieved the highest $R^2$ (0.9592) and lowest RMSE, effectively capturing market trend shifts with 8 breakpoints.
  • COVID-19 Cases (Korea): The method provided the best fit ($R^2$ = 0.9566) with 12 breakpoints, significantly outperforming APLR and PELT. It offered a more parsimonious model than the $\ell_1$ trend filter (which used 24 breakpoints) while maintaining superior accuracy.

5. Significance and Conclusion

This paper presents a robust, computationally efficient alternative to gradient-based and dynamic programming approaches for piecewise regression.

• Stability: By avoiding gradient descent, the method is immune to step-size tuning issues and initialization sensitivity.
• Interpretability: The resulting models provide clear, interpretable breakpoints that correspond to structural changes in the data, which is vital in fields like economics and epidemiology.
• Automation: The backward elimination scheme removes the need for manual tuning of the number of segments, making the method highly applicable to diverse datasets.

The authors conclude that their approach offers a superior trade-off between model complexity and predictive accuracy, with future work suggested to explore reinforcement learning for long-term optimization of breakpoint selection.