One Dataset, Three Search Paths
Exhaustive best subset, forward selection, and backward elimination all compare regression models built from the same candidate predictors, but they reach those models differently. Exhaustive search evaluates every subset. Forward selection adds predictors one at a time, while backward elimination removes them one at a time. Since the latter two methods commit to earlier choices, their candidate paths need not contain the best subset of every size.
To compare these methods fairly, use the same response observations, candidate predictors, intercept convention, and model score throughout. The small hypothetical dataset below makes the paths and the score calculations explicit. Its deliberately constructed predictor relationships also show why a good one-predictor model need not be part of the best two-predictor model.
The usual linear regression model writes each response as a linear mean plus an error. For statistical interpretation, the standard assumptions are independent errors with mean zero and common variance; normality is additionally used for exact small-sample inference, but is not needed for the least-squares calculations or the search paths here. The predictors and response below are centered, so the fitted intercept is zero. It is still included in every candidate model.
The Dataset and the Candidate Models
There are eight observations. The table reports \(\sqrt{8}\) times each variable, so the entries are integers; divide each displayed entry by \(\sqrt{8}\) to obtain the actual observation. Define four centered, mutually orthogonal vectors \(a,b,c,r\) by the sign columns below, each divided by \(\sqrt{8}\). Each vector has squared length one. The three predictors are \(x_1=a\), \(x_2=b\), and \(x_3=a+b+c\); the response is \(y=3a+3b+2r\).
| Observation | \(\sqrt{8}x_1\) | \(\sqrt{8}x_2\) | \(\sqrt{8}c\) | \(\sqrt{8}r\) | \(\sqrt{8}x_3\) | \(\sqrt{8}y\) |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 3 | 8 |
| 2 | 1 | 1 | -1 | -1 | 1 | 4 |
| 3 | 1 | -1 | 1 | -1 | 1 | -2 |
| 4 | 1 | -1 | -1 | 1 | -1 | 2 |
| 5 | -1 | 1 | 1 | 1 | 1 | 2 |
| 6 | -1 | 1 | -1 | -1 | -1 | -2 |
| 7 | -1 | -1 | 1 | -1 | -1 | -8 |
| 8 | -1 | -1 | -1 | 1 | -3 | -4 |
Because \(a,b,c,r\) are orthogonal unit vectors, the response sum of squares is \(y^\mathsf{T}y=3^2+3^2+2^2=22\). The predictor \(x_3=a+b+c\) has squared length \(3\), and its inner product with \(y\) is \(3+3+0=6\). These inner products make the least-squares fits straightforward to verify.
Worked Example: Exhaustive Best Subset
Worked Example: Exhaustive Best Subset
Compute the residual sum of squares and common score for each candidate model size, then identify the model chosen by exhaustive search. Use \(Q(M)=\operatorname{RSS}(M)+2k(M)\).
Method. Exhaustive search compares all \(2^3=8\) predictor subsets. For one predictor \(x\), the fitted coefficient is \((x^\mathsf{T}y)/(x^\mathsf{T}x)\), and the reduction in RSS is \((x^\mathsf{T}y)^2/(x^\mathsf{T}x)\).
For \(x_1\), the inner product with \(y\) is \(3\) and its squared length is \(1\), so its reduction is \(3^2/1=9\). Its RSS is \(22-9=13\), and its score is \(13+2(1)=15\). The same calculation for \(x_2\) gives RSS \(22-3^2=13\) and score \(15\). For \(x_3\), the reduction is \(6^2/3=12\), giving RSS \(22-12=10\) and score \(10+2=12\).
The pair \(x_1,x_2\) spans \(a\) and \(b\). Its fitted response is \(3a+3b\), leaving residual \(2r\). Thus its RSS is \(\|2r\|^2=4\), and its score is \(4+2(2)=8\). The pair \(x_1,x_3\) spans \(a\) and \(b+c\). After fitting \(a\), the response component in the direction \(b+c\) has coefficient \(3/2\), since \((3b)^\mathsf{T}(b+c)/\|b+c\|^2=3/2\). The part of \(3b\) left after this projection is \(1.5b-1.5c\), with squared length \(1.5^2+1.5^2=4.5\); the unmodelled component \(2r\) contributes \(4\). Therefore its RSS is \(4.5+4=8.5\) and its score is \(8.5+4=12.5\). By symmetry, \(x_2,x_3\) also have RSS \(8.5\) and score \(12.5\).
The full model spans \(a,b,c\). It fits \(3a+3b\), while \(2r\) remains, so its RSS is \(4\) and its score is \(4+2(3)=10\). The empty model has RSS \(22\) and score \(22\).
| Subset | Number of predictors \(k\) | RSS | Score \(Q\) |
|---|---|---|---|
| Empty | 0 | 22 | 22 |
| \(x_1\) or \(x_2\) | 1 | 13 | 15 |
| \(x_3\) | 1 | 10 | 12 |
| \(x_1,x_2\) | 2 | 4 | 8 |
| \(x_1,x_3\) or \(x_2,x_3\) | 2 | 8.5 | 12.5 |
| \(x_1,x_2,x_3\) | 3 | 4 | 10 |
The exhaustive winner under the common score is \(x_1,x_2\), with score \(8\). The full model has the same RSS but a larger penalty.
Worked Example: Forward Selection
Worked Example: Forward Selection
Trace forward selection, which starts with no predictors and adds the predictor that gives the smallest RSS at each step. If a step has a tie, choose the lower-numbered predictor. Then select the lowest-score model along the resulting path.
Step 1: choose one predictor. The one-predictor RSS values are \(13\) for \(x_1\), \(13\) for \(x_2\), and \(10\) for \(x_3\). Forward selection adds \(x_3\). Its score is \(10+2=12\).
Step 2: add a second predictor. Adding \(x_1\) gives the model \(x_1,x_3\) with RSS \(8.5\). Adding \(x_2\) gives \(x_2,x_3\), also with RSS \(8.5\). The specified tie rule chooses \(x_1\), so the path reaches \(x_1,x_3\). Its score is \(8.5+2(2)=12.5\).
Step 3: add the remaining predictor. The full model has RSS \(4\) and score \(4+2(3)=10\). The path’s scores are therefore \(22\) for the empty model, \(12\) for \(x_3\), \(12.5\) for \(x_1,x_3\), and \(10\) for the full model. The smallest is \(10\), so the lowest-score model on the forward path is the full model.
The method did not reach \(x_1,x_2\). Its first decision was to add \(x_3\), and forward selection never removes a predictor already added. This example shows how a greedy path can exclude a better subset under the common score.
Worked Example: Backward Elimination
Worked Example: Backward Elimination
Trace backward elimination from the full model. At each step, remove the predictor whose removal gives the smallest RSS; break any tie by removing the higher-numbered predictor. Compare the scores along this path.
Step 1: remove one predictor from the full model. Removing \(x_3\) leaves \(x_1,x_2\), with RSS \(4\). Removing \(x_1\) leaves \(x_2,x_3\), with RSS \(8.5\). Removing \(x_2\) leaves \(x_1,x_3\), also with RSS \(8.5\). The smallest RSS is \(4\), so backward elimination removes \(x_3\) and reaches \(x_1,x_2\). Its score is \(4+4=8\).
Step 2: remove one more predictor. Removing either \(x_1\) or \(x_2\) leaves a one-predictor model with RSS \(13\). The tie rule removes \(x_2\), leaving \(x_1\), whose score is \(13+2=15\).
The remaining path models are the full model (score \(10\)), \(x_1,x_2\) (score \(8\)), \(x_1\) (score \(15\)), and the empty model (score \(22\)). The lowest-score model on this path is \(x_1,x_2\), matching the exhaustive winner.
Why the Paths Differ
Exhaustive search chooses the best-scoring subset from all eight possibilities. Forward selection and backward elimination examine restricted paths through those possibilities. In this dataset, \(x_3\) has the smallest RSS among the single-predictor models, but adding it first prevents forward selection from reaching the best-scoring pair \(x_1,x_2\). Backward elimination starts with all predictors and removes \(x_3\), so it does reach that pair.
A frequent mistake is to claim that forward selection must find the best pair because it considers two-predictor models. That is not generally true: it considers only pairs containing the predictor it chose first. Here, the incorrect argument would be, “The best pair is \(x_1,x_2\), so forward selection will compare it with the other pairs.” The correction is to trace the actual path: its best one-predictor model is \(x_3\), so its next candidates are only \(x_1,x_3\) and \(x_2,x_3\). Neither is \(x_1,x_2\).
The result also depends on the specified score. Raw RSS alone always stays the same or decreases as predictors are added, so it cannot by itself reward parsimony. Here the penalty \(2k\) is applied consistently to every model, with \(k\) counting slope predictors and not the intercept. Changing the penalty could change the selected model, but it would not change the RSS-based paths traced above. The search comparison is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Check Your Understanding
Use the dataset and score defined above unless a question specifies a different penalty.
- For the one-predictor model containing only \(x_3\), calculate its least-squares coefficient, RSS, and score. (Answer: coefficient \(2\), RSS \(10\), score \(12\).)
- At the second step of forward selection, what are the two candidate models and their RSS values? (Answer: \(x_1,x_3\) and \(x_2,x_3\), each with RSS \(8.5\).)
- Suppose the score is changed to \(Q=\operatorname{RSS}+3k\). Compare the scores for \(x_1,x_2\) and the full model. Which has the lower score? (Answer: \(x_1,x_2\) scores \(4+3(2)=10\); the full model scores \(4+3(3)=13\), so \(x_1,x_2\) is lower.)
- From the full model, what are the RSS values after removing \(x_1\), \(x_2\), and \(x_3\), respectively? Which predictor does backward elimination remove first? (Answer: \(8.5,\ 8.5,\ 4\), respectively; it removes \(x_3\).)
- Why can forward selection fail to reach \(x_1,x_2\), even though it adds two predictors? (Answer: it first adds \(x_3\), and its add-only path can then reach only pairs containing \(x_3\), not \(x_1,x_2\).)