Evolution of XGBoost Now, let's start with XGBoost and how XGBoost was developed. This is a very important slide in the sense that it puts together all the steps of why we need to go beyond decision trees, why we need to go beyond bagging, or even random forests. We will see that, in general, as we go from left to right, the performance of the model is going to become better. Again, in general, no, it's not always the case, but in many, many applications, that's the case. Okay, so let me actually remind you of this graph. We're going to base all of our conversation on this graph. So, this is our test error set, and I want you to think about a cross-validation error. On the vertical axis, we have cross-validation error, and on the horizontal axis, we have model complexity. As we go from left to right, the model is going to become more complex. Right now, we are focusing on decision trees. So, what do we mean by model complexity? Let's assume we're looking at the depth of a tree. So here, this is the simplest tree out there. It's just a trunk. Basically, it doesn't have any branches; it's the smallest tree with depth one. Now, this might be the most complex, very bushy tree. Right, so this is our setup. Let's start with decision trees. So, how do we do in decision trees? We say that, okay, there are many good properties that decision trees have—they're simple, they're explainable, and we like these trees. But the problem is that they are usually, especially if you make them a little bit bushy, not very performant. The reason for this is that we say, okay, let's start from a very bushy tree, and we are here in decision trees. So, I'm starting from a very bushy tree, and when the tree is very large, we know that the bias is going to be small because, on average, we're going to hit the target. But the variance is going to be large. The model variance is going to be large. So, combined together, this will cause the performance in the cross-validation set or the test set to be bad. We know that the tree is overfitting, etc. How do we fix that? If it is a single decision tree, we say, okay, I started with a very bushy tree and then prune it back using methods like cost complexity pruning. Hopefully, we can come up with the right balance of bias and variance in the model, and we can get a decent level of complexity for the model in a single decision tree. Okay, the point is that even though we use cost complexity pruning and a greedy approach, the performance of the model is not necessarily good. So, the point is, how can we make this performance even better? That's why the idea of ensembling these methods together comes into play. Why not take advantage of the wisdom of the crowd? Let's combine a bunch of these decision trees and make one using bootstrap aggregation, and see if it can perform better. The idea is that, okay, still go ahead and start from a very bushy tree. Now, instead of pruning it back, let's combine a bunch of them together, right? And the hope is that when you're combining a bunch of them, the model variance is going to reduce. Let me use the right color—the model variance, for any level of complexity, should reduce when you're bagging. This is a statistical property: when you're combining multiple models, the variance of the estimate is going to decrease. So, hopefully, if you combine these two, now again, you should get better performance, right? So that's the idea of bagging. Usually, the performance of bagging is better than a single decision tree, so this is our number two. Now, then we decided to move on with random forest because the main question was, can we do even better? And by doing even better, is there a way we can focus on the model variance even more? Is there any way we can reduce the model variance even further down? Right, so maybe make it something like this. The answer is yes. How do we do that? So this is very subtle; I want you to pay attention. This is our number three: you're looking at random forest. In a simple decision tree, when we're doing bagging and putting all these bootstrap trees together, let's say I have an original tree—keep it very simple—and I want to generate, I don't know, thousands of these trees. Okay, if I'm doing bagging and imagine there are, I don't know, three simple features: balance, income, and age. I have balance, income, and age, and I want to generate thousands of these trees and then combine the output together, right? So if balance is the most important feature, imagine balance is super important for this problem, and no matter what you do, the first split is always going to be balance—always balance. So this means that when I'm creating the trees, almost all of those trees are going to pick balance as the first split because that was the most important one. These trees, these thousands of trees, when I'm doing bagging, are going to be correlated with each other. The idea of random forest is: how can we decorrelate these trees? So this is the key term: decorrelate decision trees in random forest. The idea is very neat, and the fact is that at each split, we're picking features... you know, at each split...You have to decide among these three features, let's pick one. Right, random forests say let's pick a sub-sample of these features, not necessarily all of them. If I have M features, let's pick the square root of M, or let's pick log(M) of these features. Right, so let's say if I have 10 features, at each split, I'm going to pick four of them. At each split, I'm going to randomly select three of them. So, this means that this mechanism allows a tree that starts with age instead of balance. Remember, if balance was the dominant one, we said that no matter what you do, every single tree is going to start with the balance. But we want to avoid this. We want to make sure that we come up with different trees with different splits, with different features at each split, which is not dominated by the most important feature. And this is the beauty of random forests. Random forests do that. This process makes the trees more decorrelated, and the more decorrelated trees we have, the smaller model variance we get. So, that's how random forests are going to reduce the variance even further down compared to bagging. Right, so this is the idea of decision trees, bagging, and random forests. Then the boostings are completely different. Right, so let me go ahead and erase all this stuff. So, the way that boosting works is looking at this bias-variance trade-off from a completely different angle.So, the idea is that we don't need to start with the greedy algorithm. We don't need to go all the way down to a bushy tree or prune it back or ensemble it. We start with a very, very simple and small tree. Let's say we start with a trunk. Actually, in some of the boosting methods, you solve the trunk. Let's say we start from here, and if we start with a very small tree, let's say this is the model, the model variance is going to be super small, right? Because, again, the model is not complicated, and different samplings are not going to give you different answers. So, most probably, the model variance is going to be very small, but the problem is that, on average, this model is not capturing anything, so the model bias is going to be very high. Okay, so the idea of boosting is that it focuses on this bias part, right? Instead of focusing on the variance part, right? So, how does it fix it? It changes the structure of the model. You do it in a sequential way. It says that, okay, at each step, fix part of the data and then pass it to the output, and then whatever is not explained, pass it to the next tree. Right? And then the next tree—who knows, maybe the next tree is working on residuals; maybe some other features may show up, right? So, it's going to attack the bias term and hopefully reduce the bias for different levels of complexity, and the combination is going to come down. Right, so this is how boosting is handling this problem of test set error versus model complexity. Again, this is a very unique technique as well. All of these techniques are fascinating when you think about them. Right, and then the next one, which is even more interesting, is gradient boosting. So, the way that gradient boosting works is that it's going to say that, okay, now not all the observations in the data are equal. Why should they be equally weighted? Let's weight them differently, and what weighting mechanism is better than if you weight them based on their gradient, the inverse of their gradient? Right, if the gradient is high, give more attention to them. Sorry, relevant to their gradients, right? The higher the gradient means that that data set, that sample, has not been trained well, so we need to focus more on them. If the gradient of the cost function is small for an observation, it has been trained well, so we can pay less attention to that. So, these are the gradient-based models, and then the difference between gradient boosting and XGBoost is that XGBoost is simply an extension to gradient boosting and focuses on some parallel processing and some other features. But the idea is that these boosting mechanisms, because they are doing it sequentially, are not necessarily parallelizable. But people figured out how they can make it work in parallel. So, that's the idea of XGBoost: focusing on the performance and speed when it comes to boosting trees.