We only discuss about ‘classification tree’ here, which is about using a tree-like predictive model to go from observations about an item to conclusions about item’s target value(wikipedia). To begin with, it is good to think of “20 Questions” game. The strategy of guesser is to ask the questions that narrow down the most of the options. The same intuition applies to ‘decision tree’. Searching for splits in decision tree is analogous to proposing the questions, but we have certain criterions for the search. Here we have a more concrete example using ‘information gain’ as the criterion(of course there are other metrics to choose from). This is based on the concept of information entropy, which is the measure of degree of chaos in the system. ‘Information gain’ captures the change in entropy after splitting.

In statistics, bootstrapping is any test or metric that relies on random sampling with replacement. This allows estimation of the sampling distribution of almost any statistic(wikipedia). Suppose that we are drawing balls of different colours from a bag once at a time. The selected ball is returned to the bag so that each selection has equal probability of drawing certain colour. More generally, for a sample X of size N, we draw N elements from it with replacement and form a new sample(bootstrap sample) of the same size. We can repeat this process and compute statistics of original distribution using a large number of bootstrap samples.

Let’s combine what we have just learnt together. Suppose that we have generated m bootstrap samples: X1,X2,…,Xm. We would like to train a decision tree classifier on each bootstrap sample and average all the individual classifiers to build our final classifier. This is called Bagging. However, though bagging is usually used with decision trees, it works with other methods as well. This technique improves stability and accuracy of algorithms —— it can be proved that mean squared error is reduced by factor of m. Plus, bagging reduces variance and prevents overfitting. More concretely, it decreases the error generated when training on different datasets. Intuitively, errors of models trained on different data are cancelled out with each other.