YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 1,426 lines · added Nov 25, 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 introduced the learning problem.
And if you have an application in your domain that you wonder if machine
learning is the right technique for it, we found that there are three
criteria that you should check.
You should ask yourself: is there a pattern to begin
with that we can learn?
And we realize that this condition can be intuitively met in many applications,
even if we don't know mathematically what the pattern is.
The example we gave was the credit card approval.
There is clearly a pattern-- if someone has a particular salary, has
been in a residence for so long, has that much debt, and so on, that this
is somewhat correlated to their credit behavior.
And therefore, we know that the pattern exists in spite of the fact
that we don't know exactly what the pattern is.
The second item is that we cannot pin down the pattern mathematically, like
the example I just gave.
And this is why we resort to machine learning.
The third one is that we have data that represents that pattern.
In the case of the credit application, for example, there are historical
records of previous customers, and we have the data they wrote in their
application when they applied, and we have some years' worth of record of
their credit behavior.
So we have data that are going to enable us to correlate what they wrote in the
application to their eventual credit behavior, and that is what we are
going to learn from.
Now, if you look at the three criteria, basically there are two that
you can do without, and one that is absolutely essential.
What do I mean?
Let's say that you don't have a pattern.
Well, if you don't have a pattern, then you can try learning.
And the only problem is that you will fail.
That doesn't sound very encouraging.
But the idea here is that, when we develop the theory of learning, we will
realize that you can apply the technique regardless of whether there
is a pattern or not.
And you are going to determine whether there's a pattern or not.
So you are not going to be fooled and think, I learned, and then give the
system to your customer, and the customer will be disappointed.
There is something you can actually measure that will tell you whether you
learned or not.
So if there's no pattern, there is no harm done in trying machine learning.
The other one, also, you can do without.
Let's say that we can pin the thing down mathematically.
Well, in that case, machine learning is not the recommended technique.
It will still work.
It may not be the optimal technique.
If you can outright program it, and find the result perfectly, then why
bother generate examples, and try to learn, and go through all of that?
But machine learning is not going to refuse.
It is going to learn, and it is going to give you a system.
It may not be the best system in this case, but it's a system nonetheless.
The third one, I'm afraid you cannot do without.
You have to have data.
Machine learning is about learning from data.
And if you don't have data, there is absolutely nothing you can do.
So this is basically the picture about the context of machine learning.
Now, we went on to focus on one type, which is supervised learning.
And in the case of supervised learning, we have a target function.
The target function we are going to call f.
That is our standard notation.
And this corresponds, for example, to the credit application.
x is your application, and f of x is whether you are a good credit risk or
not, for the bank.
So if you look at the target function, the main criterion about the target
function is that it's unknown.
This is a property that we are going to insist on.
And obviously, unknown is a very generous assumption, which means that
you don't have to worry about what pattern you are trying to learn.
It could be anything, and you will learn it-- if we manage to do that.
There's still a question mark about that.
But it's a good assumption to have, or lack of assumption, if you will,
because then you know that you don't worry about the environment that
generated the examples.
You only worry about the system that you use to implement machine learning.
Now, you are going to be given data.
And the reason it's called supervised learning is that you are not only
given the input x's, as you can see here.
You're also given the output--
the target outputs.
So in spite of the fact that the target function is generally unknown,
it is known on the data that I give you.
This is the data that you are going to use as training examples, and that you
are going to use to figure out what the target function is.
So in the case of supervising learning, you have the targets
explicitly.
In the other cases, you have less information than the target, and we
talked about it-- like unsupervised learning, where you don't have
anything, and reinforcement learning, where you have partial information,
which is just a reward or punishment for a choice of a value of y that
may or may not be the target.
Finally, you have the solution tools.
These are the things that you're going to choose in order to solve the
problem, and they are called the learning model, as we discussed.
They are the learning algorithm and the hypothesis set.
And the learning algorithm will produce a hypothesis--
the final hypothesis, the one that you are going to give your customer, and
we give the symbol g for that.
And hopefully g approximates f, the actual target function,
which remains unknown.
And g is picked from a hypothesis set, and the general the symbol for
a member of the hypothesis set is h.
So h is a generic hypothesis.
The one you happen to pick, you are going to call g.
Now, we looked at an example of a learning algorithm.
First, the learning model-- the perceptron itself, which is a linear
function, thresholded.
That happens to be the hypothesis set.
And then, there is an algorithm that goes with it that chooses which
hypothesis to report based on the data.
And the hypothesis in this case is represented by the purple line.
Different hypotheses in the set H will result
in different lines.
Some of them are good and some of them are bad, in terms of separating
correctly the examples which are the pluses and minuses.
And we found that there's a very simple rule to adjust the current
hypothesis, while the algorithm is still running, in order to get a better
hypothesis.
And once you have all the points classified correctly, which is
guaranteed in the case of the perceptron learning algorithm if the
data was linearly separable in the first place,
then you will get there, and that will be the g that you are going to report.
Now, we ended the lecture on sort of a sad note, because after all of this
encouragement about learning, we asked ourselves: well,
can we actually learn?
So we said it's an unknown function.
Unknown function is an attractive assumption, as I said.
But can we learn an unknown function, really?
And then we realized that if you look at it, it's really impossible.
Why is it impossible?
Because I'm going to give you a finite data set, and I'm going to give you
the value of the function on this set.
Good.
Now, I'm going to ask you what is the function outside that set?
How in the world are you going to tell what the function is outside, if the
function is genuinely unknown?
Couldn't it assume any value it wants?
Yes, it can.
I can give you 1000 points, a million points, and on the million-and-first point,
still the function can behave any way it wants.
So it doesn't look like the statement we made is feasible in terms of
learning, and therefore we have to do something about it.
And what we are going to do about it is the subject of this lecture.
Now, the lecture is called Is Learning Feasible?
And I am going to address this question in extreme detail from
beginning to end.
This is the only topic for this lecture.
Now, if you want an outline--
it's really a logical flow.
But if you want to cluster it into points--
we are going to start with a probabilistic situation, that is a very
simple probabilistic situation.
It doesn't seem to relate to learning.
But it will capture the idea--
can we say something outside the sample data that we have?
So we're going to answer it in a way that is concrete, and where the
mathematics is very friendly.
And then after that, I'm going to be able to relate that probabilistic
situation to learning as we stated.
It will take two stages.
First, I will just translate the expressions into something that
relates to learning, and then we will move forward and make it correspond to
real learning.
That's the last one.
And then after we do that, and we think we are done, we find that there is
a serious dilemma that we have.
And we will find a solution to that dilemma, and then declare victory-- that
indeed, learning is feasible in a very particular sense.
So let's start with the experiment that I talked about.
Consider the following situation.
You have a bin, and the bin has marbles.
The marbles are either red or green.
That's what it looks like.
And we are going to do an experiment with this bin.
And the experiment is to pick a sample from the bin--
some marbles.
Let's formalize what the probability distribution is.
There is a probability of picking a red marble, and let's call it mu.
So now you think of mu as the probability of a red marble.
Now, the bin is really just a visual aid to make us relate to the
experiment.
You can think of this abstractly as a binary experiment--
two outcomes, red or green.
Probability of red is mu, independently from
one point to another.
If you want to stick to the bin, you can say the bin has an infinite number
of marbles and the fraction of red marbles is mu.
Or maybe it has a finite number of marbles, and you are going to pick the
marbles, but replace them.
But the idea now is that every time you reach in the bin, the probability
of picking a red marble is mu.
That's the rule.
Now, there's a probability of picking a green marble.
And what might that be?
That must be 1 minus mu.
So that's the setup.
Now, the value of mu is unknown to us.
So in spite of the fact that you can look at this particular bin and see
there's less red than green, so mu must be small.
and all of that.
You don't have that advantage in real.
The bin is opaque-- it's sitting there, and I reach for it like this.
So now that I declare mu is unknown, you probably see
where this is going.
Unknown is a famous word from last lecture, and that will be the link to
what we have.
Now, we pick N marbles independently.
Capital N. And I'm using the same notation for N, which is the
number of data points in learning, deliberately.
So the sample will look like this.
And it will have some red and some green.
It's a probabilistic situation.
And we are going to call the fraction of marbles in the sample--
this now is a probabilistic quantity.
mu is an unknown constant sitting there.
If you pick a sample, someone else picks a sample, you will have a different
frequency in sample from the other person.
And we are going to call it nu.
Now, interestingly enough, nu also should appear in the figure.
So it says nu equals fraction of red marbles.
So that's where it lies.
Here is nu!
For some reason that I don't understand, the app wouldn't show nu
in the figures.
So I decided maybe the app is actually a machine learning expert.
It doesn't like things in sample.
It only likes things that are real.
So it knows that nu is not important.
It's not an indication.
We are really interested in knowing what's outside.
So it kept the mu, but actually deleted the nu.
At least that's what we are going to believe for the rest of the lecture.
Now, this is the bin.
So now, the next step is to ask ourselves the question we asked in
machine learning.
Does nu, which is the sample frequency, tell us anything about mu,
which is the actual frequency in the bin that we are interested in knowing?
The short answer--
this is to remind you what it is.
The short answer is no.
Why?
Because the sample can be mostly green, while the bin is mostly red.
Anybody doubts that?
The thing could have 90% red, and I pick 100 marbles, and all
of them happen to be green.
This is possible, correct?
So if I ask you what is actually mu, you really don't know from the sample.
You don't know anything about the marbles you did not pick.
Well, that's the short answer.
The long answer is yes.
Not because no and yes, but this is more elaborate.
We have to really discuss a lot in order to get there.
So why is it yes?
Because if you know a little bit about probability, you realize that if the
sample is big enough, the sample frequency, which is nu-- the mysterious
disappearing quantity here-- that is likely to be close to mu.
Think of a presidential poll.
There are maybe 100 million or more voters in the US, and you make a poll
of 3000 people.
You have 3000 marbles, so to speak.
And you look at the result in the marbles, and you tell me how the 100
million will vote.
How the heck did you know that?
So now the statistics come in.
That's where the probability plays a role.
And the main distinction between the two answers is
possible versus probable.
In science and in engineering, you go a huge distance by settling for not
absolutely certain, but almost certain.
It opens a world of possibilities, and this is one of the
possibilities that it opens.
So now we know that, from a probabilistic point of view, nu does
tell me something about mu.
The sample frequency tells me something about the bin.
So what does it exactly say?
Now we go into a mathematical formulation.
In words, it says: in a big sample, nu, the sample frequency,
should be close to mu, the bin frequency.
So now, the symbols that go with that-- what is a big sample?
Large N, our parameter N.
And how do we say that nu is close to mu?
We say that they are within epsilon.
That is our criterion.
Now, with this in mind, we are going to formalize this.
The formula that I'm going to show you is a formula that is going to
stay with us for the rest of the course.
I would like you to pay attention.
And I'm going to build it gradually.
We are going to say that the probability of something is small.
So we're going to say that it's less than or equal to, and hopefully the
right-hand side will be a small quantity.
Now if I am claiming that the probability of something is small, it
must be that that thing is a bad event.
I don't want it to happen.
So we have a probability of something bad happening being small.
What is a bad event in the context we are talking about?
It is that nu does not approximate mu well.
They are not within epsilon of each other.
And if you look at it, here you have nu minus mu in absolute value, so
that's the difference in absolute value.
That happens to be bigger than epsilon.
So that's bad, because that tells us that they are further away from our
tolerance epsilon.
We don't want that to happen.
And we would like the probability of that happening to
be as small as possible.
Well, how small can we guarantee it?
Good news.
It's e to the minus N.
It's a negative exponential.
That is great, because negative exponentials tend to die very fast.
So if you get a bigger sample, this will be diminishingly small
probability.
So the probability of something bad happening will be very small, and we
can claims that, indeed, nu will be within epsilon from mu, and we will be
wrong for a very minute amount of the time.
But that's the good news.
Now the bad news--
ouch!
Epsilon is our tolerance.
If you're a very tolerant person, you say:
I just want nu and mu to be within, let's say, 0.1.
That's not very much to ask.
Now, the price you pay for that is that you plug in the exponent
not epsilon, but epsilon squared.
So that becomes 0.01.
0.01 will dampen N significantly, and you lose a lot of the benefit of the
negative exponential.
And if you are more stringent and you say, I really want nu
to be close to mu.
I am not fooling around here.
So I am going to pick epsilon to be 10 to the minus 6.
Good for you.
10 to the minus 6?
Pay the price for it.
You go here, and now that's 10 to the minus 12.
That will completely kill any N you will ever encounter.
So the exponent now will be around zero.
So this probability will be around 1, if that was the final answer.
That's not yet the final answer.
So now, you know that the probability is less than or equal to 1.
Congratulations!
You knew that already. [LAUGHTER]
Well, this is almost the formula, but it's not quite.
What we need is fairly trivial.
We just put 2 here, and 2 there.
Now, between you and me, I prefer the original formula
better, without the 2's.
However, the formula with the 2's has the distinct advantage of being: true. [LAUGHTER]
So we have to settle for that.
Now that inequality is called Hoeffding's Inequality.
It is the main inequality we are going to be using in the course.
You can look for the proof.
It's a basic proof in mathematics.
It's not that difficult, but definitely not trivial.
And we are going to use it all the way-- and this is the same formula
that will get us to prove something about the VC dimension.
If the buzzword 'VC dimension' means anything to you, it will come from
this after a lot of derivation.
So this is the building block that you have to really know cold.
Now, if you want to translate the Hoeffding Inequality into words, what
we have been talking about is that we would like to make the
statement: mu equals nu.
That would be the ultimate.
I look at the in-sample frequency, that's the out-of-sample frequency.
That's the real frequency out there.
But that's not the case.
We actually are making the statement mu equals nu, but we're not
making the statement--
we are making a PAC statement.
And that stands for: this statement is probably, approximately, correct.
Probably because of this.
This is small, so the probability of violation is small.
Approximately because of this.
We are not saying that mu equals nu.
We are saying that they are close to each other.
And that theme will remain with us in learning.
So we put the glorified Hoeffding's Inequality at the top, and we spend
a viewgraph analyzing what it means.
In case you forgot what nu and mu are, I put the figure.
So mu is the frequency within the bin.
This is the unknown quantity that we want to tell.
And nu is the disappearing quantity which happens to be the frequency in
the sample you have.
So what about the Hoeffding Inequality?
Well, one attraction of this inequality is that it is valid for
every N, positive integer, and every epsilon which is greater than zero.
Pick any tolerance you want, and for any number of examples you
want, this is true.
It's not an asymptotic result.
It's a result that holds for every N and epsilon.
That's a very attractive proposition for something that has
an exponential in it.
Now, Hoeffding Inequality belongs to a large class of mathematical laws,
which are called the Laws of Large Numbers.
So this is one law of large numbers, one form of it, and
there are tons of them.
This happens to be one of the friendliest, because it's not
asymptotic, and happens to have an exponential in it.
Now, one observation here is that if you look at the left-hand side, we are
computing this probability.
This probability patently depends on mu.
mu appears explicitly in it, and also mu affects the probability
distribution of nu.
Nu is the sample, in N marbles you picked.
That's a very simple binomial distribution.
You can find the probability that nu equals anything based on
the value of mu.
So the probability that this quantity, which depends on mu, exceeds epsilon--
the probability itself does depend on mu.
However, we are not interested in the exact probability.
We just want to bound it.
And in this case, we are bounding it uniformly.
As you see, the right-hand side does not have mu in it.
And that gives us a great tool, because now we don't use the quantity
that, we already declared, is unknown.
mu is unknown.
It would be a vici
…

Need subtitles from another video?