YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 1,411 lines · added Dec 4, 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 linear models.
And linear models share what we would refer to as the signal,
which is this formula.
It's a linear sum involving the input variables and weights, that can be put
in vector form.
And all linear models, in one form or another, have that as their basic
building block.
And you can have a classification linear system, like the perceptron,
that uses that signal and takes the sign of it to make a decision,
+1 or -1.
Or you can take something like regression, which is real-valued, that
takes the signal as it is and has that as output.
We looked at the linear regression algorithm, which was a particularly
easy algorithm.
All it does, it takes the inputs and puts them in a particular matrix form,
and so the outputs. That's the inputs and outputs of the data set.
And then, by computing this very simple formula, in one shot, it can
get you the optimal value of the weight vector.
If you look at linear models, you can think of them as an economy car.
They get you where you want to go, and they don't consume a lot of gas.
You may not be very proud of them, but they actually do the job.
If you want a luxury car, wait until we get to support
vector machines.
And you have to pay the price for that.
However, for linear models, it is remarkable how often they
succeed on their own.
And they are sufficient to get you the learning performance
that you want.
So I urge you to give linear models in general more attention than you
would otherwise give.
And try to use them when you face a learning problem first, and see if they
will actually achieve what you want.
To strengthen linear models even further, we introduced nonlinear
transformation.
And the idea behind it is that the signal is not only linear in x, which
is what you would think of as the reason we call these linear systems.
But actually, they're linear in w, the vector.
And the reason this is important is because learning actually modifies w
in the learning process until it gets to the optimal one, while x, which you
usually think of as a variable, is actually a bunch of constants, which
are the data set that are handed to you.
So the linearity in w is the key point.
And if you take x and transform it in any way you form to another vector z,
in a very nonlinear way if you want, this will still preserve this
linearity, the linearity in w.
Obviously, it will not be linear in x.
And that's all that matters for you to apply the machinery that we got
here, like the simple linear regression algorithm.
And we took an example where we had the two variables x_1 and x_2, and we
transformed them nonlinearly to x_1 squared and x_2 squared.
And we found that this case, the transformation helps us separate the
data, where if we worked in the original space, we
would not be able to.
This time, I'm going to talk about error and noise.
And these are practical considerations that we have to take, when we consider
real-life problems.
And we're going to modify the learning diagram that we have, by incorporating
the notion of error and the notion of noise.
And I will do that for the bulk of the lecture.
However, my starting point will be to wrap up the nonlinear transformation
that we started last time.
So let's look at what we had last time.
We had this space.
Let me magnify it a little bit.
This space is the original X space.
And the origin is in the middle.
And you have these points, which are your data set.
And each point belongs to that space.
And as you realize, there is really no way of separating the blue from the
red using a line, which is what linear models do.
And the idea for us was: let's do a nonlinear transformation.
We called it phi.
And if you look at what happened here-- let's look at both of them at
the same time--
this is where you took x_1 squared.
So this is x_1, and this is x_2.
And that transformation here was x_1 squared.
So this would be x_1 squared, and this is x2 squared, which we're going
to label as z.
So the transformation is you take every point in the sample space x_n,
you put it through a transformation phi, and you get the
corresponding point z_n.
And now, you are working in the feature space, or the nonlinear space
Z.
When we did this, we realized that a data set like this can become linearly
separable in the new space.
And that allows us to apply the linear model algorithm here.
And when you do that, you will get a separating boundary here.
And that separating boundary is applied by applying your simple linear
model, like linear regression-- in this case, linear classification, the
perceptron--
to the data in the Z space.
So that's what we get.
But we are not working in the Z space.
When I give you a test point, it will be x.
And you have managed to separate things in the Z space.
Well, the way you do it is you go back to the input space.
And as you realize, I'm using the "inverse",
between quotation,
transformation.
Because the transformation, in principle, may not have an inverse.
There are some points in the Z space that may not be a mapping of any point
in X, and some points in the Z space which may be the mapping of
more than one point.
And therefore, in spite of the fact that phi is a mapping, a function,
phi -1, as we call it, is not.
But when you apply this, figuratively, what you're going to get is
a separating surface in the X space, that is not linear.
And that was obtained by applying purely linear methods.
And therefore, you can classify a new point by applying g of x, which would
be the hypothesis that's defined here, the linear one, which happens to have
that formula.
So you look at the diagram all together.
And this is basically the cycle you have, when you're doing the nonlinear
transformation.
You take the data set, transform it, classify it, and interpret it.
In reality, when you get the new x, what you're going to do, you are going
to take the new x, wherever it might be.
You're going to transform it.
And then look here where it lies, and classify it accordingly.
It's a very simple procedure.
And as you can see, although we are illustrating it here in a case where
you're going from two-dimensional to two-dimensional, you could in
principle go from two-dimensional to 100 dimensional, with highly nonlinear
coordinates, and the same principle will apply.
You will be classifying here, with a hyperplane in that case.
And then, this surface would be very, very complicated--
could be completely jagged and whatnot.
And that enables you to implement a lot of sophisticated surfaces.
So let's look at the nonlinear transformation and ask ourselves, what
transforms to what, to make sure that all the notions are clear.
The first thing is the input point x.
This is a single point that is represented by its coordinates x_1 up
to x_d, together with the mandatory constant x_0 which equals 1 that
takes care of the threshold term.
This is a general representation of a point in the X space.
What does this transform to?
I'd like you to think before I give the answer.
Well, it transforms to a z.
That is a vector.
Each of these coordinates,
let's say, z_1,
is a nonlinear function, potentially nonlinear function, of all of the x's,
so of the entire vector x.
For example, this could be x_1 x_2 e to the x_3.
The next one would be 1 over x_2 times x_3 cubed.
Whatever it is.
And you can go on and on and on, and there is really no limit.
So if we thought of linear methods here as an economy car,
this could be a truck.
This could be actually an 18-wheeler.
And we must be proud of that, because with such a simple method, we are able
to create such a strong machine.
But be careful, because you may not be able to drive it.
And if you do the wrong transformation,
you will end up crashing--
in this case, generalization-wise crashing.
That is, although you did everything right, and you did this
transformation, and this is a powerful machine, you don't know how to drive
the powerful machine, and you end up with very poor generalization.
And we need the theory in order to get our driver's license. That will tell us
what to do in order to be able to drive this machine.
So that is x.
Now, what do x_1 up to x_N go to?
Remember, this is the data set, the inputs of the data set.
Each of these guys, by itself, is a full vector x that has all of these
coordinates.
So this is the data set we have.
What does it transform to?
Not surprisingly, z_1 up to z_N.
So you end up with the same number of points.
That is obvious.
And each of them is a vector.
And each vector can be very long, according to the
transformation you chose.
Next one--
the labels.
The data set comes with inputs and outputs, right?
So the inputs I did the transformation--
what do y_1 up to y_N transform to?
Well, they transform to y_1 up to y_N.
These are untouched.
These are the values.
They are not touched.
And these are the ones we learn.
If it's classification, they are +1 or -1, exactly the same way
they were there before.
How about the weights?
When we use linear models, we have a weight vector.
So when we are in the X space here, what are the weights?
The answer is that there are no weights in the X space when you do
a nonlinear transformation.
The weights are done in the Z space.
And I labeled the weights here as w tilde.
And I'm using tilde as nonlinear, so that you remember
it's a nonlinear space.
And everything here is tilde.
So this is w tilde.
And if you look here at the dimension--
you may have not seen it.
Let me magnify it.
The dimensionality here is also d tilde.
So whenever we need to distinguish between z and x, we will add tilde to
the z counterpart, so that you are not confused about which is which.
So we have those weights.
And finally, you ask yourself: I've done all of this machinery.
Could you please tell me, what is the hypothesis that I'm
delivering to my customer?
We're still calling it g of x, the final hypothesis of
your learning process.
And it happens to be exactly the same way, except in Z space.
You take the linear form here, and take the sign, and that would be your
hypothesis.
Except it's a little bit annoying, because this is g of x, and you're
telling me this is w tilde transposed
times z.
Where is x?
Don't worry. Here is x.
What z is, is the transformation of x.
When you want to evaluate this for any x, all you need to do is plug into
this formula, and you are ready to go.
That's the entire story of the nonlinear transformation.
Now, with that out of the way, let's go to the main topic of the day, which
are error measures and noisy targets.
When we face a real learning problem, we will realize that there
are components, practical components in real life, that we have not fully
taken into consideration.
And what I'm going to do, I'm going to take the learning diagram, which we
introduced in the first lecture.
And then, I'm going to adjust it according to these practical components,
until we get the final general form of the supervised learning diagram.
That will take us through both topics, which are the error measures and the
noisy targets.
Here is the learning diagram in case you forgot what it was.
That's where we left it.
Let's see what it looks like.
Remember, it's a pretty simple diagram.
And we built it from scratch.
I need to rebuild it, in order for you to realize that I'm not just
flashing a jungle on you.
It has a sense.
This is what we're trying to learn.
It's an unknown target function, represented to
us by training examples.
We have a learning algorithm that will take these examples and produce the
final hypothesis.
All of this is nice.
We said that the learning algorithm is picking the hypothesis from the
hypothesis set.
And we said that this is a convenient technicality that has no loss of
generality.
So we accepted that we will always have a hypothesis set.
And then, we went into the feasibility of learning.
And we realized that for that to happen, we need to introduce
a probability distribution on X, any probability distribution, and generate
the points x_1 up to x_N, which constitute the inputs to the training
examples, using this probability distribution independently.
Once you do that, you get the benefit of Hoeffding.
And you can make a statement that you're going to do something
out-of-sample that is reflected by the in-sample.
That's where we stood.
So this is the diagram we are going to be modifying piece by piece.
Let's talk about error measures, the first notion.
Error measures try to answer the following question:
what does it mean for h to approximate f?
You have two functions.
And you say, this is a good approximation, this is a bad
approximation.
Is it a qualitative statement, or is it quantitative?
It is quantitative.
And because it's quantitative, we are going to define an error measure that
measures how well, or how badly, h approximates f.
So the error measure will be defined as E of two guys.
And these will be h and f.
It returns a number for any two functions you plug in.
One of them will be the target function.
One of them will be a hypothesis of interest.
And you ask yourself, how well, or how badly in this case, does
h approximate f?
And you get an error.
If the error is 0, then h perfectly reflects f, and you're home free.
If there's an error, then maybe you need to look for another h that has
smaller error.
So that formalizes the question of search, of the learning algorithm, into
minimizing an error function.
We call it error function.
And we call this error measure. It is neither a measure in the measure
theoretic sense, or a function--
this is actually a functional.
But we are not worrying about that.
We just take these objects and return a number.
And we refer to it as a function.
And we talk about error measure in the sense of the English word "measure",
not the mathematical "measure".
So the error function, in principle, returns a number
for a pair of functions.
But it is almost always defined in terms of difference on
a particular point.
And then, you put these points together.
That's the pointwise definition.
In this case, you define a small e that goes with a capital E that also
takes two arguments.
And these two arguments are the value of h at a particular point, and the
value of f at the same point.
That makes sense.
I'm trying to compare functions.
I want them to be the same on the same point.
Therefore, if I compare them for every point this way, then I will get
something meaningful.
And then, I will need to do something about the different e's, small e's,
that will get me the big E.
Although this is not strictly required by the definition-- you could
have a crazy error function that does not reduce to corresponding points.
But invariably, this is what you're going to do.
Have we seen this before?
Yes, we have.
Remember the squared error?
How do we formalize it in this sense?
We can say that the error in this case is h of x minus f of x squared.
That's what we did, and that is indeed an error function that measures the
difference between the two.
And indeed, if the error is 0, it means that h of x equals f of x, and
we have exactly what we want.
We also saw it before, although we didn't explicitly talk about it in
those terms, when we talked about binary error.
When we had perceptrons, every point could be either right or wrong.
And that doesn't look like a quantitative error function.
It's binary.
However, you can also put it in those terms as follows.
We agreed this notion-- let me magnify it for you.
This notation, which is the funny bracket, means that you return 1 if
the statement enclosed here is true.
And you return 0 if it is false.
That's a standard notation.
So if you take this as your error function, what will happen?
If h of x equals f of x, then this statement is false, and you return 0.
So the error is 0, good.
And if this statement is true, you return 1.
And indeed, in that case, you're making an error.
So it's a binary error because of this.
And if you take it as a formal error, and do the rest of the development to
get the other one, the big E for the global function, you will find that
this is exactly what we did when we were talking about frequency of error
and probability of error.
That will become clear in a moment.
Now, let's move from the pointwise--
you define it on one point in the space--
to define the error function, capital E, on the entire space.
The way it is done is that the overall error, which has this
notation, will always be the average of pointwise errors.
So you take these pointwise errors and average them.
And all we need to do is articulate what we mean by "average" in
order to get that.
So let's look at the in-sample error.
When we have the in-sample error, this is the formula for it.
And now, you think of in-sample error as the in-sample version of this.
Because now, we are going to use the pointwise error that goes with that
error function, or that error measure, in defining the in-sample error.
If you take a single point from your training set, you would be having
n going from 1 to N, so one of them generically is n.
And I'm putting it in red, because that's what we are going to average
with respect to.
You compute this error measure whatever it may be, squared error,
binary error, any other error you can think of.
And now, you get the average.
And average in that case will be the simple average, which is 1 over N over
that, over the sum.
This is indeed consistent with what we thought of as the training error.
And if you go back to the binary error, which is the funny error, and
you look at what this formula will return, it will return exactly the
frequency of error in the sample, correct?
Now let's go for out-of-sample error.
Again, the out-of-sample error is the out-of-sample version of this
error measure.
Now, in this case, the point is a general point in the space.
So we are labeling it as x in general, without any label.
This could be any point in the space that is picked from
X, which is the input space.
And in order to get an average in that case, what you do is you get the
expected value, in this case with respect to x.
So that is the average for the out-of-sample case.
And again, if you take the binary error, and you take the expected value
of this, this would be identically the probability of error overall.
And we are using the probability distribution over the input space X, in
order to compute this quantity.
That's how we get from a definition that you invoke on a single point, to
the in-sample and out-of-sample versions.
Now let's revise the learning diagram with this added component.
Here is the learning diagram.
There's nothing that changed here except that now, this is the standard
color, because we already got used to it.
The red stuff is the new stuff.
So you have here, and you want to add the error measure.
I'd like you to think for a moment what we are going to do.
We're going to do it in two steps.
The first one is to realize that we are defining the error
measure on a point.
So here's the addition.
The addition is that in deciding whether g is close to f, which is the
goal of learning, we test this with a point x.
And the criterion for deciding whether g of x is approximately the same as f
of x is our pointwise error measure.
Furthermore, this x is created from the space using
something very specific.
And that is, it comes from the same probability distribution.
It comes from the same probability distribution that generated those
points.
This was implicit when we talked about the bin.
mu was the probability distribution in the bin.
And nu was the sample distribution in the sample that you pick.
When you test the system that you trained using a certain probability
distribution, I ask you to test it with points drawn from the same
distribution.
That's the only requirement in order to invoke Hoeffding, or the
counterparts of Hoeffding for more elaborate type of functions.
Now, if you do that, then you have the guarantee.
And it does make
…

Need subtitles from another video?