Random Forests

Decision trees solved one major representation problem. They allowed us to learn complex, non-linear decision boundaries without forcing every prediction through one global equation.

Unfortunately, they created another problem. A single decision tree is unstable. Small changes in the training data can produce a very different tree.

Imagine training a tree to predict whether Jessie will order a burger. Last week the root question might have been:

Hungry?
  yes -> Burger
  no  -> Salad

This week you collect a few more restaurant visits and retrain. Now the first question becomes:

Friends ordering burgers > 2?
  yes -> Burger
  no  -> Hungry?

Nothing about Jessie changed dramatically. Only a few examples changed. This is high variance: the learned model moves too much when the training set moves a little.

How can we keep the flexibility of decision trees while making their predictions more stable?

Instead of trusting one decision tree, build many. Each tree is trained slightly differently. Each tree makes its own prediction. The forest combines all of those predictions into one final answer.

One tree might overreact to a strange training example. Another might split on a noisy feature. A third might find a useful rule. When many trees vote, the individual quirks begin to cancel out.

Random Forest is an ensemble method. An ensemble combines many models into one predictor. Its central idea is simple: a group of imperfect but diverse models can be more reliable than any one member of the group.

Random Forest has two mathematical stories. First, there is the algorithm: the computations performed to train and predict. Second, there is the reason it works: variance reduction through averaging low-correlation models.

The Algorithm

Suppose the training set is $D=\{(x_1,y_1),\ldots,(x_n,y_n)\}$. We want to build $T$ decision trees.

Bootstrap sampling means each tree receives a new dataset $D_t$created by sampling $n$ rows from $D$ with replacement. Because replacement is allowed, a row can be chosen multiple times.

Random feature selection means a split does not compare every possible feature. If the original data has $d$ features, the split considers only $m$ randomly selected features, where $m<d$. For classification, a common default is:

At every node, the tree still chooses the split with the largest impurity reduction, just as in the decision-tree chapter.

After the trees are trained, prediction is aggregation. For classification, each tree predicts one class and the forest returns the mode.

For regression, the forest averages the tree predictions.

Why It Works

Random Forest works because it reduces variance. A single tree can change a lot when the training data changes. Averaging many trees makes the final prediction less sensitive to any one tree.

Averaging only helps if the trees are not identical. If every tree makes the same mistake, the forest repeats that mistake. Random Forest therefore injects randomness in two places: the rows each tree sees and the features each split can consider.

Suppose every tree has variance $\sigma^2$. If the trees were completely independent, the variance of the average prediction would be:

Real trees are not completely independent. They are correlated because they are trained on data from the same underlying problem. A useful approximation is:

Here $\rho$ is the average correlation between trees. This equation explains the design of the method. Increasing $T$ shrinks the second term. Reducing correlation $\rho$ shrinks the first term.

Why Bootstrap Sampling?

If every tree receives the same dataset and can inspect every feature, many trees will learn similar boundaries. Their errors will be highly correlated, so averaging provides little benefit.

Bootstrap sampling creates natural diversity. In one bootstrap sample, the probability that a particular training example is not chosen is:

So a bootstrap sample contains about 63.2 percent unique examples on average, and about 36.8 percent of the original rows are omitted from that tree. Those omitted rows are called out-of-bag examples and can later be used to estimate performance.

Complexity

If training one tree costs approximately $O(n\log n)$, then training $T$ trees costs approximately:

Prediction also scales with the number of trees because every tree makes one prediction. Random Forest is slower than a single tree, but it usually gives much better generalization.

This implementation assumes you already have a decision-tree builder that accepts a random subset of features when choosing each split. Random Forest adds three pieces: bootstrap sampling, repeated tree training, and majority voting.

import numpy as np

class RandomForestClassifier:
    def __init__(self, n_trees=100, max_depth=None, max_features="sqrt"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.max_features = max_features
        self.trees = []

    def _feature_count(self, n_features):
        if self.max_features == "sqrt":
            return max(1, int(np.sqrt(n_features)))
        if self.max_features == "all":
            return n_features
        return int(self.max_features)

    def _bootstrap_sample(self, X, y):
        n = len(X)
        indices = np.random.choice(n, size=n, replace=True)
        return X[indices], y[indices]

    def fit(self, X, y):
        self.trees = []
        m = self._feature_count(X.shape[1])

        for _ in range(self.n_trees):
            X_sample, y_sample = self._bootstrap_sample(X, y)
            tree = DecisionTreeClassifier(
                max_depth=self.max_depth,
                max_features=m,
            )
            tree.fit(X_sample, y_sample)
            self.trees.append(tree)

        return self

    def predict_one(self, x):
        votes = [tree.predict_one(x) for tree in self.trees]
        values, counts = np.unique(votes, return_counts=True)
        return values[np.argmax(counts)]

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

The important design detail is inside the tree. At each node, the tree should pick a fresh random subset of features before searching for the best split. That is what keeps the trees from all choosing the same obvious feature at the root.