Is random forest a boosting algorithm?

Question

Short definition of boosting:

Can a set of weak learners create a single strong learner? A weak learner is defined to be a classifier which is only slightly correlated with the true classification (it can label examples better than random guessing).

Short definition of Random Forest:

Random Forests grows many classification trees. To classify a new object from an input vector, put the input vector down each of the trees in the forest. Each tree gives a classification, and we say the tree "votes" for that class. The forest chooses the classification having the most votes (over all the trees in the forest).

Another short definition of Random Forest:

A random forest is a meta estimator that fits a number of decision tree classifiers on various sub-samples of the dataset and use averaging to improve the predictive accuracy and control over-fitting.

As I understand Random Forest is an boosting algorithm which uses trees as its weak classifiers. I know that it also uses other techniques and improves upon them. Somebody corrected me that Random Forest is not a boosting algorithm?

Can someone elaborate upon this, why Random Forest is not a boosting algorithm?

Answer 1

Random Forest is a bagging algorithm rather than a boosting algorithm. They are two opposite way to achieve a low error.

We know that error can be composited from bias and variance. A too complex model has low bias but large variance, while a too simple model has low variance but large bias, both leading a high error but two different reasons. As a result, two different ways to solve the problem come into people's mind (maybe Breiman and others), variance reduction for a complex model, or bias reduction for a simple model, which refers to random forest and boosting.

Random forest reduces variance of a large number of "complex" models with low bias. We can see the composition elements are not "weak" models but too complex models. If you read about the algorithm, the underlying trees are planted "somewhat" as large as "possible". The underlying trees are independent parallel models. And additional random variable selection is introduced into them to make them even more independent, which makes it perform better than ordinary bagging and entitle the name "random".

While boosting reduces bias of a large number of "small" models with low variance. They are "weak" models as you quoted. The underlying elements are somehow like a "chain" or "nested" iterative model about the bias of each level. So they are not independent parallel models but each model is built based on all the former small models by weighting. That is so-called "boosting" from one by one.

Breiman's papers and books discuss about trees, random forest and boosting quite a lot. It helps you to understand the principle behind the algorithm.

Answer 2

A random forest is not considered a boosting type of algorithm.

As explained in your boosting link:

...most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are typically weighted in some way that is usually related to the weak learners' accuracy. After a weak learner is added, the data is reweighted...

An example of this iterative process is adaboost, whereby weaker results are boosted or reweighted over many iterations to have the learner focus more on areas it got wrong, and less on those observations that were correct.

A random forest, in contrast, is an ensemble bagging or averaging method that aims to reduce the variance of individual trees by randomly selecting (and thus de-correlating) many trees from the dataset, and averaging them.

Answer 3

It is an extension of bagging. The procedure is as follows, you take a bootstrap sample of your data and then use this to grow a classification or regression tree (CART). This is done a predefined number of times and the prediction is then the aggregation of the individual trees predictions, it could be a majority vote (for classification) or an average (for regression). This approach is called bagging (Breiman 1994). Furthermore the candidate variable for each split of each tree is taken from a random sample of all the available independent variables. This introduces even more variability and makes the trees more diverse. This is called the random subspace method (Ho, 1998). As mentioned, this produces trees which are very diverse which translates into trees which are highly independent of each other. Because of the Jensen's inequality we know that the average of the errors of these trees predictions will be smaller or equal to the error of the average tree grown from that data set. Another way to look at it is to look at the Mean Squared Error and notice how it can be decomposed in bias and variance parts (this is related to an issue in supervised learning called the bias-variance tradeoff). Random forest achieves better accuracy by reducing variance through the averaging of the prediction of orthogonal trees. It should be noted that it inherits the bias of its trees, which is quite a discussed problem, check for example this question.

Answer 4

I believe you are confusing boosting in particular with ensemble methods in general, of which there are many. Your "definition" of boosting is not the full definition, which is elaborated on in Pat's answer. If you would like to learn more about ensemble methods, I recommend you pick up the following book:

John Elder & Giovanni Seni. Ensemble Methods in Data Mining: Improving Accuracy Through Combining Predictions. (2010)

Answer 5

Random forest is a bagging technique and not a boosting technique. In boosting as the name suggests, one is learning from other which in turn boosts the learning.

The trees in random forests are run in parallel. There is no interaction between these trees while building the trees. Once all the trees are built, then a voting or average is taken across all the trees' prediction depending on whether the problem is a classification or regression problem.

The trees in boosting algorithms like GBM-Gradient Boosting machine are trained sequentially.

Let's say the first tree got trained and it did some predictions on the training data. Not all of these predictions would be correct. Let's say out of a total of 100 predictions, the first tree made mistake for 10 observations. Now these 10 observations would be given more weightage when building the second tree. Notice that the learning of the second tree got boosted from the learning of the first tree. Hence, the term boosting. This way, each of the trees are built sequentially over the learnings from the past trees.

Answer 6

I'd like to point out that Random Forest is not just a bagging technique.
It's a bagging + random subset of the features.

Definition on Wikipedia suggests that

...The above procedure describes the original bagging algorithm for trees. Random forests differ in only one way from this general scheme: they use a modified tree learning algorithm that selects, at each candidate split in the learning process, a random subset of the features. This process is sometimes called "feature bagging".

So bagged tree is bagging.
And random forest is baggging + "feature bagging".

Also recommend to check the following link for detail info by Arvind Shukla. https://www.linkedin.com/pulse/random-forest-bagging-tree-arvind-shukla