Exhaustive Best-Subset Search

What Exhaustive Best-Subset Search Does

With several candidate predictors, there are many possible regression models: one might include a single predictor, another a different pair, and another all available predictors. Exhaustive best-subset search makes the comparison systematic. For each chosen model size, it fits every predictor subset of that size and identifies the subset with the smallest residual sum of squares.

The search answers a specific question: among all models containing exactly \(k\) candidate predictors, which has the lowest least-squares residual sum of squares? It answers that question for each possible \(k\). It does not, by itself, decide which model size should ultimately be used. The comparisons here use the same response observations, the same response scale, and the same intercept convention throughout.

Definition: Suppose there are \(p\) candidate predictors, \(x_1,\ldots,x_p\). A subset \(S\) is a set of predictors included in a regression model. Its size is the number of predictors it contains, written \(|S|\). The best subset of size \(k\) is a subset \(S\) with \(|S|=k\) whose fitted least-squares model has the smallest residual sum of squares, \(RSS(S)\), among all subsets of size \(k\).

For each subset \(S\), the usual model in this search includes an intercept and the predictors in \(S\):

y_i=\beta_0+\sum_{j\in S}\beta_j x_{ij}+\varepsilon_i,\qquad i=1,\ldots,n.

The least-squares fit chooses the coefficients to minimize \(RSS(S)=\sum_{i=1}^n (y_i-\hat{y}_i)^2\). For the search calculations to be comparable, use the same \(n\) observations and response in every fit. We will assume the intercept and included predictor columns are linearly independent in each candidate model, so each set of coefficients is uniquely determined. The calculation of least-squares fits and their RSS values does not require normally distributed errors. As always, a search result does not establish that the model form or its assumptions are appropriate for a particular application.

How Many Models Must Be Fitted?

A subset with \(k\) predictors is formed by choosing \(k\) of the \(p\) candidates. The number of such subsets is the binomial coefficient \(\binom{p}{k}\). Across all sizes, every predictor has two possibilities—either it is included or it is not—so there are \(2^p\) subsets in total, including the empty subset with no predictors.

Worked Example: Counting Four-Predictor Subsets

Suppose the candidate predictors are \(x_1,x_2,x_3,x_4\). The number of subsets at each size is:

Size 0: \(\binom{4}{0}=1\), the intercept-only model.
Size 1: \(\binom{4}{1}=4\), one for each individual predictor.
Size 2: \(\binom{4}{2}=6\), one for each pair.
Size 3: \(\binom{4}{3}=4\), one for each triple.
Size 4: \(\binom{4}{4}=1\), the model with all four predictors.

The total is \(1+4+6+4+1=16=2^4\) subsets. To find the best subset at size 2, for example, the search must fit all six pairs. Fitting just a pair chosen in advance would not be an exhaustive size-2 search.

Comparing Subsets by Residual Sum of Squares

Within one fixed size, the rule is direct: calculate the RSS for every subset and select the subset or subsets attaining the minimum. Lower RSS means the fitted values leave less squared residual variation in these observations. Because the response and observations are held fixed, RSS comparisons within this search are on the same scale.

Here is a useful justification for a basic pattern in the results. If \(S\) is contained in a larger subset \(T\), the model for \(T\) can reproduce the fit for \(S\) by setting the coefficients of the added predictors to zero. Since least squares for \(T\) minimizes RSS over a model space that includes that possibility, it cannot have larger RSS:

S\subseteq T\quad\Longrightarrow\quad RSS(T)\leq RSS(S).

This nesting result applies to a particular model and its expanded version. It does not say that every subset of size \(k+1\) must have lower RSS than every subset of size \(k\); those are different models and their predictor sets need not be nested. It also explains why the minimum RSS across sizes will ordinarily decrease as the size grows, which is one reason RSS alone does not determine the preferred model size.

Worked Example: Exhaustive Search With Four Predictors

Consider a hypothetical six-observation data set with four centered, mutually orthogonal predictor columns. Each predictor column has sum of squares 1. The centered response has sum of squares \(SST=200\), and its squared projection onto \(x_1,x_2,x_3,x_4\) is, respectively, 50, 40, 56, and 30. The part of the response orthogonal to all four predictors has sum of squares 24. These are sufficient data summaries for the RSS calculations below; they are mutually consistent because \(50+40+56+30+24=200\). The intercept is included in every model.

Orthogonality makes the calculation especially transparent: including predictor \(x_j\) removes its projection sum of squares from the residual sum of squares. Thus, for a subset \(S\), \(RSS(S)=200-\sum_{j\in S}c_j\), where \(c_1=50\), \(c_2=40\), \(c_3=56\), and \(c_4=30\). For example, the model containing \(x_3\) alone has

RSS(\{x_3\})=200-56=144.

The full enumeration is:

Number of predictors	Subset	RSS
0	\(\varnothing\)	200
1	\(\{x_1\}\)	150
1	\(\{x_2\}\)	160
1	\(\{x_3\}\)	144
1	\(\{x_4\}\)	170
2	\(\{x_1,x_2\}\)	110
2	\(\{x_1,x_3\}\)	94
2	\(\{x_1,x_4\}\)	120
2	\(\{x_2,x_3\}\)	104
2	\(\{x_2,x_4\}\)	130
2	\(\{x_3,x_4\}\)	114
3	\(\{x_1,x_2,x_3\}\)	54
3	\(\{x_1,x_2,x_4\}\)	80
3	\(\{x_1,x_3,x_4\}\)	64
3	\(\{x_2,x_3,x_4\}\)	74
4	\(\{x_1,x_2,x_3,x_4\}\)	24

For instance, the pair \(\{x_1,x_3\}\) has \(RSS=200-50-56=94\); the triple \(\{x_1,x_2,x_3\}\) has \(RSS=200-50-40-56=54\). Checking all candidates at each size gives these best subsets:

Size 0: the intercept-only model, with \(RSS=200\).
Size 1: \(\{x_3\}\), with \(RSS=144\).
Size 2: \(\{x_1,x_3\}\), with \(RSS=94\).
Size 3: \(\{x_1,x_2,x_3\}\), with \(RSS=54\).
Size 4: \(\{x_1,x_2,x_3,x_4\}\), with \(RSS=24\).

The minima are calculated separately within each size. For size 2, for example, \(94\) is less than each of the other five pair RSS values, so \(\{x_1,x_3\}\) is the best pair. The table does not show that this pair is preferable to the best triple or to the best single-predictor model; those models have different sizes.

What the Search Result Means

The output of exhaustive best-subset search is a sequence of best-fitting subsets, one for each model size. It is a search procedure, not a single universal measure of predictive or scientific quality. The subset with the smallest RSS overall will be the largest candidate model when models are nested and the full set is available, but that does not automatically make the largest model the preferred one. RSS rewards improved fit without, by itself, accounting for model complexity.

A separate model-comparison rule may be used to compare sizes. The key distinction is that best subset at size \(k\) is defined by comparing only models of size \(k\). Keeping that question separate prevents the search algorithm from being mistaken for a final model-selection rule.

Worked Example: A Tie Among Best Subsets

Suppose a different hypothetical data set has centered response sum of squares 100 and three mutually orthogonal centered predictors. Their respective projection sums of squares are 30, 30, and 10; the remaining response sum of squares is 30. For every subset, compute RSS as 100 minus the projection sums for its included predictors:

Size	Subset	RSS
0	\(\varnothing\)	100
1	\(\{x_1\}\)	70
1	\(\{x_2\}\)	70
1	\(\{x_3\}\)	90
2	\(\{x_1,x_2\}\)	40
2	\(\{x_1,x_3\}\)	60
2	\(\{x_2,x_3\}\)	60
3	\(\{x_1,x_2,x_3\}\)	30

At size 1, the minimum RSS is 70, attained by both \(\{x_1\}\) and \(\{x_2\}\). Therefore there are two best subsets of size 1; an exhaustive search should report the tie, not break it arbitrarily and imply that one has a lower RSS. At size 2, the best subset is \(\{x_1,x_2\}\), with RSS 40. Equal RSS values establish a tie according to this criterion, but do not establish that the models are identical in every other respect.

Common Pitfalls

Fitting only one candidate at a given size. A selected pair is not known to be the best pair until its RSS has been compared with the RSS values of all other pairs.
Comparing different sample sets or response scales. RSS values are meaningfully comparable in this procedure when they come from fits to the same response observations on the same scale.
Treating the lowest RSS as the final model choice. The lowest RSS across sizes usually belongs to the largest model. Exhaustive search identifies the best subset at each size; RSS alone does not balance fit and complexity.
Assuming every larger subset beats every smaller one. RSS cannot increase when a particular model is expanded to include more predictors, but the best subset of a larger size need not contain the best subset of a smaller size.
Failing to report a tie. If multiple subsets share the lowest RSS at a size, each is a best subset under the stated rule.

Key takeaway: Exhaustive best-subset search fits every candidate predictor subset, groups the fits by number of predictors, and finds the minimum RSS within each group. Its result is a best-fitting subset at each size, not a decision about which size should be selected.

Check Your Understanding

Answer each question using the definition and search procedure above.

With five candidate predictors, how many subsets must be fitted at size 2, and how many subsets are there across all sizes?
What condition on the data and fits is needed for RSS comparisons across candidate subsets to be meaningful?
If a size-3 subset has lower RSS than a size-2 subset, does that prove the size-3 subset is the best at its size? Explain.
Why can adding a predictor to a particular model not increase its least-squares RSS?
If two single-predictor models have the same minimum RSS, what should the exhaustive search report?

What You'll Learn