Advertisement
English transcript
ANNOUNCER: The following program is brought to you by Caltech.
YASER ABU-MOSTAFA: Welcome back.
Last time, we discussed the feasibility of learning.
And we realized that learning is indeed feasible, but only in
a probabilistic sense.
And we modeled that probabilistic sense in terms of a bin that has
an out-of-sample performance.
We already mapped that to the out-of-sample performance.
The performance we don't know.
And in order to be able to tell what E_out of h is-- h is the hypothesis that
corresponds to that particular bin--
we look at the in-sample.
And we realize that the in-sample tracks the out-of-sample well through
the mathematical relationship which is the Hoeffding Inequality, that tells
us that the probability that E_in deviates from E_out by more than our
specified tolerance is a small number.
And that small number is a negative exponential in N.
So the bigger the sample, the more reliable that E_in
will track E_out well.
That was the basic building block.
But then we realized that this applies to a single bin.
And a single bin corresponds to a single hypothesis.
So now we go for a case where we have a full model, h_1 up to h_M.
And we take the simple case of a finite hypothesis set.
And we ask ourselves, what would apply in this case?
We realized that the problem with having multiple hypotheses is that the
probability of something bad happening could accumulate.
Because if there is a 0.5% chance that the first hypothesis is bad,
in the sense of bad generalization,
and 0.5% for the second one, we could be so unlucky as to have these 0.5%
accumulate, and end up with a significant probability that one of
the hypotheses will be bad.
And when one of the hypotheses will be bad, if we are further unlucky, and
this is the hypothesis we pick as our final hypothesis, then E_in will not
track E_out for the hypothesis we pick.
So we need to accommodate the case where we have multiple hypotheses.
And the argument was extremely simple.
g is our notation for the final hypothesis.
It is one of these guys that the algorithm will choose.
Well, the probability that E_in doesn't track E_out will obviously be
included in the fact that E_in for h_1 doesn't track the out-of-sample for
that one, or E_in for h_2 doesn't track, or E_in of h_M doesn't track.
The reason is very simple.
g is one of the guys.
If something bad happens with g, it must happen with one of these guys at
least, the one that was picked.
So we can always say that this implies these things, which is this or this or
this or this or this.
And after that, we apply a very simple mathematical rule, which
is the union bound.
The probability of an event or another event or another event is at most the
sum of the probabilities.
That rule applies regardless of the correlation between these events,
because it takes the worst-case scenario.
If all the bad events happen disjointly, then you add up the
probabilities.
If there is some correlation, and they overlap, you will
get a smaller number.
In all of the cases, the probability of this big event will be less than or
equal to the sum of the individual probabilities.
And this is useful because in the coin flipping case, which started this
argument, the events are independent.
In the case of the hypotheses of a model, the events may not be
independent, because we have the same sample.
And we are only changing the hypotheses.
So it could be that the deviation here is related to the deviation here.
But the union bound doesn't care.
Regardless of such correlations, you will be able to get a bound on the
probability of this event.
And therefore, you will be able to bound the probability that you care
about, which has to do with the generalization, to the individual
Hoeffding applied to each of those.
And since you have M of them, you have an added M factor.
So the final answer is that the probability of something bad happening
after learning is less than or equal to this quantity, which is a helpful
small quantity, times M. And we realize that now we have a problem
because if you use a bigger hypothesis set, M will be bigger.
And therefore, the right-hand side here will become bigger and bigger
when you add the M. And therefore, at some point, it will even become
meaningless.
And we are not even worried yet about M being infinity, which will
be true for many hypothesis sets, in which case, this is totally
meaningless.
However, we weren't establishing the final result in learning.
We were establishing the principle that, through learning, you can
generalize.
And we have established that.
It will take us a couple of weeks to get from that to the ability to say
that a general learning model, an infinite one, will generalize. And we will
get the bound on generalization.
That's what the theory of generalization will address.
So today the subject is linear models.
And as I mentioned at the beginning, this is out of sequence.
If I was following the logical sequence, I would go immediately to
the theory and take M, which takes care of the finite case,
and then generalize it to the more general case.
However, as I mentioned, I decided to give you something concrete and
practical to work with early on.
And then we will go back to the theory after that.
The linear model is one of the most important models in machine learning.
And what we are going to do in this lecture,
we're going to start with a practical data set that we are going to use over
and over in this class.
And then, if you remember the perceptron that we introduced in the
first lecture, the perceptron is a linear model.
So here is the sequence of the lecture.
We are going to take the perceptron and generalize it to non-separable data.
That's a relief, because we already admitted that separable
data is very rare.
And we would like to see what will happen when we have
non-separable data.
Then, we are going to generalize this further to the case where the target
function is not a binary classification function, but a real-valued function.
That also is a very important generalization.
And linear regression, as you will see, is one of the most important
techniques that is applied mostly in statistics and economics, and also in
machine learning.
Finally, as if we didn't do enough generalization already, we are going
to take this and generalize it to a nonlinear case.
All in a day's work, all in one lecture.
It's a pretty simple model.
And at the end of the lecture, you will be able to actually deal with
very general situations.
And you may ask yourself, why am I calling the lecture Linear Model when
I'm going to talk about nonlinear transformation?
Well, you'll realize that nonlinear transformation remains within the
realm of linear models.
That's not obvious.
We will see how that materializes.
So that's the plan.
Now, let's look at a real data set that we are going to use, and will be
available to you to try different ideas on.
And it's very important to try your ideas on real data.
Regardless of how sure you are when you have a toy data set that
you generate, you should always go for real data sets and see how the system
that you thought of performs in reality.
So here is the data set.
It comes from ZIP codes in the postal office.
So people write the ZIP code.
And you extract individual characters, individual digits.
And you would like to take the image, which happens to be 16 by 16 gray
level pixels, and be able to decipher what is the number in it.
Well, that looks easy except that people write digits in so many
different ways.
And if you look at it, there will be some cases like this fellow.
Is this a 1 or a 7?
Is this a 0 or an 8?
So you can see that there is a problem.
And indeed, if you get a human operator to actually read these things
and classify them, they will probably be making an error of about 2.5%.
And we would like to see if machine learning can at least equal that,
which means that we can automate the process, or maybe beat that.
So this is a data set that we are going to work with.
Let's look at it a little bit more closely to see how we input it to
our algorithm.
We have one algorithm so far, which is the perceptron learning algorithm. We
are going to try on this.
And then we are going to generalize it a little bit.
The first item is the question of input representation.
What do I mean?
This is your input, the raw input, if you will.
Now this is 16 pixels by 16 pixels.
So there are 256 real numbers in that input.
If you look at the raw input x, this would be x_1, x_2, x_3, dot, dot,
dot, dot, and x_256.
That's a very long input to encode such a simple object.
And we add our mandatory x_0.
Remember, in linear models, we have this constant coordinate,
x_0 equals 1, we add in order to take care of the threshold.
So this will always be in the background whether we
mention it or not.
If you take this raw input and try the perceptron directly on it, you
realize that the linear model in this case, which has a bunch of parameters,
has really just too many parameters.
It has 257 parameters.
If you are working in a 257th-dimensional space,
that is a huge space.
And the poor algorithm is trying to simultaneously determine the values of
all of these w's based on your set.
So the idea of input representation is to simplify the algorithm's life.
We know something about the problem.
We know that it's not really the individual pixels
that matter.
You can probably extract some features from the input, and then give those to
the learning algorithm and let the learning algorithm
figure out the pattern.
So this gives us the idea of features.
What are features?
Well, you extract the useful information.
And as a suggestion, very simple one, let's say that in this particular
case, instead of giving the raw input with all of the pixel values, you
extract some descriptors of what the image is like.
For instance, you look at this.
Depending on whether this is the digital 8 or the digit 1, et cetera,
there is a question of the intensity, average intensity.
1 doesn't have too many black pixels.
8 has a lot.
5 has some.
So if you simply add up the intensity of all the pixels, you
probably will get a number that is related to the identity.
It doesn't uniquely determine it, but it's related.
It's a higher-level representation of the raw information
there. Same as symmetry--
if you think of the digit 1, 1 will be symmetric.
If you flip it upside down, or you flip it right and left, you will get
something that overlaps significantly with it.
So you can also define a symmetry measure, which means that you take the
symmetric difference between something and its flipped versions, and you see
what you get.
If something is symmetric, things will cancel because it's symmetric.
You'll get a very small value.
And if something is not symmetric, let's say like the 5, you will get
lots of values in the symmetric difference.
And you will get a high value for that.
So what you are measuring is the anti-symmetry.
You take the negative of that, and you get the symmetry.
So you get another guy, which is the symmetry.
So now, x_1 is the intensity variable,
x_2 is the symmetry variable.
Now admittedly, you have lost information in that process.
But the chances are you lost as much irrelevant information as relevant
information.
So this is a pretty good representation of the input, as far as
the learning algorithm is concerned.
And you went from 257 dimensional to 3 dimensional.
That's a pretty good situation.
And you probably realize that having 257 parameters is bad news for
generalization, if you extrapolate from what we said.
Having 3 is a much better situation.
So this is what we are going to work with.
When you take the linear model in this case, you just
have w_0, w_1, and w_2.
And that's what the perceptron algorithm, for example, needs to use--
to determine.
Now let's look at the illustration of these features.
You have these as your inputs.
And x_1 is the intensity,
x_2 is the symmetry.
What do they look like?
They look like this.
This is a scatter diagram.
Every point here is a data point.
It's one of the digits, one of the images you have.
And I'm taking the simple case of just distinguishing the 1's from the 5's.
So I'm only taking digits that are 1's or 5's.
And you can always take other digits versus each other, and
then combine the decision.
If you can solve this unit problem, you can generalize it
to the other problem.
So when you put all the 1's and all the 5's in a scatter diagram, you realize
for example that the intensity on the 5's is usually more than the
intensity on the 1's.
There are more pixels occupied by the 5's than the 1's.
This is the coordinate which is the intensity.
And indeed, the red guys, which happen to be the 5's, are tilted
a little bit more to the right, corresponding to the intensity.
If you look at the other coordinate, which is symmetry, the 1 is often more
symmetric than the 5.
Therefore, the guys that happen to be the 1's, that are the blue, tend to be
higher on the vertical coordinate.
And just by these two coordinates, you already see that this is almost
linearly separable.
Not quite, but it's separable enough that if you pass a boundary
here, you will be getting most of them right.
Now you realize that it's impossible really to ask to get all of them right
because, believe it or not, this fellow is a 5, at least meant to be a 5 by
the guy who wrote it.
So we have to accept the fact that there will be stuff that
is completely undoable.
And we will accept an error.
It's not a zero error.
But hopefully, it's a small error.
So this is what the features look like.
Now what does the perceptron learning algorithm do?
What it does is this complicated figure, which takes the evolution of
E_in and E_out as a function of iteration.
When you apply the perceptron learning algorithm, you apply it only to E_in.
E_in is the only value you have.
E_out is sitting out there.
We don't know what it is.
We just hope that E_in tracks it well.
Let's look at the figure.
These are the iteration numbers.
So this is the first misclassified example.
You go and apply the perceptron learning algorithm again, again, again
for 1000 times.
As you do that, E_in, which is the green curve, will go down and
sometimes will go up.
We realize that the perceptron learning algorithm takes care of one
point at a time, and therefore may mess up other points while it's taking care
of a point.
So in general, it can go up or down.
But the bad news here is that the data is not linearly separable.
And we made the remark that the perceptron learning algorithm behaves
very badly when the data is not linearly separable.
It can go from something pretty good to something pretty
bad, in just one iteration.
So this is a very typical behavior of the perceptron learning algorithm.
Because the data is not linearly separable, the perceptron learning
algorithm will never converge.
So what do we do?
We force it to terminate at iteration 1000.
That is, we stop at 1000 and take whatever weight vector we have.
And we call this g, the final hypothesis of the
perceptron learning algorithm.
Now we obviously look at this, and we say, if I only took this guy.
This is a better guy than the other.
But you know, you're just applying the algorithm and cutting it off.
Now, one of the things you observe from here, I plotted E_out.
You're not going to be able to plot E_out in a real problem that you deal
with, if E_out is really an unknown function.
You may be able to estimate it using some test examples.
But all you need to know here is that E_out is drawn here for illustration,
just to tell you what is happening in reality as you work on
the in-sample error.
And in this case, you find that E_out actually tracks the E_in pretty well.
There is a difference.
So if we go from here to here, that's our epsilon.
It's a big epsilon.
But the good news is that it tracks it.
When this goes down, this goes down.
When this goes up, this goes up.
So if you make your decision based on E_in, the decision based on E_out will
also be good.
That's good for generalization.
And that is one of the advantages of something as simple as the perceptron
learning algorithm.
It doesn't have too many parameters.
And because of our efforts in getting only three features, it has even three
parameters now.
So the chances are that it will generalize well, which it does.
Now what does the final boundary look like?
This is only the illustration here,
it's just-- this is the evolution.
Eventually, you end up with a hypothesis.
The hypothesis would separate the points in the scatter diagram you saw.
So what does it look like?
Well, it looks like this.
This is your boundary.
This is the final hypothesis, that corresponds to the hypothesis you got
at the final iteration.
Well, it's OK, but definitely not good.
It's too deep into the blue region.
You would have been better off doing this.
And the chances are maybe earlier guys that had better in-sample
error will do that.
But that's what you have to live with, if you apply the
perceptron learning algorithm.
So now we go and try to modify the perceptron learning algorithm in
a very simple way, that is the simplest modification you can ever imagine.
So let's see what happens.
This is what that PLA did, right?
And when we looked at it, we said: if we only could keep this value.
Well, this value is not a mystery.
It happened in your algorithm.
You can measure it explicitly.
It's an in-sample error.
And you know that it's better than the value you ended up with.
So in spite of the fact that you're doing these iterations according to
the prescribed perceptron learning algorithm rule-- modify the weights
according to one misclassified point-- you can keep track of the total
in-sample error of the intermediate hypothesis you got.
Right?
And only keep the guy that happens to be the best throughout.
So you're going to continue as if it's really the
perceptron learning algorithm.
But when you are at the end, you keep this guy and report it as the final
hypothesis.
What an ingenious idea!
Now the reason the algorithm is called the pocket algorithm is because the
whole idea is to put the best solution so far in your pocket.
And when you get a better one, you take the better one, put it in your
pocket, and throw the old one.
And when you are done, report the guy in your pocket.
We can do that.
What does this diagram look like, when you are looking
at the pocket algorithm?
Much better.
You can look at these values, and it is the best value so far.
Here, we went down.
And here, we indeed went down.
Here, we went up.
You see this green thing?
Here, we didn't, because the good guy is in our pocket and that's what we're
reporting the value for.
And we continued with it until we dropped again.
And we dropped again.
And we never changed that, because there was never a better
guy than this guy.
So when we come to iteration 1000, we have this fellow.
Now when you do that, you can use perceptron learning algorithm with
non-separable data, terminate it by force at some iteration, and report the
pocket value.
And that will be your pocket algorithm.
And if you look at the classification boundary, PLA versus pocket, this is
what we had with the perceptron learning algorithm.
We complained a little bit that it's too deep in the blue region.
And when you look at the other guy, which is the pocket algorithm, it
looks better.
It actually does what we thought it would do.
It separates them better.
Still, obviously, it cannot separate them perfectly.
Nothing can, because they are not linearly separable.
On the other hand, this is a good hypothesis to report.
So with this very simple algorithm, you can actually deal with general
inseparable data, but inseparable data in the sense that
it's basically separable.
However, it really is--
this guy is bad, and this guys is bad.
There's nothing we can do about them.
But there are few, so we will just settle for this.
We'll see that there are other cases of inseparable data that is truly
inseparable, in which we
…
YASER ABU-MOSTAFA: Welcome back.
Last time, we discussed the feasibility of learning.
And we realized that learning is indeed feasible, but only in
a probabilistic sense.
And we modeled that probabilistic sense in terms of a bin that has
an out-of-sample performance.
We already mapped that to the out-of-sample performance.
The performance we don't know.
And in order to be able to tell what E_out of h is-- h is the hypothesis that
corresponds to that particular bin--
we look at the in-sample.
And we realize that the in-sample tracks the out-of-sample well through
the mathematical relationship which is the Hoeffding Inequality, that tells
us that the probability that E_in deviates from E_out by more than our
specified tolerance is a small number.
And that small number is a negative exponential in N.
So the bigger the sample, the more reliable that E_in
will track E_out well.
That was the basic building block.
But then we realized that this applies to a single bin.
And a single bin corresponds to a single hypothesis.
So now we go for a case where we have a full model, h_1 up to h_M.
And we take the simple case of a finite hypothesis set.
And we ask ourselves, what would apply in this case?
We realized that the problem with having multiple hypotheses is that the
probability of something bad happening could accumulate.
Because if there is a 0.5% chance that the first hypothesis is bad,
in the sense of bad generalization,
and 0.5% for the second one, we could be so unlucky as to have these 0.5%
accumulate, and end up with a significant probability that one of
the hypotheses will be bad.
And when one of the hypotheses will be bad, if we are further unlucky, and
this is the hypothesis we pick as our final hypothesis, then E_in will not
track E_out for the hypothesis we pick.
So we need to accommodate the case where we have multiple hypotheses.
And the argument was extremely simple.
g is our notation for the final hypothesis.
It is one of these guys that the algorithm will choose.
Well, the probability that E_in doesn't track E_out will obviously be
included in the fact that E_in for h_1 doesn't track the out-of-sample for
that one, or E_in for h_2 doesn't track, or E_in of h_M doesn't track.
The reason is very simple.
g is one of the guys.
If something bad happens with g, it must happen with one of these guys at
least, the one that was picked.
So we can always say that this implies these things, which is this or this or
this or this or this.
And after that, we apply a very simple mathematical rule, which
is the union bound.
The probability of an event or another event or another event is at most the
sum of the probabilities.
That rule applies regardless of the correlation between these events,
because it takes the worst-case scenario.
If all the bad events happen disjointly, then you add up the
probabilities.
If there is some correlation, and they overlap, you will
get a smaller number.
In all of the cases, the probability of this big event will be less than or
equal to the sum of the individual probabilities.
And this is useful because in the coin flipping case, which started this
argument, the events are independent.
In the case of the hypotheses of a model, the events may not be
independent, because we have the same sample.
And we are only changing the hypotheses.
So it could be that the deviation here is related to the deviation here.
But the union bound doesn't care.
Regardless of such correlations, you will be able to get a bound on the
probability of this event.
And therefore, you will be able to bound the probability that you care
about, which has to do with the generalization, to the individual
Hoeffding applied to each of those.
And since you have M of them, you have an added M factor.
So the final answer is that the probability of something bad happening
after learning is less than or equal to this quantity, which is a helpful
small quantity, times M. And we realize that now we have a problem
because if you use a bigger hypothesis set, M will be bigger.
And therefore, the right-hand side here will become bigger and bigger
when you add the M. And therefore, at some point, it will even become
meaningless.
And we are not even worried yet about M being infinity, which will
be true for many hypothesis sets, in which case, this is totally
meaningless.
However, we weren't establishing the final result in learning.
We were establishing the principle that, through learning, you can
generalize.
And we have established that.
It will take us a couple of weeks to get from that to the ability to say
that a general learning model, an infinite one, will generalize. And we will
get the bound on generalization.
That's what the theory of generalization will address.
So today the subject is linear models.
And as I mentioned at the beginning, this is out of sequence.
If I was following the logical sequence, I would go immediately to
the theory and take M, which takes care of the finite case,
and then generalize it to the more general case.
However, as I mentioned, I decided to give you something concrete and
practical to work with early on.
And then we will go back to the theory after that.
The linear model is one of the most important models in machine learning.
And what we are going to do in this lecture,
we're going to start with a practical data set that we are going to use over
and over in this class.
And then, if you remember the perceptron that we introduced in the
first lecture, the perceptron is a linear model.
So here is the sequence of the lecture.
We are going to take the perceptron and generalize it to non-separable data.
That's a relief, because we already admitted that separable
data is very rare.
And we would like to see what will happen when we have
non-separable data.
Then, we are going to generalize this further to the case where the target
function is not a binary classification function, but a real-valued function.
That also is a very important generalization.
And linear regression, as you will see, is one of the most important
techniques that is applied mostly in statistics and economics, and also in
machine learning.
Finally, as if we didn't do enough generalization already, we are going
to take this and generalize it to a nonlinear case.
All in a day's work, all in one lecture.
It's a pretty simple model.
And at the end of the lecture, you will be able to actually deal with
very general situations.
And you may ask yourself, why am I calling the lecture Linear Model when
I'm going to talk about nonlinear transformation?
Well, you'll realize that nonlinear transformation remains within the
realm of linear models.
That's not obvious.
We will see how that materializes.
So that's the plan.
Now, let's look at a real data set that we are going to use, and will be
available to you to try different ideas on.
And it's very important to try your ideas on real data.
Regardless of how sure you are when you have a toy data set that
you generate, you should always go for real data sets and see how the system
that you thought of performs in reality.
So here is the data set.
It comes from ZIP codes in the postal office.
So people write the ZIP code.
And you extract individual characters, individual digits.
And you would like to take the image, which happens to be 16 by 16 gray
level pixels, and be able to decipher what is the number in it.
Well, that looks easy except that people write digits in so many
different ways.
And if you look at it, there will be some cases like this fellow.
Is this a 1 or a 7?
Is this a 0 or an 8?
So you can see that there is a problem.
And indeed, if you get a human operator to actually read these things
and classify them, they will probably be making an error of about 2.5%.
And we would like to see if machine learning can at least equal that,
which means that we can automate the process, or maybe beat that.
So this is a data set that we are going to work with.
Let's look at it a little bit more closely to see how we input it to
our algorithm.
We have one algorithm so far, which is the perceptron learning algorithm. We
are going to try on this.
And then we are going to generalize it a little bit.
The first item is the question of input representation.
What do I mean?
This is your input, the raw input, if you will.
Now this is 16 pixels by 16 pixels.
So there are 256 real numbers in that input.
If you look at the raw input x, this would be x_1, x_2, x_3, dot, dot,
dot, dot, and x_256.
That's a very long input to encode such a simple object.
And we add our mandatory x_0.
Remember, in linear models, we have this constant coordinate,
x_0 equals 1, we add in order to take care of the threshold.
So this will always be in the background whether we
mention it or not.
If you take this raw input and try the perceptron directly on it, you
realize that the linear model in this case, which has a bunch of parameters,
has really just too many parameters.
It has 257 parameters.
If you are working in a 257th-dimensional space,
that is a huge space.
And the poor algorithm is trying to simultaneously determine the values of
all of these w's based on your set.
So the idea of input representation is to simplify the algorithm's life.
We know something about the problem.
We know that it's not really the individual pixels
that matter.
You can probably extract some features from the input, and then give those to
the learning algorithm and let the learning algorithm
figure out the pattern.
So this gives us the idea of features.
What are features?
Well, you extract the useful information.
And as a suggestion, very simple one, let's say that in this particular
case, instead of giving the raw input with all of the pixel values, you
extract some descriptors of what the image is like.
For instance, you look at this.
Depending on whether this is the digital 8 or the digit 1, et cetera,
there is a question of the intensity, average intensity.
1 doesn't have too many black pixels.
8 has a lot.
5 has some.
So if you simply add up the intensity of all the pixels, you
probably will get a number that is related to the identity.
It doesn't uniquely determine it, but it's related.
It's a higher-level representation of the raw information
there. Same as symmetry--
if you think of the digit 1, 1 will be symmetric.
If you flip it upside down, or you flip it right and left, you will get
something that overlaps significantly with it.
So you can also define a symmetry measure, which means that you take the
symmetric difference between something and its flipped versions, and you see
what you get.
If something is symmetric, things will cancel because it's symmetric.
You'll get a very small value.
And if something is not symmetric, let's say like the 5, you will get
lots of values in the symmetric difference.
And you will get a high value for that.
So what you are measuring is the anti-symmetry.
You take the negative of that, and you get the symmetry.
So you get another guy, which is the symmetry.
So now, x_1 is the intensity variable,
x_2 is the symmetry variable.
Now admittedly, you have lost information in that process.
But the chances are you lost as much irrelevant information as relevant
information.
So this is a pretty good representation of the input, as far as
the learning algorithm is concerned.
And you went from 257 dimensional to 3 dimensional.
That's a pretty good situation.
And you probably realize that having 257 parameters is bad news for
generalization, if you extrapolate from what we said.
Having 3 is a much better situation.
So this is what we are going to work with.
When you take the linear model in this case, you just
have w_0, w_1, and w_2.
And that's what the perceptron algorithm, for example, needs to use--
to determine.
Now let's look at the illustration of these features.
You have these as your inputs.
And x_1 is the intensity,
x_2 is the symmetry.
What do they look like?
They look like this.
This is a scatter diagram.
Every point here is a data point.
It's one of the digits, one of the images you have.
And I'm taking the simple case of just distinguishing the 1's from the 5's.
So I'm only taking digits that are 1's or 5's.
And you can always take other digits versus each other, and
then combine the decision.
If you can solve this unit problem, you can generalize it
to the other problem.
So when you put all the 1's and all the 5's in a scatter diagram, you realize
for example that the intensity on the 5's is usually more than the
intensity on the 1's.
There are more pixels occupied by the 5's than the 1's.
This is the coordinate which is the intensity.
And indeed, the red guys, which happen to be the 5's, are tilted
a little bit more to the right, corresponding to the intensity.
If you look at the other coordinate, which is symmetry, the 1 is often more
symmetric than the 5.
Therefore, the guys that happen to be the 1's, that are the blue, tend to be
higher on the vertical coordinate.
And just by these two coordinates, you already see that this is almost
linearly separable.
Not quite, but it's separable enough that if you pass a boundary
here, you will be getting most of them right.
Now you realize that it's impossible really to ask to get all of them right
because, believe it or not, this fellow is a 5, at least meant to be a 5 by
the guy who wrote it.
So we have to accept the fact that there will be stuff that
is completely undoable.
And we will accept an error.
It's not a zero error.
But hopefully, it's a small error.
So this is what the features look like.
Now what does the perceptron learning algorithm do?
What it does is this complicated figure, which takes the evolution of
E_in and E_out as a function of iteration.
When you apply the perceptron learning algorithm, you apply it only to E_in.
E_in is the only value you have.
E_out is sitting out there.
We don't know what it is.
We just hope that E_in tracks it well.
Let's look at the figure.
These are the iteration numbers.
So this is the first misclassified example.
You go and apply the perceptron learning algorithm again, again, again
for 1000 times.
As you do that, E_in, which is the green curve, will go down and
sometimes will go up.
We realize that the perceptron learning algorithm takes care of one
point at a time, and therefore may mess up other points while it's taking care
of a point.
So in general, it can go up or down.
But the bad news here is that the data is not linearly separable.
And we made the remark that the perceptron learning algorithm behaves
very badly when the data is not linearly separable.
It can go from something pretty good to something pretty
bad, in just one iteration.
So this is a very typical behavior of the perceptron learning algorithm.
Because the data is not linearly separable, the perceptron learning
algorithm will never converge.
So what do we do?
We force it to terminate at iteration 1000.
That is, we stop at 1000 and take whatever weight vector we have.
And we call this g, the final hypothesis of the
perceptron learning algorithm.
Now we obviously look at this, and we say, if I only took this guy.
This is a better guy than the other.
But you know, you're just applying the algorithm and cutting it off.
Now, one of the things you observe from here, I plotted E_out.
You're not going to be able to plot E_out in a real problem that you deal
with, if E_out is really an unknown function.
You may be able to estimate it using some test examples.
But all you need to know here is that E_out is drawn here for illustration,
just to tell you what is happening in reality as you work on
the in-sample error.
And in this case, you find that E_out actually tracks the E_in pretty well.
There is a difference.
So if we go from here to here, that's our epsilon.
It's a big epsilon.
But the good news is that it tracks it.
When this goes down, this goes down.
When this goes up, this goes up.
So if you make your decision based on E_in, the decision based on E_out will
also be good.
That's good for generalization.
And that is one of the advantages of something as simple as the perceptron
learning algorithm.
It doesn't have too many parameters.
And because of our efforts in getting only three features, it has even three
parameters now.
So the chances are that it will generalize well, which it does.
Now what does the final boundary look like?
This is only the illustration here,
it's just-- this is the evolution.
Eventually, you end up with a hypothesis.
The hypothesis would separate the points in the scatter diagram you saw.
So what does it look like?
Well, it looks like this.
This is your boundary.
This is the final hypothesis, that corresponds to the hypothesis you got
at the final iteration.
Well, it's OK, but definitely not good.
It's too deep into the blue region.
You would have been better off doing this.
And the chances are maybe earlier guys that had better in-sample
error will do that.
But that's what you have to live with, if you apply the
perceptron learning algorithm.
So now we go and try to modify the perceptron learning algorithm in
a very simple way, that is the simplest modification you can ever imagine.
So let's see what happens.
This is what that PLA did, right?
And when we looked at it, we said: if we only could keep this value.
Well, this value is not a mystery.
It happened in your algorithm.
You can measure it explicitly.
It's an in-sample error.
And you know that it's better than the value you ended up with.
So in spite of the fact that you're doing these iterations according to
the prescribed perceptron learning algorithm rule-- modify the weights
according to one misclassified point-- you can keep track of the total
in-sample error of the intermediate hypothesis you got.
Right?
And only keep the guy that happens to be the best throughout.
So you're going to continue as if it's really the
perceptron learning algorithm.
But when you are at the end, you keep this guy and report it as the final
hypothesis.
What an ingenious idea!
Now the reason the algorithm is called the pocket algorithm is because the
whole idea is to put the best solution so far in your pocket.
And when you get a better one, you take the better one, put it in your
pocket, and throw the old one.
And when you are done, report the guy in your pocket.
We can do that.
What does this diagram look like, when you are looking
at the pocket algorithm?
Much better.
You can look at these values, and it is the best value so far.
Here, we went down.
And here, we indeed went down.
Here, we went up.
You see this green thing?
Here, we didn't, because the good guy is in our pocket and that's what we're
reporting the value for.
And we continued with it until we dropped again.
And we dropped again.
And we never changed that, because there was never a better
guy than this guy.
So when we come to iteration 1000, we have this fellow.
Now when you do that, you can use perceptron learning algorithm with
non-separable data, terminate it by force at some iteration, and report the
pocket value.
And that will be your pocket algorithm.
And if you look at the classification boundary, PLA versus pocket, this is
what we had with the perceptron learning algorithm.
We complained a little bit that it's too deep in the blue region.
And when you look at the other guy, which is the pocket algorithm, it
looks better.
It actually does what we thought it would do.
It separates them better.
Still, obviously, it cannot separate them perfectly.
Nothing can, because they are not linearly separable.
On the other hand, this is a good hypothesis to report.
So with this very simple algorithm, you can actually deal with general
inseparable data, but inseparable data in the sense that
it's basically separable.
However, it really is--
this guy is bad, and this guys is bad.
There's nothing we can do about them.
But there are few, so we will just settle for this.
We'll see that there are other cases of inseparable data that is truly
inseparable, in which we
…