[MUSIC] We'll start with a very quick
review of gradient ascent. In the regression course, Emily went
into quite a lot of detail explaining the gradient ascent algorithm,
where it comes from, and the details. I really recommend you go
back to that if you want to remind yourself of where
it all comes from. I'm just going to do a very,
very, very quick review here so that we remember the fundamentals. You can think about the gradient
ascent algorithm as a kind of hill climbing algorithm. If you look at the picture on the left
here if you only had one parameter w, you can imagine starting at some point,
let's say w t with t iteration, and then moving little bit uphill
to the next parameter, w t+1. And the amount you move from one to the
other has to do with this term over here, which is the derivative of our likelihood
function with respect to the parameter w. And its computed at
the current parameter w t. Now remember we have this little
extra coefficient parameter eta, which we call the step size. A little later in the module,
we're going to discuss how that step size actually gets picked and
what effect it has. But imagine it's given, so you're
going to move by eta times the step size. And so you move here, then you move
a little bit, and you keep moving, moving, moving, moving uphill, and eventually you
get to the top of the hill to the optimum, which may be,
we're going to call w star for right now. And this is our goal, to get to that very,
very top of the hill. Now that we seen kind of hill climbing
the abstract way, getting to that top of the hill, so we step up until we
hit the top here which is w's term. We can talk about when we know we
are done in the interpretive algorithm, when have we converged? So you might remember that at
the optimum of convex functions and what we are dealing with today
is a convex function and we talked in quite a bit of detail what
that means, but just in general we'll have the derivative with respect to w for
likelihood is going to be equal to zero at the optimum here,
because that curve flattens out. Now, if we could get to the point where
the derivative is equal to zero we would be absolutely done. However we're never going to
get there exactly, so we're going to stop when
the derivative is small enough. So we stop when the derivative
with respect to parameter w computed to
recurrent parameter wt. So we'll stop when the derivative
is smaller than some taller s parameter epsilon. And, you know, sent out some small
numbers, 0.001 or something. Depends on your problem,
you'll explore this in your homework. But keep going,
you won't get exactly to the top, but you're going to get pretty close to
the top and that will be your w hat. So we'll continue going up and up and up until our derivative
is sufficiently small. Now that was for a one dimensional space,
but we have now a large animation space because we can have thousands
of coefficients we're trying to fit. So, instead of computing
a one dimensional derivative, we need what's called a gradient. And a gradient is just a stacking
here of the derivative of l with respect to the first
parameter the zero. The partial relative of l with respect to
the second parameter of w1 all the way to the derivative l the partial derivative
with respect to the last parameter wd. So this is a D + 1 dimensional vector for when you have D features. And in our case here, if we start
from this point and the derivative is taken this way, the gradient is
going to be something like this maybe. And that's what
the gradient correspond to. And then we're just going to
follow that gradient all the way to the top of the hill. In a little bit more detail,
more pictorially, we're going to set some sub-points. They're mainly heuristics for
where to start, but let's say we start over here and
we're just going to follow the gradient. And so on the right side I'm showing you what are called the contour plots. And so it corresponds to the level
set to the contours of this line. So if I start on the left side over here,
it's kind of like starting over here. I take a gradient step and I can keep following it until
I get to the optimum here, which is going to be rw* and
that corresponds to climbing this hill until I get to the top of the hill,
which is going to be rw*. And again, Emily went to quite a bit
of detail on contour plots and how they relate to that 3D plot. But that's our goal. So finally, just as a reminder, here's what the gradient
ascent algorithm looks like. You start from some point, w 0,
and so you might say w = 0, or random parameters or something else. And you just keep following the gradient until the magnitude of the gradient
is sufficiently small. So that's our algorithm,
that's going to take us to the optimum. And it's simplified over here and
the eta here is our famous step size. Great, so now we're done for
a review of gradient ascent. [MUSIC]