Why the Forward Path Has a One-Way Structure
Forward selection builds a regression model by starting with no candidate predictors and adding one at a time. Its defining feature is not a particular score used to choose the next predictor. It is that an entered predictor stays in the model. As a result, the path is nested: every model contains all the predictors in the preceding model.
That structure has practical consequences. At each step, the search can consider models that extend its current predictor set, but it cannot return to a model that omits an earlier choice. Forward selection therefore traces one restricted path through the possible subsets, rather than examining every candidate model. The result is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
The choice of \(j_k\) may depend on a rule for comparing candidate additions. The rule can change which path is taken, but it does not change the set update above: no selected predictor is removed. The discussion here concerns that structural fact, not the choice of entry rule or stopping rule.
The Nestedness Result
The nesting claim follows directly from the update defining forward selection. Since \(S_k\) is formed by taking every member of \(S_{k-1}\) and adding \(j_k\), every member of \(S_{k-1}\) is also a member of \(S_k\). Thus \(S_{k-1}\subseteq S_k\). Repeating this argument gives \(S_r\subseteq S_s\) whenever \(r\leq s\).
In ordinary least squares (OLS), this also means that the set of fitted values available in one step is contained in the set available in the next. To state that precisely, let \(\mathcal{M}(S)\) be the space of vectors that can be fitted using an intercept and the predictors in \(S\), on the same observations. If \(S\subseteq T\), every intercept-and-\(S\) fit is still available when the model includes \(T\), by assigning coefficient zero to the additional predictors. Therefore \(\mathcal{M}(S)\subseteq\mathcal{M}(T)\). Minimizing the squared residual length over the larger space cannot produce a larger minimum residual sum of squares (RSS).
This RSS statement assumes the same response and observations are used for each fit and that the models are fitted by least squares. It does not mean every added predictor must strictly reduce RSS: if its column adds no new direction to the existing model space, the fitted values and RSS can remain unchanged. Nor does a lower RSS by itself establish that the larger model is preferable; model assessment is a separate issue.
Worked Example: Tracking the Models a Path Can Reach
A hypothetical analyst has five candidate predictors \(A,B,C,D,E\). A forward search has selected \(C\) first, \(A\) second, and \(D\) third. Write its models through size three, determine whether the exact model \(\{A,B,D\}\) occurs on this path, and count how many size-three subsets could extend the first two selections.
Method. Apply the forward update at each step, retaining every earlier selection. This set-based method avoids the mistake of treating a later model as though it could replace a previous choice.
Initially, \(S_0=\varnothing\). After selecting \(C\), \(S_1=\{C\}\). After selecting \(A\), \(S_2=\{C,A\}\). After selecting \(D\), \(S_3=\{C,A,D\}\). The inclusions are \(S_0\subset S_1\subset S_2\subset S_3\).
The exact target \(\{A,B,D\}\) is not on this path. Every model after the first step must contain \(C\), but the target omits \(C\). In particular, the size-three model actually reached is \(\{C,A,D\}\), not \(\{A,B,D\}\).
There are \(\binom{5}{3}=10\) size-three subsets in total. To make a size-three subset that extends the prefix \(\{C,A\}\), those two predictors are fixed and one more must be chosen from \(B,D,E\). There are \(\binom{3}{1}=3\) such subsets: \(\{A,B,C\}\), \(\{A,C,D\}\), and \(\{A,C,E\}\). The actual path reaches just one of them, \(\{A,C,D\}\).
Check and trap. The reached model contains the first two choices, as required. A common error is to count every size-three subset as reachable after the prefix; only three extend that prefix, and only the one dictated by the actual third choice is on this particular path.
Why Nested Model Spaces Also Give Nonincreasing RSS
The model-space argument can be seen directly from least squares. Suppose \(S\) is the current set and \(T=S\cup\{j\}\) is the next set. Any coefficient vector for the model with \(S\) predictors gives an available fit in the model with \(T\) predictors: use the same coefficients for \(S\) and set the coefficient of \(j\) to zero. Since the fit over \(T\) is optimized over at least all those choices, it cannot have a larger minimum squared error.
In the enlarged model, set the coefficient of the new predictor to zero. The old fitted values are still possible.
Least squares chooses the coefficients with the smallest residual sum of squares among all available fits, including the old fit.
The minimum RSS in the enlarged model is no greater than the RSS from the old fit.
For a single added predictor, a conditional RSS reduction can also be calculated from residuals. In an OLS model, include the intercept in the current model space, let \(P_S\) be the orthogonal projection onto that space, and let \(x_j\) be the candidate predictor’s observation vector. Define the current residual vector \(e_S=(I-P_S)y\), and the candidate vector after removing its part explained by the current model, \(z_j=(I-P_S)x_j\). If \(z_j\neq 0\), the reduction from adding \(x_j\) is \((z_j^\top e_S)^2/(z_j^\top z_j)\).
To justify the formula, first note that the residual from the current least-squares fit is orthogonal to the current model space. Once the candidate vector is residualized against that space, fitting its coefficient amounts to fitting a multiple \(a z_j\) to \(e_S\). The residual sum of squares as a function of \(a\) is \(\|e_S-a z_j\|^2=e_S^\top e_S-2a z_j^\top e_S+a^2z_j^\top z_j\). Minimizing this quadratic gives \(a=(z_j^\top e_S)/(z_j^\top z_j)\). Substitution yields the stated reduction. If \(z_j=0\), the candidate is already in the current model space and cannot reduce RSS by adding a new direction.
The formula also explains why a predictor’s first-step improvement cannot generally be reused at a later step. Once other predictors are in the model, both the response residual and the candidate predictor’s residualized direction may have changed. The relevant quantity is conditional on the current model.
Worked Example: An Orthogonal Path and an Unreachable Subset
A hypothetical OLS search includes an intercept and four centered, mutually orthogonal candidate predictors \(A,B,C,D\). Each predictor vector has squared length \(1\). The response vector is centered and has squared length \(50\). Its inner products with the predictors are \(4,3,2,1\), respectively. Suppose the next predictor is chosen by the largest one-step RSS reduction. Find the path and RSS at each size, then decide whether the exact model \(\{B,C,D\}\) occurs.
Method. Because the response and predictors are centered, the response is orthogonal to the intercept, so the intercept-only RSS is \(50\). Because the predictors are mutually orthogonal, each has squared length \(1\), and all are centered, adding one to a model containing other candidates reduces RSS by \((x_j^\top y)^2\). This avoids attributing response variation to the intercept or treating nonorthogonal predictors as though their reductions were independent.
At the first step, the four reductions are \(A:4^2=16\), \(B:3^2=9\), \(C:2^2=4\), and \(D:1^2=1\). The largest is \(16\), so \(A\) enters and the RSS is \(50-16=34\).
At the second step, the remaining reductions are \(9,4,1\). Predictor \(B\) enters, giving RSS \(34-9=25\). At the third step, \(C\) enters and RSS becomes \(25-4=21\). At the fourth step, \(D\) enters and RSS becomes \(21-1=20\). The path is \(S_0=\varnothing\), \(S_1=\{A\}\), \(S_2=\{A,B\}\), \(S_3=\{A,B,C\}\), and \(S_4=\{A,B,C,D\}\).
The exact model \(\{B,C,D\}\) is not reached: after \(A\) enters, every later model must contain \(A\). The final RSS is checked by subtracting all four orthogonal reductions from the baseline: \(50-(16+9+4+1)=20\), which agrees with the step-by-step path.
Check and trap. The intercept-only RSS is \(50\) because the response is explicitly centered; the predictor reductions use the centered, orthogonal design. Without those conditions, the stated squared response length and raw inner products alone would not justify these RSS calculations.
Conditional Improvements When Predictors Are Correlated
With correlated predictors, the nested-set result remains true, but the simple orthogonal calculation does not apply. The residualized-vector formula accounts for overlap with predictors already selected. The next example uses centered vectors so the intercept does not contribute to the residual calculations.
Worked Example: Recalculating the Next Addition After a Correlated Choice
In a hypothetical OLS search, centered unit-length predictors \(A\) and \(B\) have correlation \(0.5\). A centered unit-length predictor \(C\) is orthogonal to both. The centered response has squared length \(30\), with \(x_A^\top y=3\), \(x_B^\top y=2.8\), and \(x_C^\top y=2\). At each step, choose the available predictor with the largest conditional RSS reduction. Find the first three choices and their RSS values.
Method. At the first step, calculate each marginal reduction. After a predictor enters, residualize both the response and each candidate against the current model. This avoids mistakenly reusing a marginal reduction after the fit has changed.
The intercept-only RSS is \(30\), since the response is centered. At the first step, the unit-length centered predictors have reductions \(A:3^2=9\), \(B:2.8^2=7.84\), and \(C:2^2=4\). Thus \(A\) enters, and the RSS becomes \(30-9=21\).
After \(A\) enters, the residualized \(B\) vector has squared length \(1-0.5^2=0.75\). Its inner product with the residual response is \(2.8-(0.5)(3)=1.3\). Therefore the conditional reduction for \(B\) is \(1.3^2/0.75=1.69/0.75=169/75\), approximately \(2.2533\). Predictor \(C\) is orthogonal to \(A\), so its residualized squared length remains \(1\), its residual-response inner product remains \(2\), and its conditional reduction is \(2^2/1=4\). Thus \(C\), not \(B\), enters next. The RSS is \(21-4=17\).
After \(A\) and \(C\) enter, \(B\)'s residualized vector and response inner product are unchanged because \(C\) is orthogonal to \(B\) and \(A\). Its reduction remains \(169/75\). Predictor \(B\) enters third, giving \(17-169/75=(1275-169)/75=1106/75\), or \(14.747\) to three decimal places.
The path is \(\{A\}\), then \(\{A,C\}\), then \(\{A,C,B\}\). Each set contains its predecessor. The final RSS is less than \(17\), as required by the least-squares nesting result.
Check and trap. Subtracting \(B\)'s original marginal reduction \(7.84\) from \(21\) would give \(13.16\), but that is wrong: the variation in \(B\) overlapping with \(A\) has already been fitted. The correct conditional reduction after \(A\) is \(169/75\), not \(7.84\).
What Nestedness Does—and Does Not—Guarantee
Nestedness is a structural guarantee, not a guarantee that the path includes every useful model. Once a predictor has entered, all subsequent models retain it. A model that omits that predictor cannot appear later on that same run. This matters when interpreting a selected path: a size-\(k\) model reached by forward selection is one of the subsets compatible with its earlier choices, not necessarily the best of all size-\(k\) subsets.
The guarantee also does not say that the same predictor must be selected under every data set or every choice of entry rule. Different choices can produce different nested paths. Nor does it say that model fit must improve strictly at each step: if a candidate adds no new direction, its conditional RSS reduction is zero. The reliable conclusions are narrower: predictor sets do not lose members, their OLS model spaces do not shrink, and their minimum RSS cannot increase.
Check Your Understanding
For each problem, track the sequence of additions and distinguish an exact model from a model that merely contains it.
- A search over \(A,B,C,D\) chooses \(D\), then \(B\), then \(A\). Write the size-zero through size-three models. Does the exact model \(\{A,D\}\) occur? (Answer: \(\varnothing,\{D\},\{B,D\},\{A,B,D\}\); no.)
- Four centered, mutually orthogonal, unit-length predictors have squared inner products with a centered response of \(9,4,1,0\), respectively, and the response has squared length \(36\). If each step chooses the largest RSS reduction, what is the first two-predictor path and RSS at each of sizes zero, one, and two? (Answer: \(\varnothing,\{A\},\{A,B\}\); RSS values \(36,27,23\).)
- Centered unit-length predictors \(A,B\) have correlation \(0.6\), and centered unit-length \(C\) is orthogonal to both. A centered response has squared length \(20\) and inner products \(x_A^\top y=2\), \(x_B^\top y=2.5\), \(x_C^\top y=1.5\). Using largest conditional RSS reduction, find the first two choices and RSS after each. (Answer: \(B\) enters first, then \(C\); RSS values \(20,13.75,11.50\).)
- A forward path over six predictors has selected \(\{Q,R\}\) after two steps. How many size-four subsets extend this prefix, and can a later model on this path omit \(Q\)? (Answer: \(\binom{4}{2}=6\); no.)
- A centered response has intercept-only RSS \(25\). A first selected predictor reduces RSS by \(5\). At the next step, a candidate’s marginal reduction from the intercept-only model was \(8\), but its conditional reduction after the first selection is \(2\). What is the current RSS after the second addition, and which reduction should be used? (Answer: \(25-5-2=18\); use the conditional reduction of \(2\).)