7.11 Tree ensembles | Random forest algorithm--[Machine Learning | Andrew Ng]
 Now that we have a way to use Soundplay with Replacement to create new training sets that are a bit similar to but also quite different from the original training set, we're ready to build our first tree ensemble algorithm. In particular, in this video, we'll talk about the random forest algorithm, which is one powerful tree ensemble algorithm that works much better than using a single decision tree. Here's how we can generate an ensemble of trees. If you are given a training set of size m, then for b equals 1 to capital B, so we do this capital B times, you can use Soundplay with Replacement to create a new training set of size m. So if you had 10 training examples, you will put the 10 training examples in that virtual bag and Soundplay with Replacement 10 times to generate a new training set with also 10 examples. And then you would train a decision tree on this data set. So here's the data set I've generated using Soundplay with Replacement. If you look carefully, you may notice that some of the training examples are repeated and that's okay. And if you train the decision tree algorithm on this data set, you end up with this decision tree. And having done this once, we would then go and repeat this a second time. Use Soundplay with Replacement to generate another training set of m or 10 training examples. This again looks a bit like the original training set, but it's also a little bit different. You then train the decision tree on this new data set and you end up with a somewhat different decision tree and so on. And you may do this a total of capital B times. Typical choice of capital B, the number of such trees you build might be around 100. People recommend any value from say 64 to 128. And having built an ensemble of say 100 different trees, you would then when you are trying to make a prediction, get these trees to all vote on the correct final prediction. It turns out that setting capital B to be larger never hurts performance. But beyond a certain point, you end up with diminishing returns and it doesn't actually get that much better when B is much larger than say 100 or so. And that's why I never use say a thousand trees that just slows down the computation significantly without meaningfully increasing the performance of the overall algorithm. Just to give this particular algorithm a name, this specific instantiation of tree ensemble is sometimes also called a bagged decision tree. And that refers to putting your training examples in that virtual bag. And that's why also we use the letters lowercase b and uppercase b here because that stands for bag. There's one modification to this algorithm that will actually make it work even much better. And that changes this algorithm, the bagged decision tree into the random forest algorithm. The key idea is that even with this sampling with replacement procedure, sometimes you end up with always using the same split at the root node and very similar splits near the root node. That didn't happen in this particular example where a small change to the training set resulted in a different split at the root node. But for other training sets, it's not uncommon that for many or even all capital B training sets, you end up with the same choice of feature at the root node and at a few of the nodes near the root node. So there's one modification to the algorithm to further try to randomize the feature choice at each node that can cause the set of trees you learn to become more different from each other so that when you vote them, you end up with an even more accurate prediction. The way this is typically done is at every node when choosing a feature to use the slit, if n features are available. So in our example, we had three features available. Rather than picking from all n features, we will instead pick a random subset of k less than n features and allow the algorithm to choose only from that subset of k features. So in other words, you would pick k features as the allowed features and then out of those k features, choose the one with the highest information gain as the choice of feature to use the split. When n is large, say n is dozens or tens or even hundreds, a typical choice for the value of k would be to choose it to be square root of n. In our example, we had only three features and this technique tends to be used more for larger problems with a larger number of features. And we'll just further change the algorithm, you end up with the random forest algorithm, which will work typically much better and becomes much more robust than just a single decision tree. One way to think about why this is more robust than a single decision tree is the sampling with replacement procedure causes the algorithm to explore a lot of small changes in the data already and is training different decision trees and is averaging over all of those changes to the data that the sampling with replacement procedure causes. And so this means that any little change further to the training set makes it less likely to have a huge impact on the overall output of the overall random forest algorithm because it's already explored and is averaging over a lot of small changes to the training set. Before wrapping up this video, there's just one more thought I want to share with you, which is where does a machine learning engineer go camping? In a random forest. All right, go and tell that joke to your friends. I hope you enjoy it. The random forest is an effective algorithm and I hope you will use it in your work. Beyond the random forest, it turns out there's one other algorithm that works even better, which is a boosted decision tree. In the next video, let's talk about a boosted decision tree algorithm called XGBoost.
[{"start": 0.0, "end": 7.4, "text": " Now that we have a way to use Soundplay with Replacement to create new training sets that"}, {"start": 7.4, "end": 12.14, "text": " are a bit similar to but also quite different from the original training set, we're ready"}, {"start": 12.14, "end": 16.1, "text": " to build our first tree ensemble algorithm."}, {"start": 16.1, "end": 21.42, "text": " In particular, in this video, we'll talk about the random forest algorithm, which is one"}, {"start": 21.42, "end": 26.580000000000002, "text": " powerful tree ensemble algorithm that works much better than using a single decision tree."}, {"start": 26.580000000000002, "end": 29.96, "text": " Here's how we can generate an ensemble of trees."}, {"start": 29.96, "end": 37.84, "text": " If you are given a training set of size m, then for b equals 1 to capital B, so we do"}, {"start": 37.84, "end": 44.06, "text": " this capital B times, you can use Soundplay with Replacement to create a new training"}, {"start": 44.06, "end": 45.480000000000004, "text": " set of size m."}, {"start": 45.480000000000004, "end": 50.68, "text": " So if you had 10 training examples, you will put the 10 training examples in that virtual"}, {"start": 50.68, "end": 57.16, "text": " bag and Soundplay with Replacement 10 times to generate a new training set with also 10"}, {"start": 57.16, "end": 58.46, "text": " examples."}, {"start": 58.46, "end": 62.24, "text": " And then you would train a decision tree on this data set."}, {"start": 62.24, "end": 66.18, "text": " So here's the data set I've generated using Soundplay with Replacement."}, {"start": 66.18, "end": 70.3, "text": " If you look carefully, you may notice that some of the training examples are repeated"}, {"start": 70.3, "end": 71.84, "text": " and that's okay."}, {"start": 71.84, "end": 76.82, "text": " And if you train the decision tree algorithm on this data set, you end up with this decision"}, {"start": 76.82, "end": 78.18, "text": " tree."}, {"start": 78.18, "end": 82.98, "text": " And having done this once, we would then go and repeat this a second time."}, {"start": 82.98, "end": 89.56, "text": " Use Soundplay with Replacement to generate another training set of m or 10 training examples."}, {"start": 89.56, "end": 94.62, "text": " This again looks a bit like the original training set, but it's also a little bit different."}, {"start": 94.62, "end": 99.94, "text": " You then train the decision tree on this new data set and you end up with a somewhat different"}, {"start": 99.94, "end": 102.22, "text": " decision tree and so on."}, {"start": 102.22, "end": 106.96000000000001, "text": " And you may do this a total of capital B times."}, {"start": 106.96000000000001, "end": 112.2, "text": " Typical choice of capital B, the number of such trees you build might be around 100."}, {"start": 112.2, "end": 117.10000000000001, "text": " People recommend any value from say 64 to 128."}, {"start": 117.10000000000001, "end": 123.68, "text": " And having built an ensemble of say 100 different trees, you would then when you are trying"}, {"start": 123.68, "end": 128.66, "text": " to make a prediction, get these trees to all vote on the correct final prediction."}, {"start": 128.66, "end": 134.94, "text": " It turns out that setting capital B to be larger never hurts performance."}, {"start": 134.94, "end": 139.26, "text": " But beyond a certain point, you end up with diminishing returns and it doesn't actually"}, {"start": 139.26, "end": 144.26, "text": " get that much better when B is much larger than say 100 or so."}, {"start": 144.26, "end": 149.82, "text": " And that's why I never use say a thousand trees that just slows down the computation"}, {"start": 149.82, "end": 155.98, "text": " significantly without meaningfully increasing the performance of the overall algorithm."}, {"start": 155.98, "end": 162.1, "text": " Just to give this particular algorithm a name, this specific instantiation of tree ensemble"}, {"start": 162.1, "end": 165.38, "text": " is sometimes also called a bagged decision tree."}, {"start": 165.38, "end": 170.29999999999998, "text": " And that refers to putting your training examples in that virtual bag."}, {"start": 170.29999999999998, "end": 176.14, "text": " And that's why also we use the letters lowercase b and uppercase b here because that stands"}, {"start": 176.14, "end": 177.14, "text": " for bag."}, {"start": 177.14, "end": 181.06, "text": " There's one modification to this algorithm that will actually make it work even much"}, {"start": 181.06, "end": 182.06, "text": " better."}, {"start": 182.06, "end": 187.42, "text": " And that changes this algorithm, the bagged decision tree into the random forest algorithm."}, {"start": 187.42, "end": 193.26, "text": " The key idea is that even with this sampling with replacement procedure, sometimes you"}, {"start": 193.26, "end": 199.26, "text": " end up with always using the same split at the root node and very similar splits near"}, {"start": 199.26, "end": 200.48, "text": " the root node."}, {"start": 200.48, "end": 205.1, "text": " That didn't happen in this particular example where a small change to the training set resulted"}, {"start": 205.1, "end": 208.39999999999998, "text": " in a different split at the root node."}, {"start": 208.39999999999998, "end": 216.18, "text": " But for other training sets, it's not uncommon that for many or even all capital B training"}, {"start": 216.18, "end": 220.7, "text": " sets, you end up with the same choice of feature at the root node and at a few of the nodes"}, {"start": 220.7, "end": 222.12, "text": " near the root node."}, {"start": 222.12, "end": 228.02, "text": " So there's one modification to the algorithm to further try to randomize the feature choice"}, {"start": 228.02, "end": 234.18, "text": " at each node that can cause the set of trees you learn to become more different from each"}, {"start": 234.18, "end": 239.38, "text": " other so that when you vote them, you end up with an even more accurate prediction."}, {"start": 239.38, "end": 247.0, "text": " The way this is typically done is at every node when choosing a feature to use the slit,"}, {"start": 247.0, "end": 249.22, "text": " if n features are available."}, {"start": 249.22, "end": 253.66, "text": " So in our example, we had three features available."}, {"start": 253.66, "end": 259.4, "text": " Rather than picking from all n features, we will instead pick a random subset of k less"}, {"start": 259.4, "end": 267.34, "text": " than n features and allow the algorithm to choose only from that subset of k features."}, {"start": 267.34, "end": 272.9, "text": " So in other words, you would pick k features as the allowed features and then out of those"}, {"start": 272.9, "end": 278.02, "text": " k features, choose the one with the highest information gain as the choice of feature"}, {"start": 278.02, "end": 279.82, "text": " to use the split."}, {"start": 279.82, "end": 287.26, "text": " When n is large, say n is dozens or tens or even hundreds, a typical choice for the value"}, {"start": 287.26, "end": 291.29999999999995, "text": " of k would be to choose it to be square root of n."}, {"start": 291.29999999999995, "end": 296.7, "text": " In our example, we had only three features and this technique tends to be used more for"}, {"start": 296.7, "end": 300.03999999999996, "text": " larger problems with a larger number of features."}, {"start": 300.03999999999996, "end": 305.09999999999997, "text": " And we'll just further change the algorithm, you end up with the random forest algorithm,"}, {"start": 305.1, "end": 310.58000000000004, "text": " which will work typically much better and becomes much more robust than just a single"}, {"start": 310.58000000000004, "end": 312.02000000000004, "text": " decision tree."}, {"start": 312.02000000000004, "end": 317.78000000000003, "text": " One way to think about why this is more robust than a single decision tree is the sampling"}, {"start": 317.78000000000003, "end": 323.54, "text": " with replacement procedure causes the algorithm to explore a lot of small changes in the data"}, {"start": 323.54, "end": 329.22, "text": " already and is training different decision trees and is averaging over all of those changes"}, {"start": 329.22, "end": 333.26000000000005, "text": " to the data that the sampling with replacement procedure causes."}, {"start": 333.26, "end": 338.34, "text": " And so this means that any little change further to the training set makes it less likely to"}, {"start": 338.34, "end": 344.3, "text": " have a huge impact on the overall output of the overall random forest algorithm because"}, {"start": 344.3, "end": 350.21999999999997, "text": " it's already explored and is averaging over a lot of small changes to the training set."}, {"start": 350.21999999999997, "end": 353.78, "text": " Before wrapping up this video, there's just one more thought I want to share with you,"}, {"start": 353.78, "end": 358.78, "text": " which is where does a machine learning engineer go camping?"}, {"start": 358.78, "end": 359.78, "text": " In a random forest."}, {"start": 359.78, "end": 362.86, "text": " All right, go and tell that joke to your friends."}, {"start": 362.86, "end": 364.34000000000003, "text": " I hope you enjoy it."}, {"start": 364.34000000000003, "end": 368.66, "text": " The random forest is an effective algorithm and I hope you will use it in your work."}, {"start": 368.66, "end": 373.86, "text": " Beyond the random forest, it turns out there's one other algorithm that works even better,"}, {"start": 373.86, "end": 376.62, "text": " which is a boosted decision tree."}, {"start": 376.62, "end": 393.42, "text": " In the next video, let's talk about a boosted decision tree algorithm called XGBoost."}]