Tutorials › Regression Analysis (Undergraduate) › Estimating an Unknown Breakpoint by Grid Search

Home  /  Tutorials  /  Piecewise Regression and Splines

Piecewise Regression and Splines · Tutorial 452 of 991

Estimating an Unknown Breakpoint by Grid Search

Learn to fit the same segmented regression at each permitted candidate knot and select the breakpoint with the smallest residual sum of squares.

Advanced 12 min read

What You'll Learn

  • Define a finite grid of permitted breakpoint candidates.
  • Fit a continuous hinge-function regression separately at each candidate.
  • Calculate and compare candidate residual sums of squares.
  • Use a worked least-squares derivation to verify candidate fits.
  • Recognize when a grid search yields a tie rather than a unique breakpoint.
  • Distinguish breakpoint selection from uncertainty calculations for a fixed knot.

Why Search Over Candidate Breakpoints?

A segmented regression can represent a relationship whose slope changes at a breakpoint. If that breakpoint is unknown, fitting the model requires two choices: specify which candidate locations are allowed, then find the best-fitting model at each one. A grid search makes this process concrete: fit the same model at every permitted candidate knot and compare the residual sums of squares.

The grid search gives a data-dependent estimate of the breakpoint, not a guarantee that the true relationship has exactly one slope change. Its result also depends on which candidate locations were included. The procedure is useful because it turns an unknown-knot fitting problem into a finite collection of ordinary least-squares fits.

Definition: For a candidate breakpoint \(\tau\), a continuous piecewise linear regression with one slope change is $$ Y_i=\beta_0+\beta_1 x_i+\beta_2(x_i-\tau)_+ +\varepsilon_i,\qquad (x_i-\tau)_+=\max(0,x_i-\tau). $$ The fitted mean is continuous at \(\tau\). Its slope to the left is \(\beta_1\), and its slope to the right is \(\beta_1+\beta_2\). A grid search fits this model for each \(\tau\) in a specified finite set \(\mathcal{T}\), then selects a candidate with the smallest residual sum of squares, \(\operatorname{RSS}(\tau)=\sum_{i=1}^n (y_i-\hat{y}_i(\tau))^2\).

Set Up the Search Before Fitting

The permitted grid \(\mathcal{T}\) is a set of candidate values on the predictor scale, in the same units as \(x\). It might be specified in advance or constructed from the observed predictor values. To make a candidate fit meaningful, the design matrix for that candidate must have full column rank: the intercept, \(x\), and hinge columns must not be linearly redundant. In practice, the grid should also leave enough observations and distinct predictor values on both sides of each candidate to support the intended segment estimates.

For each candidate \(\tau\), create the hinge values \(h_i=(x_i-\tau)_+\), and fit the regression with columns \(1\), \(x_i\), and \(h_i\). Keep the response observations, model form, and fitting criterion the same across candidates. The selected knot is

$$ \hat{\tau}\in\underset{\tau\in\mathcal{T}}{\operatorname{arg\,min}}\ \operatorname{RSS}(\tau). $$

The argmin notation allows for a tie: if multiple grid candidates share the smallest RSS, all are minimizers. If a single estimate is required, a tie-breaking rule should be stated rather than silently treating one candidate as uniquely best.

Assumptions and scope: At a fixed candidate knot, the usual regression interpretation assumes the conditional mean has the stated segmented form and that errors have mean zero given the predictors. For standard small-sample inference, additional conditions such as independent errors with constant variance, and normal errors for exact \(t\)-based inference, may be used. Choosing the candidate with the smallest RSS is an arithmetic least-squares rule and does not itself require normal errors. Inference that treats a knot selected from the data as if it had been fixed in advance is not automatically justified by fixed-knot results.

Worked Example: Compare Two Candidate Knots

Worked Example: Compare Two Candidate Knots

Suppose a hypothetical set of four observations has predictor values \(x=(-2,-1,1,2)\) and responses \(y=(1,2,4,6)\). Consider the permitted grid \(\mathcal{T}=\{0,0.5\}\). Each candidate has two observations on either side, and the intercept, predictor, and hinge columns are linearly independent for both fits.

For a transparent calculation, a four-observation fit with three linearly independent columns has a one-dimensional residual space. A vector orthogonal to all three columns is therefore enough to obtain the least-squares residuals. At \(\tau=0\), the columns \(1,x,(x-0)_+\) are \((1,1,1,1)\), \((-2,-1,1,2)\), and \((0,0,1,2)\). The vector \(q_0=(1,-2,2,-1)\) is orthogonal to each: its dot products with these columns are \(0\), \(0\), and \(0\). Thus the residual vector is the projection of \(y\) onto \(q_0\):

$$ q_0^\mathsf{T}y=1-4+8-6=-1,\qquad q_0^\mathsf{T}q_0=1+4+4+1=10, $$ $$ e(0)=q_0\frac{q_0^\mathsf{T}y}{q_0^\mathsf{T}q_0} =(-0.1,0.2,-0.2,0.1),\qquad \operatorname{RSS}(0)=\frac{(-1)^2}{10}=0.1000. $$

Subtracting these residuals from the observed responses gives fitted values \((1.1,1.8,4.2,5.9)\). The first two fitted values lie on a line of slope \(0.7\); the last two lie on a line of slope \(1.7\). Both lines meet at fitted value \(2.5\) when \(x=0\). The fitted equation is therefore \(\hat{y}=2.5+0.7x+1.0(x-0)_+\), which checks the continuous-knot form.

At \(\tau=0.5\), the hinge column is \((0,0,0.5,1.5)\). A vector orthogonal to the intercept, predictor, and hinge columns is \(q_{0.5}=(-3,5,-3,1)\). Its dot products with those columns are \(0\), \(0\), and \(0\), respectively. Hence:

$$ q_{0.5}^\mathsf{T}y=-3+10-12+6=1,\qquad q_{0.5}^\mathsf{T}q_{0.5}=9+25+9+1=44, $$ $$ e(0.5)=q_{0.5}\frac{1}{44} =\left(-\frac{3}{44},\frac{5}{44},-\frac{3}{44},\frac{1}{44}\right),\qquad \operatorname{RSS}(0.5)=\frac{1^2}{44}\approx0.02273. $$

The fitted values are the observations minus these residuals: \((47/44,83/44,179/44,263/44)\). The left segment has slope \((83/44-47/44)/1=9/11\); the right segment has slope \((263/44-179/44)/1=21/11\). Both segments meet at \(137/44\) when \(x=0.5\). The fitted equation is \(\hat{y}=119/44+(9/11)x+(12/11)(x-0.5)_+\). Since \(0.02273<0.1000\), the grid search selects \(\hat{\tau}=0.5\). In context, among these two permitted knots, \(0.5\) gives the smaller residual sum of squared response units.

Why the Residual-Projection Calculation Works

The preceding calculation used an orthogonal vector rather than solving the three normal equations directly. Here is the justification. At a fixed candidate \(\tau\), let \(X_\tau\) be the \(n\)-by-3 design matrix whose columns are \(1\), \(x\), and \((x-\tau)_+\). When its columns are linearly independent, least squares chooses coefficients so that the residual vector \(e=y-X_\tau\hat{\beta}\) is orthogonal to every column of \(X_\tau\). This is the least-squares normal-equation condition.

If \(n=4\), the column space has dimension three, so its orthogonal complement has dimension one. Let \(q\) be any nonzero vector in that complement. Every least-squares residual must be a multiple of \(q\), say \(e=cq\). Since \(y-e\) is fitted by the model, the residual must also satisfy \(q^\mathsf{T}e=q^\mathsf{T}y\). Substituting \(e=cq\) gives \(c(q^\mathsf{T}q)=q^\mathsf{T}y\), so \(c=(q^\mathsf{T}y)/(q^\mathsf{T}q)\). Squaring and summing the residuals yields the formula used above:

$$ e=q\frac{q^\mathsf{T}y}{q^\mathsf{T}q}, \qquad \operatorname{RSS}=\frac{(q^\mathsf{T}y)^2}{q^\mathsf{T}q}. $$

This short derivation applies only when the model matrix has full rank and the residual space is one-dimensional. For larger data sets, ordinary least-squares software or the general projection calculation can be used instead; the grid-search principle remains the same.

Worked Example: A Different Response Can Change the Winner

Worked Example: A Different Response Can Change the Winner

Keep the hypothetical predictor values and the grid from the previous example, but suppose the responses are now \(y=(1,3,4,7)\). The candidate design matrices are unchanged, so the same orthogonal vectors give the candidate residual sums of squares.

For \(\tau=0\), \(q_0^\mathsf{T}y=1-6+8-7=-4\), and \(q_0^\mathsf{T}q_0=10\). Therefore \(\operatorname{RSS}(0)=(-4)^2/10=1.600\). The residual vector is \((-0.4,0.8,-0.8,0.4)\), giving fitted values \((1.4,2.2,4.8,6.6)\).

For \(\tau=0.5\), \(q_{0.5}^\mathsf{T}y=-3+15-12+7=7\), and \(q_{0.5}^\mathsf{T}q_{0.5}=44\). Thus \(\operatorname{RSS}(0.5)=7^2/44=49/44\approx1.114\). The residual vector is \((-21/44,35/44,-21/44,7/44)\), and the fitted values are \((65/44,97/44,197/44,301/44)\). Since \(1.114<1.600\), the selected grid knot is again \(0.5\), but the candidate RSS values differ from those in the first example. A breakpoint estimate is determined by the observed responses as well as by the predictor values and permitted grid.

Worked Example: A Grid Search Can Produce a Tie

Worked Example: A Grid Search Can Produce a Tie

Use \(x=(-2,-1,1,2)\), \(\mathcal{T}=\{0,0.5\}\), and the hypothetical responses \(y=(-1,1,5,7)\). These responses satisfy \(y=3+2x\) exactly. For either candidate knot, set \(\beta_0=3\), \(\beta_1=2\), and \(\beta_2=0\). The hinge coefficient is zero, so the fitted values are exactly \((-1,1,5,7)\) regardless of \(\tau\).

Every residual is \(0\), and hence \(\operatorname{RSS}(0)=0\) and \(\operatorname{RSS}(0.5)=0\). Both candidates minimize RSS; the data do not select one uniquely from this grid. In particular, a grid-search minimizer should not automatically be interpreted as evidence that a slope change is present. Here the least-squares fit is a straight line and all candidate knots tie.

Interpreting and Reporting the Selected Knot

The minimum-RSS candidate is the best-fitting candidate under the specified model, grid, and fitting criterion. It is not necessarily the exact location of a physical or biological transition, and it should not be reported with more precision than the grid supports. If the grid uses increments of \(0.5\) predictor units, the search cannot distinguish between values separated by less than that spacing.

A concise report should identify the permitted grid or its resolution, state the selected knot in predictor units, and give the candidate RSS values when useful. For example: “Among candidate knots from 0 to 2 in increments of 0.5, the knot at 0.5 predictor units had the smallest RSS.” This describes the computation without claiming that the knot causes a change in response.

The RSS comparison alone does not quantify uncertainty in a knot chosen from the data. Results for a fixed, prespecified knot address a different setup; after searching, the choice itself depends on the observed responses. Likewise, a finer grid can change the minimizing candidate, but adding grid points does not by itself establish that the segmented model is preferable to a simpler model.

Common Mistakes

  • Using the wrong hinge values. For a candidate \(\tau\), values at or below the knot are zero; values above it are \(x_i-\tau\). Recompute the hinge column for every candidate.
  • Comparing coefficients instead of fit criteria. The coefficients change with the hinge column and do not by themselves identify the best candidate. Compute each candidate's RSS from its own fitted values or residuals.
  • Calling the first minimum a unique estimate. If multiple candidates have the same minimum RSS, report a tie or apply a stated tie-breaking rule.
  • Treating the selected knot as prespecified. The grid search uses the observed responses to choose a knot. Fixed-knot uncertainty calculations do not automatically account for that search.
  • Overstating precision. A search over a coarse grid selects among its listed values; it does not locate a breakpoint more finely than the grid allows.
Key takeaway: Specify a defensible candidate grid, fit the same continuous segmented regression at each candidate, verify that each fit is estimable, and select a candidate with the smallest RSS. Report ties and grid resolution, and interpret the result as the best candidate in that search—not as a causal conclusion or an uncertainty statement.

Check Your Understanding

Answer these questions using the definitions and calculations in this tutorial.

  1. For a candidate knot \(\tau\), write the continuous hinge model and state its left- and right-segment slopes.
  2. Why must the hinge column be recalculated for every candidate knot?
  3. If two candidates have RSS values of 4.20 and 3.75, which candidate is selected, and what does that conclusion mean?
  4. What does a grid search report when two candidates have the same minimum RSS?
  5. Why does selecting a knot from the data not automatically justify treating it as fixed when reporting uncertainty?

Previous

Next

Back to Tutorials