Hello world! It's Siraj.
Let us talk about how Gradient Descent has evolved
over the years.
Tensorflow gives us quite a few options for picking a
gradient descent based optimization strategy.
This is what causes our neural network to actually learn from data.
But it is not immediately clear how we should pick one.
Once we understand the underlying details, of the most popular ones,
it will become much more clearer
which one we should use. When you study machine learning
for a while you start making connections between these
mathematical techniques and the way we learn.
At this point I view pretty much everything through the lens
of data and computation and it is a beautiful feeling.
For example,
sometimes if our data set is too homogeneous,
after training, our model will be too fit to to this data.
It will be overfit, meaning it will not be able to generalize well.
So if given some different data-point,
it wont' be able to make an accurate prediction.
We have to keep our training data diverse.
And in the same way,
if we keep our brains training data diverse,
by travelling and seeking out novel experiences,
we will be able to generalize better.
And generalization is the hallmark of intelligence.
So that's why I like anchoves.
If you were to ask what the most important machine-learning technique is,
the answer is without a doubt gradient descent.
It is the foundation of how we train intelligent systems.
And it's based off a very simple idea:
Time travel.
Instead of immediately guessing the best solution to a given objective,
we guess an initial solution,
and iteratively step in a direction
closer to a better solution.
The algorithm just repeats that process,
until it arrives at a solution, that's good enough.
Since there is no way we can know the best solution from the start,
this educated guess and check method is supremely useful.
"Oh Gradient Descent, find the ideal minima!"
"Control our variance!"
"Update our parameters!"
"And lead us to convergence!"
A simple direct example of gradient descent
would be if we wanted to calculate the minimum
value of x^2. That is where the y value is the
smallest. We could just randomly guess x values from all
over the place. But if we use gradient descent,
we will arrive at a solution that is more efficient.
The derivative of x^2 is 2x.
We use that derivative to calculate the gradient at
a given point. So we could first guess 3
and take a baby step in the direction opposite of the gradient at
x =3 , which is -6.
The next guess might be 2.3, then
1.4, then 0.7 until we finally reach 0.
Which is the local minima, both we and the machine can see
that this is the optimal solution. Since we can follow the trail of optimization
visually and mathematically as it leads us to
convergence. Another way to think about the idea of gradient descent
is examining how a professional athlete improves at a game.
As long as there is some objective function
that can be measured like, the number of wins in a season,
and some data that contributes or
detracts from that function, say passes,
number of 3 pointers, steroids, that player
can iteratively take baby steps in his routines
after analyzing the data to improve. So to
decide which of the gradient descent optimization techniques
we should use in our model, let us learn about the various
discoveries around gradient descent over the years.
Traditional gradient descent computes the
gradients of the loss function with regards to the parameters for
the entire training data set for a given number
of epochs. Since we need to calculate the gradients for the
whole data set, for just a single update
this is relatively slow and even intractible for data sets
that do not fit in memory. So to get around this
intractibility, we can use stochastic gradient descent.
This is where we perform a parameter update
for each training example and label. So we just
add a loop over our training data points and calculate
the gradient with regards to each and every one.
These more frequent updates with high
variance cause the objective function to fluctuate more
intensely. This is a good thing in that it helps it
jump to new and possibly better local minima. Where with
standard gradient descent will only converge to the minimum of the
base in, where the parameters are placed in.
But it also complicates convergence to the exact minimum
since it could keep overshooting. So an improvement
would be to use mini-batch gradient descent,
as it takes the best of both worlds by performing an update
for every subset of training examples that we can
decide the size of. Training in mini-batches is usually
the method of choice for training neural networks and we
usually use the term stochastic gradient descent even
when mini-batches are used. The oscillations in plane old
SGD make it hard to reach convergence though. So a
technique called momentum was invented that lets it
navigate along the relevant directions and softens
the oscillations in the era of interactions.
All it does is it adds a fraction of the direction or
update vector of the previous step to the current step
which amplifies the speed in the correct direction.
It is just like momentum from classical physics. Thanks Isaac Newton.
When a ball is pushed down a hill,
it accumulates momentum, meaning it becomes faster
and faster. In the same way our momentum
term increases for dimensions whose gradients point
in the same direction, and reduces updates
for dimensions whose gradients change direction.
This means 1) Faster convergence and 2) Reduced oscillations
A researcher named Yuri Nesterov saw a problem
with momentum.Once we get close to our
goal point the momentum is usually pretty high.
And it does not know that it should slow down
which it could cause to miss the minima entirely. He
solved this problem in a paper he released in 1983,
and we now call this strategy the Nesterov Accelerated
Gradient. In the momentum method
we compute the gradient, then make a jump
in that direction amplified by the previous momentum.
In this method we do the same thing but in a
different order. We first make a jump based on
our previous momentum, calculate the gradient, then
make a correction, which results in an update.
This more anticipatory update prevents us from going too fast
and we are more responsive to changes. So
this idea of more dynamic learning, of adapting our updates
to the slope of our error function is a good one.
Perhaps we could apply it to our learning rate as well.
Good ideas are good.
That is what AdaGrad does. It stands
for adaptive gradient and allows the learning rate to
adapt based on the parameters. So it makes
big updates for infrequent parameters and small updates
for frequent parameters. It uses a different learning rate for every
parameter at a given time step based on the past gradients
that were computed for that parameter. This means that we
do not have to manually tune the learning rate. Its
main weakness though is that the learning rate is always decreasing.
Since the accumulation of squared gradients
in the denominator grows because each added
term is always positive. At some point
the learning rate could get so small that the model just
stops learning entirely. AdaDelta was invented
to solve this. In AdaGrad we
are constantly adding a square root to the sum causing the
learning rate to decrease. So instead of summing all the
past square roots we restrict the window of accumulated
past gradients to a fixed size.
We define the sum of gradients as
a decaying average of all past squared gradients
instead of just stored previous squared gradients. So
the running average at a time step depends only on the
previous average and the current gradient.
So now we are getting somewhere. We are
calculating individual learning rates for each parameter
calculating momentum values and we are
preventing a vanishing learning rate. What could
we possibly do to improve here?Sprinkle in some adaptive
momentum. Since we are calculating learning rates for each
parameter, why not also store momentum changes for
each of them separately. That is what Adam does. It
stands for Adaptive moment estimation.
We calculate the first moment the mean and
the 2nd moment, the un-centered variance
of the gradients respectively. Then we
use those values to update the parameters just like in
AdaDelta. If we were to visualize these optimization algorithms
during the learning process, we will see that the
adaptive learning rate methods quickly find
the right direction and converge super fast.
While momentum and the Nesterov accelerated gradient go in the
wrong direction. So which optimizer
should you use in your Neural Network? It seems
that Adam is the best overall choice, since
it usually outperforms the rest followed
very closely by the other adaptive learning rate methods,
AdaGrad and AdaDelta. Momentum,
plain SGD and Nesterov strategy are cool, but
when data is sparse, which it usually is in real world
data sets, they don't perform well. I
know we have talked about a lot of different optimization
strategies, and it is alot to take in
all at once. So what better way to apply
this knowledge, then by implementing one by yourself.
The coding challenge for this week is to implement Adam
from scratch in python. Details are in the read me, github links
go in the comments and winners will be announced in one week.
If you subscribe all of your dreams will come true.
Check out this related video, and for now I have to go covfefe.
So thanks for watching.