Tree Ensembles: Random Forests and Gradient Boosting

While individual decision trees, as we saw in the previous section, provide an interpretable way to model data by partitioning the feature space, they have limitations. They can be prone to overfitting, meaning they learn the training data too well, including its noise, and perform poorly on unseen data. They can also be unstable; small changes in the training data can lead to significantly different tree structures.

To address these issues, ensemble methods combine multiple decision trees to produce a more accurate model. Two prominent and widely used tree ensemble techniques are Random Forests and Gradient Boosting. Both use the fundamental tree structure but build and combine them in distinct ways.

Random Forests: Averaging Multiple Diverse Trees

Random Forests operate on the principle of creating a multitude of decision trees and aggregating their outputs. The core idea is that by averaging the predictions of many diverse, individually imperfect trees, the overall prediction becomes more accurate and less sensitive to the specifics of the training data. The "randomness" in Random Forests comes from two primary sources:

1. Data Randomness (Bagging): Each tree in the forest is trained on a different random subset of the original training data, selected with replacement. This process is called bootstrap aggregating, or bagging. It means some data points might appear multiple times in a subset, while others might not be included at all. This ensures that individual trees see slightly different versions of the data, leading to diversity.
2. Feature Randomness: When deciding on the best split at each node within a tree, instead of considering all available features, the algorithm considers only a random subset of the features. This further encourages diversity among the trees, preventing a few dominant features from controlling the structure of all trees.

Diagram illustrating the Random Forest process: Data is bootstrapped into multiple samples, each used to train a decision tree considering random feature subsets at splits. Predictions are aggregated.

To make a prediction for a new data point, a Random Forest passes the input through every tree in the forest. For classification, the final prediction is typically the class that receives the most votes from the individual trees. For regression, the final prediction is usually the average of the predictions from all trees.

This approach significantly reduces the variance compared to a single decision tree without substantially increasing the bias. Random Forests are known for their good performance with default settings, resistance to overfitting, and ability to estimate the importance of different features in making predictions. Structurally, a Random Forest is simply a collection (like a list or array) of tree objects.

Gradient Boosting: Sequential Error Correction

Gradient Boosting Machines (GBMs), particularly those using trees as base learners (Gradient Boosted Trees), take a different approach. Instead of building independent trees in parallel like Random Forests, Gradient Boosting builds trees sequentially. Each new tree attempts to correct the errors made by the ensemble of trees built so far.

The process generally works as follows:

1. Initialize: Start with a simple initial model. For regression, this could just be the mean of the target variable.
2. Iterate: Repeat for a specified number of trees:
   • Compute Residuals: Calculate the errors (residuals) made by the current ensemble model on the training data. The residual is the difference between the actual target value and the predicted value.
   • Fit New Tree: Train a new decision tree (often constrained in depth) to predict these residuals. This tree learns the patterns in the errors.
   • Update Ensemble: Add the newly trained tree to the ensemble. Its contribution is typically scaled by a small factor called the "learning rate" (eta, $\eta$). This scaling prevents overfitting by making smaller corrective steps. The prediction of the ensemble is updated: $F_{m}(x) = F_{m-1}(x) + \eta \cdot h_m(x)$ where $F_m(x)$ is the ensemble prediction after $m$ trees, $F_{m-1}(x)$ is the prediction from the previous ensemble, $h_m(x)$ is the prediction of the new tree (predicting residuals), and $\eta$ is the learning rate.

Diagram showing the sequential nature of Gradient Boosting. Each new tree is trained on the residuals (errors) of the current ensemble, gradually improving the overall prediction.

Gradient Boosting often results in models with very high predictive accuracy. However, it requires more careful tuning of hyperparameters (like the number of trees, tree depth, and learning rate) compared to Random Forests. If not properly controlled, Gradient Boosting models can also overfit. The sequential nature means training cannot be as easily parallelized as in Random Forests.

Data Structures and Performance

Both Random Forests and Gradient Boosting rely fundamentally on the decision tree data structure. The ensemble itself is typically stored as a collection (e.g., a list or array) of these tree structures. For Gradient Boosting, additional information like the learning rate or specific weights associated with each tree might also be stored.

• Training: Building the ensemble can be computationally intensive. Random Forests benefit from parallelization since trees can be built independently. Gradient Boosting is inherently sequential, limiting parallelization across trees (though parallelization within the construction of a single tree is possible).
• Prediction: Making predictions is usually fast. For a Random Forest, the input traverses all trees independently, and the results are aggregated. For Gradient Boosting, the input traverses trees sequentially (though the structure allows for efficient combined evaluation in many implementations). The complexity scales roughly linearly with the number of trees in the ensemble.

Understanding these ensemble methods highlights how combining simple tree structures in intelligent ways leads to powerful and widely used machine learning models. They effectively mitigate the weaknesses of individual decision trees, providing improved accuracy and robustness for a wide range of classification and regression tasks.