YouSub
Untitled

en English

Untitled English subtitles

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

Report a problem
What's wrong?
Advertisement

English transcript

ANNOUNCER: The following program is brought to you by Caltech.
YASER ABU-MOSTAFA: Welcome back.
Last time, we introduced the third linear model, which is logistic
regression.
It has the same structure as the linear models, where you have the
inputs combined linearly using weights, summed up into a signal, and then the
signal passes through something.
In this case, it passes through what we refer to as a soft threshold.
We labeled it theta.
And the model is meant to implement a probability that has a genuine
probability interpretation.
And because of that, the error measure we derived was based on likelihood
measure, which has a probabilistic connotation,
in which case we maximized the probability that we would get the data
set that we got-- the outputs given the inputs--
based on the hypothesis that is represented by the logistic
regression being assumed to be the target function identically.
And this makes us able to express the probability in terms of the parameters
that define the hypothesis, which are the weights, w.
And therefore, we have this quantity that we want to maximize.
And then we derived an error measure that very much parallels the error
measures that we had before, in terms of the in-example error for logistic
regression that we will minimize.
So this is a useful model, and it complements the other models.
One of them was for classification, one of them for real-valued function
regression.
And this one is for bounded real-valued function that is interpreted as
a probability.
One of the key issues about logistic regression is that, because the
the error measure is a little bit more complicated than we had for
example in linear regression, we were unable to optimize it directly.
And therefore, we introduced the method that is meant to minimize
an arbitrary nonlinear function that is smooth enough, twice
differentiable.
And in the case of logistic regression, although we don't have
a closed-form solution, the error measure actually
has a very nice behavior.
It's a convex function and, therefore, when you apply a method like gradient
descent or other methods, it is fairly easy to optimize because you just fall
into that minimum and stay there, rather than have problems with local
minima that we talked about briefly.
So the algorithm for gradient descent, regardless of the error measure that
you are trying to minimize.
First you initialize and, in the case of logistic regression, initializing
to all zeros was fine.
We will find out that today in neural networks, that will not be fine, and
we'll make the point why.
And then you keep iterating until termination.
And what you do is, you update your weight gradually by going along the
negative of the gradient. That would be the steepest descent in the error--
the biggest gain you would get for a fixed-size step.
And in this case, we adjusted the fixed-size step so that it's a fixed
learning rate that is proportional to the gradient at that point.
We keep doing this, and then when we arrive at termination we report that
as our final hypothesis.
And we talked a little bit in the Q&A session about criteria for termination,
and also about local minima that will become an issue for today.
So today when I modify the gradient descent into the more practical
version, which is called stochastic gradient descent, we will talk
a little bit about initialization and we'll talk about other aspects that
have to do with local minima and whatnot.
OK.
Today's topic is neural networks.
And historically, neural networks are responsible for the revival of
interest in machine learning.
They have a biological link that got people very excited and
people pursued them.
And they were very easy to implement because of the algorithm that I'm
going to describe today.
And they met a lot of success in practical applications,
and got people going.
Now, it is not necessarily the model of choice nowadays, probably people
will opt for support vector machines or other models. Yet every now and
then, neural networks would do the job as well as the other models.
And many industries use it as a standard.
For example, in banking and credit approval, neural
networks are often used.
So the outline for today is very simple.
First, I'm going to extend gradient descent into the special case of
stochastic gradient descent that is used in neural networks.
And then, I'm going to talk about neural network as a model.
What is the hypothesis that it is implementing?
And I motivate it from a biological point of view, and relate it to
perceptrons.
And then we'll talk about the backpropagation algorithm, the
efficient algorithm that goes with neural networks that actually made
that model particularly practical.
So let's start with stochastic gradient descent.
What do we have?
We have gradient descent, and gradient descent minimizes an error function.
That is function of w-- minimizes it with respect to w.
And that happens to be an in-sample error in our mind.
And it is the in-sample error.
And the only thing I would notice here that is particular to the derivation of
stochastic gradient descent is that, in order for you to compute the error or the
gradient of the error, which you need in order to
implement gradient descent,
you need to evaluate the hypothesis at every point in your sample.
So for n equals 1 to N, you need to evaluate those, or you
evaluate their gradient.
And that will tell you what is the error, or what is that direction
you would go to, which is normal because this is the error we are
minimizing.
You'd better compute it.
So you take the case of logistic regression and we had a very
particular form for that.
And now you can see that it's an analytic form.
In this case, friendly and smooth.
And indeed, you can get the gradient with respect to that vector and go
down the error surface, along the direction
suggested by gradient descent.
Now, the steps were iterative, and so we take one step at a time.
And one step is a full epoch, in the sense-- we call something epoch when you
have considered all the examples at once, which is the only
choice we have so far.
And we had this formula that we have seen.
The difference we are going to do now is that, instead of having
the movement in the w space based on all of the examples,
we are going to try to do it based on one example at a time.
That's what will make stochastic gradient descent.
So because now we are going to have another method, we're going to label
the standard gradient descent as being batch gradient descent.
It takes a batch of all the examples and does a move at once, as opposed
to the other mode.
So the stochastic aspect is as follows.
You pick one example at a time.
Think of it that you pick it at random.
You have N examples, each of them is equi-probable
to be picked.
You pick one of them at random.
Now you apply gradient descent, not to the in-sample error for all the examples,
but the in-sample error on that point.
That looks like a very meager thing to do, because the other examples are not
involved at all.
But I think you have seen something like that before.
When we take one example at a time and worry about it, and not to worry
about what other guys are doing even if we are interfering with them.
Remember the perceptron learning algorithm?
That's exactly what it did, and it worked.
And in this case, it will also work.
Now to argue that it will work, think of the average direction that you're
going to descend along.
What does that mean?
If you take the gradient of the error measure that you
are going to minimize,
which in this case just for one example,
and you take the expected value under the experiment that you picked the
example from the entire training set at random.
In that case, if you want to get the expected value with respect to the
red n, which is now a random variable, this is what you get.
And if you evaluate it, it's pretty easy.
You simply take this value.
For every example it has a probability of 1 over N. And the expected value would
be 1 over N summation of that.
So this would be the average direction.
So you think that every step, I'm going along this direction plus noise.
So this is the expected value, but because it's one example or
another, there is some stochastic aspect.
And if you look at the quantity on the right hand side, this happens to be
identically minus the gradient of the total in-sample error.
So it's as if, at least in expected value, we are actually going along the
direction we want, except that we now involve one example in the
computation, which is a big advantage, and we have a stochastic
aspect to the game.
So this is the idea, and then you keep repeating.
And as you repeat, you always get the expected value in that direction,
and you get different noises depending on which example.
So the hope now is that by the time you did it a lot of times, the noise
will average out and you actually will be going along the ideal direction.
So it's a randomized version of gradient descent, and it's called
stochastic gradient descent, SGD for short.
Now let's look at the benefits of having that stochastic aspect.
The main benefit by far--
that is the motivation for having this--
is that it's a cheaper computation.
Think of one step that you're going to do using stochastic gradient descent.
What do you need?
You take one example, you put the input and you get the output, and then
you compute whatever the gradient is for one example.
If you're doing the batch gradient descent, you will do this for all the
examples before you can declare a single move.
Nevertheless, the expected value of your move in the cheaper version is
the same as the other one.
So it looks there's a little bit of cheating here.
On the other hand, it looks attractive.
If this actually works on average, this is an attractive proposition.
So this is number 1 advantage.
The second advantage is randomization.
There is an aspect of optimization that makes randomization advantageous.
So you don't want to be extremely deterministic.
You want to have an element of chance.
Why would I want an element of chance if I know my goal exactly?
Well, because optimization is not exact.
It's not like you're going for the minimum for sure after that.
There are all kinds of traps that you can go through, like local
minima and whatnot.
So let's look at cases where randomization would help.
This is an error surface, and it is the typical
error surface you will encounter.
The one you encountered in logistic regression, which was simply like
this, that was a lucky one, the convex one.
In general, and in neural networks for sure, you are going to get lots of
hills and valleys in your error surface.
So depending on where you start, you may end up in one
local minimum or another.
You may not get the best one, you may get one or the other.
Now, this is inevitable and there is really no full-proof cure for it, as
we discussed in the Q&A session.
On the other hand, it will be quite a shame if you get stuck in this fellow.
You see this small fellow?
Because it's really just a shallow local minimum.
But according to gradient descent, you go here, the gradient is zero,
everybody is happy, and you stop there.
So you would love to have an added element that will make you escape at
least shallow valleys like that.
And the idea now is that, because you are not going in a direction that is
deterministic-- in this case, there is a random-- there is some
fluctuation here.
So there is a chance as you go here that you will escape
from the local minima.
Now this is a practical observation that in reality, stochastic gradient
descent does help with this.
It doesn't definitely cure it, far from curing it.
On the other hand, it does take care of some aspect of
escaping silly local minima.
So this is an advantage that basically is a side benefit.
We did it for the cheap computation, and we're getting this for free.
The other one we also talked about a little bit in the Q&A session, which
was the flat regions.
So you could be having this being very, very, flat and then finally
going down.
So if your termination criterion tells you that here you are OK,
then you--
it looks like flat, and nothing is happening,
and you will stop.
Every now and then when you do the random things, the fluctuation takes
you up and down and the algorithm is still alive.
Still, termination is a tricky criterion, because for termination you
need to consider all the examples in order to know exactly where you stand.
But for some of the flat regions, just the stochastic aspect also helps
a little bit with it.
So there are basically annoying artifacts of the optimization of
a surface that gradient descent will help a little bit with, if you use the
stochastic version.
Now, the third advantage--
shows randomization helps--
the third advantage you have is that it's very simple.
It is the simplest possible optimization you can think of.
You take one example, you do something, and you're ready to go.
And I will see an example in a moment that applies it.
And because it's simple, there are lots of rules of thumb for it.
So people have used it a lot, and people use it in different
applications.
So you can find rules of thumb that are actually very useful.
So I'll give you one rule of thumb that will be helpful in practice.
Remember the learning rate?
The learning rate was telling us how far we go.
And we talked about, you know, that if it's too big then you lose the linear
approximation.
If it's too small, you are moving too slowly.
So sometimes you ask, what should I use for eta, the learning rate?
Obviously, the exact answer depends on the situation, and even it is
dependent on scaling the error up and down. Mathematically, you can't really
pin it down.
From a practical point of view, if you go for a very wide range of
applications, you take a normal application, a normal error function,
mean squared or something, and then you take eta equals 0.1.
That actually works.
So you can always start with this, and then adjust it there. That's for
stochastic gradient descent.
So this is a theorem, eta equals 0.1!
And the proof is that.
These are advantages, so we are now motivated to look into stochastic
gradient descent.
And let's see it in action.
I'll take an example far from the linear models and neural
networks.
I'll take an example that we looked at before in an informal way, and it will
be very easy to formalize and implement this way.
Remember movie ratings?
What was that?
Oh, that was the example where you want a user to look at a movie and
do a rating.
And you want to look at previous ratings and predict. All of that.
Now it looked like this,
at least the proposed solution, that we will describe the user by a number of
factors, which are basically their taste.
They like comedy, they like action, they hate this, et cetera.
So there are some values here describing their taste, a profile of
the user if you will.
And then a movie-- you describe the content with the same factors.
Does it have comedy?
Does it have-- et cetera.
And the idea now is that we are going to reverse-engineer the ratings, the
existing ratings in the training set, into factors that explain
why this rating is.
And hopefully by the time we do that, we will be able to predict future guys.
So I do this for the movies that this user saw, and then I will take the
factors of the user, the factors of a movie that they haven't seen, and do
the same combination that I did here, and hopefully get a prediction for
the rating.
So all I want to do here is show you this method
using stochastic gradient descent, which was actually the method
that was used in this solution in the million-dollar prize.
So although it is very, very simple,
it is actually used.
And if you are working for something with the stakes that high, you
probably will try your best to get something right.
So the fact that actually stochastic gradient descent survived until
that late stage tells you that it's not a trivial algorithm.
So in order to put some formality on this, we need to give labels for the
users and movies.
So it would be user i, movie j,
and the rating we will call r_ij.
Very simple.
Now there are factors for the users and factors for the movie.
So let's call them something.
The factors for the user will be u_1, u_2, u_3, u_K, so it's a vector of
numbers that describe the taste of that user.
And the corresponding factors for a movie would be v_1, v_2, v_3, up to v_K,
which describe the content of that movie.
When we said we're going to match the taste of the user to the content
of the movie, what we were going to do, we were going to simply take
a coordinate,
small k, from k equals 1 to K,
and multiply these two.
So we're taking an inner product between these two guys.
And then sum up.
And that will tell us the level of matching between the two.
At least that is the quantity we are trying to make replicate the rating.
So we would like the difference between the rating and this quantity
to be small.
That's the goal.
Now in order to be accurate in the notation, the factors u_1 up to u_k and v_1
up to v_k depend on which user and which movie.
Different users have different factors, et cetera.
So I'm going to add the label of the user, and the label of the movie.
And now, if you look at the picture, i and j will appear.
So it's a bit more elaborate notation, but it's not a big deal.
And we also introduce it here in the sum.
So this will be exactly the case.
And for all of the users and all the movies, you have a shuffle of
different users rating different movies.
So the factors are reused for different ratings that appear in your
training set.
And now your idea is, how do I make these guys close to the ratings in the
training set, hopefully that they will generalize.
And the way you do it is, you define an error on that particular rating, which
is the difference between the actual rating and what the
current factors suggest.
The factors now are your parameters, and you're trying to find the value
for the parameters that minimizes this. Because you're taking one example at
a time, if you do descend on this one, it will be stochastic gradient descent.
If you wanted to do batch gradient descent, you would have to take all the
ratings, add up these terms for all the ratings you have, and
then descend on those.
But the stochastic gradient descent is the one which is used.
Could there be anything simpler?
You're going to get the partial this by partial every parameter
that appears here.
And remember in the first one, we said that all we are doing is-- we take these
factors and try to nudge them a little bit towards creating the rating.
And now we have a principled way of the nudging.
The nudging will be proportional to the partial
by partial each factor.
So I have a bunch of factors.
Which factors do I modify in order to get there?
Now we have the formula, and the formula will be, as a vector,
I'm going to move in the space that now has 2K parameters in this case.
And I'm going to move in that very high-dimensional space in a direction
that makes me, with a certain size of step, achieve the biggest drop in the
error in estimating the rating.
So you can implement this.
And indeed, if you implement it, you will get a pretty good score.
Not a winning score, but a pretty good score for the Netflix competition.
And in this case, people started adding terms, and obviously regularizing,
which will be an important issue that we'll come up with.
But basically, the simplest stochastic gradient descent with very plain
squared error on something as simple as that will get you somewhere.
So now we know that stochastic gradient descent is good.
And stochastic gradient descent is the one we're going to
apply to neural networks
model, so let's talk about neural networks model.
I am going to start with the biological inspiration of neural
networks, because it's an important factor.
That's where they got their name, and that's how they got the initial
excitement that got them to have a critical mass of
…

Need subtitles from another video?