40
$\begingroup$

I wasn't clear on couple of concepts:

  1. XGBoost converts weak learners to strong learners. What's the advantage of doing this ? Combining many weak learners instead of just using a single tree ?

  2. Random Forest uses various sample from tree to create a tree. What's the advantage of this method instead of just using a singular tree?

$\endgroup$

4 Answers 4

52
$\begingroup$

It's easier to start with your second question and then go to the first.

Bagging

Random Forest is a bagging algorithm. It reduces variance.

Say that you have very unreliable models, such as Decision Trees. (Why unreliable? Because if you change your data a little bit, the decision tree created can be very different.) In such a case, you can build a robust model (reduce variance) through bagging -- bagging is when you create different models by resampling your data to make the resulting model more robust.

Random forest is what we call to bagging applied to decision trees, but it's no different than other bagging algorithm.

Why would you want to do this? It depends on the problem. But usually, it is highly desirable for the model to be stable.

Boosting

Boosting reduces variance, and also reduces bias. It reduces variance because you are using multiple models (bagging). It reduces bias by training the subsequent model by telling him what errors the previous models made (the boosting part).

There are two main algorithms:

  • Adaboost: this is the original algorithm; you tell subsequent models to punish more heavily observations mistaken by the previous models
  • Gradient boosting: you train each subsequent model using the residuals (the difference between the predicted and true values)

In these ensembles, your base learner must be weak. If it overfits the data, there won't be any residuals or errors for the subsequent models to build upon. Why are these good models? Well, most competitions in websites like Kaggle have been won using gradient boosting trees. Data science is an empirical science, "because it works" is good enough. Anyhow, do notice that boosting models can overfit (albeit empirically it's not very common).

Another reason why gradient boosting, in particular, is also pretty cool: because it makes it very easy to use different loss functions, even when the derivative is not convex. For instance, when using probabilistic forecast, you can use stuff such as the pinball function as your loss function; something which is much harder with neural networks (because the derivative is always constant).

[Interesting historical note: Boosting was originally a theoretical invention motivated by the question "can we build a stronger model using weaker models"]


Notice: People sometimes confuse random forest and gradient boosting trees, just because both use decision trees, but they are two very different families of ensembles.

$\endgroup$
3
  • 2
    $\begingroup$ Boosting reduces bias by iteratively modeling the residual and the variance by taking a weighted average; cf. § 5.5 Bias, Variance, and Stability, pp. 118, Boosting: Foundations and Algorithms, Robert E. Schapire, Yoav Freund. $\endgroup$
    – Emre
    Nov 24, 2017 at 8:05
  • $\begingroup$ @Emre, you're of course correct. Somebody edited my post and changed reduce by increase. I have reverted it. $\endgroup$ Nov 24, 2017 at 13:27
  • $\begingroup$ Random Forests aren't precisely bagging, in random forests (as opposed to bagging) you also select a subset of features (not just subset of examples). $\endgroup$
    – sitnarf
    Jan 14, 2020 at 12:30
10
$\begingroup$

When you build a tree, you need to define some criteria for splitting nodes. These include metrics like Information Gain and Gini Index. Those are heuristic approaches, they are not guaranteed to give the best possible split.

Weight in the fact some attributes are less relevant and/or more noisy, and many other problems that happen in real data. In short, you cannot build a perfect tree in a decent computational time (you could of course build all possible trees and test the best, but then you'd have to wait some years for training even in a medium-sized dataset).

Since we cannot have the best tree, we have approximations. One approximation is to build many trees (using different data partitions or attribute partitions), since we expect most trees to be somewhat correct, and consider their classifications in a voting system; this should deal with most noise, the vertical partition can deal with irrelevant attributes, the heuristic has less importance, and maybe other advantages.

$\endgroup$
2
$\begingroup$

I would add a small addition to the good answers. The main problem is overfitting. As soon as you have more than one parameter and also add non-linear functions, all the algorithms start to overfit. They see something in the data that does not exist. Like when it is dark or the fog is strong people tend to see things in the darkness/fog that do not exist. Almost all the computational algorithms do more overfitting than humans do. Even linear regressions start to show strange coefficients when the variables are highly correlated. If there was no overfitting then usual decision trees, on which those algorithms are based on, would have been better than Random Forest or XGBoost.

And there is no exact science why overfitting occurs and why some algorithms are better than the others. In theory ARIMA models are very sound, but practice shows that using exponential smoothing techniques is better and ARIMA cannot even differentiate variables that behave according to ARIMA but with different parameters.

Some neural networks and especially convolutional neural networks appear to have low overfitting. At the same time the original idea of fully connected neural networks fails with high number of neurons because of overfitting.

The main possibilities to fight overfitting are:

  1. random sampling
  2. averaging across multiple models
  3. randomizing the model (random dropping of neurons while training neural networks)

If I understand the algorithms correctly both Random Forest and XGBoost do random sampling and average across multiple models and thus manage to reduce overfitting.

In ImageNet image recognition competition the best model for 2016 (Shao et al) was a combination of several really good models. Some of them won the competition in previous years. This model had a 20% less error than any of the models it was based on. This is how averaging across multiple models could be strong in fighting with overfitting.

$\endgroup$
0
$\begingroup$

First Question: XGBoost converts weak learners to strong learners. What's the advantage of doing this? Combining many weak learners instead of just using a single tree?

Just to get the vocabulary straight: XGBoost is a library for different coding languages. It uses the Gradient Boosting algorithm. Also, it is not correct that Gradient Boosting uses decision trees. It can additionally use other Machine Learning algorithms such as regressions.

What is the Gradient Boosting algorithm?

Gradient boosting, in turn, is a subset of many, different boosting algorithms. The basic idea behind it is that the next model should be built in such a way that it further minimizes the loss function of the ensemble.

In the simplest cases, the loss function simply describes the difference between the model's prediction and the actual value. Suppose we train an AI to predict a house price. The loss function could then simply be the mean squared error between the actual price of the house and the predicted price of the house. Ideally, the function approaches zero over time and our model can predict correct prices.

New models are added as long as prediction and reality no longer differ, i.e. the loss function has reached the minimum. Each new model tries to predict the error of the previous model.

Let's go back to our example with house prices. Let's assume a property has a living area of 100m², four rooms, and a garage and costs 200,000€. The gradient boosting process would then look like this:

Training a regression to predict the purchase price with the features of living space, the number of rooms, and the garage. This model predicts a purchase price of 170,000 € instead of the actual 200,000 €, so the error is 30,000 €.

Training another regression that predicts the error of the previous model with the features of living space, number of rooms, and garage. This model predicts a deviation of 23,000 € instead of the actual 30,000 €. The remaining error is therefore 7,000 €.

These steps are repeated until the remaining error is as small as possible or even zero.

Second Question: Random Forest uses various samples from trees to create a tree. What's the advantage of this method instead of just using a singular tree?

The Random Forest consists of a large number of these decision trees, which work together as a so-called ensemble. Each individual decision tree makes a prediction, such as a classification result, and the forest uses the result supported by most of the decision trees as the prediction of the entire ensemble. Why are multiple decision trees so much better than a single one?

The secret behind the Random Forest is the so-called principle of the wisdom of crowds. The basic idea is that the decision of many is always better than the decision of a single individual or a single decision tree. This concept was first recognized in the estimation of a continuous set.

In 1906, an ox was shown to a total of 800 people at a fair. They were asked to estimate how heavy this ox was before it was actually weighed. It turned out that the median of the 800 estimates was only about 1% away from the actual weight of the ox. No single estimate had come that close to being correct. So the crowd as a whole had estimated better than any other single person.

This can be applied in exactly the same way to the Random Forest. A large number of decision trees and their aggregated prediction will always outperform a single decision tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.