7.12 Tree ensembles | XGBoost--[Machine Learning | Andrew Ng]
 Over the years, machine learning researchers have come up with a lot of different ways to build decision trees and decision tree ensembles. Today, by far the most commonly used way or implementation of decision tree ensembles or decision trees is an algorithm called XGBoost. It runs quickly, the open source implementations are easy to use, has also been used very successfully to win many machine learning competitions as well as in many commercial applications. Let's take a look at how XGBoost works. There's a modification to the bagged decision tree algorithm that we saw in the last video that can make it work much better. Here again is the algorithm that we had written down previously. Given a training set of size M, you repeat capital B times U sampling replacement to create a new training set of size M and then train the decision tree on the new data set. And so the first time through this loop, we may create a training set like that and train the decision tree like that. But here's where we're going to change the algorithm, which is every time through this loop other than the first time, that is the second time, third time and so on, when sampling, rather than choosing each of the training examples with equal probability, we're going to choose examples with higher probability that the ensemble of trees from the trees we've built so far still gets wrong. But the second time through this loop, instead of picking from all M examples with equal probability with one over M probability, let's make it more likely that we'll pick examples that the previously trained trees misclassified or that the previously trained trees do poorly on. In training and education, there's an idea called deliberate practice. For example, if you're learning to play the piano and you're trying to master a piece on the piano, rather than practicing the entire, say, five minute piece over and over, which is quite time consuming, if you instead play the piece and then focus your attention on just the parts of the piece that you aren't yet playing that well and practice those smaller parts over and over, then that turns out to be a more efficient way for you to learn to play the piano well. And so this idea of boosting is similar. We're going to look at the decision trees we've trained so far and look at what we're still not yet doing well on. And then when building the next decision tree, we're going to focus more attention on the examples that were not yet doing well. So rather than looking at all the training examples, we focus more attention on the subset of examples that are not yet doing well on and get the new decision tree, the next decision tree we build the ensemble to try to do well on them. And this is the idea behind boosting. And it turns out to help the learning algorithm learn to do better more quickly. So in detail, we would look at this tree that we have just built and go back to the original training set. Notice that this is the original training set, not one generated through sampling or replacement, and we'll go through all 10 examples and look at what this learned decision tree predicts on all 10 examples. So this fourth most column are their predictions and put a checkmark or cross next to each example depending on whether the tree's classification was correct or incorrect. So what we'll do in the second time through this loop is we will sort of use sampling with replacement to generate another training set of 10 examples. But every time we pick an example from these 10, we'll give a higher chance of picking from one of these three examples that we're still misclassifying. And so this focuses the second decision trees attention via a process like deliberate practice on the examples that the algorithm is still not yet doing that well on. And the boosting procedure will do this for a total of capital B times, where on each iteration, you'll look at what the ensemble of trees for trees one, two, up through B minus one are not yet doing that well on. And when you're building tree number B, you will then have a higher probability of picking examples that the ensemble of the previously both trees is still not yet doing well on the mathematical details of exactly how much to increase the probability of picking this versus that example are quite complex. But you don't have to worry about them in order to use boosted tree implementations and of different ways of implementing boosting, the most widely used one today is XGBoost, which stands for extreme gradient boosting, which is an open source implementation of booster trees that is very fast and efficient. XGBoost also has a good choice of the default splitting criteria and criteria for when to stop splitting. And one of the innovations in XGBoost is that it also has built in regularization to prevent overfitting and in machine learning competitions, such as there's a widely used competition site called Kaggle, XGBoost is often a highly competitive algorithm. In fact, XGBoost and deep learning algorithms seem to be the two types of algorithms that win a lot of these competitions. Oh, and one technical note, rather than doing something with replacement, XGBoost actually assigns different weights to different training samples. So it doesn't actually need to generate a lot of randomly chosen training sets. And this makes it even a little bit more efficient than using a sampling replacement procedure. But the intuition that you saw in the previous slide is still correct in terms of how XGBoost is choosing examples to focus on. The details of XGBoost are quite complex to implement, which is why many practitioners will use the open source libraries that implement XGBoost. This is all you need to do in order to use XGBoost. You would import the XGBoost library as follows and initialize a model as a XGBoost classifier for the model. And then finally, this allows you to make predictions using this boosted decision trees algorithm. I hope that you find this algorithm useful for many applications that you may build in the future. Or alternatively, if you want to use XGBoost for regression rather than for classification, then this line here just becomes XGBregressor and the rest of the code works similarly. So that's it for the XGBoost algorithm. We have just one last video for this week and for this course where we'll wrap up and also talk about when should you use a decision tree versus maybe use a neural network. Let's go on to the last and final video of this week.
[{"start": 0.0, "end": 5.86, "text": " Over the years, machine learning researchers have come up with a lot of different ways"}, {"start": 5.86, "end": 9.3, "text": " to build decision trees and decision tree ensembles."}, {"start": 9.3, "end": 15.540000000000001, "text": " Today, by far the most commonly used way or implementation of decision tree ensembles"}, {"start": 15.540000000000001, "end": 18.88, "text": " or decision trees is an algorithm called XGBoost."}, {"start": 18.88, "end": 24.240000000000002, "text": " It runs quickly, the open source implementations are easy to use, has also been used very successfully"}, {"start": 24.240000000000002, "end": 29.2, "text": " to win many machine learning competitions as well as in many commercial applications."}, {"start": 29.2, "end": 32.08, "text": " Let's take a look at how XGBoost works."}, {"start": 32.08, "end": 37.12, "text": " There's a modification to the bagged decision tree algorithm that we saw in the last video"}, {"start": 37.12, "end": 39.8, "text": " that can make it work much better."}, {"start": 39.8, "end": 43.96, "text": " Here again is the algorithm that we had written down previously."}, {"start": 43.96, "end": 49.120000000000005, "text": " Given a training set of size M, you repeat capital B times U sampling replacement to"}, {"start": 49.120000000000005, "end": 54.32, "text": " create a new training set of size M and then train the decision tree on the new data set."}, {"start": 54.32, "end": 60.52, "text": " And so the first time through this loop, we may create a training set like that and train"}, {"start": 60.52, "end": 62.44, "text": " the decision tree like that."}, {"start": 62.44, "end": 66.76, "text": " But here's where we're going to change the algorithm, which is every time through this"}, {"start": 66.76, "end": 73.28, "text": " loop other than the first time, that is the second time, third time and so on, when sampling,"}, {"start": 73.28, "end": 78.76, "text": " rather than choosing each of the training examples with equal probability, we're going"}, {"start": 78.76, "end": 85.96000000000001, "text": " to choose examples with higher probability that the ensemble of trees from the trees"}, {"start": 85.96000000000001, "end": 89.64, "text": " we've built so far still gets wrong."}, {"start": 89.64, "end": 96.08000000000001, "text": " But the second time through this loop, instead of picking from all M examples with equal"}, {"start": 96.08000000000001, "end": 101.56, "text": " probability with one over M probability, let's make it more likely that we'll pick examples"}, {"start": 101.56, "end": 107.0, "text": " that the previously trained trees misclassified or that the previously trained trees do poorly"}, {"start": 107.0, "end": 108.96, "text": " on."}, {"start": 108.96, "end": 113.28, "text": " In training and education, there's an idea called deliberate practice."}, {"start": 113.28, "end": 118.16, "text": " For example, if you're learning to play the piano and you're trying to master a piece"}, {"start": 118.16, "end": 124.16, "text": " on the piano, rather than practicing the entire, say, five minute piece over and over, which"}, {"start": 124.16, "end": 129.44, "text": " is quite time consuming, if you instead play the piece and then focus your attention on"}, {"start": 129.44, "end": 133.32, "text": " just the parts of the piece that you aren't yet playing that well and practice those smaller"}, {"start": 133.32, "end": 137.38, "text": " parts over and over, then that turns out to be a more efficient way for you to learn to"}, {"start": 137.38, "end": 139.4, "text": " play the piano well."}, {"start": 139.4, "end": 142.51999999999998, "text": " And so this idea of boosting is similar."}, {"start": 142.51999999999998, "end": 146.23999999999998, "text": " We're going to look at the decision trees we've trained so far and look at what we're"}, {"start": 146.23999999999998, "end": 148.42, "text": " still not yet doing well on."}, {"start": 148.42, "end": 152.16, "text": " And then when building the next decision tree, we're going to focus more attention on the"}, {"start": 152.16, "end": 154.35999999999999, "text": " examples that were not yet doing well."}, {"start": 154.35999999999999, "end": 159.88, "text": " So rather than looking at all the training examples, we focus more attention on the subset"}, {"start": 159.88, "end": 164.51999999999998, "text": " of examples that are not yet doing well on and get the new decision tree, the next decision"}, {"start": 164.51999999999998, "end": 168.0, "text": " tree we build the ensemble to try to do well on them."}, {"start": 168.0, "end": 170.24, "text": " And this is the idea behind boosting."}, {"start": 170.24, "end": 175.06, "text": " And it turns out to help the learning algorithm learn to do better more quickly."}, {"start": 175.06, "end": 182.72, "text": " So in detail, we would look at this tree that we have just built and go back to the original"}, {"start": 182.72, "end": 183.72, "text": " training set."}, {"start": 183.72, "end": 188.28, "text": " Notice that this is the original training set, not one generated through sampling or"}, {"start": 188.28, "end": 194.52, "text": " replacement, and we'll go through all 10 examples and look at what this learned decision tree"}, {"start": 194.52, "end": 197.08, "text": " predicts on all 10 examples."}, {"start": 197.08, "end": 205.08, "text": " So this fourth most column are their predictions and put a checkmark or cross next to each"}, {"start": 205.08, "end": 211.8, "text": " example depending on whether the tree's classification was correct or incorrect."}, {"start": 211.8, "end": 218.24, "text": " So what we'll do in the second time through this loop is we will sort of use sampling"}, {"start": 218.24, "end": 222.76000000000002, "text": " with replacement to generate another training set of 10 examples."}, {"start": 222.76000000000002, "end": 228.4, "text": " But every time we pick an example from these 10, we'll give a higher chance of picking"}, {"start": 228.4, "end": 233.0, "text": " from one of these three examples that we're still misclassifying."}, {"start": 233.0, "end": 239.38000000000002, "text": " And so this focuses the second decision trees attention via a process like deliberate practice"}, {"start": 239.38, "end": 244.84, "text": " on the examples that the algorithm is still not yet doing that well on."}, {"start": 244.84, "end": 252.51999999999998, "text": " And the boosting procedure will do this for a total of capital B times, where on each"}, {"start": 252.51999999999998, "end": 260.71999999999997, "text": " iteration, you'll look at what the ensemble of trees for trees one, two, up through B"}, {"start": 260.71999999999997, "end": 264.94, "text": " minus one are not yet doing that well on."}, {"start": 264.94, "end": 270.48, "text": " And when you're building tree number B, you will then have a higher probability of picking"}, {"start": 270.48, "end": 277.4, "text": " examples that the ensemble of the previously both trees is still not yet doing well on"}, {"start": 277.4, "end": 283.02, "text": " the mathematical details of exactly how much to increase the probability of picking this"}, {"start": 283.02, "end": 285.84, "text": " versus that example are quite complex."}, {"start": 285.84, "end": 291.24, "text": " But you don't have to worry about them in order to use boosted tree implementations"}, {"start": 291.24, "end": 297.96000000000004, "text": " and of different ways of implementing boosting, the most widely used one today is XGBoost,"}, {"start": 297.96000000000004, "end": 303.64, "text": " which stands for extreme gradient boosting, which is an open source implementation of"}, {"start": 303.64, "end": 307.24, "text": " booster trees that is very fast and efficient."}, {"start": 307.24, "end": 311.92, "text": " XGBoost also has a good choice of the default splitting criteria and criteria for when to"}, {"start": 311.92, "end": 313.48, "text": " stop splitting."}, {"start": 313.48, "end": 319.32, "text": " And one of the innovations in XGBoost is that it also has built in regularization to prevent"}, {"start": 319.32, "end": 325.24, "text": " overfitting and in machine learning competitions, such as there's a widely used competition"}, {"start": 325.24, "end": 330.44, "text": " site called Kaggle, XGBoost is often a highly competitive algorithm."}, {"start": 330.44, "end": 336.03999999999996, "text": " In fact, XGBoost and deep learning algorithms seem to be the two types of algorithms that"}, {"start": 336.03999999999996, "end": 337.71999999999997, "text": " win a lot of these competitions."}, {"start": 337.71999999999997, "end": 343.96, "text": " Oh, and one technical note, rather than doing something with replacement, XGBoost actually"}, {"start": 343.96, "end": 346.88, "text": " assigns different weights to different training samples."}, {"start": 346.88, "end": 351.92, "text": " So it doesn't actually need to generate a lot of randomly chosen training sets."}, {"start": 351.92, "end": 357.04, "text": " And this makes it even a little bit more efficient than using a sampling replacement procedure."}, {"start": 357.04, "end": 362.2, "text": " But the intuition that you saw in the previous slide is still correct in terms of how XGBoost"}, {"start": 362.2, "end": 365.2, "text": " is choosing examples to focus on."}, {"start": 365.2, "end": 371.68, "text": " The details of XGBoost are quite complex to implement, which is why many practitioners"}, {"start": 371.68, "end": 377.56, "text": " will use the open source libraries that implement XGBoost."}, {"start": 377.56, "end": 381.8, "text": " This is all you need to do in order to use XGBoost."}, {"start": 381.8, "end": 390.92, "text": " You would import the XGBoost library as follows and initialize a model as a XGBoost classifier"}, {"start": 390.92, "end": 392.2, "text": " for the model."}, {"start": 392.2, "end": 397.4, "text": " And then finally, this allows you to make predictions using this boosted decision trees"}, {"start": 397.4, "end": 398.84000000000003, "text": " algorithm."}, {"start": 398.84, "end": 402.79999999999995, "text": " I hope that you find this algorithm useful for many applications that you may build in"}, {"start": 402.79999999999995, "end": 403.79999999999995, "text": " the future."}, {"start": 403.79999999999995, "end": 410.71999999999997, "text": " Or alternatively, if you want to use XGBoost for regression rather than for classification,"}, {"start": 410.71999999999997, "end": 417.67999999999995, "text": " then this line here just becomes XGBregressor and the rest of the code works similarly."}, {"start": 417.67999999999995, "end": 420.71999999999997, "text": " So that's it for the XGBoost algorithm."}, {"start": 420.71999999999997, "end": 425.58, "text": " We have just one last video for this week and for this course where we'll wrap up and"}, {"start": 425.58, "end": 431.15999999999997, "text": " also talk about when should you use a decision tree versus maybe use a neural network."}, {"start": 431.16, "end": 458.16, "text": " Let's go on to the last and final video of this week."}]