Advertisement
English transcript
ANNOUNCER: The following program is brought to you by Caltech.
YASER ABU-MOSTAFA: Welcome back.
Last time, we introduced the main result in learning theory, and there
were two parts.
The first part is to get a handle on the growth function m_H of N, which
characterizes the hypothesis set H. And the way we got a handle on it is
by introducing the idea of a break point, and then bounding the growth
function in terms of a formula that depends on that break point.
There was a simple recursion that you recall by this figure.
And then we finally found the formula that upper-bounds the growth function,
given that it has a break point k.
And it's a combinatorial formula that is fairly easy to understand.
And the most important aspect about it, as far as the theory is concerned,
is that this is polynomial.
It is bounded above by a polynomial in N, since k is a constant.
And if you look at this, this is indeed a polynomial, and the maximum
power you have in this expression is N to the k minus 1.
So not only is it polynomial, but also the order of the polynomial depends on
the break point.
We were interested in the growth function, because it was our way of
characterizing the redundancy that we need to understand, in order to be able
to switch from the Hoeffding inequality to the VC inequality.
And the VC inequality will be the case that handles the learning proper.
And in order to do that, we looked at the bad events that are
characterized by a small area according to Hoeffding.
And then we went here, and looked at the redundancy that results from the
fact that the different hypotheses have, by and large,
overlapping bad regions.
And the way to characterize this was through the growth function.
And after an argument that took the redundancy and related it to the growth
function, and then got rid of a technical problem with E_out, if you
recall that one, we ended up switching completely from the Hoeffding
inequality, which is the top one, into the VC inequality, which is the final
theoretical result in machine learning-- the characterization of
generalization.
And they are very similar except for a fundamental difference, which is here,
and technical differences, which are in the constants.
So as you go through the proof, you will have to change 2's into 4's, and
epsilon into a smaller epsilon, and whatnot.
But the main thing is that instead of the number of hypotheses M, we
were able to replace it by the growth function.
And we had a final technical finesse, because we took the growth function not
on N points, in spite of the fact that we have only N points in the sample.
We needed to have 2N in order to have another sample and carry the argument,
not for the single sample that we have, but for the difference between
two samples.
And that got rid of the technicality that we alluded to, which is the role
of E_out that really destroys the utility of the growth function, because
the growth function depends on dichotomies, and the E_out depends on
the full hypothesis itself.
So this is where we stand.
In today's lecture, I am going to put this together in the main notion
of the theory, which is the VC dimension.
It will not be a new notion for you.
It's very much related to the break point.
But it is the quantity that you are going to remember from all of this
after a while.
So you may forget about the recursion.
You may forget about the growth function.
But you will remember the VC dimension.
And when you are in a learning situation, you ask yourself, what is
the VC dimension?
Is it 7 or 10?
And then you say, oh, this guy is using a hypothesis set with VC
dimension 5000.
He must be crazy. And so on.
So this will be the currency we use out of the theory, in order to use in
a real learning situation.
The topics for today, first I'm going to give the definition, this
will be an easy definition.
And I'm going to discuss it a little bit, to make sure that everybody
understands it.
And then we are going to spend some time getting the VC dimension of
perceptrons.
We will be able to compute the VC dimension exactly for perceptrons, in
any-dimensional space.
It doesn't have to be two-dimensional space, like the one we
did before.
You take any dimension, and we will get the value of the VC dimension exactly.
This is a rare case.
Because usually, when we get the VC dimension, we get a bound on the VC
dimension, just out of the practicality of the situation.
But here, we'll be able to get it exactly.
And that will help us going through the
interpretation of the VC dimension.
We'll ask ourselves.
Now we understand it, and we compute it for a complete case that we are
familiar with.
Then, we would like to understand, what does it signify?
How do we apply it in practice?
And this will be the subject of the interpretation.
Finally, I will spend the last few minutes of the lecture transforming
the theory into a form that is extremely simple, and it's
very easy to remember.
And this is the one that will survive with us for the rest of the course, and
we'll be able to relate it to different theories and
techniques as we go.
So let's start with the definition.
The VC dimension is a quantity that is defined for a hypothesis set.
You give me hypothesis set, I return a number which I call the VC dimension.
And the notation for it will be d, as in dimension, sub VC as in
Vapnik-Chervonenkis.
And it is applied to H. And every now and then, we will drop the
dependency on H, where it is clear from the context.
So we don't have to carry this long notation.
We will just say d_VC, and we'll understand that
this is the VC dimension.
What is it?
In words, it is the most points you can shatter.
That is not a foreign notion for us.
So if you can shatter 20 points, and that is the most you can do, then the
VC dimension is 20.
In terms of the technical quantities we defined, this will be the largest
value of N such that the growth function is 2 to the N. So if you go
one above, the 2 to the N will be broken.
You can think, if VC dimension is the maximum, next one
must be a break point.
And that is, indeed, the case.
The most important thing to realize is that we are talking about the most
points you can shatter.
It doesn't guarantee that every N points-- let's say that the VC
dimension is N. It doesn't say that every N points can be shattered.
All you need is one set of N points that can be shattered, in order to say
that you can shatter N points.
That has always been the case in our analysis.
Let's try to take this definition and interpret it.
Let's say that I computed the VC dimension.
I told you the VC dimension in this case is 15.
Now, what can you say about N which is at most 15, in terms of the ability to
shatter or not?
You can say that if N is at most 15, the VC dimension, then H is guaranteed to
be able to shatter N points.
Which N points I haven't said, but there has to be N points which the
hypothesis set can shatter.
Why is that?
It's simply because, since the VC dimension is this number, there will
be that many points that can be shattered.
Well, any subset of them will have to be shattered as well.
Therefore, a smaller number will also be shattered.
Which means that if N is smaller, you can shatter it.
The other direction is also meaningful.
If N is greater than the VC dimension, now the statement is strong-- N is
a break point.
You cannot shatter any set of that many points.
Because by definition, the VC dimension was the maximum.
And although I called it N here, we used to call it small k.
So anything above the VC dimension is a break point, and anything below, you
can shatter.
Very simple notion.
If you look at the growth function in terms of the VC dimension, when we
had the break points, in terms of this k, we were able to find the bound that
I showed in the review.
So we know that the growth function is bounded above by this formula, and k
appears here for the index of summation, which gives us the maximum
power of this formula.
Now, in terms of the VC dimension, it's not a big deal because the smallest
break point is 1 above the VC dimension.
So all you need to do is substitute, and you will get this formula
involving the VC dimension.
The VC dimension is unique, because it's the maximum.
So you get that number.
And now you can say that the growth function, for any hypothesis set that
has VC dimension d_VC, is bounded above by this.
A nicer formula than this,
because it doesn't have the annoying 1.
And furthermore, when you look at the maximum power in this polynomial, the
maximum power happens to be N to the VC dimension.
So the VC dimension will also serve as the order of the polynomial, that
bounds the growth function of a hypothesis set
that has that VC dimension.
All of this is very simple.
Now, let's take examples in order to get the VC dimension in some cases.
And you have seen this before.
Remember positive rays?
How many points can positive rays shatter?
Just one point, right?
This is where you can get all possible patterns.
If you get two, it's a break point.
Remember that argument?
Therefore, VC dimension here is 1.
Good.
How about 2D perceptrons?
How many can we shatter?
We remember that constellation.
If we have three points in that position, then we can get
all possible patterns.
And 4 is a break point, so we cannot go up.
Therefore, the VC dimension is 3.
Convex sets.
What is the VC dimension of convex sets in two dimensions, the example
that we gave before?
We had this funny construction where, if you choose your points on the
perimeter of a circle, you can shatter any number of points. Right?
Therefore, what would be the VC dimension in this case?
It will be infinite.
There is no maximum.
Now, we said before that this one is particularly pessimistic, which indeed
it is, because this is a very specific way of getting the points.
And in all of the analysis, you will find that using the VC dimension
always gives an upper bound-- worst case.
You cannot violate it, but you can do better at times.
Here, for example, you can do better if you choose the points, let's say,
uniformly over a space.
Therefore, some of them will be internal points.
And therefore, the corresponding growth function, which can be defined
in this case, will not be 2 to the N, and you may be able to learn.
Now, let's look at the VC dimension as it relates to learning.
This is an important viewgraph.
When we talk about learning, we have to go back to our friend, the
learning diagram.
And in case you forgot it, let me magnify it a little bit.
There are different components.
And we have studied the matter so well, that we now can
relate more to this.
Remember, this is the target function, gives me the examples.
Learning algorithm picks the hypothesis, puts it as the final one.
We hope that the final hypothesis approximates this guy.
And we introduced this thing, in order to get the probabilistic analysis.
We have seen this before.
Now, let's look at this diagram, and see what the VC dimension says.
The main result is that if the VC dimension is finite-- that's all you
are asking-- then,
now the green final hypothesis will generalize.
That we have established by the theory.
So you don't even need to know its value.
You just need to know it's finite, and then you can say the g will generalize.
That we have in the bag.
Now, I'd like to understand the rest of the diagram, in terms of the VC
dimension. We can understand the green part.
Here, we'll generalize to the target function, for
better or for worse.
It could be doing very poorly in the in-sample, and that will generalize.
Or could be doing great in the in-sample, and that will generalize.
We are only talking about generalization here.
Now, this statement is independent of the learning algorithm.
Why is that?
Because the learning algorithm here, if it picks a hypothesis, it will have
to pick it from the hypothesis set.
We have gone through all of this trouble, in order to guarantee that
generalization will happen, uniformly, regardless of which
hypothesis you pick.
Therefore, you can find the craziest learning algorithm, and it can pick
anything you want, and you still can make the statement about the final
hypothesis.
So the learning algorithm doesn't matter, as far as
generalization is concerned.
Let's punish it by graying it out.
Now, it's also independent of the input distribution.
This is the box.
This was technically introduced in order to get Hoeffding.
And obviously, it has to survive in order to get the VC inequality.
The reason I am talking about the independence here is because of
an interesting point.
We mentioned that when we define the growth function or the VC dimension, I
give you the budget N and then you choose the points any way you want,
with a view to maximizing the dichotomies, right?
So now there is no probability distribution that can beat you.
I can pick the weirdest probability distribution that has preferences for
funny points, and your choice of the points will be fine,
because you chose the points that maximize.
So whatever the probability distribution does, you
will be doing more.
And therefore, your bound will hold.
Therefore, we don't have to worry about probability distributions.
The learning statement, that this guy will generalize, will hold for any
probability distribution.
So another guy bites the dust.
Now, you look at this and then there is a third guy which is an obvious
one, which is the target function.
All of this analysis, the target function didn't matter at all as far
as generalization is concerned.
We are generalizing to it, but we don't care what it is.
As long as it generates the examples we learn from, and then we test on it,
that's all we care about.
The generalization statement will hold.
So it also goes.
So now as far as the VC theory is concerned, we
really have three blocks.
The first one is the hypothesis.
That is the one that we are claiming the generalization with respect to.
That's number one.
The hypothesis set is where we define the VC dimension.
And if you remember very early on, I told you that the hypothesis set is
a little bit of an artificial notion to introduce as part of
the learning diagram.
And I said that we are going to introduce it
because there is no downside.
There is no loss of generality, which is true.
And there is an upside for the theory.
Now, you can see the upside.
The entire VC theory deals with the hypothesis set by itself.
That's what's has a VC dimension, and that's what will tell you, you are able to
generalize.
The rest of the guys that are more intuitive, that disappeared here, are not
relevant to that theory.
Now, that training examples are left, because the statement that involves
the VC dimension is a probabilistic statement.
It says that, with high probability, you will generalize.
With high probability with respect to what?
It's with respect to generating the data.
You may get a very unlucky data set, for which you are not going to
generalize.
The guarantee is that this happens with a very small probability.
So this remains here, just because it is part of the statement.
And this triangle is where the VC inequality lives.
Now we go into a fun thing of computing the VC dimension for the
perceptrons.
There are two goals for doing this.
We'll do it exactly.
We'll get exact formula for it.
One thing is to test your understanding of the definition.
The definition is a little bit tricky because I give you N. You choose the
points any which way.
You maximize this.
This is a bound, so what is minimum, what is maximum, and whatnot, may be
a little bit fuzzy.
And trying to get the number for a particular case will seal the deal.
So that's number one.
Number two is that, because we understand the perceptron model so
well, we will be able to get the result, which is the VC dimension of
perceptrons.
And that will give us insight into what the VC dimension signifies.
And that will set the stage, when we go to interpreting the VC dimension.
So this is an important part, that will take a little bit of analysis.
For the two-dimensional perceptron, we already have done the exercise, and
we got the VC dimension to be 3.
Right?
Now, if you go for the general case and you have d-dimensional space, you
expect the VC dimension to be more.
Because even if you just go to three dimensions, the troublesome case
of four points, that we had before, is very easily shattered in this case.
Just pick the points not on a plane.
And remember the problem with those guys is that if you want these guys to
be -1 and these guys to be +1, it was a problem for the plane.
Now, you can very easily separate any two points from the other two points
and you can shatter four points.
So the VC dimension went up for sure.
And we ask ourselves: how much did it go up?
Well, it turns out to be a very simple formula.
The VC dimension of perceptrons is exactly d plus 1.
Now we need to prove that.
And we are going to prove it in two stages, very simple stages.
One of them is that we are going to show that the VC dimension is
at most d plus 1.
Then, we are going to show that the VC dimension is at least d plus 1.
And that leaves the single possibility that the VC dimension is d plus 1.
So let's go.
Here is one direction.
And by the way, pay attention because I am going to give you a quiz in the
middle of the argument, to make sure that you are paying attention.
This is for real.
And for the online audience as well.
Here is the first direction.
I am going to construct a specific set of N points, and that N in this case
is d plus 1, because that's the number of points I want to shatter.
And I am going to construct them in the d-dimensional Euclidean
space, R to the d.
I am going to construct them with a view to being able to shatter them.
So I get to choose the points, which is my privilege.
As long as I can shatter them, we are OK.
So what are these points?
I am going to construct them using a matrix.
And you have seen this matrix before.
Remember our old friend linear regression?
We actually set the input points in linear regression this way, in order to
get the algorithm, the pseudo-inverse, and all of that.
And in the case of linear regression, this was a very tall matrix where this
is one data point, which means that it's d plus 1 dimensional vector.
The 1 dimension is the constant x_0, which is the constant +1 we add to
take care of the threshold.
And then the rest of the dimensions, from 1 to d, are actually the
coordinates of the point.
So we put these.
And this is one data point.
This is the second.
This is the third.
And usually, since we have many, many more points than dimensions, this is
a tall matrix.
In this case, I am choosing N to be exactly d plus 1.
And since we already established that this is d plus 1, this is
actually a square matrix in this case.
But that's all I need for the purpose that I am after here.
I need to give you the identity of these guys.
What are these guys?
These guys look like this.
This is no mystery.
See, if you look at the first column, it's all 1's.
Well, it has to be.
That's dictated.
That is the constant coordinate.
It has to be +1.
If I want a legitimate point in this representation, the d plus 1
dimensional representation, the first coordinate has to be 1.
The rest of the guys, I chose the simplest possible form I can imagine.
You have basically a diagonal matrix here, and I added all 0's here.
So these are the guys that are my data set.
Now, you can see that I chose them such that X is invertible, because
that is the technique I'm going to use in order to be able to shatter them.
You will see in a moment.
Do I know that this is invertible?
Yes, the determinant is 1, actually.
And that means it's invertible.
Can you compute the determinant?
This is 1.
And then every time you have this guy, you have the 0 term wiping out
everything.
So I get a 1.
So this is an invertible matrix.
Why am I interested in an invertible matrix?
Because we can shatter the data set.
This is how we are going to do it.
Look at any set of labels you want.
S
…
YASER ABU-MOSTAFA: Welcome back.
Last time, we introduced the main result in learning theory, and there
were two parts.
The first part is to get a handle on the growth function m_H of N, which
characterizes the hypothesis set H. And the way we got a handle on it is
by introducing the idea of a break point, and then bounding the growth
function in terms of a formula that depends on that break point.
There was a simple recursion that you recall by this figure.
And then we finally found the formula that upper-bounds the growth function,
given that it has a break point k.
And it's a combinatorial formula that is fairly easy to understand.
And the most important aspect about it, as far as the theory is concerned,
is that this is polynomial.
It is bounded above by a polynomial in N, since k is a constant.
And if you look at this, this is indeed a polynomial, and the maximum
power you have in this expression is N to the k minus 1.
So not only is it polynomial, but also the order of the polynomial depends on
the break point.
We were interested in the growth function, because it was our way of
characterizing the redundancy that we need to understand, in order to be able
to switch from the Hoeffding inequality to the VC inequality.
And the VC inequality will be the case that handles the learning proper.
And in order to do that, we looked at the bad events that are
characterized by a small area according to Hoeffding.
And then we went here, and looked at the redundancy that results from the
fact that the different hypotheses have, by and large,
overlapping bad regions.
And the way to characterize this was through the growth function.
And after an argument that took the redundancy and related it to the growth
function, and then got rid of a technical problem with E_out, if you
recall that one, we ended up switching completely from the Hoeffding
inequality, which is the top one, into the VC inequality, which is the final
theoretical result in machine learning-- the characterization of
generalization.
And they are very similar except for a fundamental difference, which is here,
and technical differences, which are in the constants.
So as you go through the proof, you will have to change 2's into 4's, and
epsilon into a smaller epsilon, and whatnot.
But the main thing is that instead of the number of hypotheses M, we
were able to replace it by the growth function.
And we had a final technical finesse, because we took the growth function not
on N points, in spite of the fact that we have only N points in the sample.
We needed to have 2N in order to have another sample and carry the argument,
not for the single sample that we have, but for the difference between
two samples.
And that got rid of the technicality that we alluded to, which is the role
of E_out that really destroys the utility of the growth function, because
the growth function depends on dichotomies, and the E_out depends on
the full hypothesis itself.
So this is where we stand.
In today's lecture, I am going to put this together in the main notion
of the theory, which is the VC dimension.
It will not be a new notion for you.
It's very much related to the break point.
But it is the quantity that you are going to remember from all of this
after a while.
So you may forget about the recursion.
You may forget about the growth function.
But you will remember the VC dimension.
And when you are in a learning situation, you ask yourself, what is
the VC dimension?
Is it 7 or 10?
And then you say, oh, this guy is using a hypothesis set with VC
dimension 5000.
He must be crazy. And so on.
So this will be the currency we use out of the theory, in order to use in
a real learning situation.
The topics for today, first I'm going to give the definition, this
will be an easy definition.
And I'm going to discuss it a little bit, to make sure that everybody
understands it.
And then we are going to spend some time getting the VC dimension of
perceptrons.
We will be able to compute the VC dimension exactly for perceptrons, in
any-dimensional space.
It doesn't have to be two-dimensional space, like the one we
did before.
You take any dimension, and we will get the value of the VC dimension exactly.
This is a rare case.
Because usually, when we get the VC dimension, we get a bound on the VC
dimension, just out of the practicality of the situation.
But here, we'll be able to get it exactly.
And that will help us going through the
interpretation of the VC dimension.
We'll ask ourselves.
Now we understand it, and we compute it for a complete case that we are
familiar with.
Then, we would like to understand, what does it signify?
How do we apply it in practice?
And this will be the subject of the interpretation.
Finally, I will spend the last few minutes of the lecture transforming
the theory into a form that is extremely simple, and it's
very easy to remember.
And this is the one that will survive with us for the rest of the course, and
we'll be able to relate it to different theories and
techniques as we go.
So let's start with the definition.
The VC dimension is a quantity that is defined for a hypothesis set.
You give me hypothesis set, I return a number which I call the VC dimension.
And the notation for it will be d, as in dimension, sub VC as in
Vapnik-Chervonenkis.
And it is applied to H. And every now and then, we will drop the
dependency on H, where it is clear from the context.
So we don't have to carry this long notation.
We will just say d_VC, and we'll understand that
this is the VC dimension.
What is it?
In words, it is the most points you can shatter.
That is not a foreign notion for us.
So if you can shatter 20 points, and that is the most you can do, then the
VC dimension is 20.
In terms of the technical quantities we defined, this will be the largest
value of N such that the growth function is 2 to the N. So if you go
one above, the 2 to the N will be broken.
You can think, if VC dimension is the maximum, next one
must be a break point.
And that is, indeed, the case.
The most important thing to realize is that we are talking about the most
points you can shatter.
It doesn't guarantee that every N points-- let's say that the VC
dimension is N. It doesn't say that every N points can be shattered.
All you need is one set of N points that can be shattered, in order to say
that you can shatter N points.
That has always been the case in our analysis.
Let's try to take this definition and interpret it.
Let's say that I computed the VC dimension.
I told you the VC dimension in this case is 15.
Now, what can you say about N which is at most 15, in terms of the ability to
shatter or not?
You can say that if N is at most 15, the VC dimension, then H is guaranteed to
be able to shatter N points.
Which N points I haven't said, but there has to be N points which the
hypothesis set can shatter.
Why is that?
It's simply because, since the VC dimension is this number, there will
be that many points that can be shattered.
Well, any subset of them will have to be shattered as well.
Therefore, a smaller number will also be shattered.
Which means that if N is smaller, you can shatter it.
The other direction is also meaningful.
If N is greater than the VC dimension, now the statement is strong-- N is
a break point.
You cannot shatter any set of that many points.
Because by definition, the VC dimension was the maximum.
And although I called it N here, we used to call it small k.
So anything above the VC dimension is a break point, and anything below, you
can shatter.
Very simple notion.
If you look at the growth function in terms of the VC dimension, when we
had the break points, in terms of this k, we were able to find the bound that
I showed in the review.
So we know that the growth function is bounded above by this formula, and k
appears here for the index of summation, which gives us the maximum
power of this formula.
Now, in terms of the VC dimension, it's not a big deal because the smallest
break point is 1 above the VC dimension.
So all you need to do is substitute, and you will get this formula
involving the VC dimension.
The VC dimension is unique, because it's the maximum.
So you get that number.
And now you can say that the growth function, for any hypothesis set that
has VC dimension d_VC, is bounded above by this.
A nicer formula than this,
because it doesn't have the annoying 1.
And furthermore, when you look at the maximum power in this polynomial, the
maximum power happens to be N to the VC dimension.
So the VC dimension will also serve as the order of the polynomial, that
bounds the growth function of a hypothesis set
that has that VC dimension.
All of this is very simple.
Now, let's take examples in order to get the VC dimension in some cases.
And you have seen this before.
Remember positive rays?
How many points can positive rays shatter?
Just one point, right?
This is where you can get all possible patterns.
If you get two, it's a break point.
Remember that argument?
Therefore, VC dimension here is 1.
Good.
How about 2D perceptrons?
How many can we shatter?
We remember that constellation.
If we have three points in that position, then we can get
all possible patterns.
And 4 is a break point, so we cannot go up.
Therefore, the VC dimension is 3.
Convex sets.
What is the VC dimension of convex sets in two dimensions, the example
that we gave before?
We had this funny construction where, if you choose your points on the
perimeter of a circle, you can shatter any number of points. Right?
Therefore, what would be the VC dimension in this case?
It will be infinite.
There is no maximum.
Now, we said before that this one is particularly pessimistic, which indeed
it is, because this is a very specific way of getting the points.
And in all of the analysis, you will find that using the VC dimension
always gives an upper bound-- worst case.
You cannot violate it, but you can do better at times.
Here, for example, you can do better if you choose the points, let's say,
uniformly over a space.
Therefore, some of them will be internal points.
And therefore, the corresponding growth function, which can be defined
in this case, will not be 2 to the N, and you may be able to learn.
Now, let's look at the VC dimension as it relates to learning.
This is an important viewgraph.
When we talk about learning, we have to go back to our friend, the
learning diagram.
And in case you forgot it, let me magnify it a little bit.
There are different components.
And we have studied the matter so well, that we now can
relate more to this.
Remember, this is the target function, gives me the examples.
Learning algorithm picks the hypothesis, puts it as the final one.
We hope that the final hypothesis approximates this guy.
And we introduced this thing, in order to get the probabilistic analysis.
We have seen this before.
Now, let's look at this diagram, and see what the VC dimension says.
The main result is that if the VC dimension is finite-- that's all you
are asking-- then,
now the green final hypothesis will generalize.
That we have established by the theory.
So you don't even need to know its value.
You just need to know it's finite, and then you can say the g will generalize.
That we have in the bag.
Now, I'd like to understand the rest of the diagram, in terms of the VC
dimension. We can understand the green part.
Here, we'll generalize to the target function, for
better or for worse.
It could be doing very poorly in the in-sample, and that will generalize.
Or could be doing great in the in-sample, and that will generalize.
We are only talking about generalization here.
Now, this statement is independent of the learning algorithm.
Why is that?
Because the learning algorithm here, if it picks a hypothesis, it will have
to pick it from the hypothesis set.
We have gone through all of this trouble, in order to guarantee that
generalization will happen, uniformly, regardless of which
hypothesis you pick.
Therefore, you can find the craziest learning algorithm, and it can pick
anything you want, and you still can make the statement about the final
hypothesis.
So the learning algorithm doesn't matter, as far as
generalization is concerned.
Let's punish it by graying it out.
Now, it's also independent of the input distribution.
This is the box.
This was technically introduced in order to get Hoeffding.
And obviously, it has to survive in order to get the VC inequality.
The reason I am talking about the independence here is because of
an interesting point.
We mentioned that when we define the growth function or the VC dimension, I
give you the budget N and then you choose the points any way you want,
with a view to maximizing the dichotomies, right?
So now there is no probability distribution that can beat you.
I can pick the weirdest probability distribution that has preferences for
funny points, and your choice of the points will be fine,
because you chose the points that maximize.
So whatever the probability distribution does, you
will be doing more.
And therefore, your bound will hold.
Therefore, we don't have to worry about probability distributions.
The learning statement, that this guy will generalize, will hold for any
probability distribution.
So another guy bites the dust.
Now, you look at this and then there is a third guy which is an obvious
one, which is the target function.
All of this analysis, the target function didn't matter at all as far
as generalization is concerned.
We are generalizing to it, but we don't care what it is.
As long as it generates the examples we learn from, and then we test on it,
that's all we care about.
The generalization statement will hold.
So it also goes.
So now as far as the VC theory is concerned, we
really have three blocks.
The first one is the hypothesis.
That is the one that we are claiming the generalization with respect to.
That's number one.
The hypothesis set is where we define the VC dimension.
And if you remember very early on, I told you that the hypothesis set is
a little bit of an artificial notion to introduce as part of
the learning diagram.
And I said that we are going to introduce it
because there is no downside.
There is no loss of generality, which is true.
And there is an upside for the theory.
Now, you can see the upside.
The entire VC theory deals with the hypothesis set by itself.
That's what's has a VC dimension, and that's what will tell you, you are able to
generalize.
The rest of the guys that are more intuitive, that disappeared here, are not
relevant to that theory.
Now, that training examples are left, because the statement that involves
the VC dimension is a probabilistic statement.
It says that, with high probability, you will generalize.
With high probability with respect to what?
It's with respect to generating the data.
You may get a very unlucky data set, for which you are not going to
generalize.
The guarantee is that this happens with a very small probability.
So this remains here, just because it is part of the statement.
And this triangle is where the VC inequality lives.
Now we go into a fun thing of computing the VC dimension for the
perceptrons.
There are two goals for doing this.
We'll do it exactly.
We'll get exact formula for it.
One thing is to test your understanding of the definition.
The definition is a little bit tricky because I give you N. You choose the
points any which way.
You maximize this.
This is a bound, so what is minimum, what is maximum, and whatnot, may be
a little bit fuzzy.
And trying to get the number for a particular case will seal the deal.
So that's number one.
Number two is that, because we understand the perceptron model so
well, we will be able to get the result, which is the VC dimension of
perceptrons.
And that will give us insight into what the VC dimension signifies.
And that will set the stage, when we go to interpreting the VC dimension.
So this is an important part, that will take a little bit of analysis.
For the two-dimensional perceptron, we already have done the exercise, and
we got the VC dimension to be 3.
Right?
Now, if you go for the general case and you have d-dimensional space, you
expect the VC dimension to be more.
Because even if you just go to three dimensions, the troublesome case
of four points, that we had before, is very easily shattered in this case.
Just pick the points not on a plane.
And remember the problem with those guys is that if you want these guys to
be -1 and these guys to be +1, it was a problem for the plane.
Now, you can very easily separate any two points from the other two points
and you can shatter four points.
So the VC dimension went up for sure.
And we ask ourselves: how much did it go up?
Well, it turns out to be a very simple formula.
The VC dimension of perceptrons is exactly d plus 1.
Now we need to prove that.
And we are going to prove it in two stages, very simple stages.
One of them is that we are going to show that the VC dimension is
at most d plus 1.
Then, we are going to show that the VC dimension is at least d plus 1.
And that leaves the single possibility that the VC dimension is d plus 1.
So let's go.
Here is one direction.
And by the way, pay attention because I am going to give you a quiz in the
middle of the argument, to make sure that you are paying attention.
This is for real.
And for the online audience as well.
Here is the first direction.
I am going to construct a specific set of N points, and that N in this case
is d plus 1, because that's the number of points I want to shatter.
And I am going to construct them in the d-dimensional Euclidean
space, R to the d.
I am going to construct them with a view to being able to shatter them.
So I get to choose the points, which is my privilege.
As long as I can shatter them, we are OK.
So what are these points?
I am going to construct them using a matrix.
And you have seen this matrix before.
Remember our old friend linear regression?
We actually set the input points in linear regression this way, in order to
get the algorithm, the pseudo-inverse, and all of that.
And in the case of linear regression, this was a very tall matrix where this
is one data point, which means that it's d plus 1 dimensional vector.
The 1 dimension is the constant x_0, which is the constant +1 we add to
take care of the threshold.
And then the rest of the dimensions, from 1 to d, are actually the
coordinates of the point.
So we put these.
And this is one data point.
This is the second.
This is the third.
And usually, since we have many, many more points than dimensions, this is
a tall matrix.
In this case, I am choosing N to be exactly d plus 1.
And since we already established that this is d plus 1, this is
actually a square matrix in this case.
But that's all I need for the purpose that I am after here.
I need to give you the identity of these guys.
What are these guys?
These guys look like this.
This is no mystery.
See, if you look at the first column, it's all 1's.
Well, it has to be.
That's dictated.
That is the constant coordinate.
It has to be +1.
If I want a legitimate point in this representation, the d plus 1
dimensional representation, the first coordinate has to be 1.
The rest of the guys, I chose the simplest possible form I can imagine.
You have basically a diagonal matrix here, and I added all 0's here.
So these are the guys that are my data set.
Now, you can see that I chose them such that X is invertible, because
that is the technique I'm going to use in order to be able to shatter them.
You will see in a moment.
Do I know that this is invertible?
Yes, the determinant is 1, actually.
And that means it's invertible.
Can you compute the determinant?
This is 1.
And then every time you have this guy, you have the 0 term wiping out
everything.
So I get a 1.
So this is an invertible matrix.
Why am I interested in an invertible matrix?
Because we can shatter the data set.
This is how we are going to do it.
Look at any set of labels you want.
S
…