Stanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)

1. 0:00 – 0:45

   Intro

   1. ANAndrew Ng0:04

      Morning and welcome back.

   2. SPSpeaker0:05

      Welcome back.

   3. ANAndrew Ng0:07

      So what we'll see today in class is, um, the first in-depth discussion of a learning algorithm, linear regression. And in particular, over the next, what, hour and a bit, you see, uh, linear regression, um, batch and stochastic gradient descent as an algorithm for fitting linear regression models, and then, uh, the normal equations, um, uh, as a way of- as a very efficient way to let you fit linear models. Um, and we're going to define notation and a few concepts today that will lay the foundation for a lot of the work that we'll see the rest of this quarter.

2. 0:45 – 3:01

   Motivate Linear Regression

   1. ANAndrew Ng0:45

      Um, so to, to motivate linear regression, it's kind of, you know, maybe the, maybe the simplest- one of the simplest learning algorithms. Um, you remember, uh, the Alvin video, the autonomous driving video that I had shown in class on Monday. Um, for the self-driving car video, that was a supervised learning problem, right? And, uh, the term supervised learning meant that you were given X's, which was a picture of what's in front of the car, and the algorithm had to map that to an output Y, which was the steering direction. And, uh, that was a regression problem because the output Y that you want is a continuous value, right? As opposed to a classification problem where Y is the speed. And we'll talk about classification, um, next Monday, but supervised learning regression. So I think the simplest, maybe the simplest possible learning algorithm, a supervised learning regression problem, is linear regression. Um, and to motivate that, rather than using a, uh, self-driving car example, you know, which is quite complicated, we'll, we'll build up a supervised learning algorithm using a simpler example. Um, so let's say you want to predict or estimate the prices of houses. So the way you'd build a learning algorithm is start by collecting a data set of houses and their prices. Um, so this is a data set that we collected off Craigslist a little bit back. Uh, this is data from, uh, Portland, Oregon. But so that's the size of a house in square feet, um, and that's the price of a house in thousands of dollars. Right? And so there's a house that is, uh, two thousand one hundred and four square feet whose asking price was four hundred thousand dollars, um, house with, uh, that size with that price, and so on. Okay? Um, and maybe more conventionally, if you plot this data, that's the size, that's the price. So you have some data set like that, and what we'll end up doing today is, uh, fit a straight line to this data. Right? And go through how to do

3. 3:01 – 4:44

   Supervised Learning

   1. ANAndrew Ng3:01

      that. So in supervised learning, um, the process of supervised learning is that you have a training set, uh, such as the data set that I drew on the left, and you feed this to a learning algorithm. Right. And the job of the learning algorithm is to output a function, uh, to make predictions about housing prices. And by convention, um, I'm gonna call this function that outputs a hypothesis. Right. And the job of the hypothesis is, you know, it will, uh, it can input the size of a new house, the size of a different house that you haven't seen yet, and will output the estimated price. Okay? Um, so the job of the learning algorithm is to input a training set and output a hypothesis. The job of the hypothesis is to take as input any size of a house and try to tell you what it thinks should be the price of that house. Now, when designing a learning algorithm, um, and, and, you know, even though, uh, linear regression, right? You may have seen it in a linear algebra class before, in a summer class before. Um, the way you go about structuring a machine learning algorithm is important, and design choices of, you know, what is the workflow, what is the data set, what is the hypothesis, how to represent the hypothesis. These are the key decisions you have to make in pretty much every supervised learning, every machine learning algorithm design. So, uh, as we go through linear regression, I'll try to describe the concepts clearly as well because they'll lay the foundation for the rest of the algorithms, sometimes much more complicated algorithms you see later this quarter.

4. 4:44 – 8:27

   Designing a Learning Algorithm

   1. ANAndrew Ng4:44

      So when designing a learning algorithm, the first thing we'll need to ask is, um, how, how do you represent the hypothesis H, right? And in linear regression, for the purpose of this lecture, we're going to say that, um, the hypothesis is going to be that, right? That it'll input, uh, size X and, uh, output a number as a, as a linear function, um, of the size X. Okay? And then all the mathematicians in the room will say, technically, this is an affine function. It was a linear function. There's no theta zero. Technically, you know, but, but in machine learning, sometimes just called as a linear function, but technically, it's an affine function. Doesn't, doesn't matter. Um, so more generally, in, in, in this example, we have just one input feature, X. Uh, more generally, if you have multiple input features, so if you have more data, more information about these houses, uh, such as number of bedrooms... Excuse me. Well, handwriting's not good. That's the word bedrooms. Right. Then I guess... All right. Yeah. Cool. Yeah. My, my, my father-in-law lives a little bit outside Portland, uh, and he's actually really into real estate, so this is actually a real data set from Portland Um, so more generally, uh, if you know the size as well as the number of bedrooms in these houses, then you may have two input features where X1 is the size and X2 is the number of bedrooms. Um, I'm using the pound sign bedrooms to denote number of bedrooms. And you might say that you estimate the size of a house as, um, H of X equals theta zero plus theta one X1, plus theta two X2, where X1 is the size of the house and X2 is, [clears throat] is the number of bedrooms. Okay? Um, so in order to... So in order to simplify the notation, um, in order to make that notation a little bit more compact, um, I'm also gonna introduce this other notation where, um, we want to write the hypothesis as sum from J equals zero to two of theta J XJ. So this is summation, where for conciseness, we define X zero to be equal to one. Okay? So if we define, uh, if you define X zero to be a dummy feature that always takes on the value of one, then you can write the hypothesis H of X this way, sum from J equals zero to two of just theta J XJ. Right. So same with that equation that you saw to the upper right. And so here, theta becomes a three-dimensional parameter, theta zero, theta one, theta two. This index starting from zero, and the features become a three-dimensional feature vector X zero, X1, X2, where X zero is always one, X1 is the size of the house, and X2 is the number of bedrooms of the house. Okay? So, um, so to introduce a bit more terminology, theta

5. 8:27 – 14:44

   Parameters of the learning algorithm

   1. ANAndrew Ng8:27

      is called the Parameters of the learning algorithm, and the job of the learning algorithm is to choose parameter theta that allows you to make good predictions about, you know, prices of houses. Right? Um, and just to lay out some more, uh, notation that we're gonna use throughout this quarter, gonna use the standard that, uh, M we'll define as the number of training examples. So M is going to be the number of rows, right, in the table above, um, where, you know, each house you have in your training set is one training example. Um, you've already seen me use X to denote the inputs, um, and often the inputs are called features. Um, you know, I think, I don't know, as, as, as a, as a emerging discipline grows up, right, notation kind of emerges depending on what different scientists use for the first time when they write a paper. So I think that, I don't know. I think that the fact we call these things hypotheses, frankly, I don't think that's a great name, but, but I think someone many decades ago wrote a few papers calling it hypotheses, and then others follow, and we're kind of stuck with some of this terminology. But X is what's called input features or sometimes input attributes, um, and Y is the output. Right. And sometimes we call this the target variable. Um, and so X comma Y is, uh, one training example. Um, and, uh, I'm going to use this notation, um, X superscript I comma Y superscript I in parentheses to denote the Ith training example. Okay, so the superscript parentheses I, that's not exponentiation. Uh, I think that as you build, as, uh-- this is, um, this notation XI comma YI, this is just a way of, uh, writing an index into the table of training examples above. Okay. So, so maybe for example, if the first training example is, uh, the size, house of size two one o four, so X one one would be equal to twenty-one o four, right? Because this is the size of the first house in the training example. And I guess, uh, X, um, second example, feature one would be one four one six with our example above. So the superscript in parentheses is just, um, uh, uh, is, is, is just the, um, index into the different training examples where I, superscript I here would run from one through M, one through the number of training examples you have. Um, and then one last bit of notation, um, I'm going to use N to denote the number of features you have for the supervised learning problem. So in this example, uh, N is equal to two, right? Uh, because we have two features, which is, um, the size of the house and the number of bedrooms. So two features, which is why you can take this, right, and write this, um, as a sum from J equals zero To n. Um, and so here, x and Theta are n plus 1 dimensional because we added the extra, um, x0 and Theta 0. Okay? So, so we have two features, then these are three-dimensional vectors, and more generally, if you have n features, uh, you, you end up with x and Theta being n plus 1 dimensional features. All right. And, you know, uh, you see this notation multiple times in multiple algorithms throughout this course. So if you, you know, don't manage to memorize all these symbols right now, don't worry about it. You'll see them over and over, and they'll become familiar. All right. So, um, given the data set and given that this is the way you define the hypothesis, how do you choose the parameters? Right. So you- the learning algorithm's job is to choose values for parameters Theta so that it can output a hypothesis. So how do you choose parameters Theta? Well, what we'll do, um, is let's choose Theta such that h of x is close to y, uh, for the training examples. Okay. So, um, and I think the final bit of notation, um, I've been writing h of x as a function of the features of the house, as a function of the size and number of bedrooms the house. Um, sometimes to emphasize that h depends both on the parameters Theta and on the input features x, um, I'm going to use h subscript Theta of x to emphasize that the hypothesis depends both on the parameters and on the, you know, input features x, right? But, uh, sometimes for notational convenience, I just write this as h of x. Sometimes I include the Theta there, and they mean the same thing. It's just, uh, maybe a abbreviation in notation. But so in order to, um, learn a set of parameters, what we'll want to do is choose the parameters Theta so that at least for the houses whose prices you know, that, you know, the learning algorithm outputs prices that are close to what you know were the correct prices for that set of houses, right? Were, were the correct asking prices for those houses. And so more formally, um,

6. 14:44 – 18:06

   Linear Regression Algorithm

   1. ANAndrew Ng14:44

      in the linear regression algorithm, uh, also called ordinary least squares, but in linear regression, um, we will want to minimize-- I'm gonna build out this equation one piece at a time. Okay? Minimize the squared difference between what the hypothesis outputs, h subscript Theta of x minus y squared, right? So let's say we wanna minimize the squared difference between the prediction, which is h of x and y, which is the correct price. Um, and so what we want to do is choose values of Theta that minimizes that. Um, to fill this out, you know, you have m training examples, so I'm going to sum from i equals 1 through m of that squared difference. So this is sum over i equals 1 through all, say, 50 examples you have, right? Um, of the squared difference between what your algorithm predicts and what the true price of the house is. Um, and then finally, by convention, we put a one-half there, uh, so put a one-half constant there because, uh, when we take derivatives to minimize this later, putting one-half there will make some of the math a little bit simpler. So, you know, changing one-- adding a one-half, minimizing that formula should give you the same answer as minimizing one-half of that, but we often put a one-half there since it'll make the math a little bit simpler later. Okay? And so in linear regression, gonna define the cost function j of Theta to be equal to that. And, uh, we'll find parameters Theta that minimizes the cost function j of Theta. Okay? Um, and questions I've often gotten is, you know, why squared error? Why not absolute error or this error to the power of four? Uh, we'll talk more about that when we talk about, um, uh, when, when, when we talk about the generalization of, uh, linear regression. Um, when we talk about generalized linear models, which we'll do next week, you see that, um, uh, linear regression is a special case of a bigger family of algorithms called generalized linear models, and that, uh, using squared error corresponds to Gaussian. But, uh, but, but, but we'll, we'll, we'll justify maybe a little bit more why squared error rather than absolute error or error to the power of four, uh, next week. So, um, let me just check, see if any questions at this point. No? Okay, cool. All right. So, um, so let's-- Next, let's see how we can implement an algorithm to find the value of Theta that minimizes j of Theta, that mi-- that minimizes the cost function j of Theta. Um, we're going to

7. 18:06 – 33:01

   Gradient Descent

   1. ANAndrew Ng18:06

      use an algorithm called gradient descent. And, um, sorry. You know, this is my first class teaching in this classroom, so trying to figure out logistics like this. All right. Let's get rid of the chair. Okay, cool. Um, all right. And so with, uh, gradient descent, we are going to start with some value of theta. Um, and it could be, you know, theta equals the vector of all zeros would be a reasonable default. We can initialize it randomly. It kind of doesn't really matter. But, uh, theta is this three-dimensional vector, and I'm writing zero with an arrow on top to denote the vector of all zeros. So zero with an arrow on top, that's a vector that says zero, zero, zero everywhere, right? So, um, uh, so start with some, you know, initial value of theta, and we're going to keep changing theta, um, to reduce j of theta, okay? So let me show you a, um, vi-vi- let me show you a visualization of gradient descent, and then, and then we'll write out the math. Um, so all right. Let's say you want to minimize some function j of theta. And, uh, it's important to get the axes right in this diagram, right? So in this diagram, the horizontal axes are theta zero and theta one, and what you want to do is find values for theta zero and theta one. Um, in our, in our example, it's actually theta zero, theta one, theta two, 'cause theta's three-dimensional, but I can't plot that, so I'm just using theta zero and theta one. But what you want to do is find values for theta zero and theta one, right? That's the, um, uh, right. You wanna find values for theta zero and theta one that minimizes the height of the surface j of theta. So maybe this, this looks like a pretty good point or something, okay? Um, and so in gradient descent, you, you know, start off at some point on this surface, and you do that by initializing theta zero and theta one either randomly or to the value of all zeros or something. Doesn't, doesn't matter too much. And, um, what you do is, uh, im- imagine you're standing on this little hill, right? Standing at the point of that little X or that little cross. Um, what you do in gradient descent is, uh, turn on, turn around all three hundred and sixty degrees and look all around you and see if you were to take a tiny little step, you know, take a tiny little baby step, in what direction should you take a little step to go downhill as fast as possible? Because you're trying to go downhill, which is go to the lowest possible elevation, go to the lowest possible point of j of theta. So what gradient descent will do is, uh, stand at that point, look around, look all, all around you and say, "Well, what direction should I take a little step in to go downhill as quickly as possible?" Because you want to minimize, uh, j of theta. You wanna minim- reduce the value of j of theta. You wanna go to the lowest possible elevation on this hill. Um, and so gradient descent will take that little baby step, right? And then, and then repeat. Uh, now you're a little bit lower on the surface, so you can take-- look all around you and say, "Oh, looks like that hill, that, that little direction is the steepest direction or the steepest gradient downhill." So you take another little step, take another step, another step, and so on until, um, uh, until you, until you get to, hopefully, a local optima. Now, one property of gradient descent is that, um, uh, depending on where you initialize parameters, you can get to local dif- different points, right? So previously, you had started it at that little point X, but imagine if, uh, you had started it, you know, just a few steps over to the right, right? Uh, at that, at that new X instead of the one on the left. If you had run gradient descent from that new point, then, uh, that wouldn't have been the first step, that would've been the second step, and so on, and you would have gotten to a different local optimum, to a different local minimum. Okay? Um, it turns out that when you run gradient descent on linear regression, it turns out that, uh, uh, uh, there will not be local optimum, uh, but we'll, we'll talk about that in a little bit. Okay? So let's formalize the Gradient Descent Algorithm. Um, in gradient descent, um, each step of gradient descent, uh, is implemented as follows. So, so remember, in, in this example, the training set is fixed, right? You've, you know, you've collected a data set of housing prices from Portland, Oregon, so you just have that stored in your computer memory. And so the data set is fixed. Uh, the cost function j is a fixed function. It is a function of parameters theta, and the only thing you're gonna do is tweak or modify the parameters theta. One step of gradient descent, um, can be implemented as follows, which is theta j gets updated as theta j minus-- I'll just write this out. Okay? Um, so a bit more notation. I'm gonna use colon equals. I'm gonna use this notation to denote assignment. So what this means is we're gonna take the value on the right and assign it to theta on the left, right? And so, um, so in other words, in the notation, we'll use this quarter, you know, a colon equals a plus one. This means increment the value of a by one. Um, whereas, you know, A equals B, if I write A equals B, I'm asserting a statement of fact, right? I'm asserting that the value of A is equal to the value of B. Um, and hopefully I won't ever write A equals A plus one, right? 'Cause, 'cause that is rarely true. Okay? Um, all right. So, uh, in each step of gradient descent, you're going to, for each value of J, so you're gonna do this for J equals zero, one, two, or zero, one, up to N, where N is the number of features. For each value of J, take theta J and update it according to theta J minus alpha, um, which is called the learning rate. Um, alpha, the learning rate, times this formula. And this formula is the partial derivative of the cost function J of theta with respect to the parameter, um, theta J, okay? And then this is partial derivative notation. Uh, for those of you that, um, I don't know, haven't seen calculus for a while or haven't seen, you know, some of the prerequisites for a while, we'll, we'll, we'll go over some more of this in a little bit greater detail in discussion section, but I'll, I'll, I'll do this, um, quickly now. But, um, I don't know, if, if you've taken a calculus class a while back, you may remember that the derivative of a function is, you know, defines the direction of steepest ascent. So it defines the direction that allows you to go downhill as steeply as possible, uh, uh, on the, on the hill like that. There's a question?

   2. SPSpeaker26:05

      How do you determine the learning rate?

   3. ANAndrew Ng26:06

      Oh, how do you determine the learning rate? Uh, let me get back to that. It's a good question. Uh, for now, um, uh, you know, there's a theory and there's a practice. Uh, in practice, you set it to zero point zero one. Um-

   4. SPSpeaker26:16

      [laughs]

   5. ANAndrew Ng26:16

      [laughs] All right. Le-let me say a bit more about that later. Um, if, if you-- Actually, if, if you scale all the features between zero and one, you know, minus one and plus one or something like that, then, then, yeah, then, then try, uh, you could try a few values and see what lets you minimize the function best. But if the features are scaled to plus minus one, I usually start with point zero one and then, and then try increasing and decreasing it. Say, say a little bit more about that. Um, uh, all right, cool. So, um, let's see. Let me just quickly show how the derivative calculation is done. Um, and you know, I'm, I'm gonna do a few more equations in this lecture, uh, and then, and then over time, I think. Um, all, all, all of this, all of these definitions and derivations are written out in full detail in the lecture notes, uh, posted on the course website. So sometimes I'll do more math in class when, um, we want you to see the steps of the derivation, and sometimes to save time in class, we'll gloss over the mathematical details and leave you to read over the full details in the lecture notes on the CS229 course website. Um, so partial derivative with respect to J of theta, that's the partial derivative with respect to that of, um, one half H of theta of X minus Y squared. Uh, and so I'm gonna do a slightly simpler version, assuming we have just one training example, right? The, the actual derivate-- definition of J of theta has a sum over I from, uh, one to M over all the training examples, so I'm just forgetting that sum for now. So if you have only one training example. Um, and so from calculus, if you take the derivative of a square, you know, the two comes down, and so that cancels out with the half. So two times one half times, um, uh, the thing inside, right? Uh, and then by the, uh, chain rule of, uh, derivatives, uh, that's times the partial derivative of theta J of X, theta of X minus Y, right. So if you take the derivative of a square, the two comes down, and then you take the derivative of what's inside and multiply that, right? Um, and so the two and the one half cancel out, so this leaves you with H minus Y times partial derivative with respect to theta J of theta zero X zero plus theta one X one plus dot, dot, dot plus theta NXN minus Y, right? Uh, where I just took the definition of H of X and expanded it out to that, um, to that sum, right? Because, uh, H of X is just equal to that. So if you look at the partial derivative of each of these terms with respect to theta J, the partial derivative of every one of these terms with respect to theta J is going to z-- be zero, except for, uh, the term corresponding to J, right? Because, uh, um, you know, if, if, if J was equal to one, say, right? Then this term doesn't depend on theta one. Uh, this term, this term, all of them do not even depend on theta one. The only term that depends on theta one is this term over there. Um, and the partial derivative of this term with respect to theta one would be just X one, right? And so, um, when you take the partial derivative of this big sum with respect to theta J, uh, in, in, in-- instead of just J equals one and with respect to theta J in general, then the only term that even depends on theta J is the term theta J XJ. And so the partial derivative of all the other terms end up being zero, and partial derivative of this term with respect to theta J is equal to XJ. Okay? And so this ends up being H theta X minus Y times XJ. Okay. Um, and again, listen, if you haven't, if you haven't played with calculus for a while, if you, you know, don't quite remember what a partial derivative is or don't quite get what I just said, don't worry too much about it. Go over a bit more in the section and we, uh, and then also read through the lecture notes, which kind of goes over this in, in, in, um, in more detail and more slowly than, than, uh, we might do in class. Okay? So, um, so plugging this-- Let's see. So we've just calculated that this partial derivative, right, is equal to this. And so plugging it back into that formula, one step of gradient descent is, um, is the following, which is that we will let theta j be updated according to theta j minus the learning rate times h of x minus y times xj. Okay? Now, um, I'm gonna just add a few more things to this equation. Um, so I did this with one training example, but, uh, this was-- I kind of used definition of the cost function j of theta defined using just one single training example. But you actually have m training examples. And so, um, the, the, the correct formula for the derivative is actually if you take this thing and sum it over all m training examples, um, the derivative of, you know, the, the derivative of sum is the sum of the derivatives, right? So, um, so you actually-- If, if, if you redo this derivation, you know, summing with the correct definition of j of theta, which sums over all m training examples, if you just redo that little derivation, you end up with, uh, sum equals i through m of that, right? Where remember, xi is the i-th training example's input features, yi is the target label, is the, uh, price in the i-th training example. Okay? Um, and so this is the actual correct formula for the partial derivative with respect to that of the cost function j of theta when it's defined using, um, uh, all of the, um, uh, w-when it's defined using all of the training examples. Okay?

8. 33:01 – 42:34

   Gradient Descent Algorithm

   1. ANAndrew Ng33:01

      And so the gradient descent algorithm is to repeat until convergence, carry out this update. And in each iteration of gradient descent, uh, you do this update for j equals, um, zero, one up to n, uh, where n is the number of features. So n was two in our example. Okay? Um, and if you do this, then, uh, uh, you know... Actually, let me just show you. Then what will happen is, um... Well, I'll show you the animation. [video playing] Yes, you fit-- Hopefully, you find a pretty good value of the parameters theta. Right. So, um, it turns out that when you plot the cost function j of theta for a linear regression model, um, it turns out that unlike the earlier diagram I had shown, which has local optima, it turns out that if j of theta is defined the way that, you know, we just defined it for linear regression, is the sum of squared terms, um, then j of theta turns out to be a quadratic function, right? It's the sum of these squares of terms. And so j of theta will always look like, look like a big bowl like this. Okay? Um, another way to look at this-- Uh, oh, and so, and so j of theta, uh, does not have local optima, um, or the only local optima is also the global optimum. The other way to look at a function like this is to look at the contours of this plot, right? So you plot the contours by looking at the big bowl and taking horizontal slices and plotting where the, where the curves, where, where the, uh, edges of the horizontal slice is. So the contours of a big bowl, or I guess the formal is, uh, of, of a big, uh, el- uh, uh, ellip- of, of this, uh, quadratic function will be ellipses, um, like these, or these ovals or these ellipses like this. And so if you run gradient descent on this algorithm, um, let's say I initialize, uh, my parameters at that little x, uh, shown over here, right? And usually, you initialize theta to the value of zero, but, but, you know, but it doesn't matter too much. So let's say we initialize over there. Then, um, with one step of gradient descent, the algorithm will take that step downhill. Uh, and then with the second step, it'll take that step downhill. Oh, and by the way, fun fact, uh, if you, if you think about the contours of the function, it turns out that the direction of steepest descent is always at ninety degrees, is always orthogonal, uh, to the contour direction, right? So I don't know. Yeah. I, I, I seem to remember that from my high school something. I think it's true. All right. Uh, and so, uh, as you, as you take steps downhill, uh, uh, because there's only one global minimum, um, this algorithm will eventually converge to the global minimum. Okay? Um, and so the question just now about the choice of the learning rate alpha, um, if you set alpha to be very, very large, to be too large, then it can overshoot, right? The steps you take can be too large, and you can run past the minimum. Uh, if you set it to be too small, then you need a lot of iterations, and the algorithm will be slow. And so what happens in practice is, uh, usually you try a few values and, and, and see what value of the learning rate allows you to most efficiently, you know, drive down the value of j of theta. Um, and if you see J of Theta increasing rather than decreasing, you see the cost function increasing rather than decreasing, then that's a very strong sign that the learning rate is, uh, too large. And so, um, actually, what, what I often do is actually try out multiple values of, um, the learning rate Alpha and, uh, uh, and, and, and usually try them on exponential scale. So try open o one, open o two, open o four, open o eight, kinda like a doubling scale or some- uh, uh, uh, or doubling scale or tripling scale, and try a few values and see what value allows you to drive down the learning rate fastest. Okay? Um, let me just... So I just wanna visualize this in one other way, um, which is with the data. So, uh, this is, this is the actual dataset. Uh, there are, um, there are actually forty-nine points in this dataset, so M, the number of training examples is forty-nine. And so if you initialize the parameters to zero, that means initializing your hypothesis or initializing a straight line fit to the data to be that horizontal line, right? So if you initialize Theta zero equals zero, Theta one equals zero, then your hypothesis is, you know, for any input size of house sale price, the estimated price is zero, right? And so your, your hypothesis starts off with a horizontal line that just whatever the input X, the output Y is zero. And what you're doing, um, as you run gradient descent is you're changing the parameters Theta, right? So the parameters went from this value to this value, to this value, to this value, and so on. And so the other way of visualizing gradient descent is if gradient descent starts off with this hypothesis, with each iteration of gradient descent, you are trying to find different values of the parameters Theta, uh, that allows the straight line to fit the data better. So after one iteration of gradient descent, this is a new hypothesis. You now have different values of Theta zero and Theta one that fits the data a little bit better. Um, after two iterations, you end up with that hypothesis. Uh, and with each iteration of gradient descent, it's trying to minimize J of Thetas. It's trying to minimize one half of the sum of squares errors of the hypothesis or predictions on the different examples, right? With three iterations of gradient descent, um, uh, four iterations, and so on. And then, and then a bunch more iterations, uh, and eventually it converges to that hypothesis, which is a pretty, pretty decent straight line fit to the data. Okay. Is there a question? Yeah, go for it.

   2. SPSpeaker39:08

      I think I'm good with visualizing the gradient norm, but I don't understand why we subtract off the derivative of the cost function times a positive constant Alpha if the gradient points in the direction of least descent, and we wanna follow down that descent. Why is it, uh, negative and why is it not positive?

   3. ANAndrew Ng39:27

      Uh, sure. Maybe, uh, just to repeat the question, why is the-- why are you subtracting Alpha times the gradient rather than adding Alpha times the gradient? Um, let me suggest... Actually, let me raise the screen. Um, so let me suggest you work through one example. Um, uh, it turns out that if you add a multiple times the gradient, you'll be going uphill rather than going downhill. And maybe one way to see that would be if, um, you know, take a quadratic function, um, excuse me, right? If you're here, the gradient is a positive direction, and you want to reduce, so this would be Theta, and this would be J, I guess. So you want Theta to decrease, so the gradient is positive, you wanna decrease Theta, so you wanna subtract a multiple times the gradient. Um, I think maybe the best way to see that would be to work through an example yourself. Uh, uh, set J of Theta equals Theta squared, and set Theta equals one. So here at the quadratic function, the derivative is equal to one, so you wanna subtract a value from Theta rather than add. Okay, cool. Um, all right. Great. So you've now seen your first learning algorithm. Um, and, you know, gradient descent and linear regression is definitely still one of the most widely used learning algorithms in the world today. And if you implement this, if you, if you, if you implement this today, right, you could use this for, for some actually pretty, pretty decent purposes, right? Um, now I wanna give this algorithm one other name. Uh, so our gradient descent algorithm here, um, calculates this derivative by summing over your entire training set M. And so sometimes this version of gradient descent has another name, which is batch gradient descent. Oops. Right. Uh, and the term batch, um, you know, and again, I, I think in machine learning, a, a whole community, we just make up names of stuff, and sometimes the names aren't great. But, uh, the, the term batch gradient descent refers to that you look at the entire training set, all forty-nine examples in the example I just had on, uh, PowerPoint. You know, you, you, you think of all forty-nine examples as one batch of data. I'm gonna process all the data as a batch, so hence the name batch gradient descent. The disadvantage of batch gradient descent is that if you have a giant dataset, if you have, um... And, and y- in the era of big data, we're really moving to larger and larger datasets, right? So I've used, you know, trained machine learning models of, like, hundreds of millions of examples. Uh, uh, and, and if you are trying to-- if you have a-- if you download the US Census database or your data on the U- United States Census, that's a very large dataset. And you wanna predict housing prices from all across the United States, um, that, that, that may have a dataset with many, many millions of examples. And the disadvantage

9. 42:34 – 44:56

   Batch Gradient Descent

   1. ANAndrew Ng42:34

      of batch gradient descent is that in order to make one update- To your parameters. In order to take even a single step of gradient descent, you need to calculate this sum, and if m is, say, a million or ten million or a hundred million, you need to scan through your entire database, scan through your entire dataset, and calculate this for, you know, a hundred million examples and sum it up. And so every single step of gradient descent becomes very slow because you're scanning over, you're reading over, right, like a hundred million training examples, uh, uh, and, uh, uh, before you can even, you know, make one tiny little step of gradient descent. Okay? Um, yeah. And by the way, I think-- I don't know. I, I, I feel like, uh, in today's era of big data, people start to lose intuitions about what's a big dataset. I think even by today's standards, like a hundred million examples is still very big, right? I, I, I rarely-- only rarely use a hundred million examples. Um, I don't know. May-maybe in a few years, we'll, we'll look back on a hundred million examples and say that was really small, but at least today, uh, yeah. So the main disadvantage of, um, batch gradient descent is every single step of gradient descent requires that you read through, you know, your entire dataset, maybe terabytes of datasets, maybe, maybe, maybe, uh, tens of hundreds of terabytes of data, uh, before you can even update the parameters just once. And if gradient descent needs, you know, hundreds of iterations to converge, then you'd be scanning through your entire dataset hundreds of times, right? Or, or, or-- And, and sometimes we train our algorithms to thousands to tens of thousands of iterations. And so, so this, this gets expensive. So there's an alternative to batch gradient descent. Um, and let me just write out the algorithm here, then we can talk about it, which is going to repeatedly do this. Oops. Okay. Um, so this algorithm,

10. 44:56 – 1:18:12

    Stochastic Gradient Descent

    1. ANAndrew Ng44:56

       uh, which is called stochastic gradient descent, um, instead of scanning through all million examples before you update the parameters theta even a little bit, in stochastic gradient descent, instead, in the inner loop of the algorithm, you loop through j equals one through m of taking a gradient descent step using the derivative of just one single example, of just that, uh, one example. Oh, excuse me. It's through i, right. Yeah. So let i go from one to m and update theta j, uh, for every j. So you update this for j equals one through n. Uh, update theta j using this derivative that-- where now this derivative is taken just with re-with respect to one training example, example i. Okay? Um, yeah, I'll j- I'll just... Right. And I guess you update this for every j. Okay. And so let me just draw a picture of what this algorithm is doing. If, um, this is the contour, like the one you saw just now. So the axes are, uh, theta zero and theta one, and the height of the surface, right, you know, the contours is j of theta. With stochastic gradient descents, what you do is you initialize the parameters somewhere, and then, um, you will look at your first training example. "Hey, let's just look at one house and see if we can predict that house is better." And you modify the parameters to increase the accuracy of where you predict the price of that one house. And because you're fitting the theta just to one house, um, you know, maybe you end up improving the parameters a little bit, but not quite going in the most direct direction downhill. And you can look at the second house and say, "Hey, let's try to fit that house better." And then you update the parameters. And you look at third house, fourth house. Right. And so as you run stochastic gradient descent, it takes a slightly noisy, slightly random path, uh, but on average is headed toward the global minimum. Okay? Um, so as you run stochastic gradient descent, stochastic gradient descent will actually never quite converge. In-- With, with batch gradient descent, it kind of went to the global minimum and stopped, right? Uh, but stochastic gradient descent, even as you run, run it, the parameters oscillate and won't ever quite converge because you're always running around looking at different houses and trying to do better on just that one house, on that one house, on that one house. Uh, but when you have a very large dataset, um, stochastic gradient descent allows your implementation, allows your algorithm to make much faster progress. Uh, and so, um, uh, uh, and, and so when you have very large datasets, stochastic gradient descent is used much more in practice than batch gradient descent. Oh, sorry.

    2. SPSpeaker48:01

       Is it ever possible to start with stochastic gradient descent if you sum minimum each, and then is that the initialized batch gradient descent?

    3. ANAndrew Ng48:10

       Uh-

    4. SPSpeaker48:11

       Would you do them?

    5. ANAndrew Ng48:12

       Yeah. Uh, is it possible to start with stochastic gradient descent and then switch over to batch gradient descent? Yes, it is. Uh, um, so, uh, boy, something that wasn't a topic in this class, topic in CS230 is mini batch gradient descent, where, um, you don't-- where you use, say, a hundred examples at a time rather than one example at a time. Uh, and s- uh, so that's another algorithm that's actually used more often in practice. I think people rarely-- Actually, so, so in practice, um, you know, when your dataset is large, um, we rarely ever switch to batch gradient descent, uh, because batch gradient descent is just so slow. Right. So I, I, I don't know. I'm, I'm thinking through concrete examples of problems I've worked on. Uh, and, and I think that, uh, what... May- actually, may- I, I think that, um, uh, right, for a lot of, for, for, for modern machine learning, where you have-- if you have very, very large datasets, right? So, you know, whether if you're building a speech recognition system, you might have like a terabyte of data, right? And so, um, it's so expensive to scan through a terabyte of data. Just reading it from disk, right, is so expensive that you would probably never even run one iteration of Batch Gradient Descent. Uh, and it turns out the, the, the, the one, one huge saving grace of Stochastic Gradient Descent is, um, let's say it runs Stochastic Gradient Descent, right? And, you know, you end up with this parameter and, and that's the parameter you use for your machine learning system rather than the global optimum. It turns out that parameter is actually not that bad, right? You, you probably make perfectly fine predictions even if you don't quite get to like the global, global minimum. So, uh, what you said I think is a fine thing to do. Um, no harm trying it. Although in practice, uh, uh, uh, in, in practice we don't bother, I think. In practice, we usually use Stochastic Gradient Descent. Um, the thing that actually is more common is to slowly decrease the learning rate. So just keep using Stochastic Gradient Descent, but reduce the learning rate over time so it takes smaller and smaller steps. So if you do that, then what happens is the size of the oscillations will decrease. Uh, and so you end up oscillating or bouncing around the smaller regions. So wherever you end up may not be the global, global minimum, but at least it's, it'll be, it'll be closer to the global minimum. Yeah, so decreasing the learning rate is used much more often. Cool. Question? Yeah.

    6. SPSpeaker50:34

       If Stochastic Gradient Descent never converges, uh, what's the usual metric to decide when to stop?

    7. ANAndrew Ng50:40

       Oh, sure. When do you stop the Stochastic Gradient Descent? Uh, uh, plot J of Theta, uh, over time. So J of Theta is a cost function that you're trying to drive down. So monitor J of Theta as, you know, it's going down over time and then if it looks like it stop going down, then you can say, "Oh, it looks like it's stopped going down. I'm gonna stop training." Uh, although... And then, uh, um, you know, one nice thing about Linear Regression is, uh, it has no local optimum. And so, um, uh, it-- you run into these convergence debugging types of issues less often. When you're training highly nonlinear things like neural networks, which we'll talk about later in CS229 as well, uh, these issues become more acute. Cool. Okay, great. So, um... Oh, yeah.

    8. SPSpeaker51:31

       Quick question. Would your learning rate here be like one over n times the learning rate for batch gradient descent?

    9. ANAndrew Ng51:35

       Oh, would your learning rate be one over n times learning rate for gradient descent? Not really. It's usually much bigger than that. Uh, uh, yeah. Uh, I, yeah. Um, because if your learning rate was one over n times that of what you'd use with gradient descent, then it'd end up being as slow as Batch Gradient Descent. So it's usually much bigger. Yeah. Okay. So, um, so that's Stochastic Gradient Descent. Oh, and, and so and, and I'll tell you what I do. If, if you have a relatively small dataset, you know, if you have, if you have, I don't know, like, uh, hundreds of examples, maybe thousands of examples where, uh, it's computationally efficient to do Batch Gradient Descent, if Batch Gradient Descent doesn't cost too much, I would almost always just use Batch Gradient Descent because it's one less thing to fiddle with, right? It's just one less thing to have to worry about, uh, the parameters oscillating. But if your dataset is too large that Batch Gradient Descent becomes prohe- precipitously slow, then, uh, almost everyone would use, you know, Stochastic Gradient Descent instead, right? Or, or an algorithm more like Stochastic Gradient Descent. Um, okay. All right. So, um, gradient descent, both Batch Gradient Descent and Stochastic Gradient Descent, is an iterative algorithm, meaning that you have to take multiple steps to get to, you know, get near hopefully the global optimum. It turns out there's another algorithm, uh... Oh, and, and, um, for many other algorithms we'll talk about in this class, including generalized linear models and neural networks and a few other algorithms, uh, you will have to use gradient descent. And so, and so we'll see gradient descent, you know, as we develop multiple different algorithms later this quarter. It turns out that for the special case of Linear Regression, uh, uh, and I mean Linear Regression, but not the algorithm we'll talk about next Monday, not the algorithm we'll talk about next Wednesday, but if the algorithm you're using is Linear Regression, like exactly Linear Regression, it turns out that there's a way to, uh, solve for the optimal value of the parameters Theta to just jump in one step to the global optimum, uh, without needing to use an iterative algorithm, right? And, and this, this, this one I'm gonna present next is called the normal equation. It works only for Linear Regression. It doesn't work for any of the other algorithms we'll talk about later this quarter. But, um, uh, but let me quickly show you the derivation of that. And, um, what I want to do is, uh, give you a flavor of how to derive the normal equation, and where you end up with is, you know, well, what, what, what I hope to do is end up with a formula that lets you say Theta equals some stuff, where you just set Theta equals to that, and in one step with a few matrix multiplications, you end up with the optimal value of Theta that lands you right at the global optimum, right? Kind of just like that, just in one step. Okay. Um, and if you've taken s- you know, advanced linear algebra classes before or something, you may have seen, um, this formula for linear regression. Uh, what, what, what a lot of linear algebra classes do is, um, what some linear algebra classes do is cover the board with, you know, pages and pages of matrix derivatives. Um, what I wanna do is describe to you a matrix derivative notation that allows you to derive the normal equation in roughly four lines of linear algebra, uh, rather than sort of pages and pages of linear algebra. And in the work I've done in machine learning, you know, some- sometimes notation really matters, right? If you have the right notation, you can solve some problems much more easily. And what I wanna do is, um, uh, define this, uh, matrix linear algebra notation, and then I don't wanna do all the steps of the derivation. I wanna give you a f- give you a sense of the flavor of what it looks like, and then, um, I'll ask you to, uh, uh, get a lot of details yourself, um, in the, uh, in, in, in the lecture notes. We'll work out everything in more detail than I want to do algebra in class. Oh, and, um, in problem set one, you get to practice using this yourself to, to, to, you know, derive some additional things. I, I found this notation really convenient, right, uh, for deriving learning algorithms. Okay. So, um, I'm going to use the following notation. Um, so J, right, was a function mapping from parameters to the real numbers. So I'm going to define this, this is the derivative of J of theta with respect to theta, where re- remember, theta is a three-dimensional vector, so it's R3, or actually it's R n plus 1, right? If you have, uh, two features for the halls, if n equals 2, then theta is three-dimensional. It's n plus 1-dimensional, so it's a vector. And so I'm gonna define the derivative with respect to theta of J of theta as follows. Um, this is going to be itself, uh, 3 by 1 vector. Okay. So I hope this notation is clear. So this is a three-dimensional vector with, um, three components. Well, well, all right. So that's-- Boy. Get some... So that's the first component of this vector, that's the second, and that's the third. Okay? It's a partial derivative of J with respect to each of the three elements. Yeah. Um, and more generally, in the notation we'll use, um, let me give you an example. Um, uh, let's say that A is a matrix. So let's say that, uh, A is a two-by-two matrix. Then, um, you can have a function, right? So let's say A is, you know, A one one, A one two, A two one, A two two. Right? So A is a two-by-two matrix. Then you might have some function, um, of a matrix A, right? Then that's a real number. So maybe f maps from A two by two to-- Oh, excuse me, R two by two to a real number. All right. So, um, uh, and so for example, if f of A equals A one one plus A one two squared, then f of, you know, five, six, seven, eight would be equal to, I guess, five plus six squared. Right? So as we derive this, we'll be working a little bit with functions that map from matrices to real numbers, and this is just one made-up example of a function that inputs a matrix and maps the matrix, maps the values of the matrix to a real number. And when you have a matrix function like this, I'm going to define the derivative with respect to A of f of A to be equal to itself a matrix, where the derivative of f of A with respect to the matrix A, uh, this itself will be a matrix with the same dimension of A, and the elements of this are the derivative with respect to the individual elements. Actually, let me just write it like this. Okay. So if A was a two-by-two matrix, then the derivative of f of A with respect to A is itself a two-by-two matrix, and you compute this two-by-two matrix just by looking at f and taking, uh, derivatives with respect to the different elements and plugging them into the different, the different elements of this matrix. Okay? Um, and so in this particular example, I guess the derivative with respect to A of f of A, this would be, um, right? It would be, it would be that. Uh, and I got these four numbers by taking, um, the definition of f and taking the derivative with respect to A one one and plugging that here. Right. Uh, taking the derivative with respect to A one two and plugging that here, and taking the derivative with respect to the remaining elements and plugging them here, which, which, which was zero. Okay. So that's the definition of a matrix derivative. Yeah.

    10. SPSpeaker1:01:08

        Would you use the same definition for a vector or just like a one by N or N by one matrix?

    11. ANAndrew Ng1:01:12

        Oh, yes. We'd use same definition for a vector, uh, N by one or N by one matrix. Yes. And in fact, um, that definition and this definition for the d- derivative of J with respect to theta, these are consistent. So if you applied that definition to a column vector, treating a column vector as a N by one matrix or N by N-- or I guess it'd be N plus one by one matrix, then that, that, that specializes to what we described here. All right. So, um, let's see. Okay. So, um, I want to leave the details to the lecture notes because there is more lines of algebra I wouldn't wanna do, but I'll give you an overview of what the derivation of the normal equation looks like. Um, so armed with this definition of a derivative of a, of a matrix, uh, the, the broad outline of what we're going to do is we're going to take J of theta, right? That's the cost function. Um, take the derivative with respect to theta. Right? Uh, since theta is a vector, so we want to take derivatives with respect to theta. And, you know, well, how do you minimize the function? You take derivatives with respect to theta and set it equal to zero, and then you solve for the value of theta so that the derivative is zero. Right? The, the minimum, you know, the maximum or minimum of function is where the derivative equals zero. So, so how you derive the normal equation is take this vector. Uh, so J of theta maps from a vector to a real number. So we'll take derivatives with respect to theta, set the derivative equal to zero, and solve for theta. And then we'll end up with a formula for theta that lets you just, um, uh, you know, immediately go to the global minimum of the, of the cost function J of theta. And, and, and a lot of the build-up, a lot of this notation is, you know, is there-- w-what does this mean, and is there an easy way to compute the derivative of J of theta? Okay. So, um, uh, to help you understand the lecture notes when hopefully you take a look at them, uh, just a couple other derivations. Um, if A is a square matrix, so let's say A is, uh, an N by N matrix, so number of rows equals number of columns. Um, I'm going to denote the trace of A to be equal to the sum of the diagonal entries. Right. So sum of I of A II. And this is pronounced the trace of A. Um, and, uh, and, and you, you could, you could also write this as trace operator, like the trace function applied to A, but by convention, we often write trace of A without the parentheses. And so this is called the trace of A. So trace just means sum of diagonal entries. And, um, some facts about the trace of a matrix. You know, trace of A is equal to the trace of A transpose because if you transpose a matrix, right, you're just flipping it along the, the forty-five degree axis, and so the, the diagonal entries actually stay the same when you transpose the matrix. So the trace of A is equal to trace of A transpose. Um, and then, uh, there, there, there are some other useful properties of, um, the trace operator. Um, here's one that I don't want to prove, but that you could go home and prove yourself with a, with a few, w-with, with some, w-with a little bit of work, maybe not, not too much, which is, uh, if you define, um, F of A equals trace of A times B. So here, if B is some fixed matrix, right? Uh, and what F of A does is it multiplies A and B, and then it takes the sum of diagonal entries. Then it turns out that the derivative with respect to A of F of A is equal to, um, B transpose. Right. Um, and this is, uh, you could prove this yourself. For any matrix B, if F of A is defined this way, the, the, the derivative is equal to B transpose. Um, the trace function or the trace operator has other interesting properties. The trace of AB is equal to the trace of BA. Uh, um, you could, you could prove this from first principles. It's a little bit of work to prove, uh, uh, but, but you-- if you expand out the definitions of A and B, you should prove that. And the trace of A times B times C is equal to u- the trace of C times A times B. Uh, this is a, a cyclic permutation property. If you have a multi-- you know, multiply several matrices together, you can always take one from the end and move it to the front, and the trace will remain the same. Right. And, um, another one that is a little bit harder to prove is that the trace, excuse me, derivative of A trans-- of AA transpose C is, um Okay. Yeah. So I think just as, just as for, you know, ordinary, um, calculus, we know the derivative of x squared is 2x, right? And so we all figured out that rule, and we just use it too much without, without having to re-derive it every time. Uh, this is a little bit like that. The trace of A squared C is, you know, two times CA, right? It's a little bit like that, but, but with, with matrix notation that's there. So think of this as analogous to dda of A squared C equals 2AC, right? But the, just like the matrix version of that. All right. So finally, um, what I'd like to do is take J of theta and express it in this, uh, you know, matrix vector notation. So we can take derivatives with respect to theta and set the derivatives equal to zero and just solve for the value of theta, right? And so, um, let me just write out the definition of J of theta. So J of theta was one half sum from i equals one through m of, uh, h of x i minus y i squared. Um, and it turns out that, um, all right. It turns out that, um, if you des- if you define a matrix capital X as follows, which is I'm gonna take the matrix capital X and, uh, take the training examples we have, you know, and stack them up in rows. So we have m training examples, right? So, so the x's were column vectors. So I'm taking transpose and just stack up the training examples in, uh, in rows here. So we're gonna call this a design matrix, uh, but capital X called the design matrix. And, um, uh, it turns out that if you define X this way, then X times theta is this thing times theta. And, uh, the way a matrix vector multiplication works is, you know, theta is now a column vector, right? So theta is, you know, theta zero, theta one, theta two. So the way that, um, matrix vector multiplication works is you multiply this column vector with each of these in, in turn. And so this ends up being x one transpose theta, x two transpose theta, down to x m transpose theta, which is, of course, just the vector of all of the predictions of the algorithm. And so if, um... Now let me also define a vector y to be taking all of the, um, labels from your training example and stacking them up into a big column vector, right? Let me define y that way. Um, it turns out that, um, J of theta can then be written as one half of X theta minus y transpose X theta minus y. Okay? Um, and let me see. Yeah. Let me just, uh, uh, outline the proof, but I won't do this in great detail. So X theta minus y is going to be, right, so this is X theta. This is y. So, you know, X theta minus y is going to be this vector of h of x one minus y one down to h of x m minus y m. Right? So it's just all the errors your learning algorithm is making on the m examples, the difference between predictions and the actual labels. And, um, if you re- you, you remember, so z transpose z is equal to sum over i z squared, right? A vector transpose itself is the sum of squares of elements. And so this vector transpose itself is the sum of squares of the elements, right? So, so which is why, uh, so, so the cost function J of theta is computed by taking the sum of squares of all of these elements, of all of these errors. And, and the way you do that is to take this vector, you know, X theta minus y transpose itself, is the sum of squares of these, which is exactly the error. So that's why you end up with, uh, this is the sum of squares of the, those error terms. Okay? And, um, if some of the steps don't quite make sense, really don't worry about it. All this is written out more slowly and carefully in the lecture notes, but I wanted you to have a sense of the, uh, broad arc of the, of the big picture of the derivation before you go through them yourself in greater detail in the lecture notes elsewhere. So finally, what we want to do is take the derivative with respect to theta of J of theta and set that to zero. And so this is going to be equal to the derivative of one-half x theta minus y transpose x theta minus y. Um, and so I'm gonna, I'm gonna do the steps really quickly, right? So the steps require some of the little properties of traces and matrix derivatives that I wrote down briefly just now. But so I'm gonna do these very quickly without going into the details. But, uh, so this is equal to one-half derivatives with theta of, um... So take transposes of these things, so this becomes theta transpose x transpose minus y transpose. Um, and then, uh, kinda like expanding out a quadratic function, right? This is, you know, A minus B times C minus D. So you can, this is AC minus AD and s- and so on. So, so I'll just write this out. Right. And so, uh, what I just did here, this is similar to how, you know, Ax minus B times Ax minus B is equal to A squared x squared minus AxB, minus BAx plus B squared. It, it, it's kind of... It's, it's just expanding out a quadratic function. Right. Um, and then the final step is-- Yeah, go ahead.

    12. SPSpeaker1:15:08

        I think this is X transpose the second term.

    13. ANAndrew Ng1:15:12

        Uh, is that right? Oh, yes. Thank you. Great, thank you. Um, and then the final step is, you know, for each of these four terms, first, second, third, and fourth terms, to take the derivative with respect to theta. And if you use some of the formulas I was alluding to over there, you find that the derivative, um, which, which I don't want to show the derivation of, but it turns out that the derivative is, um, X transpose X theta plus X transpose X theta minus, um, X transpose Y minus X transpose Y. Um, and we're going to set this derivative. Actually, yeah, let me just do this. And so this simplifies to X transpose X theta minus X transpose Y. And so as, as described earlier, you're gonna set this derivative to zero. And how to go from this step to that step is using the matrix derivatives, uh, explained in more detail in the lecture notes. And so the final step is, you know, having set this to zero, this implies that X transpose X theta equals X transpose Y. Um, so this is called the normal equations. And, uh, the optimum value for theta is theta equals X transpose X inverse, X transpose Y. Okay? Um, and if you implement this, um, then, you know, you can in basically one step get the value of theta that corresponds to the global minimum. Okay? Um, and, and, and again, common question I get at this point is, "Well, what if X is non-invertible?" Uh, what that usually means is you have, uh, redundant features, uh, that your features are linearly dependent. Uh, uh, but if you use something called the pseudo inverse, you, you kind of get the right answer if that's the case. Although I think the even more right answer is if you have linearly dependent features, probably means you have the same feature repeated twice, and I would usually go and figure out what feature is actually repeated leading to this problem. Okay? All right. Uh, any last questions before-- So that, so that's the normal equations. Hope you read through the detailed derivations in the lecture notes. Any last questions before we break? Yeah, great.

    14. SPSpeaker1:17:44

        Um, just on learning rate. Um, so the last lecture talked about like learning strategy, like there are some smart ways to apply

    15. ANAndrew Ng1:17:56

        Oh, yeah. How do you choose the learning rate? It's, it's, it's quite empirical, I think. So most people would try different values and then just pick one. Yeah. All right. I think let's, let's break. If pe- if people have more questions when the TAs come up, we can keep taking questions, but let's break for today. Thanks, everyone.

Episode duration: 1:18:16