We've previously defined the cost function
J. In this video I want to tell you about
an algorithm called gradient descent for
minimizing the cost function J. It turns
out gradient descent is a more general
algorithm and is used not only in linear
regression. It's actually used all over
the place in machine learning. And later
in the class we'll use gradient descent to
minimize other functions as well, not just
the cost function J, for linear regression.
So in this video, I'm going to
talk about gradient descent for minimizing
some arbitrary function J. And then in
later videos, we'll take those algorithm
and apply it specifically to the cost
function J that we had to find for linear
regression. So here's the problem
setup. We're going to see that we have
some function J of (theta0, theta1).
Maybe it's a cost function from linear
regression. Maybe it's some other function
we want to minimize. And we want
to come up with an algorithm for
minimizing that as a function of J of
(theta0, theta1). Just as an aside,
it turns out that gradient descent
actually applies to more general
functions. So imagine if you have
a function that's a function of
J of (theta0, theta1, theta2, up to
some theta n). And you want to
minimize over (theta0 up to theta n)
of this J of (theta0 up to theta n).
It turns out gradient descent
is an algorithm for solving
this more general problem, but for the
sake of brevity, for the sake of
your succinctness of notation, I'm just
going to present only two parameters
throughout the rest of this video. Here's
the idea for gradient descent. What we're
going to do is we're going to start off
with some initial guesses for theta0 and
theta1. Doesn't really matter what they
are, but a common choice would be if we
set theta0 to 0, and
set theta1 to 0. Just initialize
them to 0. What we're going to do in
gradient descent is we'll keep changing
theta0 and theta1 a little bit to
try to reduce J of (theta0, theta1)
until hopefully we wind up at a minimum or
maybe a local minimum. So, let's see
see pictures of what gradient descent
does. Let's say I try to minimize this
function. So notice the axes. This is,
(theta0, theta1) on the horizontal
axes, and J is a vertical axis. And so the
height of the surface shows J, and we
want to minimize this function. So, we're
going to start off with (theta0, theta1)
at some point. So imagine picking some
value for (theta0, theta1), and that
corresponds to starting at some point on
the surface of this function. Okay? So
whatever value of (theta0, theta1)
gives you some point here. I did
initialize them to 0, but
sometimes you initialize it to other
values as well. Now. I want us to imagine
that this figure shows a hill. Imagine
this is like a landscape of some grassy
park with two hills like so.
And I want you to imagine that you are
physically standing at that point on the
hill on this little red hill in your park.
In gradient descent, what we're
going to do is spin 360 degrees around and
just look all around us and ask, "If I were
to take a little baby step in some
direction, and I want to go downhill as
quickly as possible, what direction do I
take that little baby step in if I want to
go down, if I sort of want to physically
walk down this hill as rapidly as
possible?" Turns out that if we're standing
at that point on the hill, you look all
around, you find that the best direction
to take a little step downhill
is roughly that direction. Okay. And now
you're at this new point on your hill.
You're going to, again, look all around, and then
say, "What direction should I step in order
to take a little baby step downhill?" And
if you do that and take another step, you
take a step in that direction, and then
you keep going. You know, from this new
point, you look around, decide what
direction will take you downhill most
quickly, take another step, another step,
and so on, until you converge to this,
local minimum down here. Further descent
has an interesting property. This first
time we ran gradient descent, we were
starting at this point over here, right?
Started at that point over here. Now
imagine, we initialize gradient
descent just a couple steps to the right.
Imagine we initialized gradient descent with
that point on the upper right. If you were
to repeat this process, and stop at the
point, and look all around. Take a little
step in the direction of steepest descent.
You would do that. Then look around, take
another step, and so on. And if you start
it just a couple steps to the right, the
gradient descent will have taken you to
this second local optimum over on the
right. So if you had started at this first
point, you would have wound up at this
local optimum. But if you started just a
little bit, a slightly different location,
you would have wound up at a very
different local optimum. And this is a
property of gradient descent that we'll
say a little bit more about later. So,
that's the intuition in pictures. Let's
look at the map. This is the definition of
the gradient descent algorithm. We're
going to just repeatedly do this. On to
convergence. We're going to update my
parameter theta j by, you know, taking
theta j and subtracting from it alpha
times this term over here. So, let's
see. There are a lot of details in this
equation, so let me unpack some of it.
First, this notation here, colon equals.
We're going to use := to denote
assignment, so it's the assignment
operator. So concretely, if I
write A: =B, what this means in
a computer, this means take the
value in B and use it to overwrite
whatever the value of A. So this means we
will set A to be equal to the value of B.
Okay, it's assignment. I can
also do A:=A+1. This means
take A and increase its value by one.
Whereas in contrast, if I use the equals
sign and I write A=B, then this is a
truth assertion. So if I write A=B,
then I'm asserting that the value of A
equals to the value of B. So the left hand
side, that's a computer operation, where
you set the value of A to be a value. The
right hand side, this is asserting, I'm
just making a claim that the values of A
and B are the same. And so, whereas I can
write A: =A+1, that means increment A by
1. Hopefully, I won't ever write A=A+1.
Because that's just wrong.
A and A+1 can never be equal to
the same values. So that's the first
part of the definition. This alpha
here is a number that is called the
learning rate. And what alpha does is, it
basically controls how big a step we take
downhill with gradient descent. So if
alpha is very large, then that corresponds
to a very aggressive gradient descent
procedure, where we're trying to take huge
steps downhill. And if alpha is very
small, then we're taking little, little
baby steps downhill. And, I'll come
back and say more about this later.
About how to set alpha and so on.
And finally, this term here. That's the
derivative term, I don't want to talk
about it right now, but I will derive this
derivative term and tell you exactly what
this is based on. And some of you
will be more familiar with calculus than
others, but even if you aren't familiar
with calculus don't worry about it, I'll
tell you what you need to know about this
term here. Now there's one more subtlety
about gradient descent which is, in
gradient descent, we're going to
update theta0 and theta1. So
this update takes place where j=0, and
j=1. So you're going to update j, theta0,
and update theta1. And the subtlety of
how you implement gradient descent is,
for this expression, for this
update equation, you want to
simultaneously update theta0 and
theta1. What I mean by that is
that in this equation,
we're going to update
theta0:=theta0 - something, and update
theta1:=theta1 - something.
And the way to implement this is,
you should compute the right hand
side. Compute that thing for both theta0
and theta1, and then simultaneously at
the same time update theta0 and
theta1. So let me say what I mean
by that. This is a correct implementation
of gradient descent meaning simultaneous
updates. I'm going to set temp0 equals
that, set temp1 equals that. So basically
compute the right hand sides. And then having
computed the right hand sides and stored
them together in temp0 and temp1,
I'm going to update theta0 and theta1
simultaneously, because that's the
correct implementation. In contrast,
here's an incorrect implementation that
does not do a simultaneous update. So in
this incorrect implementation, we compute
temp0, and then we update theta0
and then we compute temp1. Then we
update temp1. And the difference between
the right hand side and the left hand side
implementations is that if we look down
here, you look at this step, if by this
time you've already updated theta0
then you would be using the new
value of theta0 to compute this
derivative term and so this gives you a
different value of temp1 than the left
hand side, because you've now
plugged in the new value of theta0
into this equation. And so this on right
hand side is not a correct implementation
of gradient descent. So I don't
want to say why you need to do the
simultaneous updates, it turns
out that the way gradient descent
is usually implemented, we'll say more
about it later, it actually turns out to
be more natural to implement the
simultaneous update. And when people talk
about gradient descent, they always mean
simultaneous update. If you implement the
non-simultaneous update, it turns out
it will probably work anyway, but this
algorithm on the right is not what people
people refer to as gradient descent and
this is some other algorithm with
different properties. And for various
reasons, this can behave in
slightly stranger ways. And
what you should do is to really
implement the simultaneous update of
gradient descent. So, that's the outline of the
gradient descent algorithm. In the next video,
we're going to go into the details of the
derivative term, which I wrote out but
didn't really define. And if you've taken
a calculus class before and if you're
familiar with partial derivatives and
derivatives, it turns out that's exactly
what that derivative term is. But in case
you aren't familiar with calculus, don't
worry about it. The next video will give
you all the intuitions and will tell you
everything you need to know to compute
that derivative term, even if you haven't
seen calculus, or even if you haven't seen
partial derivatives before. And with
that, with the next video, hopefully,
we'll be able to give all the intuitions
you need to apply gradient descent.