Bagged Tree Ensembles

The previous lesson separated the split criterion of the decision tree from pruning; the pruned tree beat the baseline and became the most readable model among the families tried in the four lessons. One of its properties was left unmeasured: when the training set changes a little, the tree chooses entirely different splits. When the root moves, everything under it moves; the number a single tree gives is not a measurement but the result of a draw.

This lesson first counts that draw, then builds the way to narrow it. Bagging runs the same procedure separately on many samples drawn with replacement and takes the majority vote of the trees. Feature randomness adds a second split: each tree chooses its splits from a randomly chosen subset of columns. What is measured is not one number but two: the number of the ensemble and the spread of that number.

• NM31. The set is the fictional subscriber table of the Introduction to Machine Learning course: 1,260 subscribers, 756/252/252, seed 20260218. The baseline is 0.7579 on the test set and 0.8135 on validation; the number the course carries is the one on the test set.
• NM32. The feature set comes from the Data Preparation and Feature Engineering course and is eleven columns; the only thing that changes is the model.
• NM33. The comparison point is the tree of the previous lessons: depth 6, leaf minimum 2, split criterion impurity reduction. The thresholds are extracted once from the training set and are at most twenty-four per column; this is a speed decision and does not change the splits that can be chosen.
• NM34. The bag sample is 756 rows and is drawn with replacement. Sampling with replacement was established in the Applied Statistics topic of the Statistical Analysis and Exploratory Data Analysis course; its method is not repeated.
• NM35. The decision is a majority vote: if the share of trees that say positive exceeds 0.5, the subscriber is counted as suspicious. The threshold is fixed from the Data Preparation and Feature Engineering course; its selection is left to model evaluation.
• NM36. The number of candidates tried is 31: seven tree counts and twenty-four column-subset–depth pairs. The choice is read from the validation set; the test set appears only in the last line.

The Spread of a Single Tree

The setup generates the table, bins the columns by thresholds and prints the single tree that is the comparison point.

# bagging.py — MODEL: the FICTIONAL subscriber table of the Introduction to Machine Learning course is rebuilt with the same seed;
# the feature set comes from the Data Preparation and Feature Engineering course and is kept fixed throughout the course.
import bisect
import math

SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21, 0.00), ("south", 0.22, 17, -0.10),
          ("east", 0.18, 26, 0.30), ("west", 0.14, 14, -0.05),
          ("central", 0.18, 23, 0.05)]


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


SUBSCRIBERS, DATA = [], []
for i in range(RAW):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    household = 1 + pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    rating = 1 + pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        SUBSCRIBERS.append({"id": 10001 + i, "region": b, "household": household,
                            "satisfaction": rating})
for k in SUBSCRIBERS:
    r, v = rng(SEED + 7000 + k["id"]), []
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - n * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    mean, vol, r = sum(v) / len(v), max(v) - min(v), rng(SEED + 51000 + k["id"])
    z = (0.052 * (mean - 20) + 0.85 * (min(v) == 0.0) + 0.026 * vol
         + 0.24 * (k["household"] >= 5) - 0.20 * (k["satisfaction"] >= 4) + k["region"][3]
         + 0.9 * (k["id"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"household": k["household"], "satisfaction": k["satisfaction"],
         "period": len(v), "mean_consumption": round(mean, 2), "volatility": round(vol, 2),
         "zero_readings": int(min(v) == 0.0), "suspicious": int(z > 1.35)}
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)


def shuffle(data, seed):
    r, s = rng(seed), list(range(len(data)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [data[i] for i in s]


K = shuffle(DATA, SEED + 90000)
TRAIN, VAL, TEST = K[:756], K[756:1008], K[1008:]
FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period", "zero_readings",
          "area_north", "area_south", "area_east", "area_west", "area_central"]
THRESHOLDS = {}
for a in FIELDS:
    d = sorted({x[a] for x in TRAIN})
    THRESHOLDS[a] = d[1:] if len(d) <= 24 else [d[int(i * len(d) / 25)] for i in range(1, 25)]
BINS = [len(THRESHOLDS[a]) + 1 for a in FIELDS]


def binarize(s):                            # each row: bin numbers and label
    return [(tuple(bisect.bisect_right(THRESHOLDS[a], x[a]) for a in FIELDS), x["suspicious"])
            for x in s]


B_TRAIN, B_VAL, B_TEST = binarize(TRAIN), binarize(VAL), binarize(TEST)
ALL = list(range(len(FIELDS)))


def tree(sample, depth, columns, least=2):  # MODEL: decision tree
    n, p, best = len(sample), sum(y for _, y in sample), None
    if depth and n >= 2 * least and 0 < p < n:
        for k in columns:
            count, pos = [0] * BINS[k], [0] * BINS[k]
            for b, y in sample:
                count[b[k]] += 1
                pos[b[k]] += y
            sc = sp = 0
            for j in range(BINS[k] - 1):
                sc, sp = sc + count[j], sp + pos[j]
                if sc < least or n - sc < least:
                    continue
                gain = sp * sp / sc + (p - sp) ** 2 / (n - sc) - p * p / n
                if best is None or gain > best[0]:
                    best = (gain, k, j)
    if best is None or best[0] <= 1e-9:
        return p / n
    _, k, j = best
    return (k, j, tree([o for o in sample if o[0][k] <= j], depth - 1, columns, least),
            tree([o for o in sample if o[0][k] > j], depth - 1, columns, least))


def ratio(d, b):
    while type(d) is tuple:
        d = d[2] if b[d[0]] <= d[1] else d[3]
    return d


def accuracy(d, target):
    return sum((ratio(d, b) > 0.5) == y for b, y in target) / len(target)


def baseline(target):
    return sum(y == 0 for _, y in target) / len(target)


SINGLE = tree(B_TRAIN, 6, ALL)
print(f"baseline             validation {baseline(B_VAL):.4f}  test {baseline(B_TEST):.4f}")
print(f"single tree depth 6  validation {accuracy(SINGLE, B_VAL):.4f}  "
      f"test {accuracy(SINGLE, B_TEST):.4f}  train {accuracy(SINGLE, B_TRAIN):.4f}")

baseline             validation 0.8135  test 0.7579
single tree depth 6  validation 0.8056  test 0.7778  train 0.8426

Two held-out sets give two different baselines with the same procedure: 0.7579 on the test set, 0.8135 on validation. The tree reads 0.7778 on the test set, beating the baseline by 0.0199, and stays at 0.8056 on validation, falling 0.0079 below its own baseline.

The fragility is counted as follows: 41 samples are drawn from the training set with replacement and a tree is built on each with the same procedure. The only thing that changes is which row appears how many times.

def spread(v):
    o = sum(v) / len(v)
    return (sum((q - o) ** 2 for q in v) / len(v)) ** 0.5


def forest(seed, count, m, depth):          # MODEL: bagged tree ensemble
    r, trees, bags = rng(seed), [], []
    for _ in range(count):
        chosen = [int(r() * len(B_TRAIN)) for _ in range(len(B_TRAIN))]
        pool, columns = list(ALL), []
        for _ in range(min(m, len(ALL))):
            columns.append(pool.pop(int(r() * len(pool))))
        trees.append(tree([B_TRAIN[i] for i in chosen], depth, sorted(columns)))
        bags.append(set(chosen))
    return trees, bags


def vote(trees, b):                         # majority vote: share of trees that say positive
    return sum(ratio(d, b) > 0.5 for d in trees) / len(trees)


def forest_accuracy(trees, target):
    return sum((vote(trees, b) > 0.5) == y for b, y in target) / len(target)


FORESTS = [forest(SEED + 13 * i, 41, 11, 6) for i in range(5)]
TREES = FORESTS[0][0]
roots = {}
for d in TREES:
    roots[(d[0], d[1])] = roots.get((d[0], d[1]), 0) + 1
labels = [[ratio(d, b) > 0.5 for b, _ in B_VAL] for d in TREES]
differ = [sum(u != v for u, v in zip(labels[i], labels[j]))
          for i in range(len(TREES)) for j in range(i + 1, len(TREES))]
print(f"{len(roots)} distinct (column, threshold) pairs for the root split, "
      f"the most frequent in {max(roots.values())} trees")
print(f"{'single tree':<12} {'mean':>9} {'spread':>9} {'lowest':>9} {'highest':>10}")
for name, target in (("validation", B_VAL), ("test", B_TEST)):
    v = [accuracy(d, target) for d in TREES]
    print(f"{'  ' + name:<12} {sum(v) / len(v):>9.4f} {spread(v):>9.4f} "
          f"{min(v):>9.4f} {max(v):>10.4f}")
print(f"subscribers two trees classify differently (out of 252): mean "
      f"{sum(differ) / len(differ):.1f}, at least {min(differ)}, at most {max(differ)}")
print(f"vote of the same 41 trees   validation {forest_accuracy(TREES, B_VAL):.4f}  "
      f"test {forest_accuracy(TREES, B_TEST):.4f}")

9 distinct (column, threshold) pairs for the root split, the most frequent in 16 trees
single tree       mean    spread    lowest    highest
  validation    0.7744    0.0218    0.7222     0.8135
  test          0.7489    0.0246    0.6905     0.7897
subscribers two trees classify differently (out of 252): mean 46.2, at least 24, at most 77
vote of the same 41 trees   validation 0.8095  test 0.7698

The root split is not the same in all 41 trees: nine different column-threshold pairs become the root, and the most frequent appears in only 16 trees. The split that determines everything beneath it moves somewhere else in 60% of the trees when the sample changes.

The second number is more concrete: two random trees classify on average 46.2 of the 252 subscribers differently, 24 in the closest pair and 77 in the farthest pair.

The third is how this reflects on the held-out set. The single trees’ test number has a mean of 0.7489, a spread of 0.0246, and a range from 0.6905 to 0.7897; the distance between the two ends is 25 subscribers. Reading a model’s number from a single sample is picking a random point from this range. Spread is the square root of the mean of the squared distances from the mean.

The last line is the vote of the same 41 trees: validation 0.8095, test 0.7698. This number is 0.0209 above the single trees’ mean of 0.7489, but below the single tree’s 0.7778: with all the columns open to every tree, bagging pulls the mean up but does not beat the single tree.

Number of Trees and Variability

What bagging really adds is not in the mean but in the spread. Five ensembles are built with five seeds, and the first 1, 3, 5, 11, 21, 31 and 41 trees of each are voted separately.

print(f"{'trees':>5} {'validation':>10} {'spread':>9} {'test':>9} {'spread':>9}")
for count in (1, 3, 5, 11, 21, 31, 41):
    vv = [forest_accuracy(a[:count], B_VAL) for a, _ in FORESTS]
    vt = [forest_accuracy(a[:count], B_TEST) for a, _ in FORESTS]
    print(f"{count:>5} {sum(vv) / 5:>10.4f} {spread(vv):>9.4f} "
          f"{sum(vt) / 5:>9.4f} {spread(vt):>9.4f}")

trees validation    spread      test    spread
    1     0.7786    0.0193    0.7627    0.0088
    3     0.7944    0.0136    0.7762    0.0102
    5     0.8032    0.0096    0.7778    0.0148
   11     0.7984    0.0095    0.7722    0.0122
   21     0.8103    0.0105    0.7762    0.0082
   31     0.8183    0.0119    0.7754    0.0124
   41     0.8214    0.0075    0.7778    0.0066

The spread columns are the lesson’s measure. For a single tree the validation spread is 0.0193, for 41 trees 0.0075: the difference among the five runs narrows 2.6-fold. The mean rises from 0.7786 to 0.8214 but not smoothly; 0.8032 at 5 trees, 0.7984 at 11. Adding trees does not give a better number at every step; what it gives is a number that moves less on repetition. On the test set it is the same: from 0.7627 to 0.7778, a gain of four subscribers, and the spread from 0.0088 to 0.0066. The cost is 41 times the computation.

Feature Randomness and the Out-of-Bag Estimate

Bagged trees resemble one another, because all of them look at the same eleven columns and find the same strong column at the root. A second source of randomness breaks this: each tree chooses its splits from a randomly chosen subset of m columns. The grid takes m from two to eleven and the depth from three to eight. A third number is also produced: the out-of-bag estimate has each training row voted on only by the trees that did not take that row into their bag, and gives a number without touching the held-out set.

def out_of_bag(trees, bags):                # each row is voted on by the trees that did not see it
    out = [(b, y, [d for d, c in zip(trees, bags) if i not in c])
           for i, (b, y) in enumerate(B_TRAIN)]
    return sum((vote(v, b) > 0.5) == y for b, y, v in out if v) / sum(1 for *_, v in out if v)


CANDIDATES, GRID = 7, {}
print(f"{'m':>3}" + "".join(f"{'depth ' + str(d):>16}" for d in (3, 4, 6, 8)))
for m in (2, 3, 4, 6, 8, 11):
    line = []
    for depth in (3, 4, 6, 8):
        a, t = forest(SEED, 41, m, depth)
        GRID[(m, depth)] = (forest_accuracy(a, B_VAL), forest_accuracy(a, B_TEST),
                            out_of_bag(a, t))
        CANDIDATES += 1
        line.append(f"{GRID[(m, depth)][0]:.4f}/{GRID[(m, depth)][1]:.4f}")
    print(f"{m:>3}" + "".join(f"{q:>16}" for q in line))
ORDER = [(m, d) for m in (2, 3, 4, 6, 8, 11) for d in (3, 4, 6, 8)]


def top(column):
    e = max(GRID[k][column] for k in ORDER)
    return next(k for k in ORDER if GRID[k][column] == e)


for name, column in (("from validation", 0), ("from test", 1), ("from out-of-bag", 2)):
    m, depth = top(column)
    d, s, o = GRID[(m, depth)]
    print(f"choice {name:<15} m={m:<3} depth={depth:<3} "
          f"validation {d:.4f}  test {s:.4f}  out-of-bag {o:.4f}")
m, depth = top(0)
print(f"candidates tried {CANDIDATES}, family number {GRID[(m, depth)][1]:.4f}, "
      f"above baseline {GRID[(m, depth)][1] - baseline(B_TEST):+.4f}")

  m         depth 3         depth 4         depth 6         depth 8
  2   0.8135/0.7579   0.8135/0.7579   0.8135/0.7579   0.8135/0.7579
  3   0.8095/0.7540   0.8135/0.7579   0.8175/0.7619   0.8095/0.7579
  4   0.8175/0.7698   0.8214/0.7817   0.8175/0.7817   0.8254/0.7817
  6   0.8214/0.7778   0.8413/0.7897   0.8373/0.7937   0.8413/0.7857
  8   0.8254/0.7857   0.8214/0.7817   0.8254/0.7698   0.8294/0.7738
 11   0.8175/0.7857   0.8214/0.7778   0.8095/0.7698   0.8016/0.7698
choice from validation m=6   depth=4   validation 0.8413  test 0.7897  out-of-bag 0.7884
choice from test       m=6   depth=6   validation 0.8373  test 0.7937  out-of-bag 0.7950
choice from out-of-bag m=6   depth=8   validation 0.8413  test 0.7857  out-of-bag 0.7989
candidates tried 31, family number 0.7897, above baseline +0.0317

The top row shows the limit of randomness: when m is two, the ensemble gives exactly the baseline at all four depths, because the vote of two-column trees moves no subscriber to the suspicious side. When m is six, 0.8413 on validation and 0.7897 on the test set come out; at m eleven, that is, with no randomness, the number falls back to 0.7778. The difference randomness adds is this column, three to four subscribers.

The last three lines pay off the course’s rule. The choice read from validation says m six and depth four; that candidate’s test number is 0.7897. Had it been read from the test set, depth six would be chosen and the number would be 0.7937; the difference is 0.0040, a single subscriber. Small, but its direction is fixed: if the choice and the measurement are made from the same 252 rows, the number grows.

The out-of-bag column is sharper. The chosen candidate’s validation number is 0.8413, its test number 0.7897 and its out-of-bag estimate 0.7884: 0.0013 from the test set and 0.0516 from validation. The out-of-bag is read from 756 rows and spends no held-out set; validation is read from 252 rows and is used up with every look.

The family number is 0.7897, the candidates tried 31; 0.0317 above the baseline. The real difference is here: the single tree’s number was a draw between 0.6905 and 0.7897, the ensemble’s is not.

Summary

• The same procedure chooses nine different column-threshold pairs for the root across 41 bag samples; two trees classify on average 46.2 of the 252 subscribers differently.
• The single tree’s test number wanders between 0.6905 and 0.7897 with a spread of 0.0246; a number read from a single sample is a randomly chosen point of this range.
• As the number of trees goes from 1 to 41, the validation spread goes from 0.0193 to 0.0075 and the mean from 0.7786 to 0.8214; the rise is not smooth, the fall is.
• Without feature randomness, bagging does not beat the single tree: with eleven columns open, the test number is 0.7698 against the single tree’s 0.7778; when m is six it is 0.7897.
• The out-of-bag estimate is 0.7884, 0.0013 from the test set and 0.0516 from validation; it is read without spending a held-out set.

Next Step

Bagging builds the trees independently of one another: not one of the 41 trees knows where the others err, all of them solve the same problem from scratch and vote at the end. Independence lowered the spread and moved the mean by only four subscribers. What if the trees could see one another: if the second tree looked only where the first erred, and the third at the remaining error of the first two. The next lesson builds this sequential arrangement and sets two tuning variables against each other: how many rounds to run and with what size of step each round is added. The two substitute for each other; the same number can come out with many rounds of a small step or few rounds of a large step, and the budgets of the two paths are not the same.