YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 1,724 lines · added Dec 6, 2015

Report a problem
What's wrong?
Advertisement

English transcript

ANNOUNCER: The following program is brought to you by Caltech.
YASER ABU-MOSTAFA: Welcome back.
Last time, we talked about the bias-variance decomposition of the
out-of-sample error.
And we managed, by taking the expected value of the out-of-sample with
respect to the identity of the data points-- the size is fixed at N--
to get rid of the variation due to the data set.
And we ended up with a very clean decomposition of the expected value of
the E_out, into a bias term and a variance term, that have very
interesting interpretation.
And they're illustrated here in terms of a tradeoff.
If you have a small hypothesis set, the chances are the target
function is far away.
And therefore, there is a significant bias term, which is the blue one.
And if you have a bigger hypothesis set, perhaps big enough to include
your target, you don't have very much of a bias, perhaps none at all.
But on the other hand, you do have variance depending on which hypothesis
you zoom in based on the data set you have.
So in the bias-variance decomposition, we basically had two hops from the
final hypothesis you produced based on a particular data set, into the target
function which is what we're trying to approximate.
The intermediate step was the new notion, which is the expected value
of the hypothesis set with respect to D. And the jump, from your actual
hypothesis to that fictitious hypothesis, describes the variance,
because here is the centroid of this, which is the g bar, and you are
somewhere here.
So in order to get there, that is described by the size of the red
region, and that is the variance.
And then there is another one, which is inevitable for a given hypothesis
set, which is the hop from that one, which designates the best
approximation, in a certain sense, within the hypothesis set, of your target
function, into your target function.
And that difference is the bias, which is captured here.
After doing the bias-variance decomposition, we went into
an illustrative tool called the learning curves, where we plot the expected
value of the in-sample error and the out-of-sample error, as you increase
the sample size.
If you look at the curve-- let's look at the bottom one here.
Not surprisingly, as you increase the number of examples, the out-of-sample
error goes down.
If you have more examples to learn from, you are likely to perform better
out-of-sample.
And another interesting observation is that when you have fewer examples, the
in-sample error goes down.
And that is because you are fitting fewer examples, and you have the same
resources to fit.
So you tend to fit them better.
And the discrepancy between them describes the generalization error.
Then we contrasted the analysis of the bias-variance decomposition, which is
the top curve, to the VC analysis, which we have done before.
And we realized that both of them describe a tradeoff between
approximation and generalization.
In the bias-variance case, the approximation is an absolute
approximation--
how your best hypothesis approximates the target.
And that is described by g bar, again with certain liberty.
And in the case of the VC analysis, the approximation was approximation
in sample only.
So it was E_in.
And then the jump from the approximation to the final performance
describes the generalization, whether it's this red region or this red region,
which have basically the same monotonicity, except that they have
different terms.
The final lesson from the theory, which is really what we're going to
carry out through the techniques, which start today until the end of the
course, is that the number of examples needed to achieve a certain
performance is proportional to the VC dimension.
And I'm putting it between quotes, because we defined it formally only for
classification.
But then we took the linear regression case, which is not classification, and
we found out that the corresponding quantity, which is the degrees of
freedom-- same thing, d plus 1--
happens to also describe the generalization property.
And therefore, we basically have a certain rule that you need examples
in proportion to the VC dimension, or to the effective degrees of
freedom, in order to do generalization.
And the more you have, the better performance you get.
This is the key observation.
Today, I'm going to start a series of techniques.
And today is special, because the techniques of the linear models have
already been covered in part.
Remember, this is the part that was split into two portions.
And we got a portion very early on, out of sequence, just to give you
something to work with.
And then, I'm going to complete the exposition of the linear models today.
So let's see where we are.
This is the big picture of linear models.
And they start with linear classification-- perceptrons.
We have seen that.
And then go on to linear regression.
We have also seen that.
That was the part that was covered.
There is a third one, which is another linear model that is neither linear
classification nor linear regression, which will be the bulk of
the lecture today.
It will be called logistic regression.
And then, for all of these linear models, we have this nice trick called
nonlinear transforms that allows us to use the learning algorithms
of linear models, which are very simple ones, and apply
them to nonlinear transformation.
And if you remember, that the observation here was that linearity in the
parameters was the key issue for deriving the algorithm.
So let's see what we finished, and what we didn't finish in these topics.
Linear classification is pretty much done.
We know the algorithm, perceptron or pocket.
There are obviously more sophisticated algorithms.
And we did the generalization analysis.
We got the VC dimension of perceptrons explicitly.
And therefore, we are able to predict the generalization ability of linear
classification.
So this is a done deal.
Linear regression is also a done deal.
We have the algorithm, remember, that was the pseudo-inverse, the
one-step learning.
And last time, we did a very brief analysis of generalization ability.
And we found that it parallels that of the perceptron, d plus 1 is the
operative point, the operative quantity in this case.
And therefore, we have linear regression as a technique, and as
a generalization ability.
In the case of nonlinear transforms, we are almost done.
We did the techniques, but remember, we left at a point where we say
nonlinear transforms are a very useful tool.
And they actually can make us separate any data points, by going to
a sufficiently high-dimensional space.
And we had a suspicion that this is not really a safe process to follow.
We have to worry about generalization issues.
So the generalization issues were left out.
And I'm going to start this lecture by tying up the loose ends in
generalization for nonlinear transforms, before I go into the main
topic, which is the third one.
That is logistic regression.
So.
Very brief analysis of nonlinear transforms in terms of generalization,
then logistic regression beginning to end.
That's the plan.
OK.
Nonlinear transforms.
Let's remind ourselves.
We were working in an X space.
And we had a d-dimensional vector that represented the input.
And we added the constant +1 coordinate, to
take care of the threshold.
And now, we are going to transform this into another space using
a transformation we called phi.
This takes us into the Z space, or the feature space.
So each of these guys is derived from the raw input x.
And the transformation we have can be quite general. If you
look at it,
any one of these coordinates can be an arbitrary nonlinear transformation of
the entire vector x.
It doesn't take one coordinate.
It takes the entire vector--
so all of these guys--
computes any formula you want, and then puts it as the feature here.
So you can imagine how general this can be.
And also, the length of this can be arbitrary.
You can have this as long as you want.
As a matter of fact, when we move to support vector machines, we will be
able to go to infinite-dimensional feature space, which is an interesting
generalization.
So, each of them is a general transformation.
And therefore, the small phi_i is a member of the big transformation,
capital phi, that takes the vector x, and produces the vector z working in
the Z space.
That's that transform.
An example for that, which we used, was 2nd order.
Instead of using linear surfaces here, we wanted to use quadratic surfaces.
And quadratic surfaces in the X space correspond to linear surfaces in
a quadratic-transformed space, Z.
So this would be the transformation.
We got all possible factors that contribute to a 2nd-order
term.
And now if you put coefficients to each of these and sum them up, you
will get a general 2nd-order surface in the X space.
Now the final hypothesis for us will always live in the X space.
The Z space is transparent to the user.
This is our tool in order to get more sophisticated surfaces in the X space,
while we are able to use the linear techniques.
So the final hypothesis will be mentioned as g of x equals--
So you have the linear thing, but you have that transformed version of x.
That's what you get the dot product with.
So this is z.
And in the case of classification, you take the sign, +1 or -1,
according to the signal whether it is positive or negative.
And in the case of linear regression, you get the raw signal itself.
And as we will see, we will have a third one, which is in-between taking
the sign and leaving the quantity alone, when we talk about logistic
regression.
That's the summary of nonlinear transforms that we have seen so far.
And now we talk about generalization,
and ask ourselves: what is the price we pay when we do a nonlinear transform?
The price we will pay, obviously, in terms of generalization.
So this is the transform.
Now if you look at the X space, and ask: what is the generalization
behavior in the X space?
Let's say that you don't do the nonlinear transform.
You do the linear model in the X space.
Well, in that case, you are going to get a weight vector in the X space.
And the dimensionality of the weight vector is the same as here, so it will
be d plus 1.
There is a weight corresponding to each of these coordinates.
And then you take the dot product, and whether you use threshold, or report it,
depending on which type of linear model you are talking about.
But basically, you have d plus 1 free parameters.
And we realize that d plus 1 free parameters correspond
directly to a VC dimension.
In the case of the Z space, the feature space, we have
potentially a longer vector--
much longer, possibly.
And the dimensionality here is d tilde.
That's the notation we give for it.
And the vector that will apply here will be w tilde.
That will be a much longer vector in general than w.
So for example, in our case, if we used the linear with x_0, x_1, x_2,
we would have 3.
If we did the full 2nd order, we would get 6.
So we get more there.
And we have seen that the VC dimension is, in this case, for the perceptron,
d plus 1.
So this is the price you pay for the generalization.
And here, the price you pay for the generalization can be
pretty serious.
Now you see that if I want to separate the points, and then I go to
a 17th-order polynomial,
general 17th-order polynomial, and then you count the number of
coordinates you have gone to, the VC dimension would be so large that, in
spite of the fact that you were able to fit-- because you went to a 17th
order polynomial--
you don't really have a real chance of generalization.
Just to be accurate, this is really not equality here, because we always
measure the VC dimension in the X space.
Again, the Z space is transparent to the user.
So we go here, and we come back, and we ask ourselves what can we shatter
here and whatnot.
So in spite of the fact that in this case, if you had the full space, and
you were able to choose the points any which way you want, you will be able to get
exactly that VC dimension, it is possible that there are certain
combinations of points here that are impossible to come by as
transformations of legal points here.
If you want a simple case, let me just take two coordinates to be identical--
same transformation.
So obviously, now I'm stuck.
I don't have the full benefit of the coordinates, because if I choose one,
the other one is dictated.
So just because of that fact, in order to be accurate, we will say that it is
actually, at most d plus 1.
Usually, it's very close to d plus 1--
d tilde plus 1.
So let's apply this to two cases where we use nonlinear transformations, in
order to appreciate, in practical terms, what is the price we pay.
The first non-separable case is a pretty easy one.
It's almost separable, except for some points that you can consider, maybe, outliers.
This red point is in the blue region, this blue in the red region.
But otherwise, everything can be classified linearly.
So one may think of this case-- this case is really linearly
separable, and we just have a bunch of outliers, maybe we shouldn't use
nonlinear transform, just settle for the linear--
We will talk about that.
So this is one class of things, when we look at nonlinear
transforms.
The other one is genuinely nonlinear.
This thing-- I really don't stand a chance if I use a line, and therefore,
I'm really talking about something that needs to be transformed.
So let's see how the generalization behavior goes, for both of them when we
apply the nonlinear transforms.
The first case is pretty easy.
It's almost linearly separable.
So here are the choices.
You can use a linear model in X space, in the input space that you have, and
then accept that the in-sample error will be positive.
It's not going to be 0.
In this case, here's the picture.
There is an in-sample error, because this guy is erroneously classified, and
this guy is erroneously classified by your hypothesis.
So this is option number one.
Now, option number two is to say I would like to get E_in to be 0, so you
insist on E_in being zero.
And in order to do that, you have to go to another space.
So you decide to go to a high-dimensional space.
Now you can see what the problem is here, because we are just taking care
of two points, for crying out loud!
And in order to actually be able to classify them using a surface, believe it
or not, you're not going to be able to do it with a 2nd-order surface, or
a 3rd-order surface.
You will have to go to a 4th-order surface in order to get it all right.
And when you do that, this is what you get.
Now, you don't need the VC analysis to realize that this is an overkill, and
this doesn't have a very good chance of generalizing.
Of course, you can do the formal thing.
You see 4th order.
Instead of having 3, I have however many there are.
And therefore, for the limited number of examples I have, when I see the
generalization behavior, I am completely in the dark.
So in this case, that is a straightforward application of the
approximation-generalization tradeoff.
We went to a more complex model.
We were able to approximate the data better, but we are generalizing worse.
This has been completely covered already, so there is no surprise in
this, other than to understand the fact that at times, you might as
well settle for a small training error, in order not to use too high
a complexity for the hypothesis set.
The other one is the case where you really don't stand
a chance with linear.
It will be very, very poor approximation and generalization.
The data seems to be coming from inherently a nonlinear surface.
And in this case, we used this transformation.
And this transformation is my way of putting a general
2nd-order surface.
And if you look at it, if we use only the x, which would be conveniently the
first three guys-- that would be the vector x, get weights--
I have 3 weights, so I pay for the price of 3.
Whereas if I use this, I have 6, so I pay for a price of 6.
So basically, in our mind, you need twice as many examples to do the same
level of performance.
Not that we have a choice in this case, because the linear doesn't work,
but this is basically the formula we have in mind.
Now comes an interesting discussion.
I don't want to pay the 6.
I want to go to the nonlinear space, but I don't want to pay the 6.
I want to get a discount!
Here is a way to get a discount--
not necessarily legitimate, but let's pursue it and see why it would be
legitimate or not.
Why not transform x into this guy only?
The idea here, this is the origin.
x_1 goes like this, x_2 goes like this, so it seems that I only need x_1
squared and x_2 squared.
These guys are just making me pay, without really contributing.
So I'm just going to use this model.
Well, if I use this model, it looks like I have now 3.
So I have exactly the same number of examples as if this was linear, and as
if I was doing it in the X space.
If you are smelling a rat, you are correct!
And in order to make it clear, let's just pursue this line.
I can do even better than this.
Why not take 2 guys instead of 3?
I have the second guy being x_1 squared plus x_2 squared, because I really don't
care about x_1 squared and x_2 squared being independent.
They are just the radius in my mind.
So I need to do this.
Now we have achieved a lot, because now we have even fewer parameters than
if we use the linear guy, so the generalization must be getting better
and better.
Now let's get carried away, and go for the ultimate.
I have one guy.
I even let go of the mandatory constant.
I just have this guy.
And all I'm learning in this case is just what is outside and what is
inside the circle, really.
It doesn't even need a parameter, just needs a binary one.
Now I have one guy, and the VC dimension is 1.
And I can generalize greatly--
dot, dot, dot.
Well, something is wrong.
Now it's clear that something is wrong, but it's very important to
articulate what is wrong.
What is wrong is that you're charging the VC dimension of this hypothesis
set, right?
Think of the VC inequality as providing you with a warranty.
Now in order for the warranty to be valid, you cannot look at the data
before you choose the model.
That will forfeit the warranty.
why does it forfeit it?
Because of the following.
I am going to charge you-- if I do the analysis correctly--
not the VC dimension of the final guy you got.
I'm not going to get the VC dimension of this fellow.
I'm going to charge you the VC dimension of the entire hypothesis
space, that you explored in your mind in getting there, because you have
acted as a learning algorithm, unknowingly.
You looked at the data.
Before you looked at the data, you had no idea.
Let's say that you decided ahead of time, I'm going to use
a 2nd-order set.
2nd order, OK?
Now you look at the data, and you realize that some coefficients are 0.
That's called learning, right?
I don't need this.
You did it very quickly in your mind.
So the hypothesis that was learned was a hierarchical learning.
First, you learned, and then you passed it on to the algorithm to
complete the learning.
So the effective hypothesis set is what you started with.
You see where the point is.
And the lesson learned from this is that, if you look at the data before
you choose the model, this can be hazardous to your health.
Not your health, but the generalization health.
Why is that?
Because now, the quantity that describes generalization
becomes very vague.
When we propose a particular model, I can go and mathematically estimate the
VC dimension.
If you look at the data, we said that you did learning.
Now I'm asking, what is exactly the full hypothesis space that you
explored in the beginning?
That's a little bit vague--
very difficult to pin down.
Definitely bigger than what you are going to use if you use the VC
dimension of the hypothesis set that you ended up with.
And this is a manifestation of the biggest trap that
practitioners fall into.
When you go into machine learning, I want you to learn from the data, and
choosing the model is very tricky.
Some
…

Need subtitles from another video?