A Small Exhaustive Search Worked Example

What an Exhaustive Search Produces

With three available predictors, there are eight possible subsets, including the model with no predictors and the model with all three. An exhaustive best-subset search fits every candidate model and compares their residual sums of squares (RSS). Its basic output is not just one selected model: it identifies the candidate with the smallest RSS at each predictor count.

That distinction matters. The best model among those with one predictor need not be the best among those with two. And finding the best candidate at each size does not, by itself, determine which size should be chosen overall. Here the focus is the complete search and its within-size comparisons.

Definition: For a set of available predictors \(x_1,\ldots,x_p\), a candidate subset \(S\) is any subset of \(\{1,\ldots,p\}\). Its least-squares regression model includes an intercept and the predictors whose indices belong to \(S\). The model size is \(|S|\), the number of included predictors; the intercept is not counted. The residual sum of squares is the sum of squared differences between observed and fitted response values for that model.

For three predictors, the complete search has \(2^3=8\) candidates: one with zero predictors, three with one, three with two, and one with three. A reliable table records the subset, its size, and its RSS. The minimum RSS within each size is then easy to identify without confusing the candidates.

A Useful Calculation When Predictors Are Orthogonal

For a hand-worked example, suppose the predictor columns have been centered and are mutually orthogonal: \(x_j^\mathsf{T}x_k=0\) whenever \(j\ne k\). Suppose also that the full-model residual \(e\) is orthogonal to the intercept and to all three predictor columns. Write the centered response as \(y=\beta_1x_1+\beta_2x_2+\beta_3x_3+e\). These conditions let us calculate every subset’s RSS from the full-model RSS and the contribution of each omitted predictor.

Result for an orthogonal design: If \(R_{\mathrm{full}}\) is the full-model RSS, then the RSS for a subset \(S\) is \(R(S)=R_{\mathrm{full}}+\sum_{j\notin S}\beta_j^2(x_j^\mathsf{T}x_j)\). The result depends on the stated orthogonality conditions; for correlated predictors, omitting a predictor can change the fitted coefficients of the included predictors, so this shortcut generally does not apply. Fit and compare each subset instead.

The omitted-predictor contribution is the squared length of the part of the response along that predictor. The formula follows by decomposing the residual from the subset model into the full-model residual plus the omitted predictor components.

y-\widehat y_S=e+\sum_{j\notin S}\beta_jx_j

By assumption, \(e\) is orthogonal to every \(x_j\), and distinct predictor columns are orthogonal to one another. Therefore, when the residual is squared and summed, all cross-product terms are zero. The squared length is the sum of the separate squared lengths:

\begin{aligned} R(S) &=(y-\widehat y_S)^\mathsf{T}(y-\widehat y_S)\\ &=e^\mathsf{T}e+\sum_{j\notin S}\beta_j^2x_j^\mathsf{T}x_j\\ &=R_{\mathrm{full}}+\sum_{j\notin S}\beta_j^2(x_j^\mathsf{T}x_j). \end{aligned}

This is a calculation aid for suitably orthogonal data, not a general replacement for fitting subset models. The exhaustive-search procedure itself works for any design: list the subsets, fit each one, record its RSS, and take the minimum within each size.

Worked Example: Completing All Eight Fits From Orthogonal Contributions

In a hypothetical risk-modeling study, three centered predictor columns represent engineered rating measures. They are mutually orthogonal. For the full regression, the fitted coefficients are \(\beta_1=1\), \(\beta_2=-2\), and \(\beta_3=0.5\); the predictor squared lengths are \(x_1^\mathsf{T}x_1=4\), \(x_2^\mathsf{T}x_2=3\), and \(x_3^\mathsf{T}x_3=8\). The full-model RSS is 1. Calculate the RSS of every subset and identify the best subset at each size.

Step 1: Calculate the three contributions. For predictor 1, the contribution is \(1^2(4)=4\). For predictor 2, it is \((-2)^2(3)=4(3)=12\). For predictor 3, it is \((0.5)^2(8)=0.25(8)=2\). Thus the contribution values are 4, 12, and 2, and the full-model RSS is 1.

Step 2: Calculate each subset’s RSS. Add the full-model RSS to the contributions of the omitted predictors. For the empty subset, \(1+4+12+2=19\). For \(\{x_1\}\), \(1+12+2=15\); for \(\{x_2\}\), \(1+4+2=7\); and for \(\{x_3\}\), \(1+4+12=17\). For \(\{x_1,x_2\}\), \(1+2=3\); for \(\{x_1,x_3\}\), \(1+12=13\); and for \(\{x_2,x_3\}\), \(1+4=5\). The full subset has RSS 1.

Predictor subset	Model size	RSS
\(\varnothing\)	0	19
\(\{x_1\}\)	1	15
\(\{x_2\}\)	1	7
\(\{x_3\}\)	1	17
\(\{x_1,x_2\}\)	2	3
\(\{x_1,x_3\}\)	2	13
\(\{x_2,x_3\}\)	2	5
\(\{x_1,x_2,x_3\}\)	3	1

Step 3: Compare within each size. The size-zero candidate has RSS 19. Among size-one candidates, the minimum is 7 for \(\{x_2\}\). Among size-two candidates, the minimum is 3 for \(\{x_1,x_2\}\). The only size-three candidate is the full model, with RSS 1. These are the best candidates at their respective sizes.

Method and mistake avoided. This is exhaustive enumeration using omitted contributions. A common mistake is to omit the wrong contribution or miscalculate it: the RSS for \(\{x_1\}\) is \(1+12+2=15\), not 14, and the RSS for \(\{x_2\}\) is \(1+4+2=7\), not 5. Check that each subset adds precisely the contributions for predictors it leaves out.

Repeat the Bookkeeping With a Different Set of Contributions

A useful check on the method is to rebuild the table for different values rather than relying on a remembered pattern. In the next example, the predictors again satisfy the orthogonality conditions, but the contributions change. Each subset’s RSS still comes from the same omitted-component calculation.

Worked Example: Finding the Best Candidate at Each Size

A hypothetical portfolio study uses three orthogonal, centered predictors. The contributions \(\beta_j^2(x_j^\mathsf{T}x_j)\) are 9 for \(x_1\), 4 for \(x_2\), and 16 for \(x_3\), and the full-model RSS is 2. Calculate the RSS for all eight subsets and state the winner at each size.

Step 1: Start with the empty model. It omits all three predictors, so its RSS is \(2+9+4+16=31\).

Step 2: Calculate the size-one models. The model containing \(x_1\) omits \(x_2\) and \(x_3\), giving \(2+4+16=22\). The model containing \(x_2\) gives \(2+9+16=27\). The model containing \(x_3\) gives \(2+9+4=15\).

Step 3: Calculate the size-two models. The model \(\{x_1,x_2\}\) omits \(x_3\), so its RSS is \(2+16=18\). The model \(\{x_1,x_3\}\) omits \(x_2\), giving \(2+4=6\). The model \(\{x_2,x_3\}\) omits \(x_1\), giving \(2+9=11\). The full model has RSS 2.

Size	Candidate RSS values	Best candidate at that size
0	\(\varnothing:31\)	\(\varnothing\), RSS 31
1	\(\{x_1\}:22,\ \{x_2\}:27,\ \{x_3\}:15\)	\(\{x_3\}\), RSS 15
2	\(\{x_1,x_2\}:18,\ \{x_1,x_3\}:6,\ \{x_2,x_3\}:11\)	\(\{x_1,x_3\}\), RSS 6
3	\(\{x_1,x_2,x_3\}:2\)	\(\{x_1,x_2,x_3\}\), RSS 2

Conclusion. The best size-one model is \(\{x_3\}\), and the best size-two model is \(\{x_1,x_3\}\). The table shows which candidates win at each size; it does not, by itself, establish a preferred size. Selecting a size requires a separate model-comparison objective.

Method and mistake avoided. Classify each RSS by its omitted predictors before doing the addition. For example, \(\{x_1,x_3\}\) omits only \(x_2\), so its RSS is \(2+4=6\), not \(2+9=11\). The latter is the RSS for \(\{x_2,x_3\}\), which omits \(x_1\).

Exact Size and a Size Constraint Are Different Questions

A fixed-size comparison asks which subset of exactly \(k\) predictors has the smallest RSS. A size-constrained comparison asks which candidate has the smallest RSS among a specified collection, such as all models with at most two predictors. These questions can have different answers because the second comparison includes models of multiple sizes.

Worked Example: Comparing Candidates With at Most Two Predictors

A hypothetical claims study has three orthogonal predictors with contributions 5 for \(x_1\), 8 for \(x_2\), and 1 for \(x_3\). The full-model RSS is 3. Find the best model of exactly one predictor, the best model of exactly two predictors, and the lowest-RSS candidate among models with at most two predictors.

Step 1: Find the exact size-one winner. The empty model has RSS \(3+5+8+1=17\). The three one-predictor RSS values are: \(\{x_1\}\), \(3+8+1=12\); \(\{x_2\}\), \(3+5+1=9\); and \(\{x_3\}\), \(3+5+8=16\). The size-one winner is \(\{x_2\}\), with RSS 9.

Step 2: Find the exact size-two winner. The pair \(\{x_1,x_2\}\) omits \(x_3\), so its RSS is \(3+1=4\). The pair \(\{x_1,x_3\}\) omits \(x_2\), so its RSS is \(3+8=11\). The pair \(\{x_2,x_3\}\) omits \(x_1\), so its RSS is \(3+5=8\). The size-two winner is \(\{x_1,x_2\}\), with RSS 4.

Step 3: Compare all candidates of size at most two. The best RSS at size zero is 17, at size one it is 9, and at size two it is 4. Comparing \(17\), \(9\), and \(4\), the lowest is 4, so the best candidate among these sizes is \(\{x_1,x_2\}\).

Method and mistake avoided. First find the minimum within each exact size, then compare those minima for the at-most-size question. Do not report the size-one winner as the answer to the at-most-two question without checking the size-two candidates.

Checks That Make an Exhaustive Table Reliable

A complete search is small enough that its bookkeeping should be explicit. Use these checks when constructing or interpreting a table:

List every subset once, including the empty subset and the full subset.
Count the intercept as part of every fitted regression, but not as a predictor when reporting model size.
For an omitted-contribution calculation, identify exactly which predictors are absent before adding their contributions to the full-model RSS.
Within each size, compare only candidates of that size before naming the winner.
Do not infer from a winner-at-each-size table alone that a particular size is preferred overall.

For a nonorthogonal design, retain the exhaustive-search logic but not the shortcut formula: fit each candidate subset by least squares and record its RSS. The coefficient estimates for a subset can differ from those in the full model, so simply adding the full-model coefficients’ squared contributions for omitted predictors will generally give incorrect values.

Key takeaway: An exhaustive search with three predictors contains eight candidate models. Record each subset and its RSS, then identify the minimum separately for sizes zero, one, two, and three. Verify every omitted-predictor calculation, and keep the fixed-size result distinct from any decision about model size.

Check Your Understanding

For each question, use the orthogonal-contribution formula when its assumptions are stated. Each scenario is hypothetical.

A three-predictor model has orthogonal centered predictors, full-model RSS \(0.5\), and contributions 3, 5, and 2 for \(x_1,x_2,x_3\), respectively. Calculate the three one-predictor RSS values and name the best size-one subset. (Answer: RSS values are 7.5 for \(\{x_1\}\), 5.5 for \(\{x_2\}\), and 8.5 for \(\{x_3\}\); best is \(\{x_2\}\).)
For orthogonal predictors with full-model RSS 2 and contributions 4, 10, and 1, calculate all three one-predictor RSS values. Which subset is best at size one? (Answer: 13 for \(\{x_1\}\), 7 for \(\{x_2\}\), and 16 for \(\{x_3\}\); best is \(\{x_2\}\).)
With full-model RSS 1 and contributions 2, 6, and 9, find every size-two RSS and identify the winner. (Answer: \(\{x_1,x_2\}\) has RSS 10, \(\{x_1,x_3\}\) has RSS 7, and \(\{x_2,x_3\}\) has RSS 3; best is \(\{x_2,x_3\}\).)
With full-model RSS 4 and contributions 7, 3, and 5, compare the best candidate of each size from zero through two. Which is best among models with at most two predictors? (Answer: the best RSS values for sizes 0, 1, and 2 are 19, 12, and 7; the best at-most-two candidate is \(\{x_1,x_3\}\), RSS 7.)
A three-predictor orthogonal model has full-model RSS 2 and contributions 1, 4, and 6. Find the best subset at sizes one and two. (Answer: size one, \(\{x_3\}\), RSS 7; size two, \(\{x_2,x_3\}\), RSS 3.)

What You'll Learn