Random Forest & Boosting

The wisdom of crowds

A decision tree is easy to read, but it is unstable: change a few training points and the tree can change completely. It also draws boundaries out of axis-parallel boxes, which fit a curved boundary badly.

An ensemble trains many models and combines their answers. If each model is better than guessing and their mistakes are not all the same, the combined answer is better than any single one. There are two main families:

The 3D model uses the same task for both: 60 training points in a square, labelled “inside” if they lie in a circle of radius 3.2 (the white ring), with a few labels flipped as noise. Accuracy is measured on 400 separate test points.

Random forest

1. Bootstrap. Draw n points from the n training points with replacement. Some points appear twice or three times (bigger balls), and about one third are left out (faded). The probability that a given point is never drawn is (1 − 1/n)ⁿ ≈ 1/e ≈ 0.37.
2. Grow a tree on that sample, but at each node consider only a random subset of the features (here: one of the two features, chosen at random).
3. Repeat for T trees. To predict, every tree votes and the majority wins.

Most individual trees are worse than the single tree, because each saw only about two thirds of the distinct points and could use only one random feature per split. But they make different mistakes, and the vote cancels most of them out. The forest’s boundary is much closer to a circle.

The out-of-bag points give a free validation set: each point can be tested on the trees that never saw it (the OOB error).

Boosting: AdaBoost

Boosting builds the team in sequence, so that every new member focuses on what the team still gets wrong. AdaBoost (Freund & Schapire, 1995) with decision stumps (trees with a single split):

1. Give every training point the weight w = 1/n.
2. For t = 1 … T:
   • Choose the stump with the smallest weighted error ε (the sum of the weights of the points it misclassifies).
   • Give it a say α = ½ · ln((1 − ε) / ε). Good stumps get a big say; a stump at ε = 0.5 gets α = 0.
   • Multiply the weight of each misclassified point by e^α and each correct one by e^−α, then normalise.
3. Predict with the sign of Σ α_t · h_t(x), where each stump votes +1 (inside) or −1 (outside).

In the model the ball size shows each point’s weight. After round 1 the points that the first stump got wrong swell, so round 2 picks a stump that classifies them correctly, and so on. One stump alone reaches only 70%: it just says “outside” almost everywhere. After 12 rounds the stumps together outline the circle with 88.8% on the test set (91.7% on the training set). The test accuracy goes up and down along the way, which is normal with so few stumps and noisy labels.

The weak point of boosting

A mislabelled point can never be classified “correctly”, so its weight keeps growing and later stumps waste effort on it. Boosting is therefore more sensitive to label noise than a random forest. Modern gradient boosting (XGBoost, LightGBM) generalises the idea with small trees, a learning rate and regularisation, and is one of the most successful methods for tabular data.

Code

import math

def mulberry32(seed):
    """A tiny seeded random generator (the same one the 3D model uses, so the numbers match)."""
    a = seed & 0xFFFFFFFF
    def imul(x, y):
        return (x * y) & 0xFFFFFFFF
    def rand():
        nonlocal a
        a = (a + 0x6d2b79f5) & 0xFFFFFFFF
        t = imul(a ^ (a >> 15), a | 1)
        t ^= (t + imul(t ^ (t >> 7), t | 61)) & 0xFFFFFFFF
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296
    return rand

def make_data(n, rand, noise):
    """Points in [0, 10]²; label 1 inside a circle of radius 3.2 around (5, 5); a few labels flipped."""
    rows = []
    for _ in range(n):
        x, y = rand() * 10, rand() * 10
        label = 1 if (x - 5) ** 2 + (y - 5) ** 2 < 10.24 else 0
        if noise and rand() < noise:
            label = 1 - label
        rows.append((x, y, label))
    return rows

def gini(rows):
    if not rows:
        return 0.0
    p = sum(r[2] for r in rows) / len(rows)
    return 1 - p * p - (1 - p) * (1 - p)

def majority(rows):
    return 1 if sum(r[2] for r in rows) * 2 > len(rows) else 0

def build(rows, depth, rand=None, max_depth=3):
    """A small decision tree. With `rand`, each node may only split on ONE random feature."""
    if depth == max_depth or len(rows) < 2 or gini(rows) == 0:
        return ('leaf', majority(rows))
    features = [int(rand() * 2)] if rand else [0, 1]
    best = None
    for f in features:
        vals = sorted(set(r[f] for r in rows))
        for a, b in zip(vals, vals[1:]):
            t = (a + b) / 2
            left = [r for r in rows if r[f] < t]
            right = [r for r in rows if r[f] >= t]
            score = (len(left) * gini(left) + len(right) * gini(right)) / len(rows)
            if best is None or score < best[0]:
                best = (score, f, t, left, right)
    if best is None:
        return ('leaf', majority(rows))
    _, f, t, left, right = best
    return ('split', f, t, build(left, depth + 1, rand, max_depth), build(right, depth + 1, rand, max_depth))

def predict(tree, x, y):
    while tree[0] == 'split':
        tree = tree[3] if (x, y)[tree[1]] < tree[2] else tree[4]
    return tree[1]

def random_forest(rows, n_trees, rand):
    trees = []
    for _ in range(n_trees):
        bag = [rows[int(rand() * len(rows))] for _ in range(len(rows))]   # bootstrap sample
        trees.append(build(bag, 0, rand))
    return trees

def vote(trees, x, y):
    return 1 if sum(predict(t, x, y) for t in trees) * 2 > len(trees) else 0

def adaboost(rows, rounds):
    n = len(rows)
    w = [1 / n] * n
    model = []
    for _ in range(rounds):
        best = None
        for f in (0, 1):
            vals = sorted(set(r[f] for r in rows))
            for a, b in zip(vals, vals[1:]):
                t = (a + b) / 2
                for pol in (1, -1):                          # pol 1: "inside" when value >= t
                    err = sum(wi for r, wi in zip(rows, w)
                              if (1 if (r[f] >= t) == (pol == 1) else 0) != r[2])
                    if best is None or err < best[0]:
                        best = (err, f, t, pol)
        err, f, t, pol = best
        alpha = 0.5 * math.log((1 - err) / err)              # the stump's say
        model.append((alpha, f, t, pol))
        for i, r in enumerate(rows):                         # wrong points get heavier
            right = (1 if (r[f] >= t) == (pol == 1) else 0) == r[2]
            w[i] *= math.exp(-alpha if right else alpha)
        total = sum(w)
        w = [wi / total for wi in w]
    return model

def boost_predict(model, x, y):
    score = sum(a * (1 if ((x, y)[f] >= t) == (p == 1) else -1) for a, f, t, p in model)
    return 1 if score > 0 else 0

def accuracy(fn, rows):
    return sum(fn(x, y) == label for x, y, label in rows) / len(rows)

rand = mulberry32(6)
train, test = make_data(60, rand, 0.06), make_data(400, rand, 0)

tree = build(train, 0)
print('one tree      ', accuracy(lambda x, y: predict(tree, x, y), test))
# one tree       0.845
trees = random_forest(train, 7, rand)
print('each tree     ', [accuracy(lambda x, y: predict(t, x, y), test) for t in trees])
# each tree      [0.7975, 0.825, 0.8475, 0.8175, 0.7825, 0.7675, 0.825]
print('random forest ', accuracy(lambda x, y: vote(trees, x, y), test))
# random forest  0.9375
model = adaboost(train, 12)
print('1 stump       ', accuracy(lambda x, y: boost_predict(model[:1], x, y), test))
# 1 stump        0.7
print('12 stumps     ', accuracy(lambda x, y: boost_predict(model, x, y), test),
      'train', round(accuracy(lambda x, y: boost_predict(model, x, y), train), 3))
# 12 stumps      0.8875 train 0.917

In practice you would use sklearn.ensemble.RandomForestClassifier and AdaBoostClassifier (or GradientBoostingClassifier), which implement the same ideas with many more options.

Common mistakes

• Thinking the trees of a random forest are trained on different parts of the data. Each gets a full-size sample of n points, drawn with replacement from all the data.
• Forgetting the random features. Bootstrap samples alone (“bagging”) give trees that are still very similar. The random feature subsets are what make it a random forest.
• Saying boosting trains models in parallel. Each round needs the weights produced by the previous one.
• Giving every boosted model the same vote. In AdaBoost each stump’s vote is weighted by α.
• Expecting ensembles to stay easy to explain. One tree is readable; a hundred voting trees are not. Feature importances and similar tools help.