[MUSIC]
In this lesson, we'll discuss extension of gradient descent methods that allow us to
learn better and faster.
So in gradient descent, we try to minimize a loss function which is usually
a sum of loss functions on separate examples from our training set.
In gradient descent, we start with initialization w0, and
then on every step we take current approximation of parameter wt-1.
Then we subtract the gradient at this point, multiply by e to t,
the loading rate, and then we weigh the step.
Then we check the stopping criteria.
For example, we can check whether the new parameter vector is close to the previous.
And if it's close, then we stop our gradient descent.
For example, for a mean squared error, the loss function looks like
sum of squared errors of separate examples from the training set.
So to calculate the gradient of mean squared error,
we should sum gradients of squared errors over all gradient examples.
And if we have a million of gradient examples, then we have to sum over 1
million of gradients to calculate the gradient for one step of our algorithm.
That's a lot. For example, to make 1,000 gradient steps,
we have to calculate a billion of gradients.
So this makes gradient descent infeasible for large scale problems.
To overcome this problem we can use stochastic gradient descent.
It's very similar to gradient descent with only one difference.
We start with some initialization w0,
and then on every step at a time t, we select some
random example from our training set, the number of this example by i.
And then we calculate the gradient only on this example.
And then we make a step in the direction of this gradient.
So in stochastic gradient descent we approximate the gradient
of all the loss function by the gradient of loss function on only one example.
Of course, this leads to very noisy approximations.
If we analyze how the stochastic gradient descent behaves on some sample,
then we can see this picture.
So if you form iteration to iteration, the loss function can increase or decrease.
But if you make enough iterations of gradient descent then
it converges to sum minimum.
So stochastic gradient descent makes very noisy updates.
But it has a large advantage.
It needs only one example to make one gradient step.
And also it maybe used in online setting.
Suppose that you have some stream of data, for example, a click stream from a search
engine, and you want to adapt to the stream to learn a new module online.
So if you use stochastic gradient descent when you receive
another example from the click stream, you can just make one gradient step for
this particular example, and that would be online learning.
There is also a disadvantage of stochastic gradient descent.
Learning rate nt should be chosen very carefully because if you choose
a large learning rate, then the matrix cannot converge.
And if you choose too small learning rate, then the conversions will be too small
to require thousands and maybe millions of iterations to converge to the minimum.
To overcome some of these problems, one can use mini-batch gradient descent, which
merges some properties of the gradient descent and stochastic gradient descent.
So in mini-batch gradient descent,
on every iteration we choose m random examples from our training sample.
You know their indices by i1, etc, im.
Then we calculate the gradient for every of these examples.
And than we average their gradients, and make a step towards this direction.
So in mini-batch gradient descent, we use m points to estimate the full
gradient instead of one point like a stochastic gradient descent.
The updates of mini-batch gradient descent have much less noise
than stochastic gradient descent.
And this might still can be used in online learning setting.
Just accumulate n examples from your stream, and then you make an update.
And still, learning rate eta t should be chosen very carefully for
mini-batch gradient descent.
And also there is another problem with this stochastic and nonstochastic methods.
Suppose that we have a difficult function that has levelized like this.
They have elliptic form.
It is known from the calculus that gradient is always
orthogonal to the level line.
So we start from some point w0,
then we'll make a gradient step that takes us to the other side of this function.
Then we take another gradient step that takes us in the opposite direction, etc.
So the gradient distance will also rate on this function and this is not very good.
It will take many iterations for
it to converge, and it will be good to somehow overcome this problem.
So in this video, we've discussed stochastic extensions of gradient descent,
stochastic gradient descent, and mini-batch gradient descent.
They're much faster than gradient descent and
can be used in online learning setting.
But they have some problems. They have learning rates that should be
somehow chosen and they can have some problems with difficult functions.
And in the next video, we will discuss some other extensions of stochastic
methods that can overcome these difficulties.
[MUSIC]