6
$\begingroup$

I am trying to understand the logic behind forward-backward selection (even though I know that there are better methods for model selection). In forward model selection, the selection process is started with an empty model and variables are added sequentially. In backward selection, the selection process is started with the full model and variables are excluded sequentially.

Question: With which model does forward-backward selection start?

Is it the full model? The empty model? Something in between? Wikipedia and Hastie et al. (2009) - The Elements of Statistical Learning, page 60 are explaining the method, but I wasn't able to find anything about the starting model. For my analysis I am using the function stepAIC of the R package MASS.

UPDATE:

Below you can find an example in R. The stepAIC function automatically prints each step of the selection process in the console and it seems like the selection starts with the full model. However, based on the answer of jjet I am not sure if I have done anything wrong.

# Example data
N <- 1000000
y <- rnorm(N)
x1 <- y + rnorm(N)
x2 <- y + rnorm(N)
x3 <- y + rnorm(N)
x4 <- rnorm(N)
x5 <- rnorm(N)
x6 <- rnorm(N)
data <- data.frame(y, x1, x2, x3, x4, x5, x6)

# Selection
library("MASS")
mod <- lm(y ~., data)
stepAIC(mod, direction = "both")
$\endgroup$
2
  • 2
    $\begingroup$ Read the manual: you can use the object & scope arguments to start with whichever model you want: stepAIC(lm(y~1, data), scope=~x1+x2+x3+x4+x5, direction = "both"). I don't know if there's an authoritative answer as to whether "forward-backward" implies a particular starting model, or which; but even if there is, it'd be sensible not to assume other people know about it when they use the expression. $\endgroup$ May 3 '17 at 8:28
  • $\begingroup$ Thank you for your answer Scortchi! I read the manual before, but it seems like I missed some things. Based on your comment and jjet's answer I was able to solve my problem. $\endgroup$ May 3 '17 at 13:36
6
$\begingroup$

I believe "forward-backward" selection is another name for "forward-stepwise" selection. This is the default approach used by stepAIC. In this procedure, you start with an empty model and build up sequentially just like in forward selection. The only caveat is that every time you add a new variable, $X_{new}$, you have to check to see if any of the other variables that are already in the model should be dropped after $X_{new}$ is included. In this approach, you can end up searching "nonlinearly" through all the different models.

-------- EDIT --------

The following R code illustrates the difference between the three selection strategies:

# library(MASS)
set.seed(1)

N <- 200000
y <- rnorm(N)
x1 <- y + rnorm(N)
x2 <- y + rnorm(N)
x3 <- y + rnorm(N)
x4 <- rnorm(N)
x5 <- rnorm(N)
x6 <- x1 + x2 + x3 + rnorm(N)
data <- data.frame(y, x1, x2, x3, x4, x5, x6)

fit1 <- lm(y ~ ., data)
fit2 <- lm(y ~ 1, data)
stepAIC(fit1,direction="backward")
stepAIC(fit2,direction="forward",scope=list(upper=fit1,lower=fit2))
stepAIC(fit2,direction="both",scope=list(upper=fit1,lower=fit2))

I've modified your example just slightly in this code. First, I set a seed so that you can see the same data I used. I also made N smaller so the algorithm runs a little faster. I kept all your variables the same except for x6. x6 is now the most predictive of y individually - this will make it the first variable chosen in forward and forward-stepwise selection. But once x1, x2 and x3 enter the model, x6 becomes independent of y and should be excluded. You'll see that forward-stepwise does exactly this. It starts with x6, proceeds to include x1, x2 and x3, then it goes back and drops x6 and terminates. If you just use forward, then x6 will stay in the model because the algorithm never goes back to this sort of multicollinearity check.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer jjet! It makes perfectly sense what you say, but if you run the code that I updated above it seems like the selection starts with the full model. Have I done anything wrong? $\endgroup$ May 3 '17 at 7:31
  • 1
    $\begingroup$ Just a slight issue with your code. You wrote mod <- lm(y ~., data) followed by stepAIC(mod, direction = "both"). In your first line, you've effectively defined an initial model to include all variables by writing "y ~.". This is now your starting point for forward selection. Instead, you'll want to write "y ~ 1" which is just an intercept model - the starting point you're looking for. I've made edits above with R code which should clear this up for you. $\endgroup$
    – jjet
    May 3 '17 at 12:29
  • $\begingroup$ Thank you so much for the great help! One last question: If I keep my example like it is without the scope argument and with mod <- lm(y ~., data), is it then performing a normal backward selection or is it performing a forward-backward selection with a full starting model? $\endgroup$ May 3 '17 at 12:44
  • 1
    $\begingroup$ The latter. It's doing forward-backward using an initial model which includes all variables. If you don't have the scope list defined, it will assume your "lower" model is whatever model you specified initially and your "upper" model is the full model. $\endgroup$
    – jjet
    May 3 '17 at 13:22
2
$\begingroup$

Forward-backward model selection are two greedy approaches to solve the combinatorial optimization problem of finding the optimal combination of features (which is known to be NP-complete). Hence, you need to look for suboptimal, computationally efficient strategies. See for example Floating search methods in feature selection by Pudil et. al.

In Forward method you start with an empty model, and iterate over all features. For each feature you train a model, and select the feature which yields the best model according to your metric. In a similar fashion you proceed by adding the next feature that yield the best improvement when combined with the already selected ones.

In backward method you just invert the procedure: start with all features, and iteratively remove that one whose removal least hurt the performance, or leads to the biggest improvement.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer jpmuc! However, I am not sure if this answers my original question, which was: "With which model does forward-backward selection start?" Am I missing something in your answer or did you just want to clarify the procedure of forward-backward selection in general? $\endgroup$ May 3 '17 at 15:48
  • $\begingroup$ In this feature selection method you are not bound to a concrete model or set of parameters. You select the set of features with which you can build the best model of a particular type (in your case a linear model). This is better illustrated in these two links: stat.columbia.edu/~martin/W2024/R10.pdf and rstudio-pubs-static.s3.amazonaws.com/… $\endgroup$
    – jpmuc
    May 4 '17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.