[MUSIC]
Okay, so that's one way to find the maximum or
minimum of a function depending on which scenario we're in.
It's just taking the derivative of the function, setting it equal to zero.
And that solution will be unique assuming we're either in this convex or
concave situation.
But there are other methods for finding the maximum or minimum.
So, if we're looking at these concave situations and
our interest is in finding the max over all w of g(w) one thing we can look at is
something called a hill-climbing algorithm.
Where it's going to be an integrative algorithm where we start
somewhere in this space of possible w's and
then we keep changing w hoping to get closer and closer to the optimum.
Okay, so, let's say that we start w here.
And a question is well should I increase w,
move w to the right or should I decrease w and
move w to the left to get closer to the optimal.
Well, what is the optimal?
The optimal is this point here.
So, if I had this picture in front of me,
I know that I should be moving to the right.
But mathematically what's a way to say that?
What's a way to say that where increasing that we know.
Let me write this down.
How do we know whether
to move w to the right or left
and equivalently meaning increase or
decrease the value of w.
Well, what I can do is I can look at the function at w and
I can take the derivative and if the derivative is positive like it is here,
this is the case where I want to increase w.
But what if on the other hand I had started the algorithm over here
at this value of w?
Would I want to move increasing w or move to the left decreasing w?
Well, in this case, I'd want to decrease w.
And again, if I look at the derivative, I see in this case,
the derivative is negative.
So, we can actually divide the space.
Where on the left of the optimal, we have that
the derivative of g with respect to w is greater than 0.
And these are the cases where we're gonna wanna increase w.
And on the right-hand side of the optimum we have
that the derivative of g with respect to w is negative.
And these are cases where we're gonna wanna decrease w.
And what about if I'm exactly at the optimum, which maybe I'll call w Star?
Do I want to move to the left or the right?
Well, neither.
I want to stay exactly where I am.
That's the maximum.
And what happens in this case?
Well, if I look at the derivative at the optimum,
we know that the derivative is 0.
So, again, the derivative is telling me what I wanna do.
I don't wanna change w at all.
So, this hill climbing algorithm, the way we can write it is, we say.
While our algorithm has not converged.
So, while not converged, if I can spell converged.
I'm gonna take my previous w, where I was at iteration t.
So this is an iteration counter.
And I'm gonna move in the direction
indicated by the derivative.
So, if the derivative of the function is positive,
I'm going to be increasing w, and if the derivative is negative,
I'm going to be decreasing w, and that's exactly what I want to be doing.
But instead of moving exactly the amount specified by the derivative at that point,
we can introduce something, I'll call it ada.
And ada is what's called a step size.
It says when I go, so let me just complete this statement here.
So, it's a little bit more interpretable.
So, when I go to compute my next w value,
I'm gonna take my previous w value and I'm going to move and
amount based on the derivative as determined by the step size.
Okay so let's look at a picture of how this might work.
So, let's say I happen to start on this left hand side at this w value here.
Compute the derivative, and I take a step.
Determined by that step size.
And at this point the derivative is pretty large.
This function's pretty steep.
So, I'm going to be taking a big step.
Then, I compute the derivative.
I'm still taking a fairly big step.
I keep stepping increasing.
What I mean by each of these is I keep increasing w.
Keep taking a step in w.
Going, computing the derivative and
as I get closer to the optimum The size of the derivative has decreased, and so
if I assume that eda is just some constant we'll get back to this in a couple slides.
But if I assume that there is just a fixed step size that I am taking.
Then, I'm gonna be decreasing how much I'm moving.
As I get to the optimal.
And if I end up on the other side of the optimum, then
the derivative there is negative, it's going to push me back towards the optimum.
So, eventually I'm gonna converge to the optimum itself.
And note that if I'm close to the optimum, I'm not gonna jump very far.
Again because when you're close to the optimum, that derivative Is really,
really small.
So this term here is gonna be really small and I'm not gonna be changing w very much.
[MUSIC]