10.15 Continuous State Spaces | Algorithm refinement Mini-batch and soft updates (optional)-[ML-Ng]
 In this video, we'll look at two further refinements to the reinforcement learning algorithm you've seen. The first idea is called using mini-batches, and this turns out to be an idea that can both speed up your reinforcement learning algorithm and is also applicable to supervised learning and can help you speed up your supervised learning algorithm as well, like training a neural network or training a linear regression or logistic regression model. The second idea we'll look at is soft updates, which it turns out will help your reinforcement learning algorithm do a better job to converge to a good solution. Let's take a look at mini-batches and soft updates. To understand mini-batches, let's just look at supervised learning to start. Here's a data set of housing sizes and prices that you had seen way back in the first course of this specialization on using linear regression to predict housing prices. There we had come up with this cost function for the parameters w and b. It was 1 over 2m sum of the prediction minus the actual value y squared. And the gradient descent algorithm was to repeatedly update w as w minus the learning rate alpha times the partial derivative with respect to w of the cost j of wb. And similarly to update b as follows. Let me just take this definition of j of wb and substitute it in here. Now when we looked at this example way back when we're starting to talk about linear regression and supervised learning, the training set size m was pretty small. I think we had 47 training examples. But what if you have a very, very large training set, say m equals 100 million. There are many countries, including the United States, with over 100 million housing units. And so a national census will give you a data set that is this order of magnitude of size. The problem with this algorithm when your data set is this big is that every single step of gradient descent requires computing this average over 100 million examples. And this turns out to be very slow. Every step of gradient descent means you would compute this sum or this average over 100 million examples. Then you take one tiny gradient descent step and you go back and have to scan over your entire 100 million example data set again to compute the derivative on the next step. Then you take another tiny gradient descent step and so on and so on. So when the training set size is very large, this gradient descent algorithm turns out to be quite slow. The idea of mini-batch gradient descent is to not use all 100 million training examples on every single iteration through this loop. Instead, we may pick a smaller number, let me call it m prime equals say 1000. And on every step, instead of using all 100 million examples, we would pick some subset of 1000 or m prime examples. And so this inner term becomes 1 over 2 m prime sum over some m prime examples. And so now each iteration through gradient descent requires looking only at 1000 rather than 100 million examples. And every step takes much less time and just leads to a more efficient algorithm. What mini-batch gradient descent does is on the first iteration through the algorithm, maybe it looks at that subset of the data. On the next iteration, maybe it looks at that subset of the data and so on. For the third iteration and so on. So that every iteration is looking at just a subset of the data. So each iteration runs much more quickly. To see why this might be a reasonable algorithm, here's the housing data set. And if on the first iteration, we were to look at just say five examples, this is not the whole data set, but it's slightly representative of the straight line you might want to fit in the end. So taking one gradient descent step to make the algorithm better fit these five examples is okay. But then on the next iteration, you take a different five examples like that shown here. You take one gradient descent step using these five examples. And on the next iteration, you use a different five examples and so on and so forth. You can scan through this list of examples from top to bottom. That would be one way. Another way would be if on every single iteration, you just pick a totally different five examples to use. So you might remember with bash gradient descent, if these are the contours of the cost function J, then bash gradient descent would say start here and take a step, take a step, take a step, take a step, take a step. So every step of gradient descent causes the parameters to reliably get closer to the global minimum of the cost function here in the middle. In contrast, mini-bash gradient descent or a mini-bash learning algorithm will do something like this. If you start here, then the first iteration uses just five examples. So it'll kind of head in the right direction, but maybe not the best gradient descent direction. Then the next iteration, it may do that. The next iteration, that and that, that. And sometimes just by chance, the five examples you chose may be an unlucky choice. They even head in the wrong direction, away from the global minimum and so on and so forth. But on average, mini-bash gradient descent will tend towards the global minimum, not reliably and somewhat noisily, but every iteration is much more computationally inexpensive. And so mini-bash learning or mini-bash gradient descent turns out to be a much faster algorithm when you have a very large training set. So in fact, for supervised learning, when you have a very large training set, mini-bash learning or mini-bash gradient descent or a mini-bash version with other optimization algorithms like Adam is used more common than bash gradient descent. Going back to our reinforcement learning algorithm, this is the algorithm that we had seen previously. So the mini-bash version of this would be, even if you have stored the 10,000 most recent tuples in the replay buffer, what you might choose to do is not to use all 10,000 every time you train a model. Instead, what you might do is just take a subset. So you might choose just 1,000 examples of these SAR of S as prime tuples and use it to create just 1,000 training examples to train the neural network. And it turns out that this will make each iteration of training a model a little bit more noisy, but much faster. And this will overall tend to speed up this reinforcement learning algorithm. So that's how mini-bashing can speed up both a supervised learning algorithm like linear regression as well as this reinforcement learning algorithm where you may use a mini-bash size of say, 1,000 examples, even if you've stored away 10,000 of these tuples in your replay buffer. Finally, there's one other refinement to the algorithm that can make it converge more reliably, which is I've written out this step here of set Q equals Q new, but it turns out that this can make a very abrupt change to Q. If you train a new neural network, Q new, maybe just by chance is not a very good neural network, maybe it's even a little bit worse than the old one, then you just overwrote your Q function with a potentially worse, noisy neural network. So the soft update method helps to prevent Q new from through just one unlucky step getting worse. In particular, the neural network Q will have some parameters W and B, all the parameters for all the layers of the neural network. And when you train the new neural network, you get some parameters W new and B new. So in the original algorithm as described on that slide, you would set W to be equal to W new and B equals B new, right? That's what set Q equals Q new means. With the soft update, what we do is instead set W equals 0.01 times W new plus 0.99 times W. In other words, we're going to make W to be 99% the old version of W plus 1% of the new version W new. So this is called a soft update because whenever we train a new neural network W new, we're only going to accept a little bit of the new value. And similarly, B equals 0.01 times B new plus 0.99 times B. These numbers 0.01 and 0.99, these are hyperparameters that you could set, but it controls how aggressively you move W to W new. And these two numbers are expected to add up to one. One extreme would be if you were to set W equals 1 times W new plus 0 times W, in which case you're back to the original algorithm up here where you're just copying W new onto W. But the soft update allows you to make a more gradual change to Q or to the new network parameters W and B that affect your current guess for the Q function Q of S A. And it turns out that using the soft update method causes the reinforcement learning algorithm to converge more reliably. It makes it less likely that the reinforcement learning algorithm will oscillate or diverge or have other undesirable properties. And so with these two final refinements to the algorithm, mini-batching, which actually applies very well to supervised learning as well, not just reinforcement learning, as well as the idea of soft updates, you should be able to get your learning algorithm to work really well on the lunar lander. The lunar lander is actually a decently complex, decently challenging application and so that you can get it to work and land safely on the moon. I think that's actually really cool and I hope you enjoy playing with the practice lab. Now we've talked a lot about reinforcement learning. Before we wrap up, I'd like to share with you my thoughts on the state of reinforcement learning so that as you go out and build applications using different machine learning techniques, be it supervised and unsupervised reinforcement learning techniques, that you have a framework for understanding where reinforcement learning fits in to the world of machine learning today. So let's go take a look at that in the next video.
[{"start": 0.0, "end": 7.44, "text": " In this video, we'll look at two further refinements to the reinforcement learning algorithm you've"}, {"start": 7.44, "end": 8.44, "text": " seen."}, {"start": 8.44, "end": 13.92, "text": " The first idea is called using mini-batches, and this turns out to be an idea that can"}, {"start": 13.92, "end": 19.240000000000002, "text": " both speed up your reinforcement learning algorithm and is also applicable to supervised"}, {"start": 19.240000000000002, "end": 23.2, "text": " learning and can help you speed up your supervised learning algorithm as well, like training"}, {"start": 23.2, "end": 28.32, "text": " a neural network or training a linear regression or logistic regression model."}, {"start": 28.32, "end": 33.32, "text": " The second idea we'll look at is soft updates, which it turns out will help your reinforcement"}, {"start": 33.32, "end": 37.36, "text": " learning algorithm do a better job to converge to a good solution."}, {"start": 37.36, "end": 41.2, "text": " Let's take a look at mini-batches and soft updates."}, {"start": 41.2, "end": 47.879999999999995, "text": " To understand mini-batches, let's just look at supervised learning to start."}, {"start": 47.879999999999995, "end": 55.04, "text": " Here's a data set of housing sizes and prices that you had seen way back in the first course"}, {"start": 55.04, "end": 60.48, "text": " of this specialization on using linear regression to predict housing prices."}, {"start": 60.48, "end": 66.48, "text": " There we had come up with this cost function for the parameters w and b."}, {"start": 66.48, "end": 73.48, "text": " It was 1 over 2m sum of the prediction minus the actual value y squared."}, {"start": 73.48, "end": 78.88, "text": " And the gradient descent algorithm was to repeatedly update w as w minus the learning"}, {"start": 78.88, "end": 87.52, "text": " rate alpha times the partial derivative with respect to w of the cost j of wb."}, {"start": 87.52, "end": 90.64, "text": " And similarly to update b as follows."}, {"start": 90.64, "end": 98.67999999999999, "text": " Let me just take this definition of j of wb and substitute it in here."}, {"start": 98.67999999999999, "end": 104.91999999999999, "text": " Now when we looked at this example way back when we're starting to talk about linear regression"}, {"start": 104.92, "end": 109.16, "text": " and supervised learning, the training set size m was pretty small."}, {"start": 109.16, "end": 112.04, "text": " I think we had 47 training examples."}, {"start": 112.04, "end": 118.68, "text": " But what if you have a very, very large training set, say m equals 100 million."}, {"start": 118.68, "end": 124.8, "text": " There are many countries, including the United States, with over 100 million housing units."}, {"start": 124.8, "end": 131.64, "text": " And so a national census will give you a data set that is this order of magnitude of size."}, {"start": 131.64, "end": 136.92, "text": " The problem with this algorithm when your data set is this big is that every single"}, {"start": 136.92, "end": 146.07999999999998, "text": " step of gradient descent requires computing this average over 100 million examples."}, {"start": 146.07999999999998, "end": 148.67999999999998, "text": " And this turns out to be very slow."}, {"start": 148.67999999999998, "end": 154.48, "text": " Every step of gradient descent means you would compute this sum or this average over 100"}, {"start": 154.48, "end": 155.95999999999998, "text": " million examples."}, {"start": 155.95999999999998, "end": 161.35999999999999, "text": " Then you take one tiny gradient descent step and you go back and have to scan over your"}, {"start": 161.36, "end": 167.24, "text": " entire 100 million example data set again to compute the derivative on the next step."}, {"start": 167.24, "end": 171.60000000000002, "text": " Then you take another tiny gradient descent step and so on and so on."}, {"start": 171.60000000000002, "end": 177.88000000000002, "text": " So when the training set size is very large, this gradient descent algorithm turns out"}, {"start": 177.88000000000002, "end": 179.32000000000002, "text": " to be quite slow."}, {"start": 179.32000000000002, "end": 186.06, "text": " The idea of mini-batch gradient descent is to not use all 100 million training examples"}, {"start": 186.06, "end": 188.56, "text": " on every single iteration through this loop."}, {"start": 188.56, "end": 195.52, "text": " Instead, we may pick a smaller number, let me call it m prime equals say 1000."}, {"start": 195.52, "end": 203.8, "text": " And on every step, instead of using all 100 million examples, we would pick some subset"}, {"start": 203.8, "end": 207.86, "text": " of 1000 or m prime examples."}, {"start": 207.86, "end": 214.56, "text": " And so this inner term becomes 1 over 2 m prime sum over some m prime examples."}, {"start": 214.56, "end": 221.24, "text": " And so now each iteration through gradient descent requires looking only at 1000 rather"}, {"start": 221.24, "end": 223.44, "text": " than 100 million examples."}, {"start": 223.44, "end": 228.96, "text": " And every step takes much less time and just leads to a more efficient algorithm."}, {"start": 228.96, "end": 234.36, "text": " What mini-batch gradient descent does is on the first iteration through the algorithm,"}, {"start": 234.36, "end": 237.58, "text": " maybe it looks at that subset of the data."}, {"start": 237.58, "end": 242.84, "text": " On the next iteration, maybe it looks at that subset of the data and so on."}, {"start": 242.84, "end": 245.84, "text": " For the third iteration and so on."}, {"start": 245.84, "end": 250.6, "text": " So that every iteration is looking at just a subset of the data."}, {"start": 250.6, "end": 253.52, "text": " So each iteration runs much more quickly."}, {"start": 253.52, "end": 259.62, "text": " To see why this might be a reasonable algorithm, here's the housing data set."}, {"start": 259.62, "end": 266.56, "text": " And if on the first iteration, we were to look at just say five examples, this is not"}, {"start": 266.56, "end": 270.9, "text": " the whole data set, but it's slightly representative of the straight line you might want to fit"}, {"start": 270.9, "end": 271.9, "text": " in the end."}, {"start": 271.9, "end": 276.35999999999996, "text": " So taking one gradient descent step to make the algorithm better fit these five examples"}, {"start": 276.35999999999996, "end": 277.64, "text": " is okay."}, {"start": 277.64, "end": 283.32, "text": " But then on the next iteration, you take a different five examples like that shown here."}, {"start": 283.32, "end": 286.59999999999997, "text": " You take one gradient descent step using these five examples."}, {"start": 286.59999999999997, "end": 291.28, "text": " And on the next iteration, you use a different five examples and so on and so forth."}, {"start": 291.28, "end": 296.44, "text": " You can scan through this list of examples from top to bottom."}, {"start": 296.44, "end": 298.32, "text": " That would be one way."}, {"start": 298.32, "end": 303.84, "text": " Another way would be if on every single iteration, you just pick a totally different five examples"}, {"start": 303.84, "end": 305.36, "text": " to use."}, {"start": 305.36, "end": 311.68, "text": " So you might remember with bash gradient descent, if these are the contours of the cost function"}, {"start": 311.68, "end": 318.48, "text": " J, then bash gradient descent would say start here and take a step, take a step, take a"}, {"start": 318.48, "end": 321.08, "text": " step, take a step, take a step."}, {"start": 321.08, "end": 327.12, "text": " So every step of gradient descent causes the parameters to reliably get closer to the global"}, {"start": 327.12, "end": 330.12, "text": " minimum of the cost function here in the middle."}, {"start": 330.12, "end": 335.44, "text": " In contrast, mini-bash gradient descent or a mini-bash learning algorithm will do something"}, {"start": 335.44, "end": 336.68, "text": " like this."}, {"start": 336.68, "end": 340.96, "text": " If you start here, then the first iteration uses just five examples."}, {"start": 340.96, "end": 345.76, "text": " So it'll kind of head in the right direction, but maybe not the best gradient descent direction."}, {"start": 345.76, "end": 348.4, "text": " Then the next iteration, it may do that."}, {"start": 348.4, "end": 352.16, "text": " The next iteration, that and that, that."}, {"start": 352.16, "end": 356.68, "text": " And sometimes just by chance, the five examples you chose may be an unlucky choice."}, {"start": 356.68, "end": 362.36, "text": " They even head in the wrong direction, away from the global minimum and so on and so forth."}, {"start": 362.36, "end": 368.64, "text": " But on average, mini-bash gradient descent will tend towards the global minimum, not"}, {"start": 368.64, "end": 375.8, "text": " reliably and somewhat noisily, but every iteration is much more computationally inexpensive."}, {"start": 375.8, "end": 381.72, "text": " And so mini-bash learning or mini-bash gradient descent turns out to be a much faster algorithm"}, {"start": 381.72, "end": 384.24, "text": " when you have a very large training set."}, {"start": 384.24, "end": 390.08, "text": " So in fact, for supervised learning, when you have a very large training set, mini-bash"}, {"start": 390.08, "end": 395.84000000000003, "text": " learning or mini-bash gradient descent or a mini-bash version with other optimization"}, {"start": 395.84000000000003, "end": 400.88, "text": " algorithms like Adam is used more common than bash gradient descent."}, {"start": 400.88, "end": 408.92, "text": " Going back to our reinforcement learning algorithm, this is the algorithm that we had seen previously."}, {"start": 408.92, "end": 417.44, "text": " So the mini-bash version of this would be, even if you have stored the 10,000 most recent"}, {"start": 417.44, "end": 424.56, "text": " tuples in the replay buffer, what you might choose to do is not to use all 10,000 every"}, {"start": 424.56, "end": 426.44, "text": " time you train a model."}, {"start": 426.44, "end": 430.16, "text": " Instead, what you might do is just take a subset."}, {"start": 430.16, "end": 438.8, "text": " So you might choose just 1,000 examples of these SAR of S as prime tuples and use it"}, {"start": 438.8, "end": 444.76000000000005, "text": " to create just 1,000 training examples to train the neural network."}, {"start": 444.76000000000005, "end": 449.64000000000004, "text": " And it turns out that this will make each iteration of training a model a little bit"}, {"start": 449.64000000000004, "end": 451.8, "text": " more noisy, but much faster."}, {"start": 451.8, "end": 456.84000000000003, "text": " And this will overall tend to speed up this reinforcement learning algorithm."}, {"start": 456.84, "end": 462.23999999999995, "text": " So that's how mini-bashing can speed up both a supervised learning algorithm like linear"}, {"start": 462.23999999999995, "end": 469.32, "text": " regression as well as this reinforcement learning algorithm where you may use a mini-bash size"}, {"start": 469.32, "end": 475.71999999999997, "text": " of say, 1,000 examples, even if you've stored away 10,000 of these tuples in your replay"}, {"start": 475.71999999999997, "end": 476.71999999999997, "text": " buffer."}, {"start": 476.71999999999997, "end": 482.67999999999995, "text": " Finally, there's one other refinement to the algorithm that can make it converge more reliably,"}, {"start": 482.68, "end": 489.68, "text": " which is I've written out this step here of set Q equals Q new, but it turns out that"}, {"start": 489.68, "end": 497.04, "text": " this can make a very abrupt change to Q. If you train a new neural network, Q new, maybe"}, {"start": 497.04, "end": 501.64, "text": " just by chance is not a very good neural network, maybe it's even a little bit worse than the"}, {"start": 501.64, "end": 510.84000000000003, "text": " old one, then you just overwrote your Q function with a potentially worse, noisy neural network."}, {"start": 510.84, "end": 519.12, "text": " So the soft update method helps to prevent Q new from through just one unlucky step getting"}, {"start": 519.12, "end": 520.12, "text": " worse."}, {"start": 520.12, "end": 526.16, "text": " In particular, the neural network Q will have some parameters W and B, all the parameters"}, {"start": 526.16, "end": 528.76, "text": " for all the layers of the neural network."}, {"start": 528.76, "end": 537.0799999999999, "text": " And when you train the new neural network, you get some parameters W new and B new."}, {"start": 537.08, "end": 542.84, "text": " So in the original algorithm as described on that slide, you would set W to be equal"}, {"start": 542.84, "end": 548.5600000000001, "text": " to W new and B equals B new, right?"}, {"start": 548.5600000000001, "end": 551.2800000000001, "text": " That's what set Q equals Q new means."}, {"start": 551.2800000000001, "end": 562.76, "text": " With the soft update, what we do is instead set W equals 0.01 times W new plus 0.99 times"}, {"start": 562.76, "end": 563.76, "text": " W."}, {"start": 563.76, "end": 571.28, "text": " In other words, we're going to make W to be 99% the old version of W plus 1% of the new"}, {"start": 571.28, "end": 573.4399999999999, "text": " version W new."}, {"start": 573.4399999999999, "end": 579.48, "text": " So this is called a soft update because whenever we train a new neural network W new, we're"}, {"start": 579.48, "end": 582.88, "text": " only going to accept a little bit of the new value."}, {"start": 582.88, "end": 592.28, "text": " And similarly, B equals 0.01 times B new plus 0.99 times B. These numbers 0.01 and 0.99,"}, {"start": 592.28, "end": 598.88, "text": " these are hyperparameters that you could set, but it controls how aggressively you move"}, {"start": 598.88, "end": 601.28, "text": " W to W new."}, {"start": 601.28, "end": 604.88, "text": " And these two numbers are expected to add up to one."}, {"start": 604.88, "end": 611.24, "text": " One extreme would be if you were to set W equals 1 times W new plus 0 times W, in which"}, {"start": 611.24, "end": 616.3199999999999, "text": " case you're back to the original algorithm up here where you're just copying W new onto"}, {"start": 616.3199999999999, "end": 617.3199999999999, "text": " W."}, {"start": 617.32, "end": 624.1600000000001, "text": " But the soft update allows you to make a more gradual change to Q or to the new network"}, {"start": 624.1600000000001, "end": 631.6, "text": " parameters W and B that affect your current guess for the Q function Q of S A."}, {"start": 631.6, "end": 637.5600000000001, "text": " And it turns out that using the soft update method causes the reinforcement learning algorithm"}, {"start": 637.5600000000001, "end": 638.84, "text": " to converge more reliably."}, {"start": 638.84, "end": 643.74, "text": " It makes it less likely that the reinforcement learning algorithm will oscillate or diverge"}, {"start": 643.74, "end": 646.36, "text": " or have other undesirable properties."}, {"start": 646.36, "end": 651.32, "text": " And so with these two final refinements to the algorithm, mini-batching, which actually"}, {"start": 651.32, "end": 655.6, "text": " applies very well to supervised learning as well, not just reinforcement learning, as"}, {"start": 655.6, "end": 659.5600000000001, "text": " well as the idea of soft updates, you should be able to get your learning algorithm to"}, {"start": 659.5600000000001, "end": 662.5600000000001, "text": " work really well on the lunar lander."}, {"start": 662.5600000000001, "end": 668.88, "text": " The lunar lander is actually a decently complex, decently challenging application and so that"}, {"start": 668.88, "end": 671.8000000000001, "text": " you can get it to work and land safely on the moon."}, {"start": 671.8, "end": 677.9599999999999, "text": " I think that's actually really cool and I hope you enjoy playing with the practice lab."}, {"start": 677.9599999999999, "end": 681.24, "text": " Now we've talked a lot about reinforcement learning."}, {"start": 681.24, "end": 685.4799999999999, "text": " Before we wrap up, I'd like to share with you my thoughts on the state of reinforcement"}, {"start": 685.4799999999999, "end": 690.5999999999999, "text": " learning so that as you go out and build applications using different machine learning techniques,"}, {"start": 690.5999999999999, "end": 694.76, "text": " be it supervised and unsupervised reinforcement learning techniques, that you have a framework"}, {"start": 694.76, "end": 699.5999999999999, "text": " for understanding where reinforcement learning fits in to the world of machine learning"}, {"start": 699.5999999999999, "end": 700.5999999999999, "text": " today."}, {"start": 700.6, "end": 702.84, "text": " So let's go take a look at that in the next video."}]