Decision Trees, Bagging, and Boosting

Part 1: The Decision Tree

At its core, a decision tree is an intuitive model that mimics human decision-making. It's essentially a flowchart of questions asked about your data, where each answer leads you down a different path until you reach a conclusion or classification. The models we've seen so far, like linear and logistic regression, work by finding an optimal set of parameters for a single, complex equation. Decision trees, in contrast, work by recursively partitioning the feature space into smaller, more manageable regions.

For a fantastic and gentle introduction to the structure and terminology of decision trees, the StatQuest video below is an excellent starting point.

How a Tree Learns: Recursive Splitting

A decision tree is built using a process called recursive binary splitting. It's a top-down, greedy approach.

• Top-down: It starts at the root node (with the entire dataset) and progressively splits the data into smaller subsets.
• Greedy: At each step, the algorithm chooses the best possible split at that moment, without looking ahead to see if a different split might lead to a better overall tree.

The "best" split is the one that results in the most homogeneous child nodes—that is, nodes that are as "pure" as possible in terms of their class composition. For instance, a perfectly pure node would contain data points from only one class.

To quantify this, we use an impurity measure. Two common measures are:

1. Gini Impurity: Measures the probability of incorrectly classifying a randomly chosen element in the dataset if it were randomly labeled according to the class distribution in the subset. A Gini score of 0 represents perfect purity (all elements belong to one class).
2. Entropy & Information Gain: Entropy is another measure of disorder or impurity, originating from information theory. A split is chosen based on which feature provides the highest Information Gain, which is the reduction in entropy achieved by the split.

While the math differs slightly, both methods achieve the same goal: finding the feature and the split point that best separate the classes. The following video provides a clear, step-by-step example of how Gini impurity is calculated to find the best split.

Overfitting and Pruning

A single decision tree, if left to grow indefinitely, is highly susceptible to overfitting. It can create a tree so deep and complex that it perfectly memorizes the training data, creating individual leaves for just a few or even single data points. Such a model will not generalize well to unseen data.

To combat this, we use pruning. Pruning is a technique to reduce the size and complexity of the tree. There are two main strategies:

1. Pre-pruning (Early Stopping): We stop the tree from growing once it meets certain criteria. Common hyperparameters for this include max_depth (the maximum depth of the tree) and min_samples_leaf (the minimum number of samples a leaf node must have).
2. Post-pruning: We first grow the full tree and then remove branches that provide little predictive power. A popular method is Cost Complexity Pruning (CCP), which uses a parameter (ccp_alpha in scikit-learn) to control the trade-off between tree complexity and fit.

For a deeper dive into these concepts, especially the mathematical details of the splitting criteria and pruning, the following article is an excellent resource.

Part 2: Ensemble Learning - Strength in Numbers

While pruning helps, a single decision tree is often considered a "weak learner." The solution is to use ensemble methods, which combine many weak learners to create a single, powerful model. This is the core idea behind Random Forest and Gradient Boosting.

The two main ensemble philosophies are Bagging and Boosting.

Part 3: Bagging and Random Forests

Bagging stands for Bootstrap Aggregating. It's a simple but powerful technique to reduce the variance of a high-variance model like a decision tree.

1. Bootstrap: We create many new datasets by sampling with replacement from our original training data. Each of these "bootstrap samples" is the same size as the original dataset, but some data points will be repeated, and others will be left out.
2. Aggregate: We train a separate decision tree on each bootstrap sample. To make a prediction for a new data point, we let all the trees "vote," and the majority class wins.

A Random Forest is a specific implementation of bagging that adds one more crucial twist to improve performance.

From Bagging to Random Forest

The problem with standard bagging is that if there is one very strong, dominant feature in the dataset, most of the trees will use that feature for their top split. This causes the trees to be highly correlated, and their predictions will be very similar. If the trees are similar, we lose the benefit of averaging, as they will tend to make the same mistakes.

Random Forest solves this by introducing feature randomness: at each split in a tree, the algorithm considers only a random subset of features from which to choose the best split.

This forces the trees to be different from one another, making them less correlated and improving the variance reduction from averaging. This decorrelation is the key to Random Forest's success.

The following StatQuest video explains this process beautifully.

Out-of-Bag (OOB) Error

A clever feature of Random Forests is that they can be validated without needing a separate validation set. Because each tree is trained on a bootstrap sample, on average about one-third of the original data points are left out of that sample. These are the out-of-bag (OOB) samples.

We can use these OOB samples to get an unbiased estimate of the model's performance. For each data point, we make a prediction using only the trees that did not see that data point during training. The overall error rate on these OOB predictions is the OOB error, which is a reliable estimate of the test error.

Part 4: Boosting and Gradient Boosting

Boosting is another ensemble technique, but it works sequentially. Instead of building independent trees, boosting builds a "chain" of trees, where each new tree is trained to correct the errors made by the previous ones.

The general idea is:

1. Train a simple decision tree on the data.
2. Identify the data points that the tree misclassified.
3. Increase the weight of these misclassified points, forcing the next tree to pay more attention to them.
4. Train a new tree on this re-weighted data.
5. Repeat this process for a specified number of trees. The final prediction is a weighted sum of all tree predictions.

Gradient Boosting is a more generalized and widely used form of boosting. Instead of re-weighting data points, it fits each new tree to the residuals (the errors) of the previous ensemble's predictions. In a regression context, the residual is simply (actual_value - predicted_value). In classification, the concept is similar but involves the gradient of the loss function. The intuition remains the same: each new model focuses on what the ensemble is currently getting wrong.

Unlike Random Forest, where adding more trees generally doesn't cause overfitting, Gradient Boosting can overfit if you add too many trees, as it will start to model the noise in the residuals. To control this, a key hyperparameter called the learning rate (or eta) is used. It shrinks the contribution of each new tree, forcing the model to learn more slowly and improving generalization.

Key Differences for Your Interview

Being able to compare and contrast Random Forest and Gradient Boosting is a common interview question. Here are the key points:

Conclusion

Today we've journeyed from the intuitive simplicity of a single decision tree to the collective power of ensemble methods. You now have the conceptual tools to explain these fundamental algorithms in an interview setting.

Key Takeaways:

• Decision Trees are non-linear models that create rules by recursively partitioning the feature space to increase class purity, but they are prone to overfitting.
• Pruning is used to control tree complexity and prevent overfitting.
• Random Forests (a form of bagging) build many independent, decorrelated trees and average their predictions. They are robust, easy to tune, and great at reducing variance. The key innovations are bootstrapping and random feature selection.
• Gradient Boosting builds trees sequentially, where each tree corrects the errors of the preceding ensemble. It is often more powerful than Random Forest but is more sensitive to hyperparameter tuning and can overfit.

In our next lesson, we will shift our focus from the models themselves to the data we feed into them. We'll begin our exploration of Feature Engineering and Preprocessing, starting with essential techniques like feature scaling, normalization, and transformations.