Sign in to continue learning
Calculus for Machine Learning and Data Science
26 hours 57 mins
In this and the following videos, I'm going to show you an alternate method to gradient descent called Newton's method. Newton's method is also very fast and very powerful. In principle, Newton's method is used to find the zeros of a function. However, we can adapt it a bit to be used for optimization. Newton's method works in many variables as well. But let's start by looking at how it works in one variable. So let's say you have this function over here. And your goal is to find the zero. So find this point over here. That's the point where f of x is equal to zero. So here's a pretty good method to approximate this zero really well that works similar to gradient descent. Let's start with some random point x zero. That's not the zero of the function, but that's okay. We're going to get a better one from here. Let's take the tangent at this point. So let's take the derivative and draw the tangent and see where it hits the horizontal x-axis. And at this point, we're going to call it x1. Notice that x1 is much closer to the zero than x0. So all we need to do is iterate over here. So let's do it one more time. Draw the derivative and find the new point x2. Notice how close x2 is from the zero of the function. So we pretty much almost got there. By the third point, we're very, very, very close to the zero. So we pretty much found it. We didn't exactly found it, but we got pretty close. And that's a point to be able to approximate the zero of the function really well. Now let's add some numbers. This line over here has slope f prime of x0. And this height over here is f of x0. And the base is x0 minus x1. So this formula over here for the slope is rise over run. Now rise is f of x0 and run is x0 minus x1. So therefore, f prime of x0 is f of x0 divided by x0 minus x1. We can manipulate this to get that x1 is equal to x0 minus f of x0 divided by f prime of x0. And that's the iterative step. You have f of x0. You simply calculate x1 based on x0 and then iterate. So how do we iterate? Well, let's go to one more step. Let's say that you've done it k times and you got to xk. This slope over here is f prime of xk. This height is f of xk. And this horizontal distance is xk minus xk plus 1. Therefore, doing the same math as before, xk plus 1 is equal to xk minus f of xk divided by f prime of xk. And since you know xk, you know f, and you know the derivative, then you can find xk plus 1. So you iterate on this step and you get Newton's method. Now the question is, how do you use that for optimization? Because remember, gradient descent found the minimum of a function. Newton's method is only finding the zero of a function, not the minimum. Well, we simply remember that when you want to minimize a function g of x, you actually have to find the zeros of g prime of x. So if I can find the zeros of a function, I'm very close to minimizing it. I just have to look at all the zeros and see which ones are minimum, because those are the candidates for minimum. So in other words, if I let f of x be the derivative of g of x, then by finding the zeros of f of x, I am minimizing g prime of x. And the derivative of f prime of x is simply the derivative of g of x and the derivative of that. So in other words, here are the algorithms. For Newton's method, we start with some x zero. Now, if I wanted to find the zero of f, what I have to do is update. And the step is x k plus one is x k minus f of x k over f prime of x k, where x k is my kth iteration and x k plus one is my k plus one iteration. Now in Newton's method for optimization, I have to do the same thing, except not with f, but with g prime. So I have x k plus one, the k plus one iteration is x k minus g prime of x k divided by g prime of x k prime, the second derivative. So that's going to be a big deal very soon. But before that, let's do the iterative step. The iterative step is repeat two until you find the root on the left, and on the right is repeat two until you find the minimum.