Hi.
In this module, I'm going to be talking
about the generalization of machine learning algorithms.
So recall that a machine learning framework
has three design decisions.
The first is the hypothesis class,
which could be linear predictors or neural networks.
The second design decision is a loss function,
which in the case of regression, this could be squared loss.
If it's a classification, it could
be the hinge or logistic loss.
If you take the loss and you average them,
you get the training loss, which is our training objective
that we so far have been optimizing.
And finally, we have the optimization algorithm,
which is either gradient descent or stochastic gradient descent.
All good so far.
Now let's take a step back and be a little more critical.
Is this, the training loss in particular,
a good objective to be optimizing?
So here is a little cartoon example that does really well
on training loss.
Here it goes.
It's called rote learning.
So the rote learning algorithm is just
going to store all the training examples.
And then it's going to return this predictor.
And this predictor takes an input x.
And it's going to search for an x in the training set,
and if it can find it, then it is going
to return the corresponding y.
And otherwise, it just gives up and segfaults or crashes.
And so this learning algorithm minimizes the objective
perfectly.
It gets zero training loss.
But you can kind of tell that it's
a bad idea because it doesn't get anything else right.
So, this was an example of extreme overfitting.
Here are some examples of less extreme overfitting
in pictures.
So here's an example from classification.
You can see that the green decision boundary here
tries really hard to separate the blue and the red points
and does so successfully getting zero training error.
But you can kind of intuitively sense that it's overfitting.
And perhaps this black decision boundary would be better.
In the case of regression, this red curve
gets zero training loss by going through all the training
points.
But you can see that it's overfitting
and instead maybe you should be capturing the broader trend
using a simple line.
So, in general, if you try to overly optimize
the training loss, then you risk overfitting [AUDIO OUT]..
So then, what is the true objective
if it isn't the training loss?
Well, to answer that question, let's
take a step back and think, what are we trying to do?
Machine learning is just a means to an end.
The end is a predictor that you're
going to launch into the world and make predictions
on real people.
And this just happens to be trained from a learning
algorithm.
So how good is this predictor in the world?
Well, the answer is, it's the goal--
how good it is depends on how well
it's able to predict on unseen future examples.
So a true learning objective should
be to minimize the error on unseen future examples.
Sounds great.
Only one small problem is that we don't have access
to the future.
And in particular, if we don't see the examples,
how can we do anything about them?
So, often we settle for the next best
thing, which is get a test set.
And the test set is just a set of examples
that you didn't use for training.
So it is a surrogate for the unseen future examples.
So I make this distinction because I
want to stress the fact that when you deploy
a machine learning algorithm--
a predictor into the world, it might encounter
all sorts of crazy things.
And what you do in the training, in the lab,
is-- all you have is a test set.
So what you're trying to do is trying
to have the test set be as close and as representative
of what you actually get in the real world as possible.
So now we have an intuitive feeling
for what overfitting is.
Can we make this a little bit more precise?
In particular, when does a learning algorithm
generalize from the training set to the test set?
Because that's kind of what we settle for.
So, there is a way to make this mathematically rigorous.
But I just want to give you the framing of how
to think about generalization.
So the starting point is f star.
This is the predictor that is the ideal thing.
It predicts everything as correctly as you can hope for.
This lives in the family of all predictors.
Of course, we can't get to f star.
So what do we do?
Well, we do two things.
We first define a hypothesis class, script F.
And then we are going to have a learning algorithm that
finds a particular predictor within this hypothesis class.
So another predictor I'm going to talk about is g.
This is also a kind of a thing that you can't get a hold of.
It's the best predictor that you can
find in the hypothesis class.
So now, we're interested in the difference
between the error of the thing you have
and the thing that you wish you had, OK?
So, mathematically, that's written
as error of the learned predictor minus the error of f
star [AUDIO OUT].
And this error can be decomposed into two parts.
The first part is the approximation error.
Approximation error is the difference
between g and f star.
Mathematically, that's the difference
between the error of--
so approximation error is the difference between the error
of g minus the error of f star.
This measures how good your hypothesis class is.
The second error is the estimation error, which
is the gap between f hat and g.
This measures how good is the learned predictor
relative to the potential of the hypothesis class, error
of f hat minus the error of g.
And you can verify this identity because we're
doing just subtracting the error of g and adding error of g.
So this right-hand side is equal to this left-hand side.
This kind of trivial identity highlights
these two quantities' approximation error
and estimation error and gives us
a language to talk about the trade-offs and generalizations.
So let's get some more intuition about how approximation
and estimation error behave as you
increase the size of the hypothesis class.
So when the hypothesis class grows,
the approximation error will decrease.
This is because the approximation error
is measuring how good g is and the g
is the best thing in the class.
And if you're adding more things,
the best thing is just going to get better.
So, in other words, you're taking a min
over a larger set [AUDIO OUT] where you're optimizing.
The second thing that happens is that the estimation error
increases when the hypothesis class grows.
And this is because it's harder to estimate something
more complex.
There's just more functions that the learning algorithm
has to figure out which one is the correct one given
the limited data.
So there are ways to make this more precise using
the tools from statistical learning theory,
but I'll just leave it as intuition for now.
So, given these trade-offs, what are
the ways that we can use to control the hypothesis class
size?
So we're going to focus our attention
to a linear predictor.
But remember, in linear predictors,
each predictor has a particular weight vector.
So effectively the number of--
the size of the set of weight vectors
determines the size of the hypothesis class.
So one thing you can do is to reduce
the dimensionality of the set of possible weight vectors.
So pictorially, this looks like this.
So imagine you had three features.
So the set of weight vectors for this three-dimensional weight
vector is just a ball.
And if we remove one feature, then you
end up with a two-dimensional ball.
Equivalently, this is saying one of the features
has to have zero weight, which you can think about
as a restriction on a set of values that w should have.
So how do you control the dimensionality in practice?
The process is called feature selection,
or feature template selection.
You can do this manually by adding feature templates,
seeing if they help, and removing them if they don't.
And you're trying to kind of manually
figure out what is the smallest set of features that actually
gets you good accuracy.
There's also ways to do this more automatically.
You can do forward selection, boosting, or L1 regularization.
This is beyond the scope of the class.
But there are ways to make this less manual.
One thing I want to stress is that controlling
the dimensionality-- dimensionality
is this number of features.
And that's the key quantity that matters,
not the number of feature templates,
and also not the complexity of each individual feature.
So imagine you write 1,000 lines to compute one feature.
Well, it's still a very simple hypothesis class
because it's just one feature in so far
as generalization is concerned.
So the second strategy is controlling
the norm or the length of this weight vector.
So we can reduce the norm of-- or the length.
Visually, this looks like if you have a set of weight vectors
which are bounded in length, you can
shrink the length and that results
in a smaller circle, which is pointedly a smaller
number of weight factors.
And so this is probably the most common way to control the norm.
So there are two ways to do this.
One is by regularization.
So remember the objective, which we didn't like,
was minimizing the training loss of w
because that can lead to overfitting.
So one way to regularize is you add a penalty term--
lambda over 2 times the norm of w squared.
So w is a positive number which controls
the strength of this penalty.
And what this penalty does is it says,
let's try to minimize the training loss,
but we also want to keep the norm small because we're
taking a min over the sum here.
So if we look at what gradient descent does to this objective,
we can interpret it as follows.
So gradient descent, remember, initializes weights,
iterates over t fx and performs an update.
So the update is w minus eta, the step size,
times this gradient of the training loss.
And now we take the gradient of this penalty, which
is just lambda times w.
So, remember we're subtracting eta.
So if w is let's say, 10, 10, then what we're going to do
is we're going to subtract that vector
and move the weights closer to 0 by an amount that depends.
So another way to control the norm is by early stopping.
So, early stopping is really easy to explain.
So here it is.
You run gradient descent.
You initialize w.
And you repeat a number of epochs.
And you perform the update.
And the only thing is that you're just
going to reduce the number of epochs you go for.
That's it.
So this seems like a hack.
There is-- you can develop some theory about it.
But the intuition is that when you start the weights at 0,
that's the smallest norm.
And when you update the weights over a number of iterations,
the norm of w is actually going to grow.
It's not obvious that this always happens,
but empirically it is true, generally.
So by stopping gradient descent early, you're saying,
don't let the norm of w get too big.
So the lesson here is you're trying
to minimize the training error.
But you're not trying too hard because you're just going
to call it quits after a while.
OK, so let's summarize now.
So we started by saying the training loss is not
the true objective.
The real objective is minimizing the loss
on unseen future examples.
Unfortunately, we don't have access to that.
So we're going to settle for the loss on some test data which
serves as a surrogate to the unseen examples.
Then we studied approximation and estimation error as a way
to understand generalization.
And it's always just going to be a balancing
act between fitting the training error
and not letting your hypothesis class grow too big.
And the mantra to end with is, perhaps, just keep it simple.
So right now we've introduced a bunch of knobs
for varying the size of the hypothesis class.
Next, we'll see how to actually turn the knobs.