Random Forest

A random forest is Bagging applied to Decision trees with extra feature-subsampling at each split.

Why subsample features if bagging already randomizes data?

Pure bagging can leave one very informative feature dominating every tree, so the bootstrapped trees stay highly correlated. Random feature subsets at each split decorrelate them further.

Algorithm

1. For $b=1\text{ to }B$ bootstrap-sample datasets $D_1,\dots ,D_B$ of size $N$

2. Grow a random-forest tree $T_b$ by recursively repeating the following steps for each terminal node of the tree until the minimum node size is reached

   • look at a random subsample of $m\ll d$ features and pick the best among those
     • Typical choice: $m=\sqrt{d}$
   • Split the node into two daughter nodes

3. Generate the ensemble of trees $\{T_b{\}}_1^B$.

4. Aggregate the individual results:

   • Regression (average across all trees): ${\hat{f}}_{rf}^B(x)=\frac{1}{B}{\sum }_{b=1}^B{T}_b(x)$
   • Classification (majority vote of the class predictions): ${\hat{C}}_{rf}^B(x)=\text{majority vote of }\{{\hat{C}}_b{\}}_{b=1}^B$

Standard decision tree: at each split, look at all $d$ features and pick the best.