Introduction
A predictor-subset search does not necessarily fit every possible model. Forward selection starts with a small model and considers additions to the current model. Backward elimination starts with a large model and considers deletions from it. At each step, the algorithm evaluates a limited set of candidates, chooses one, and continues from that choice. The resulting path depends on the current model, not just on the total number of available predictors.
To interpret a search correctly, distinguish the candidate models evaluated at a step from the selected models retained along the path. A model can be evaluated and rejected; another model may not be evaluated at all. Neither search should be mistaken for an exhaustive comparison of all subsets.
The Full Subset Space and a Greedy Path
Every predictor can either be included or excluded. Therefore, with \(p\) predictors, the full subset space contains \(2^p\) models, including the intercept-only model with no predictors. If a search targets a particular size \(k\), there are \(\binom{p}{k}\) models of that size. The full space includes models that a path-based procedure may never evaluate.
At a forward step from a model of size \(k\), exactly \(p-k\) one-predictor additions are candidates. At a backward step from a model of size \(k\), exactly \(k\) one-predictor deletions are candidates. These counts follow directly from the available choices: forward selection can add any predictor not already present, while backward elimination can remove any predictor currently present.
These are local candidate sets. Once a model is selected, the next candidate set is formed from that selected model alone. For example, if forward selection chooses \(C\), its next step considers additions to \(C\), not additions to some other one-predictor model that it rejected at the first step.
Worked Example: Counting What a Search Can Examine
A pricing analyst has five candidate predictors, \(A,B,C,D,E\), and wants to compare models of size two. How many models are in the full subset space, how many models have size two, and how many size-two candidates does forward selection examine if its first selected predictor is \(C\)?
Method. Count all inclusion-or-exclusion choices for the full space, use a combination for models of a fixed size, and form the forward candidate set from the chosen first predictor.
There are five predictors, each with two possible statuses, so the full subset space has \(2^5=32\) models. This count includes the empty subset and the full five-predictor model.
The number of size-two models is \( \binom{5}{2}=\frac{5\cdot4}{2\cdot1}=10 \).
If the first selected model is \(\{C\}\), the predictors still available to add are \(A,B,D,E\). Thus the four size-two candidates are \(\{A,C\},\{B,C\},\{C,D\},\{C,E\}\).
Check. There are ten size-two models in total, but this particular forward step examines only four of them. Each of those four contains \(C\), so the other six size-two models cannot be in this step’s candidate set.
Common mistake avoided. It would be wrong to say that the forward step compares all ten size-two models. It compares only the four extensions of the model already selected.
A Worked Comparison of Forward and Backward Candidates
The next example uses a single hypothetical least-squares analysis to trace both directions. Each model includes an intercept, all models use the same response and observations, and the reported values are training residual sums of squares (RSS). For this example, each search chooses the candidate with the smallest RSS at its current step. Because the candidates within a step have the same number of predictors, this rule compares their training fit at that step.
The RSS values below are a hypothetical fit ledger, not observations from an actual insurer or other organization. The values are constructed so that both paths can be traced and compared.
Worked Example: Different Size-Two Candidates on the Two Paths
Five predictors \(A,B,C,D,E\) are available. The intercept-only model has RSS \(100\). The single-predictor RSS values are \(A:90\), \(B:92\), \(C:80\), \(D:94\), and \(E:93\). The forward candidates formed by adding one predictor to \(C\) have RSS values \(AC:70\), \(BC:74\), \(CD:75\), and \(CE:73\).
For backward elimination, the full model \(ABCDE\) has RSS \(30\). Its deletion candidates have these values: \(ABCD:34\), \(ABCE:32\), \(ABDE:50\), \(ACDE:33\), and \(BCDE:38\). From \(ABCE\), the size-three candidates have RSS values \(BCE:42\), \(ACE:38\), \(ABE:55\), and \(ABC:39\). From \(ACE\), the size-two candidates have RSS values \(CE:73\), \(AE:69\), and \(AC:70\). Trace both searches to size two and compare their final candidate sets and choices.
Forward selection, first step. From the intercept-only model, the five one-predictor candidates have RSS values \(90,92,80,94,93\). The smallest is \(80\), for model \(C\). Therefore, the selected size-one model is \(\{C\}\).
Forward selection, next step. From \(\{C\}\), the available additions are \(A,B,D,E\). The four candidate models and their RSS values are \(AC:70\), \(BC:74\), \(CD:75\), and \(CE:73\). The smallest RSS is \(70\), so forward selection selects \(\{A,C\}\). Its size-two candidate set is exactly \(\{AC,BC,CD,CE\}\).
Backward elimination, first step. Start from the full model \(\{A,B,C,D,E\}\), with RSS \(30\). Removing one predictor gives five candidates: \(ABCD:34\), \(ABCE:32\), \(ABDE:50\), \(ACDE:33\), and \(BCDE:38\). The smallest candidate RSS is \(32\), so the selected size-four model is \(\{A,B,C,E\}\).
Backward elimination, second step. From \(\{A,B,C,E\}\), the four deletion candidates have RSS values \(BCE:42\), \(ACE:38\), \(ABE:55\), and \(ABC:39\). The smallest is \(38\), so the selected size-three model is \(\{A,C,E\}\).
Backward elimination, final step. From \(\{A,C,E\}\), backward elimination evaluates three candidates: \(CE:73\), \(AE:69\), and \(AC:70\). The smallest is \(69\), so it selects \(\{A,E\}\). Its size-two candidate set is \(\{CE,AE,AC\}\).
Comparison and check. At this target size, forward selection evaluates four candidates: \(\{AC,BC,CD,CE\}\). Backward elimination evaluates three: \(\{CE,AE,AC\}\). Both sets contain \(AC\) and \(CE\), but forward selection also evaluates \(BC\) and \(CD\), while backward elimination also evaluates \(AE\). The selected models differ: forward selects \(AC\), and backward selects \(AE\). The candidate counts agree with the step sizes: \(5-1=4\) forward additions from a one-predictor model, and \(3\) backward deletions from a three-predictor model.
Common mistake avoided. The final steps do not each fit three candidates. The forward final step fits four, while the backward final step fits three. Their counts differ because they start those steps from models of different sizes.
Why the Candidate Counts Follow from the Search Rules
The count formulas require no assumptions about the values of the predictors or the quality of the fits. They are consequences of how the algorithms construct candidates. For forward selection, suppose the current model is \(S\) and contains \(k\) predictors. Of the \(p\) available predictors, \(k\) are already in \(S\), leaving \(p-k\) available additions. Adding each one separately creates \(p-k\) candidates.
For backward elimination, the current model contains \(k\) predictors. The rule considers removing each one separately. There are \(k\) such choices and therefore \(k\) candidates. In both directions, a candidate is one step away from the current model; a model requiring two additions or two deletions is not a candidate for that step.
This also explains why comparing counts without recording the current model size can cause errors. A forward step from size one with five available predictors has four candidates, whereas a backward step from size three has three. The fact that both procedures are approaching size two does not make the preceding candidate counts equal.
Worked Example: Checking Membership in a Search Path
A separate study has four predictors \(P,Q,R,S\). A forward run selects \(R\) at size one and then \(PR\) at size two. A backward run starts at \(PQRS\), selects \(PQR\) at size three, and then selects \(PR\) at size two. List the size-two candidate sets for both final steps, find their intersection, and identify which of the six size-two models neither final step evaluates.
Forward candidates. From \(\{R\}\), the available additions are \(P,Q,S\), so the candidates are \(\{PR,QR,RS\}\).
Backward candidates. From \(\{P,Q,R\}\), removing \(P\), \(Q\), or \(R\) gives \(\{QR,PR,PQ\}\).
Intersection. Both candidate sets contain \(\{PR,QR\}\). The forward-only candidate is \(\{RS\}\), and the backward-only candidate is \(\{PQ\}\).
There are \(\binom{4}{2}=6\) size-two models: \(PQ,PR,PS,QR,QS,RS\). The union of the two final candidate sets is \(PQ,PR,QR,RS\). Therefore, neither final step evaluates \(PS\) or \(QS\).
Check. The forward set has three models because \(4-1=3\); the backward set has three because its current model has three predictors. Their union has \(3+3-2=4\) models, since two are shared, leaving \(6-4=2\) size-two models outside the union.
Common mistake avoided. A model’s size does not determine whether it is evaluated. The model \(PS\) has the target size, but it is not a one-step addition to the selected forward model \(R\) or a one-step deletion from the selected backward model \(PQR\).
What a Search Path Does and Does Not Establish
A forward or backward path reports results for the candidates its rules actually examine. If a subset is not in those candidate sets, its fit is not determined by the path. In particular, choosing the best candidate at every step does not mean that every model of the target size has been compared. Exhaustive best-subset search, by contrast, fits all subsets in the specified comparison space, subject to the feasibility of fitting those models.
The distinction matters when reading a selected model. For the five-predictor example, forward selection chose \(AC\) from four size-two candidates. This establishes that \(AC\) had the lowest RSS among those four at that step. It does not establish that \(AC\) had the lowest RSS among all ten size-two models. Likewise, backward elimination chose \(AE\) from its three final candidates; that does not compare \(AE\) with every size-two subset.
The same bookkeeping is useful even if a procedure uses a selection rule other than smallest training RSS. The candidate sets are determined by the current subset and the allowed one-variable move. A different rule can change which candidate is selected, and therefore alter later candidate sets, but it does not make an unvisited subset an evaluated candidate.
Check Your Understanding
For each question, distinguish the complete subset space from the candidates on the specified search step.
- A study has six candidate predictors. How many models are in the full subset space, including the intercept-only model? (Answer: \(2^6=64\) models.)
- With seven predictors, forward selection has selected a model containing three predictors. How many one-predictor additions does it evaluate next? (Answer: \(7-3=4\) candidates.)
- With five available predictors, backward elimination is currently at a model containing four predictors. How many one-predictor deletions does it evaluate? (Answer: 4 candidates.)
- There are four predictors \(A,B,C,D\). Forward selection has selected \(B\), while backward elimination is at \(ABC\). List each method’s size-two candidate set and their intersection. (Answer: Forward \(\{AB,BC,BD\}\); backward \(\{AB,AC,BC\}\); intersection \(\{AB,BC\}\).)
- A search has five predictors and targets size two. Forward selection first chooses \(D\). How many of the \(\binom{5}{2}=10\) size-two models does its next step evaluate, and how many are not evaluated at that step? (Answer: It evaluates 4 models containing \(D\), so 6 size-two models are not evaluated at that step.)