[MUSIC]
So now let's talk about the complexity of this forward stepwise algorithm.
And contrast it with the all subsets procedure.
So how many models did we evaluate here?
Well, in the first step, assuming that we have a total of D features,
we searched over D models.
Then, in the second step, we had D-1 models to search over.
So all remaining features we might think about adding.
And then the third step, we had D-2 features and so on.
And a question is, how many steps did we take, how many of these and so
ons did we have?
Well, it depends.
It depends on when we chose to stop, but
at most we're gonna have D steps, which gets us to the full model.
So, the complexity of this is O(D squared).
So at most D steps each on the order of looking over D models.
And that's gonna be much, much less than 2 to the D,
which is what we had for all subsets, when D is reasonably large.
Okay, so this procedure is gonna be significantly
more computationally efficient or feasible than doing all subsets.
Well this was just one of many possible choices you have for
greedy algorithms for doing feature selection.
As an example, instead of always starting from an empty model and growing and
growing and growing, adding more features, you could do the opposite.
You could start from a full model and then choose,
at each iteration, which feature to eliminate.
But you could also think about combining these steps.
So you could do a forward procedure, where you search over which feature to add, but
then every so often you could go back and think about deleting features.
Because like we said, you might in the forward process, add a feature that later,
once you've added another feature, is no longer relevant.
So, as an example of this, maybe, and
it's not completely probably true in this application.
But maybe once you've added number of bedrooms and number of baths, maybe square
feet is no longer so relevant since these other things can act as a proxy for
square feet, or something like that.
And there are lots and lots of other variants of algorithms people have
proposed with different metrics for when you add or remove features.
And different ways to search over the features because this problem of feature
selection is really important.
It's not a new problem, and so
a lot of different procedures have been proposed to solve it.
[MUSIC]