# Random Forest and Decision Tree Algorithm

A random forest is a collection of decision trees following the bagging concept. When we move from one decision tree to the next decision tree then how does the information learned by last decision tree move forward to the next?

Because, as per my understanding, there is nothing like a trained model which gets created for every decision tree and then loaded before the next decision tree starts learning from the misclassified error.

So how does it work?

• "When we move from one decision tree to the next decision tree". This suggests an linear process. We've built parallel implementations where we worked on one tree per CPU core; this works perfectly fine unless you use a separate random number generator per CPU core in training, all of which share the same seed. In that case you can end up with lots of identical trees. – MSalters Nov 21 '18 at 14:25

No information is passed between trees. In a random forest, all of the trees are identically distributed, because trees are grown using the same randomization strategy for all trees. First, take a bootstrap sample of the data, and then grow the tree using splits from a randomly-chosen subset of features. This happens for each tree individually without attention to any other trees in the ensemble. However, the trees are correlated purely by virtue of each tree being trained on a sample from a common pool of training data; multiple samples from the same data set will tend to be similar, so the trees will encode some of that similarity.

You might find it helpful to read an introduction to random forests from a high-quality text. One is "Random Forests" by Leo Breiman. There's also a chapter in Elements of Statistical Learning by Hastie et al.

It's possible that you've confused random forests with boosting methods such as AdaBoost or gradient-boosted trees. Boosting methods are not the same, because they use information about misfit from previous boosting rounds to inform the next boosting round. See: Is random forest a boosting algorithm?

The random forests is a collection of multiple decision trees which are trained independently of one another. So there is no notion of sequentially dependent training (which is the case in boosting algorithms). As a result of this, as mentioned in another answer, it is possible to do parallel training of the trees.

You might like to know where the "random" in random forest comes from: there are two ways with which randomness is injected into the process of learning the trees. First is the random selection of data points used for training each of the trees, and second is the random selection of features used in building each tree. As a single decision tree usually tends to overfit on the data, the injection of randomness in this way results in having a bunch of trees where each one of them have a good accuracy (and possibly overfit) on a different subset of the available training data. Therefore, when we take the average of the predictions made by all the trees, we would observe a reduction in overfitting (compared to the case of training one single decision tree on all the available data).

To better understand this, here is a rough sketch of the training process assuming all the data points are stored in a set denoted by $$M$$ and the number of trees in the forest is $$N$$:

1. $$i = 0$$
2. Take a boostrap sample of $$M$$ (i.e. sampling with replacement and with the same size as $$M$$) which is denoted by $$S_i$$.
3. Train $$i$$-th tree, denoted as $$T_i$$, using $$S_i$$ as input data.
• the training process is the same as training a decision tree except with the difference that at each node in the tree only a random selection of features is used for the split in that node.
1. $$i = i + 1$$
2. if $$i < N$$ go to step 2, otherwise all the trees have been trained, so random forest training is finished.

Note that I described the algorithm as a sequential algorithm, but since training of the trees is not dependent on each other, you can also do this in parallel. Now for prediction step, first make a prediction for every tree (i.e. $$T_1$$, $$T_2$$, ..., $$T_N$$) in the forest and then:

• If it is used for a regression task, take the average of predictions as the final prediction of the random forest.

• If it is used for a classification task, use soft voting strategy: take the average of the probabilities predicted by the trees for each class, then declare the class with the highest average probability as the final prediction of random forest.

Further, it is worth mentioning that it is possible to train the trees in a sequentially dependent manner and that's exactly what gradient boosted trees algorithm does, which is a totally different method from random forests.

Random forest is a bagging algorithm rather than a boosting algorithm.

Random forest constructs the tree independently using random sample of the data. A parallel implementation is possible.

You might like to check out gradient boosting where trees are built sequentially where new tree tries to correct the mistake previously made.

So how does it works ?

Random Forest is a collection of decision trees. The trees are constructed independently. Each tree is trained on subset of features and subset of a sample chosen with replacement.

When predicting, say for Classification, the input parameters are given to each tree in the forest and each tree "votes" on the classification, label with most votes wins.

Why to use Random Forest over simple Decision Tree? Bias/Variance trade off. Random Forest are built from much simpler trees when compared to a single decision tree. Generally Random forests provide a big reduction of error due to variance and small increase in error due to bias.

• If we are chosing different features for every Decision Tree, then how the learning by a set of features in previous Decision Tree improves while we send the missclassified values ahead as for the next Decision Tree there is totally a new set of features ? – Abhay Raj Singh Nov 20 '18 at 6:50
• @AbhayRajSingh - you do not "send the misclassified values ahead" in Random Forest. As Akavall says, "The trees are constructed independently" – Henry Nov 20 '18 at 10:16

Yes, as authors above said, the Random Forest algorithm is a bagging, not boosting algorithm.

Bagging can reduce the variance of the classificator, because the base algorithms, that are fitted on different samples and their errors are mutually compensated for in the voting. Bagging refers to averaging slightly different versions of the same model as a means to improve the predictive power. To apply bagging we simply construct B regression trees using B bootstrapped training sets, and average the resulting predictions

A common and quite successful application of bagging is the Random Forest

But when building these decision trees in random forest, each time a split in a tree is considered, a random sample of m predictors is chosen as split candidates from the full set of p predictors. The split is allowed to use only one of those m predictors.