2.7 Practical Tips for Linear Regression | Checking gradient descent for convergence -- ML Andrew Ng
 When running gradient descent, how can you tell if it is converging? That is, whether it's helping you to find parameters close to the global minimum of the cost function. By learning to recognize what a well-running implementation of gradient descent looks like, we will also, in a later video, be better able to choose a good learning rate alpha. Let's take a look. As a reminder, here's the gradient descent rule, and one of the key choices is the choice of the learning rate alpha. Here's something that I often do to make sure that gradient descent is working well. Recall that the job of gradient descent is to find parameters w and b that hopefully minimize the cost function j. So what I'll often do is plot the cost function j, which is calculated on the training set, and I'll plot the value of j at each iteration of gradient descent. Remember that each iteration means after each simultaneous update of the parameters w and b, so in this plot, the horizontal axis is the number of iterations of gradient descent that you've run so far. And so you may get a curve that looks like this. Notice that the horizontal axis is the number of iterations of gradient descent, and not a parameter like w or b. This differs from previous graphs you've seen, where the vertical axis was cost j, and the horizontal axis was a single parameter like w or b. This curve is also called a learning curve. Note that there are a few different types of learning curves used in machine learning, and you'll see some of the types later in this course as well. Secondly, if you look at this point on the curve, this means that after you've run gradient descent for 100 iterations, meaning 100 simultaneous updates of the parameters, you have some learned values for w and b. And if you compute the cost, jwb, for those values of w and b, the ones you got after 100 iterations, you get this value for the cost j, that is, this point on the vertical axis. And this point here corresponds to the value of j for the parameters that you got after 200 iterations of gradient descent. So looking at this graph helps you to see how your cost j changes after each iteration of gradient descent. If gradient descent is working properly, then the cost j should decrease after every single iteration. If j ever increases after one iteration, that means either alpha is chosen poorly, and it usually means alpha is too large, or there could be a bug in the code. Another useful thing that this plot can tell you is that if you look at this curve, by the time you reach maybe 300 iterations or so, the cost j is leveling off and is no longer decreasing much. And by 400 iterations, it looks like the curve has flattened out. So this means that gradient descent has more or less converged because the curve is no longer decreasing. So looking at this learning curve, you can try to spot whether or not gradient descent is converging. By the way, the number of iterations that gradient descent takes to converge can vary a lot between different applications. In one application, it may converge after just 30 iterations. For a different application, it could take a thousand or a hundred thousand iterations. It turns out to be very difficult to tell in advance how many iterations gradient descent needs to converge, which is why you can create a graph like this, a learning curve, to try to find out when you can stop training your particular model. Another way to decide when your model is done training is with an automatic convergence test. So let's let epsilon, this here is the Greek alphabet epsilon, let's let epsilon be a variable representing a small number, such as 0.001 or 10 to the power of negative three. If the cost J decreases by less than this number epsilon on one iteration, then you're likely on this flattened part of the curve that you see on the left and you can declare convergence. Remember, convergence hopefully indicates that you found parameters W and B that are close to the minimum possible value of J. I usually find that choosing the right threshold epsilon is pretty difficult. So I actually tend to look at graphs like this one on the left, rather than rely on automatic convergence tests. Looking at this other figure can tell you, I'll give you some advanced warning if maybe gradient descent is not working correctly as well. So you've now seen what the learning curve should look like when gradient descent is running well. Let's take these insights and in the next video, take a look at how to choose an appropriate learning rate.
[{"start": 0.0, "end": 5.96, "text": " When running gradient descent, how can you tell if it is converging?"}, {"start": 5.96, "end": 10.32, "text": " That is, whether it's helping you to find parameters close to the global minimum of"}, {"start": 10.32, "end": 12.16, "text": " the cost function."}, {"start": 12.16, "end": 16.8, "text": " By learning to recognize what a well-running implementation of gradient descent looks like,"}, {"start": 16.8, "end": 22.72, "text": " we will also, in a later video, be better able to choose a good learning rate alpha."}, {"start": 22.72, "end": 23.98, "text": " Let's take a look."}, {"start": 23.98, "end": 29.68, "text": " As a reminder, here's the gradient descent rule, and one of the key choices is the choice"}, {"start": 29.68, "end": 33.12, "text": " of the learning rate alpha."}, {"start": 33.12, "end": 38.32, "text": " Here's something that I often do to make sure that gradient descent is working well."}, {"start": 38.32, "end": 43.28, "text": " Recall that the job of gradient descent is to find parameters w and b that hopefully"}, {"start": 43.28, "end": 46.16, "text": " minimize the cost function j."}, {"start": 46.16, "end": 53.519999999999996, "text": " So what I'll often do is plot the cost function j, which is calculated on the training set,"}, {"start": 53.519999999999996, "end": 59.480000000000004, "text": " and I'll plot the value of j at each iteration of gradient descent."}, {"start": 59.48, "end": 66.36, "text": " Remember that each iteration means after each simultaneous update of the parameters w and"}, {"start": 66.36, "end": 74.62, "text": " b, so in this plot, the horizontal axis is the number of iterations of gradient descent"}, {"start": 74.62, "end": 77.16, "text": " that you've run so far."}, {"start": 77.16, "end": 80.92, "text": " And so you may get a curve that looks like this."}, {"start": 80.92, "end": 86.44, "text": " Notice that the horizontal axis is the number of iterations of gradient descent, and not"}, {"start": 86.44, "end": 90.16, "text": " a parameter like w or b."}, {"start": 90.16, "end": 96.8, "text": " This differs from previous graphs you've seen, where the vertical axis was cost j, and the"}, {"start": 96.8, "end": 103.03999999999999, "text": " horizontal axis was a single parameter like w or b."}, {"start": 103.03999999999999, "end": 106.96, "text": " This curve is also called a learning curve."}, {"start": 106.96, "end": 112.03999999999999, "text": " Note that there are a few different types of learning curves used in machine learning,"}, {"start": 112.03999999999999, "end": 116.36, "text": " and you'll see some of the types later in this course as well."}, {"start": 116.36, "end": 122.68, "text": " Secondly, if you look at this point on the curve, this means that after you've run gradient"}, {"start": 122.68, "end": 130.0, "text": " descent for 100 iterations, meaning 100 simultaneous updates of the parameters, you have some learned"}, {"start": 130.0, "end": 133.07999999999998, "text": " values for w and b."}, {"start": 133.07999999999998, "end": 140.8, "text": " And if you compute the cost, jwb, for those values of w and b, the ones you got after"}, {"start": 140.8, "end": 148.4, "text": " 100 iterations, you get this value for the cost j, that is, this point on the vertical"}, {"start": 148.4, "end": 150.04000000000002, "text": " axis."}, {"start": 150.04000000000002, "end": 156.56, "text": " And this point here corresponds to the value of j for the parameters that you got after"}, {"start": 156.56, "end": 160.10000000000002, "text": " 200 iterations of gradient descent."}, {"start": 160.10000000000002, "end": 166.26000000000002, "text": " So looking at this graph helps you to see how your cost j changes after each iteration"}, {"start": 166.26000000000002, "end": 168.18, "text": " of gradient descent."}, {"start": 168.18, "end": 173.48000000000002, "text": " If gradient descent is working properly, then the cost j should decrease after every single"}, {"start": 173.48000000000002, "end": 175.20000000000002, "text": " iteration."}, {"start": 175.20000000000002, "end": 182.84, "text": " If j ever increases after one iteration, that means either alpha is chosen poorly, and it"}, {"start": 182.84, "end": 188.28, "text": " usually means alpha is too large, or there could be a bug in the code."}, {"start": 188.28, "end": 193.44, "text": " Another useful thing that this plot can tell you is that if you look at this curve, by"}, {"start": 193.44, "end": 201.28, "text": " the time you reach maybe 300 iterations or so, the cost j is leveling off and is no longer"}, {"start": 201.28, "end": 203.16, "text": " decreasing much."}, {"start": 203.16, "end": 208.07999999999998, "text": " And by 400 iterations, it looks like the curve has flattened out."}, {"start": 208.07999999999998, "end": 214.44, "text": " So this means that gradient descent has more or less converged because the curve is no"}, {"start": 214.44, "end": 217.12, "text": " longer decreasing."}, {"start": 217.12, "end": 222.48, "text": " So looking at this learning curve, you can try to spot whether or not gradient descent"}, {"start": 222.48, "end": 224.6, "text": " is converging."}, {"start": 224.6, "end": 229.92, "text": " By the way, the number of iterations that gradient descent takes to converge can vary"}, {"start": 229.92, "end": 232.6, "text": " a lot between different applications."}, {"start": 232.6, "end": 237.0, "text": " In one application, it may converge after just 30 iterations."}, {"start": 237.0, "end": 242.88, "text": " For a different application, it could take a thousand or a hundred thousand iterations."}, {"start": 242.88, "end": 249.23999999999998, "text": " It turns out to be very difficult to tell in advance how many iterations gradient descent"}, {"start": 249.24, "end": 255.8, "text": " needs to converge, which is why you can create a graph like this, a learning curve, to try"}, {"start": 255.8, "end": 261.12, "text": " to find out when you can stop training your particular model."}, {"start": 261.12, "end": 266.68, "text": " Another way to decide when your model is done training is with an automatic convergence"}, {"start": 266.68, "end": 268.24, "text": " test."}, {"start": 268.24, "end": 276.16, "text": " So let's let epsilon, this here is the Greek alphabet epsilon, let's let epsilon be a variable"}, {"start": 276.16, "end": 283.92, "text": " representing a small number, such as 0.001 or 10 to the power of negative three."}, {"start": 283.92, "end": 289.32000000000005, "text": " If the cost J decreases by less than this number epsilon on one iteration, then you're"}, {"start": 289.32000000000005, "end": 294.76000000000005, "text": " likely on this flattened part of the curve that you see on the left and you can declare"}, {"start": 294.76000000000005, "end": 296.16, "text": " convergence."}, {"start": 296.16, "end": 301.8, "text": " Remember, convergence hopefully indicates that you found parameters W and B that are"}, {"start": 301.8, "end": 306.04, "text": " close to the minimum possible value of J."}, {"start": 306.04, "end": 310.44, "text": " I usually find that choosing the right threshold epsilon is pretty difficult."}, {"start": 310.44, "end": 314.68, "text": " So I actually tend to look at graphs like this one on the left, rather than rely on"}, {"start": 314.68, "end": 317.52000000000004, "text": " automatic convergence tests."}, {"start": 317.52000000000004, "end": 323.08000000000004, "text": " Looking at this other figure can tell you, I'll give you some advanced warning if maybe"}, {"start": 323.08000000000004, "end": 327.20000000000005, "text": " gradient descent is not working correctly as well."}, {"start": 327.20000000000005, "end": 331.58000000000004, "text": " So you've now seen what the learning curve should look like when gradient descent is"}, {"start": 331.58000000000004, "end": 332.96000000000004, "text": " running well."}, {"start": 332.96, "end": 338.03999999999996, "text": " Let's take these insights and in the next video, take a look at how to choose an appropriate"}, {"start": 338.04, "end": 363.92, "text": " learning rate."}]