Random Forest › Formula

The mathematical foundation of Random Forest involves understanding how individual decision trees are combined to form the ensemble. Let's break this down step by step, starting with the basic structure and progressing to the complete ensemble formulation.

Each tree in the Random Forest is a decision tree that makes predictions by recursively partitioning the feature space. We denote the $b$-th tree in the ensemble as $T_b$, where the capital $T$ represents the tree as a function or mapping from input features to a prediction. For a given input $\mathbf{x}$, this tree produces a prediction $\hat{y}_b = T_b(\mathbf{x})$. Here, $T_b(\mathbf{x})$ means we apply the $b$-th decision tree to the input $\mathbf{x}$ to obtain its predicted value.

The prediction from a single tree can be written as:

$$\hat{y}_b = \sum_{i=1}^{n} w_i(\mathbf{x}) \cdot y_i$$

where:

• $\hat{y}_b$: Prediction from the $b$-th tree in the ensemble
• $n$: Total number of training observations in the dataset
• $w_i(\mathbf{x})$: Weight assigned to training observation $i$ when making a prediction for input $\mathbf{x}$
• $y_i$: Target value (actual outcome) of training observation $i$
• $\mathbf{x}$: Input feature vector for which we are making a prediction

The weights $w_i(\mathbf{x})$ are determined by which leaf node the input $\mathbf{x}$ falls into. If $\mathbf{x}$ falls into the same leaf as training observation $i$, then $w_i(\mathbf{x}) = \frac{1}{n_{\text{leaf}}}$ where $n_{\text{leaf}}$ is the number of training observations in that leaf. Otherwise, $w_i(\mathbf{x}) = 0$. The weights always sum to 1: $\sum_{i=1}^{n} w_i(\mathbf{x}) = 1$.

Each tree is trained on a bootstrap sample of the original training data. A bootstrap sample is created by randomly sampling $n$ observations with replacement from the original $n$ observations. This means some observations may appear multiple times in a bootstrap sample, while others may not appear at all.

Mathematically, for tree $b$, we create a bootstrap sample $\mathcal{D}_b$ by sampling with replacement from the original dataset $\mathcal{D} = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)\}$.

The probability that a specific observation is included in a bootstrap sample is:

$$P(\text{observation } i \text{ in bootstrap sample}) = 1 - \left(1 - \frac{1}{n}\right)^n$$

where:

• $n$: Total number of observations in the original dataset
• $P(\text{observation } i \text{ in bootstrap sample})$: Probability that observation $i$ appears at least once in a bootstrap sample of size $n$

As $n$ becomes large, this probability approaches $1 - e^{-1} \approx 0.632$, meaning approximately 63.2% of the original observations appear in each bootstrap sample.

At each split in each tree, only a random subset of features is considered for the split. If the original dataset has $p$ features, then at each split, we randomly select $m$ features where typically $m = \sqrt{p}$ for classification or $m = p/3$ for regression.

This random feature selection introduces additional diversity among the trees and helps prevent overfitting to specific features.

The final Random Forest prediction combines the predictions from all $B$ trees in the ensemble. For regression problems, the prediction is the average of all tree predictions:

$$\hat{y} = \frac{1}{B} \sum_{b=1}^{B} \hat{y}_b = \frac{1}{B} \sum_{b=1}^{B} T_b(\mathbf{x})$$

where:

• $\hat{y}$: Final ensemble prediction for input $\mathbf{x}$
• $B$: Total number of trees in the Random Forest
• $\hat{y}_b$: Prediction from the $b$-th tree
• $T_b(\mathbf{x})$: Function representing the $b$-th tree applied to input $\mathbf{x}$

For classification problems, the prediction is made by taking a majority vote among all the trees in the forest. This means that each tree "votes" for a class label, and the class that receives the most votes is chosen as the final prediction.

In mathematical terms, this is called taking the "mode" of the predicted class labels, where the mode is simply the value that appears most frequently in a set. If there is a tie, some implementations may break the tie randomly or by another rule.

$$\hat{y} = \text{mode}\{T_1(\mathbf{x}), T_2(\mathbf{x}), \ldots, T_B(\mathbf{x})\}$$

Or, if we consider the probability of each class:

$$\hat{p}_k = \frac{1}{B} \sum_{b=1}^{B} P_b(\text{class } k | \mathbf{x})$$

where:

• $\hat{p}_k$: Estimated probability that input $\mathbf{x}$ belongs to class $k$
• $P_b(\text{class } k | \mathbf{x})$: Probability that tree $b$ assigns to class $k$ for input $\mathbf{x}$

Putting it all together, the Random Forest algorithm can be written as:

Input: Training data $\mathcal{D} = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)\}$, number of trees $B$, number of features to consider at each split $m$

For $b = 1$ to $B$:

1. Create bootstrap sample $\mathcal{D}_b$ by sampling $n$ observations with replacement from $\mathcal{D}$
2. Train decision tree $T_b$ on $\mathcal{D}_b$ using the following splitting rule:
   • At each split, randomly select $m$ features from the $p$ available features
   • Choose the best split among the $m$ selected features
   • Continue until stopping criteria are met (e.g., minimum samples per leaf, maximum depth)

Output: Ensemble of trees $\{T_1, T_2, \ldots, T_B\}$

Prediction: For new input $\mathbf{x}$:

• Regression: $\hat{y} = \frac{1}{B} \sum_{b=1}^{B} T_b(\mathbf{x})$
• Classification: $\hat{y} = \text{mode}\{T_1(\mathbf{x}), T_2(\mathbf{x}), \ldots, T_B(\mathbf{x})\}$

Random Forests possess several key mathematical properties that help explain their effectiveness. One of the most important is the bias-variance decomposition. When we use a single decision tree, the model tends to have low bias but high variance, meaning it can fit the training data closely but may not generalize well to new data. By averaging the predictions of many trees, Random Forests reduce the variance component of the error while keeping the bias relatively low. The overall error of the ensemble can be expressed as:

$$\text{Error} = \text{Bias}^2 + \text{Variance} + \text{Noise}$$

This formula shows that the total prediction error consists of three parts: the squared bias (how far the average model prediction is from the true values), the variance (how much the predictions fluctuate for different training sets), and the irreducible noise inherent in the data. By averaging over multiple trees, Random Forests specifically target and reduce the variance term, leading to more stable and reliable predictions.