Random Forest

Definition

Random forest constructs a multitude of de-correlated decision trees at training time and make a prediction through Bagging.

Algorithm

1. For $b=1,\dots ,B$:
   1. Draw a size $n$ bootstrap sample $\{Z^{\ast b}|b=1,\dots ,B\}$ from training data.
   2. Grow a random-forest tree $T_b$ to the bootstrapped data, by recursively repeating the following steps for each terminal node of the tree, until the minimum node size $\text{nmin}$ is reached.
      1. Select $m<<p$ variables at random.
      2. Pick the best variable and split point among the selected variables.
      3. Split the node into two children nodes.
2. Output the ensemble of trees $\{T_b{\}}_1^B$ to make a prediction at a new point $x$
   • Regression: ${\hat{f}}_{\text{rf}}^B(x)=\frac{1}{B}\sum _{b=1}^B{T}_b(x)$
   • Classification: $C_{\text{rf}}^B(x)=\underset{1\le b\le B}{\mathrm{argmax}}\#\{b|{\hat{C}}_b(x)=b\}$ where ${\hat{C}}_b(x)$ is the class prediction of the $b$th random-forest tree.

Facts

Selection of hyperparameter $m$ is recommended as

• For classification: $\min (\lfloor \sqrt{p}\rfloor ,1)$
• For regression: $\min (\lfloor \frac{p}{3}\rfloor ,1)$