OOB Error Estimation

Recap: The Role of Bootstrapping

Remember how we trained our Random Forest? For each of the n_trees in our forest, we didn't use the entire training dataset. Instead, we used bootstrapping: creating a new dataset of the same size by sampling from the original data with replacement.

This sampling method is the key to OOB estimation. Because we sample with replacement, some data points from the original set will be selected multiple times for a given tree's training set, and more importantly, some will not be selected at all.

What are Out-of-Bag (OOB) Samples?

The data points that are not included in the bootstrap sample used to train a specific tree are called the out-of-bag (OOB) samples for that tree.

Statistically, it can be shown that for a large dataset, about two-thirds (≈63.2%) of the original data points will be in any given bootstrap sample, leaving about one-third (≈36.8%) as OOB samples.

This means that every tree in our forest has been trained on a slightly different subset of the data, and for each tree, there's a portion of the original data it has never seen. We can use this "unseen" data as a validation set to test the performance of that tree.

To get a clear visual intuition for this concept, please watch the following video.

The OOB Error Estimation Procedure

Since each tree has its own set of OOB samples, we can't just test the whole forest on one OOB set. Instead, the OOB score is calculated on a sample-by-sample basis for the entire training set. The process is as follows:

1. For each data point in the original training set, identify all the trees that did not use this data point in their training (i.e., the trees for which this point was OOB).
2. Pass that single data point through all of those identified trees to get their predictions.
3. Take a majority vote of these predictions to get a single, final OOB prediction for that data point.
4. Repeat this for all data points in the original training set.
5. The OOB score is the accuracy (or another metric) calculated by comparing these OOB predictions against the true labels. The OOB error is simply 1 - OOB score.

The following image provides a brilliant step-by-step walkthrough of this process.

To solidify your understanding of how this process serves as a validation mechanism, let's watch another short video.

Implementing OOB Error Estimation

Now, let's integrate this into the RandomForest class you've already built. We need to modify our fit method to keep track of OOB samples and calculate the final score.

Here is the high-level plan:

1. Modify fit: Inside the loop that builds each tree, we need to identify and store the indices of the OOB samples for that tree.
2. Store Predictions: We need a data structure to store the predictions for each sample, made only by the trees that held it out. A list of lists is a good choice, where oob_predictions[i] will hold all predictions for sample i.
3. Calculate Final Score: After all trees are trained, we'll iterate through our stored OOB predictions, determine the final OOB prediction for each sample via majority vote, and compute the overall accuracy.

Let's look at the code. You will need to update your fit method to include this logic.

# You will need your helper function from the previous lesson
from collections import Counter
import numpy as np

def most_common_label(y):
    counter = Counter(y)
    if not counter:
        # Handle cases where there are no predictions (should be rare)
        return None
    return counter.most_common(1)[0][0]

class RandomForest:
    # Your __init__, _create_bootstrap, predict, etc. methods remain here
    # ...

    def fit(self, X, y):
        """
        Trains the Random Forest and calculates the OOB score.
        """
        self.trees = []
        n_samples = X.shape[0]
        
        # A list of lists to store OOB predictions for each sample.
        # oob_predictions[i] will be a list of votes for sample i.
        oob_predictions = [[] for _ in range(n_samples)]

        for _ in range(self.n_trees):
            # 1. Create a bootstrap sample and get OOB indices
            bootstrap_indices = np.random.choice(
                n_samples, size=n_samples, replace=True
            )
            # A set is much faster for checking membership (`in`)
            bootstrap_indices_set = set(bootstrap_indices)
            oob_indices = [i for i in range(n_samples) if i not in bootstrap_indices_set]

            X_bootstrap, y_bootstrap = X[bootstrap_indices], y[bootstrap_indices]

            # 2. Train a tree on the bootstrap sample
            tree = DecisionTree(
                min_samples_split=self.min_samples_split,
                max_depth=self.max_depth,
                n_features=self.n_features
            )
            tree.fit(X_bootstrap, y_bootstrap)
            self.trees.append(tree)

            # 3. Use the trained tree to predict its OOB samples
            if len(oob_indices) > 0:
                X_oob = X[oob_indices]
                oob_preds_for_tree = tree.predict(X_oob)

                # 4. Store these predictions
                for i, pred in zip(oob_indices, oob_preds_for_tree):
                    oob_predictions[i].append(pred)

        # 5. Calculate the final OOB score after all trees are trained
        oob_correct_predictions = 0
        total_oob_samples_evaluated = 0
        for i in range(n_samples):
            # Only evaluate samples that were OOB for at least one tree
            if len(oob_predictions[i]) > 0:
                total_oob_samples_evaluated += 1
                final_oob_pred = most_common_label(oob_predictions[i])
                if final_oob_pred == y[i]:
                    oob_correct_predictions += 1
        
        # Store the OOB score as an attribute of the model
        if total_oob_samples_evaluated > 0:
            self.oob_score_ = oob_correct_predictions / total_oob_samples_evaluated
        else:
            # This would happen only if n_trees is very small or dataset is tiny
            self.oob_score_ = 0.0

Code Walkthrough:

• Step 1 & 2: We initialize oob_predictions as a list of empty lists. Inside our main loop, after creating bootstrap_indices, we efficiently find oob_indices.
• Step 3 & 4: After a tree is trained, we immediately use it to predict its corresponding X_oob. We then iterate through the OOB indices and their predictions, appending each prediction to the correct list in oob_predictions. For example, if sample i=5 was OOB for this tree and the tree predicted 1, we perform oob_predictions[5].append(1).
• Step 5: After the loop finishes, oob_predictions is fully populated. We iterate through it one last time. For each sample i that has received at least one OOB vote, we calculate the majority vote (final_oob_pred) and check if it's correct. We sum up the correct predictions and divide by the number of samples we were able to evaluate.
• self.oob_score_: We store the final score as a class attribute. The trailing underscore is a common convention (used by Scikit-learn) for attributes that are learned or derived from the training data during the fit process.

The following resource provides code examples for a similar implementation strategy. While the structure is slightly different, it reinforces the core ideas of identifying OOB samples and using them for evaluation.

Conclusion

Congratulations on completing this module! You have now implemented a full-fledged Random Forest from scratch, complete with sophisticated prediction aggregation and a built-in, data-efficient evaluation mechanism.

Key Takeaways:

• Out-of-Bag (OOB) samples are the data points not selected during the bootstrapping process for a specific tree.
• These samples act as a "free" validation set for the forest, allowing for reliable performance estimation without sacrificing training data for a separate validation split.
• The OOB score is calculated by generating an aggregate prediction for each sample using only the trees that did not train on it.
• The implementation involves tracking which samples are OOB for each tree, collecting their predictions, and then performing a final majority vote for each sample.

Preview of the Next Lesson:
We have now mastered bagging (Bootstrap Aggregating), an ensemble technique where models are built in parallel. In the next module, we will explore a different, powerful family of ensemble methods: boosting. We'll start by implementing a decision stump (a one-level decision tree) to act as a "weak learner" and then use it to build our first boosting algorithm, AdaBoost, where trees are built sequentially, with each new tree focusing on the mistakes of the previous one.