22
$\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$
32
$\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$
  • 1
    $\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 '17 at 8:05
  • $\begingroup$ @Emre, you're of course correct. Somebody edited my post and changed reduce by increase. I have reverted it. $\endgroup$ – Ricardo Cruz Nov 24 '17 at 13:27
7
$\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$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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