3
$\begingroup$

In ISLR (Intro to Stat Learning using R by James, Witten, Hastie, Tibs), in the section on Forward Selection on page 208, the footer states:

Though forward stepwise selection considers $p(p+1)/2 + 1$ models, it performs a guided search over the model space, and so the effective model space considered contains substantially more than $p(p+1)/2 + 1$ models.

What do they mean by substantially more? How much more, for example?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Since there are no answers to this question even after a year, I can try answering the first part of your question. Or atleast, almost answer it.

Say we have 4 predictors a,b,c,d. Hence p=4. Now let's apply the Forward selection Algorithm.

First Iteration (Find best model with one predictor) -> 4 options : (a),(b),(c),(d) -> suppose the best performing Model is the one with b

Second Iteration (Find best model with 2 predictors) -> 3 options : (b,a),(b,c),(b,d) -> suppose the best performing model among this is the one with (b,c)

Third Iteration (Find best model with 3 predictors) -> 2 options : (b,c,a) , (b,c,d) -> suppose the best performing model among this is the one with (b,c,a)

Fourth Iteration (here k=p, i.e all predictors are used) 1 option : (a,b,c,d) -> Suppose this model doesn't perform as good as (b,c,a).

So we choose model (b,c,a) as the best model.

Now we know that all the possible combinations of models is 2^p for Subset Selection (page 206). In this case 2^4= 16 models. Let's see them all :- (0),(a),(b),(c),(d),(a,b),(a,c),(b,c),(a,d),(b,d),(c,d),(a,b,c),(a,b,d),(a,d,c),(b,d,c),(a,b,c,d)

Whereas in our example the Forward selection went through only 1+p(p+1)/2 models (0),(a),(b),(c),(d),(b,a),(b,c),(b,d),(b,c,a),(b,c,d),(b,c,a,d) : 11 models

Of course Subset Selection brings us closest to the truth (at a high computational cost though). If suppose the best true model is (a,c). Although the Forward Selection did not assess it, it has assessed (b,c,a) with contains a and c, and so is close to the true model (a,c).

In this way we can also say that the Forward Selection Algorithm came close to assessing (c,d) as well because it assessed (b,c,d). So if the truth had been lying here, this iteration (3rd) would have given a (b,c,d).

So, although the search is guided (filtered) in each iteration, the effective model space considered is in fact more than just the 1+p(p+1)/2 models. However I'm not sure by 'how much'.

I hope my understanding is correct. If not, kindly correct me. I would be grateful.

Thank you!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer. Wouldn't this argument hold true for any guided search? According to this argument, any guided search would be effectively searching something larger. Also, the model that considers all the parameters, (a, b, c, d), would effectively have considered all combinations, right? $\endgroup$
    – user650654
    Commented Dec 17, 2019 at 19:19
  • $\begingroup$ @user650654 Before answering your questions let me make it clear that guided is searching something smaller (and not larger, as per your question). i.e the guiding avoids a full search. Our main intention was to REDUCE THE COST of the algorithm by bringing down the search from 2^p to 1+p(p+1)/2. $\endgroup$
    – Salih
    Commented Jan 3, 2020 at 18:43
  • $\begingroup$ @user650654 How the effective search of the models is indeed larger than what is actually searched is answered. Kindly vote if you have found this answer useful. :) $\endgroup$
    – Salih
    Commented Jan 3, 2020 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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