Chapter 2.3 - Gradient Descent Ax=b

0:07 we're going to now talk about a very important method in optimization and just a generic algorithm for for what for many broad applications which is called gradient descent it turns out that gradient descent will be used everywhere throughout many of the things we do in terms of optimization and it's one of the classic methods for actually training machine learning models as well what we're going to do here is use it for solving ax equal to B we've already

0:35 learned how to essentially use iteration schemes for solving for ax equal to B and we're going to similarly learn now how to use what's called gradient descent to build an iteration scheme to find solutions for this it's a really quite flexible framework of optimization and one that certainly everybody should know in general in in many application areas so let's get to it so we're going to talk about ax equal to B so that is going to be the thing we're

1:05 after and so we want to start thinking about solving ax equal to B you know in in an efficient manner there we go

1:37 okay so we're now moving on to talk about what's called gradient descent gradient descent is a very flexible optimization framework and we're going to use it here for solving ax equal to B we've already learned how to solve ax equal to B using iteration techniques and so now we're going to sort of Step this up and think about a different iteration schema for solving a x equal to B which is this gradient descent algorithm again you can find all the

2:04 code we're going to go through here directly on this GitHub link that you can clone that has all the code availability and you can find more information including notes for this course and open source lectures here at this at my website all right so let's go after this so I want to solve ax equal to B it's a linear system of equations we already know how to solve this with Galaxy elimination we know how to solve

2:28 it with lu decomposition we know how to solve it now with jacobe iterations gidel iterations and so now we want to think about one other method here which is going to be this gradient descent so we're going to have this linear system of equation x equal to B and we're going to change its formulation and write it in what's called a quadratic form so essentially the quadratic form is some functional F ofx which is given by here for this

2:55 equation for the x equal to B it's essentially a quadratic form which means the highest highest form term here is a quadratic which is X transpose ax 12 B transpose X plus C and this form you we're going to see is that the gradient of this F gives back ax equal to B so we're going to look at this quadratic form and optimize for the solution of this quadratic form where it's in fact goes to zero where the

3:27 where the gradient is zero and that's going to be the solution to x equal to B so let's walk through this through so in other words we're not solving x equal B directly we're solving a different formulation which is this quadratic form so let's take the quadratic form and what I'm going to claim here is that in fact the gradient of f is going to be given by the following so F itself is a function of X which has multiple

3:52 components so it's an N dimensional space and so the gradient itself is defined here by essentially taking the derivative with respect to each of the coordinate directions X1 X2 all the way through X of n so that's the gradient and typically we've learned gradient some calculus for thinking about surfaces and gradients on surfaces which gives us essentially a gradient gives us the direction of downhill essentially the gradient of a surface will tell us which way is pointing downhill and

4:22 that's exactly what we're going to use here is we're going to Define this quadratic form and again we want to walk our Solutions downhill which is going to be the solution that we're looking for so what we want to do is compute the gradient and if you compute the gradient of F and if if of our quadratic form which is given by here this is exactly what you get 12 a transpose X plus 12 a x minus B now if a transpose is equal to

4:50 a in other words it's it's a symmetric Matrix then this collapses directly to axus b equals to zero or if we move the to the other side axal B okay so that's that's what we're looking at when we have this quadratic form more generally right the solution to this gradient problem is is actually here it's what we're finding is the solution here if you find the gradient of being zero it's 12 a transpose plus a

5:21 x is equal to B that's actually what it's what this specific gradient form is actually giving us is that is the solution to this which is very again if we assume that a is and for now what we're going to do assume is a is symmetric so that's going to be ax equal to B okay so that's what we're we're looking at let me show you one example of this and how we derive this so we're looking at here is a matrix a

5:50 right so a is symmetric there it is B and C we're just going to be Tak to to zero so I'm going to specify these components as my crch form so here's my quadratic form you can see I have X transpose a x minus BX and then plus C was Zero C doesn't matter because I'm going to take the derivative of this thing but if I do out this computation here's what this thing looks like in practice so I can actually

6:18 do these dot products out and Matrix multiplies out to derive the following and now what I'm going to do is take the gradient of this so the gradient of f with respect to X x 1 and X2 so when you do this this is exactly what you get here so this derivative is pretty easy to compute this is what I get here and now if I rearrange and reorganize this in fact this gives me back exactly A and

6:44 B ax equal to B right so here's the three and the two the two and the six which is part of the Matrix a and on the B side I have M I've move it to the other side I'll get two and minus 8 so this is just one example of the gradient where we're actually Computing this gradient directly from this quadratic form and reproducing our ax equal to B now what is here's what this surface

7:09 looks like this this quadratic form if I were to plot it in X1 and X2 here's what it looks like this is the function as a function of these two variables X and Y and this is the function here and what you can see is it's got this quadratic form it's a parabola right so that's the beauty of this quadratic form is you're basic basically constructing a parabola and what I'm really looking at when I minimize this or where the solution is

7:35 is the bottom of this Parabola right here so this is the the bottom of this bowl so I've created this quadratic surface in other words it's convex and what I'm going to do for an optimization is the gradient is going to tell me which way is downhill and what I'm going to do then with that gradient information is walk myself downhill right to that Center Point which is right here okay and here's a top view of

7:57 this so you can again from the top view you you can see this is the point I'm interested in that's actually where my solution is and I'm going to walk myself right downhill into that okay so I'm going to solve ax equal to B by finding the bottom of this Parabola that's that's another way to say it right so it's the gradient f is equal to zero what are the points at which the gradient is zero that's this flat spot

8:24 here in the bottom and that's where the solution is now in enal quadratic forms can gives us several canonical shapes that we not all of them are advantageous but some of them are very nice to optimize with what we're hoping for is something like this which is a convex surface which is a parabola so we can optimize to find the bottom of that bowl which is essentially where the Minima is and where our solution is alternatively we

8:51 get something convex the other way but then here we can just solve the negative of it to find where the maximum is the more problematic ones is when we have things like these these Saddles the Saddles themselves they come down in One Direction go down in another Direction so these Saddles can create problems in terms of you're not going to you're trying to find a saddle but an iteration procedure walking down hill will sort of get close to that saddle and then fall

9:18 off so it's not going to be The best scenario for you to find a minimum however there are many points where you're looking for gradient descent is is is in this kind of structure here a come back structure where you're trying to find the bottom of that convex structure okay so first of all what I want to do is set up an iteration scheme we've already learned that iteration schemes are common place and we've already solved ax equal to B with

9:45 iteration schemes which included jacobe iteration gidel so what we're going to do with the iteration scheme is we're going to have an update Rule and here's how the update rule is going to work my new solution is col C is going to be the current value of x that I have and what I'm going to do is take the minus direction of the gradient the gradient is away from downhill so the minus of it is pointing downhill so

10:11 that is the direction in which at a point x it's the fastest descent Direction and what I'm going to do then is say my update to the value of x which is let's say a guess that I might start with is going to be X is going to be the current value minus y walk downhill a distance tow so I'm going to update it with some towel so I explicitly represent this new value with parameterized by to in other words I

10:40 take a step downhill of size tow what that size should be is something that I can actually determine from optimization or I could just pick it to be some value and walk it downhill when we come to think about machine learning to is going to be what's called a learning rate it's going to be the step size take to walk downhill in this convex structure but for now we this we're going to be able to actually explicitly compute towel for

11:09 walking downhill and how I'm going to compute it well just like you would anything else what's the optimal size of towel well think about my function as a function of towel and then you just say what's the optimal step size for minimizing the error just take the derivative of of f with respect to toal and set it to zero so this gives us a formula where I'm taking the the now the derivative of this expression with respect to towel to

11:39 determine what towel I should take which is an optimal step for walking downhill so those are the two steps now in practice we don't typically do this because this is a hard computation to do so often times and I'm going to show you this we just pick to to be some value and can play around with it it's called hyperparameter 2 where I say well what if to's 0.1 what if it's 0.1 I want to walk downhill and

12:04 often times we can figure out a good tow to take but this is sort of in some sense a way to get the optimal step size to walk downhill so let's build a little code to do this the first thing is is I need initial guess for the solution X and Y remember I'm solving ax equal to B and I'm going to write in some quadratic form right so my initial guesses here are going to be you know x = 1 y is.2

12:34 these are some initial guesses and then my quadratic form is right here this is the F this is the function that I have for the quadratic form so I can evaluate it and what I'm looking for is when is this thing here when is this thing going to be derivative be equal to zero okay so that's my function and that I'm going to go ahead and take gradient descent with and so now let's start building this gradient descent algorithm remember

12:59 that the algorithm itself is updating like this so my solution now this my initial guess minus some step Tow Times the gradient of my function f now I can compute the gradient of this function f explicitly in fact we already did that and so now let's write a code that will do this and so here's the code that we want to do remember it's an iteration scheme so I have a for Loop so the for Loop here right it's going to go through

13:27 T J and it's going to walk walk through this here the first thing it's going to do is it's going to go and find an optimal value of to we're going to go through and look what to search is in one a moment but what to search is is a code which actually computes the optimal step size the optimal to so we're going to have one code that just actually has the perfect you know the optimal step size computed

13:50 at every round of the step so that's it here and it uses this command called fmin so it's going to go ahead and compute the optimal step size by hand now what we're doing here the updates in X and the updates in y is to I have a front the new value of x is the old value of x minus to times the gradient of the function in X and then the gradient of the function of Y so my old

14:16 value of f is is f and so now here's my new value of F and what I'm really looking to see is is my old value of f how close is is it to the new value of F and here it is so once it becomes Within 10 and minus 5 I stop okay otherwise I just keep appending it so I'm keeping track of my X and Y values from my starting point in this algorithm until I

14:40 converge until in other words I take enough steps until this is satisfied I'm in within 10 to minus5 of the solution so that's a that's what this thing is doing here is is walking me to convergence and and what we've seen through these iteration algorithms both in jacobe gidel is everything sort of iterate to get to the solution same thing with Newton rapson which we considered previously in our intros to iteration schemes so this is the whole

15:09 algorithm where now we have to talk about what this algorithm is here for optimizing the tow itself to search has the following structure it's a function define to search as to and what I give it is the step size where it's actually finding the correct towel here so here's what it's optimizing for is towel and minimize this functional here okay and return Min so it's going to go find us a new towel value and send back that value

15:41 as the tow so every time I take a step it's going to decide I'm going to take a gradient step in tow what's the optimal towel size this is what this algorithm will get for us find that step size now it takes the new Step computes a new gradient finds the optimal towel updates updates updates so we keep walking forward and in this algorithm every time we take a step in the direction we recompute the optimal towel to take the

16:09 next step so that's how this works okay the other thing I could have done here is just take to is 0.1 in other words I could just fix the value of to and see what happens and often times that's what's done in practice because this extra optimization procedure can be quite expensive so often times you just just pick a value of to and let it walk downhill with your prescribed value of to so there's no optimization for the value of

16:37 to so here are two examples of this and these two examples I'm going to show you is this one here okay if you're looking at this example here this is actually taking optimal towel steps so what it's doing is here is going all the way here to you see this point here this is on this ellipse of this Parabola that we have here which is this this bowl that we're sitting in and so it takes an optimal step size and then now

17:09 you recompute the new towel it takes an optimal step size to here optimal step size to here and walks you right downhill right onto the solution and this is the solution to this problem so this is the X1 X2 values is when I find the bottom of this thing that's the solution and you can see how quickly it converges in fact within three or four four iterations it converges to the solution of ax equal to B if I know if I

17:34 have that quadratic form in the second one I just fixed the value of to in other words I picked it to be like 0.1 and so now it's not taking optimal step sizes so it takes a little bit longer to converge so but you can see it's going this direction and eventually it will converge here it just takes more time to converge because I haven't taken the optimal step sizes to getting down to the bottom of that hill but in either

18:00 case it's a very simple algorithm based upon the quadratic form of axal to B and setting up an iteration procedure to walk to the bottom of of my quadratic form so gradient descent the reason I bring it up here is it's going to play a huge role later on in terms of optimization when we start training machine learning models which will come much later in lectures or even solving nonlinear system of equations gradient descent is like essentially the

18:32 classic algorithm when you want to start thinking about using because it's very flexible it's not necessarily the fastest algorithm but is one of the most heavily used algorithms for optimization is just setting up this infrastructure of walking downhill and you've got and and then letting your computer iterate because that's the strength of your computer is its ability to do iterations so again what we've talked about here is this gradient descent algorithm and what we've been thinking

19:02 about is how do you use this gradient descent for ax equal to B which is one of our most common operations we're going to do and of course we're going to do different things than ax equal to B with it but it is something that you should be aware of that we can have this entire new paradigm for solving ax equal to B with this gradient descent again lecture on data driven modeling scientific computations you can find all

19:25 the code I went over through here this GitHub and so you can clone this and have all the code base that I just showed you there so you can play around with the code and see how it works for yourself