# What does it mean that stepwise, backward and forward selection methods are “path dependent”?

In many papers I read that stepwise, backward and forward selection methods are "path dependent". What does it mean? Could anyone give me some practical example to understand the underlying concept? It is related to the fact that these methods are local search techniques?

Forward stepwise selection begins with a model containing no predictors, and then adds predictors to the model, one-at-a-time, until all of the predictors are in the model.

In particular, at each step the variable that gives the greatest additional improvement to the fit is added to the model.

In detail:

• Let $\mathcal{M}_0$ denote the null model, which contains no predictors.
• For $k = 0, \dots, p - 1:$ Consider all $p - k$ models that augment the predictors in $\mathcal{M}_k$ with one additional predictor. Choose the best among these $p - k$ models, and call it $\mathcal{M}_{k + 1}$. Here best is defined as having the smallest $RSS$, or equivalently largest $R^2$.
• Select a single best model from among $\mathcal{M}_0, \dots, \mathcal{M}_p$ using cross-validated prediction error, $AIC$, $BIC$, or adjusted $R^2$.

It is not guaranteed to find the best possible model out of all $2^p$ models containing subsets of the $p$ predictors. This is because the variable that has been selected in round 1 (i.e., for $k=0$) will definitely be in the final model, even if it occurred at a later stage that, when considering the best $k$-dimensional model, $k>1$, does not need that particular variable.

In slightly different words, it might happen that a variable gives the largest reduction in $RSS$ relative the null model, but that, when also considering combinations of, say, three variables, that some combination of three predictors makes the variable chosen in round 1 redundant.

• Thanks christoph, your answer is really clear. Could you explain me why this path dependence occurs also for stepwise selection? Because, it will start with an arbitrary subset of the full model (the subset is chosen by the user) and then it is not true (in this case) that the variables selected in round 1 (for k=0) will definitely be in the final model: at each step I can add variables but I can also eliminate the variables that already are in the model. If you can explain that I will accept your answer because I think is really clear and useful. – Luca Dibo Oct 23 '15 at 13:32
• Could you provide a link where that flavor of stepwise is explained in more detail? I am not sure I understand it correctly. – Christoph Hanck Oct 23 '15 at 15:16
• sure, try the function step in R with the argument direction="both". – Luca Dibo Oct 23 '15 at 16:27
• stats.stackexchange.com/questions/4640/… – Luca Dibo Oct 23 '15 at 16:28
• The basic logic is still the same. Since only one regressor is added at a time, pairs or larger groups of variables that are relevant only together but not separately may be skipped in stepwise selection even though they might belong to the best model if all possible subsets are considered. – Richard Hardy Oct 23 '15 at 18:05