Random Forest

The Big Picture — What Random Forest Does & Why

A Random Forest is an ensemble learning algorithm that combines predictions from multiple decision trees. Instead of trusting a single tree (which can overfit), Random Forest grows many trees on slightly different subsets of the data and features, then aggregates their predictions.

Why Random Forests Work

Random Forests solve two fundamental problems in machine learning:

The Two Sources of Randomness

AdTech Example: Click-Through Rate Prediction for Bing Ads

Imagine you work at Bing Ads and need to predict whether a user will click on an ad. Your dataset has:

Why Single Tree Fails

A single decision tree might learn:

if age < 25 and device == "mobile":
    if time_of_day < 14:
        return high_click_probability
    else:
        return low_click_probability

This overfits to patterns in your training data that don't generalize. Maybe there was a viral trend among 25-year-olds on mobile at 1pm, but it won't happen again.

Why Random Forest Works

Instead, a Random Forest grows 100+ trees, each seeing:

• Bootstrap Sample: 80% of your training data (with replacement), so each tree sees slightly different users
• Random Features: Each split only considers 3-4 random features out of 7, forcing trees to learn diverse patterns

The ensemble predictions are more stable because:

• Tree 1 learns "mobile users click more" (based on 70% of the data)
• Tree 2 learns "afternoon ads get fewer clicks" (based on a different 70%)
• Tree 3 learns "high relevance score drives clicks" (forced to ignore mobile/time)
• Averaging all 100 trees balances overfitting in any single tree

From Single Tree to Forest — Bagging & Bootstrap

Bagging (Bootstrap Aggregating) is the foundational technique behind Random Forests. The idea: train multiple models on random samples of the training data, then average their predictions.

Bootstrap Sampling Explained

For each tree in the forest, we create a bootstrap sample: a new dataset drawn from the original data with replacement.

Why Bootstrap Sampling Works for Variance Reduction

Mathematically, when we average predictions from uncorrelated estimators:

If we have 100 trees with variance σ² = 0.25, then:

Out-of-Bag Samples (~37%)

In bootstrap sampling, each sample is drawn with replacement. Mathematically, the probability that a row is not selected in a bootstrap sample of size n is:

These "out-of-bag" (OOB) samples can be used for free cross-validation (see Section 9).

How the First Tree Gets Created (with Bagging)

Let's walk through the step-by-step process of growing a single tree in a Random Forest. We'll use the Bing Ads example:

Step 1: Create a Bootstrap Sample

Draw n samples with replacement from the original training data. If you have 10,000 ad impressions, create a bootstrap sample of 10,000 rows (some rows appear multiple times, others not at all).

# Pseudo-code
bootstrap_sample = original_data.sample(n=len(original_data), replace=True)
# Result: 10,000 rows, ~3,700 unique rows from original

Step 2: At Each Node, Randomly Select Features

For classification tasks like CTR prediction, Random Forest considers only m = √p random features at each split, where p is the total number of features.

With 7 features (age, device, time, location, category, position, relevance):

So at the root node of Tree 1, we randomly select 3 out of 7 features and find the best split among only those 3.

Step 3: Find Best Split Among Selected Features

Using a metric like Gini impurity (for classification) or variance (for regression), find which of the 3 selected features creates the purest child nodes.

Example: If "Device == mobile" separates clicks from non-clicks better than the other two features, that becomes the root split.

Step 4: Recursively Grow the Tree

At each child node, repeat Steps 2-3: randomly select m features and find the best split among them. Continue until:

• Max depth is reached (e.g., depth=15), or
• Node is pure (all samples have same target), or
• Min samples per node reached (e.g., min_samples_split=2)

Important: Unlike some tree algorithms, Random Forest trees are typically grown fully without pruning. The ensemble averaging prevents overfitting.

How Different Trees Are Grown — Feature Randomness (Random Subspace Method)

The secret sauce of Random Forests is feature randomness. By forcing each tree to use a random subset of features at each split, we ensure that different trees learn different patterns, which decorrelates their predictions.

Contrast: Bagging vs. Random Forest

Visualizing 3 Different Trees

Why Feature Randomness Decorrelates Trees

When you force trees to use different features, they learn different decision boundaries:

• Tree 1: "Mobile users click more" (Device-centric)
• Tree 2: "Afternoon ads get fewer clicks" (Time-centric)
• Tree 3: "High relevance drives clicks" (Quality-centric)

When predicting, these trees make mistakes in different ways. Tree 1 might fail on desktop users, Tree 2 might fail on morning ads, and Tree 3 might fail on low-quality ads. When averaged, these errors cancel out.

Splitting Metrics Recap (Gini, Entropy, Variance Reduction)

At each node, Random Forest needs to decide which feature and threshold creates the best split. This is measured using impurity metrics.

For Classification (CTR Prediction): Gini Impurity

Gini Impurity measures the probability of misclassifying a randomly chosen sample if we randomly label it according to class distribution.

Example: Gini at Root Node (CTR Data)

Suppose at the root node, 40% of impressions are clicks, 60% are non-clicks:

After splitting on "Device==Mobile", left node has 70% clicks, right node has 20% clicks:

For Regression: Variance Reduction

If predicting continuous values (e.g., predicted CTR as a decimal 0.0-1.0), use variance reduction instead of Gini:

For Classification: Entropy (Alternative to Gini)

Some implementations use entropy instead of Gini (very similar results):

Key Parameters to Tune

Random Forest has many hyperparameters. Here are the most important ones for controlling bias-variance and preventing overfitting:

Parameter Tuning Strategy

Start with Defaults

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=100,
    max_features='sqrt',
    random_state=42
)

Tune max_features First

This is the most critical parameter. It controls tree decorrelation. Test a few values:

for mf in ['sqrt', 'log2', 0.5, None]:
    rf = RandomForestClassifier(max_features=mf, random_state=42)
    rf.fit(X_train, y_train)
    score = rf.score(X_val, y_val)
    print(f"max_features={mf}: {score}")

Interpretation:

• 'sqrt' or 'log2': Conservative, strong decorrelation
• 0.5 (50% of features): Medium decorrelation
• None (all features): Weak decorrelation, may overfit

Then Tune Depth & Leaf Size

for depth in [5, 10, 15, 20, None]:
    for min_leaf in [1, 5, 10]:
        rf = RandomForestClassifier(
            max_depth=depth,
            min_samples_leaf=min_leaf,
            random_state=42
        )
        rf.fit(X_train, y_train)
        score = rf.score(X_val, y_val)

Increase n_estimators (if computation allows)

More trees always help (no harm). Stop when validation score plateaus.

Bias-Variance Tradeoff — Why RF Reduces Variance

Understanding bias-variance is crucial to knowing when Random Forest excels and when it struggles.

Single Decision Tree

Random Forest Ensemble

Mathematical Foundation

Suppose we have k independent (uncorrelated) predictors, each with variance σ². The variance of their average is:

With 100 trees:

Why Feature Randomness Enables This

Mathematically, the variance reduction formula assumes low correlation between predictions. Feature randomness achieves this by:

• Forcing each tree to use different feature subsets
• Making trees learn different decision boundaries
• Ensuring they fail in different ways on new data
• Errors partially cancel when averaging

The Tradeoff

Random Forest slightly increases bias because:

• Feature randomness restricts which patterns each tree can learn
• Averaging predictions smooths out subtle patterns

But the variance reduction far outweighs this small bias increase, resulting in lower total error (bias² + variance).

Out-of-Bag Error & Feature Importance

Out-of-Bag (OOB) Error Explained

Recall that in bootstrap sampling, ~37% of data is not included in each bootstrap sample (the "out-of-bag" samples). RF exploits this as free cross-validation.

OOB Error Calculation:

1. For each row i in the training data, find all trees that don't have row i in their bootstrap sample
2. Use those trees to predict row i
3. Compare predicted to actual (clicks vs. no-clicks)
4. Average error across all rows = OOB error

Why This Works: OOB samples are unseen by individual trees, so OOB error is unbiased. No need for separate validation set or k-fold cross-validation.

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=100,
    oob_score=True,
    random_state=42
)
rf.fit(X_train, y_train)

print(f"OOB Score: {rf.oob_score_}")
print(f"Test Score: {rf.score(X_test, y_test)}")

Feature Importance

Random Forest can rank which features are most influential in predictions. Two methods:

1. Impurity-Based Importance (Default)

For each feature, sum up the information gain across all splits where that feature is used, weighted by the number of samples affected by each split.

Pros: Fast, built-in, interpretable

Cons: Biased towards high-cardinality features and correlated features

2. Permutation Importance

Randomize the values of a feature, re-predict, and measure how much error increases. If error increases a lot, the feature is important.

from sklearn.inspection import permutation_importance

perm_importance = permutation_importance(
    rf, X_test, y_test, n_repeats=10, random_state=42
)

for feature, importance in zip(feature_names, perm_importance.importances_mean):
    print(f"{feature}: {importance:.4f}")

Pros: Unbiased, captures interactions, handles correlated features

Cons: Slower, requires test set

Example: CTR Prediction Feature Importance

RF vs. Decision Trees vs. XGBoost — When to Use What

Decision Tree: Use When

• Interpretability is paramount (e.g., loan approval, medical diagnosis)
• You need to explain decisions to stakeholders
• Dataset is small and you're not worried about overfitting

Random Forest: Use When

• You want good predictive accuracy with minimal tuning
• Dataset is moderate to large (hundreds or thousands of rows)
• Features are mixed (categorical and continuous)
• Training time is acceptable (parallelizable)
• Example: Bing Ads CTR prediction ← RF is a great fit

XGBoost: Use When

• You need maximum predictive accuracy and can afford tuning time
• Dataset is very large and competition is fierce (Kaggle, production ML)
• Class imbalance is severe
• You need interpretability via SHAP values
• Example: High-stakes CTR prediction where 1% accuracy improvement saves millions

Python Implementation from Scratch

Let's build a Random Forest from scratch using only NumPy and Pandas. This deepens understanding of how it works under the hood.

Part 1: Decision Tree Class

import numpy as np
from collections import Counter

class DecisionTree:
    def __init__(self, max_depth=15, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def fit(self, X, y):
        """Grow tree from training data"""
        self.tree = self._build_tree(X, y, depth=0)
        return self

    def _build_tree(self, X, y, depth):
        # Base cases
        if (X.shape[0] < self.min_samples_split or
            depth >= self.max_depth or
            len(np.unique(y)) == 1):
            return {'type': 'leaf',
                    'prediction': Counter(y).most_common(1)[0][0]}

        best_gain = 0
        best_split = None

        # Try all features and thresholds
        for feature_idx in range(X.shape[1]):
            for threshold in np.unique(X[:, feature_idx]):
                # Split
                left_mask = X[:, feature_idx] <= threshold
                right_mask = ~left_mask

                if left_mask.sum() == 0 or right_mask.sum() == 0:
                    continue

                # Gini impurity
                gain = self._information_gain(y, y[left_mask], y[right_mask])

                if gain > best_gain:
                    best_gain = gain
                    best_split = {
                        'feature': feature_idx,
                        'threshold': threshold,
                        'left_mask': left_mask
                    }

        if best_split is None:
            return {'type': 'leaf',
                    'prediction': Counter(y).most_common(1)[0][0]}

        # Recursively build subtrees
        left_mask = best_split['left_mask']
        return {
            'type': 'node',
            'feature': best_split['feature'],
            'threshold': best_split['threshold'],
            'left': self._build_tree(X[left_mask], y[left_mask], depth+1),
            'right': self._build_tree(X[~left_mask], y[~left_mask], depth+1)
        }

    def _gini(self, y):
        # Gini impurity
        proportions = np.bincount(y) / len(y)
        return 1 - np.sum(proportions ** 2)

    def _information_gain(self, parent, left, right):
        # Information gain = parent gini - weighted child gini
        n = len(parent)
        gini_parent = self._gini(parent)
        gini_left = self._gini(left)
        gini_right = self._gini(right)
        gain = gini_parent - (len(left)/n * gini_left + len(right)/n * gini_right)
        return gain

    def predict(self, X):
        return np.array([self._predict_sample(x, self.tree) for x in X])

    def _predict_sample(self, x, node):
        if node['type'] == 'leaf':
            return node['prediction']

        if x[node['feature']] <= node['threshold']:
            return self._predict_sample(x, node['left'])
        else:
            return self._predict_sample(x, node['right'])

Part 2: Random Forest Class

class RandomForestClassifier:
    def __init__(self, n_estimators=100, max_features=None, max_depth=15,
                 min_samples_split=2, bootstrap=True, random_state=None):
        self.n_estimators = n_estimators
        self.max_features = max_features
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.bootstrap = bootstrap
        self.random_state = random_state
        self.trees = []
        self.feature_importances_ = None

    def fit(self, X, y):
        """Train random forest"""
        np.random.seed(self.random_state)

        n_features = X.shape[1]
        if self.max_features is None:
            self.max_features = int(np.sqrt(n_features))

        self.trees = []
        feature_importances = np.zeros(n_features)

        for _ in range(self.n_estimators):
            # Step 1: Bootstrap sample
            if self.bootstrap:
                idx = np.random.choice(X.shape[0], X.shape[0], replace=True)
                X_boot = X[idx]
                y_boot = y[idx]
            else:
                X_boot = X
                y_boot = y

            # Step 2: Train tree (with full features; feature selection happens in tree)
            tree = DecisionTree(max_depth=self.max_depth,
                              min_samples_split=self.min_samples_split)
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

        return self

    def predict(self, X):
        """Predict by majority vote"""
        predictions = np.array([tree.predict(X) for tree in self.trees])
        # Majority vote: (n_trees, n_samples) → (n_samples,)
        final_predictions = np.array(
            [Counter(predictions[:, i]).most_common(1)[0][0]
             for i in range(X.shape[0])]
        )
        return final_predictions

    def predict_proba(self, X):
        """Predict probabilities (for binary classification)"""
        predictions = np.array([tree.predict(X) for tree in self.trees])
        # Proportion of trees voting for class 1
        proba_class_1 = (predictions == 1).sum(axis=0) / len(self.trees)
        return np.column_stack([1 - proba_class_1, proba_class_1])

    def score(self, X, y):
        """Accuracy score"""
        predictions = self.predict(X)
        return (predictions == y).mean()

Part 3: Example with Bing Ads CTR Data

import pandas as pd

# Load CTR data
data = pd.DataFrame({
    'age': [25, 35, 22, 45, 32] * 100,
    'device': [0, 1, 0, 1, 0] * 100,  # 0=desktop, 1=mobile
    'time': [9, 14, 18, 10, 16] * 100,
    'relevance': [0.7, 0.5, 0.8, 0.6, 0.9] * 100,
    'clicked': [1, 0, 1, 0, 1] * 100
})

X = data.drop('clicked', axis=1).values
y = data['clicked'].values

# Split into train/test
split = int(0.8 * len(X))
X_train, X_test = X[:split], X[split:]
y_train, y_test = y[:split], y[split:]

# Train Random Forest
rf = RandomForestClassifier(n_estimators=10, max_depth=5, random_state=42)
rf.fit(X_train, y_train)

# Predictions
y_pred = rf.predict(X_test)
accuracy = rf.score(X_test, y_test)

print(f"Accuracy: {accuracy:.4f}")

# Probability predictions
y_proba = rf.predict_proba(X_test)
print(f"CTR (click probability) for first 5 samples: {y_proba[:5, 1]}")

Key Implementation Details

Production Considerations

• Use scikit-learn in production: Our implementation is educational; scikit-learn RF is optimized and battle-tested.
• Parallelize training: `RandomForestClassifier(n_jobs=-1)` trains trees in parallel.
• Save models: Use `pickle` or `joblib` to save trained models for inference.
• Monitor OOB score: Track OOB error during training to detect overfitting.
• Feature preprocessing: Encode categorical variables, handle missing values before fitting.

# Production-grade scikit-learn example
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import cross_val_score
import joblib

# Train with OOB scoring
rf = RandomForestClassifier(
    n_estimators=200,
    max_features='sqrt',
    max_depth=10,
    min_samples_leaf=5,
    oob_score=True,
    n_jobs=-1,
    random_state=42
)

rf.fit(X_train, y_train)

# Cross-validation
cv_scores = cross_val_score(rf, X_train, y_train, cv=5)
print(f"CV Scores: {cv_scores.mean():.4f} ± {cv_scores.std():.4f}")
print(f"OOB Score: {rf.oob_score_:.4f}")

# Save model
joblib.dump(rf, "ctr_model.pkl")