Sequential Boosting

The previous lesson built forty-one trees independently of one another; none of them knew where the others erred. Independence lowered the spread from 0.0193 to 0.0075 but moved the test mean up by only four subscribers. This lesson tries the opposite direction: each new model is built by looking at the remaining error of the previous ones.

Sequential boosting builds a sum. The start is the logit of the suspicious rate in the training set; each round fits a weak learner to the difference the sum leaves at each subscriber and adds its contribution to the sum multiplied by a learning rate. The weak learner here is a small tree with one or two splits. Three things are measured: the separation of two numbers as the number of rounds grows, the substitution of the learning rate and the number of rounds for each other, and the bill these write to the tuning budget.

• NM37. The set, the split and the baseline are the same as in the previous lesson: 1,260 subscribers, 756/252/252, seed 20260218, the baseline is 0.7579 on the test set and 0.8135 on validation. The features do not change.
• NM38. In this lesson the tree is a regression tree: each example carries a gradient and a curvature, and the value of a leaf is the ratio of the two. Giving the label as the gradient and one as the curvature turns the same function into the previous lesson’s classification tree.
• NM39. The gradient of a round is taken as label - probability and the curvature as probability * (1 - probability), and the curvature does not fall below 1e-6; this is an overflow guard, not a tuning choice.
• NM40. The decision threshold is the zero of the sum, that is, 0.5 of the probability; it is fixed from the Data Preparation and Feature Engineering course.
• NM41. The depth of the weak learner is 1, 2 or 3; the learning rate is 0.02 / 0.05 / 0.15 / 0.45; the number of rounds is at most 300.
• NM42. The target of the trade-off measurement is 208/252 on the validation set, that is, 0.8254, and it was fixed before the measurement.
• NM43. The cost measure is the number of splits: the total of the internal nodes. Time is not written.
• NM44. The tuning budget counts every (rate, depth, rounds) triple measured on the validation set; the choice is made only from the seventy-two-cell grid.

Building on the Remaining Error

The setup generates the table, writes the tree and the boosting loop, and sweeps the number of rounds with a fixed setting.

# boosting.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)
SETS, ALL = (B_TRAIN, B_VAL, B_TEST), list(range(len(FIELDS)))


def tree(sample, depth, columns, least=2):  # MODEL: each example is (bins, gradient, curvature)
    n, best = len(sample), None
    G, H = sum(o[1] for o in sample), sum(o[2] for o in sample)
    if depth and n >= 2 * least:
        for k in columns:
            sg, sh, sn = [0.0] * BINS[k], [0.0] * BINS[k], [0] * BINS[k]
            for b, g, h in sample:
                sg[b[k]] += g
                sh[b[k]] += h
                sn[b[k]] += 1
            cg = ch = cn = 0
            for j in range(BINS[k] - 1):
                cg, ch, cn = cg + sg[j], ch + sh[j], cn + sn[j]
                if cn < least or n - cn < least:
                    continue
                gain = cg * cg / ch + (G - cg) ** 2 / (H - ch) - G * G / H
                if best is None or gain > best[0]:
                    best = (gain, k, j)
    if best is None or best[0] <= 1e-9:
        return G / H
    _, 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 value(d, b):
    while type(d) is tuple:
        d = d[2] if b[d[0]] <= d[1] else d[3]
    return d


def squash(z):
    return 1.0 / (1.0 + math.exp(-z)) if z > -30 else 0.0


def boost(rate, rounds, depth, stops):      # MODEL: sequential boosting
    p = sum(y for _, y in B_TRAIN) / len(B_TRAIN)
    F = [[math.log(p / (1 - p))] * len(k) for k in SETS]
    trace = {}
    for t in range(1, rounds + 1):
        sample = []
        for i, (b, y) in enumerate(B_TRAIN):
            q = squash(F[0][i])
            sample.append((b, y - q, max(q * (1 - q), 1e-6)))
        d = tree(sample, depth, ALL)
        for u, subset in enumerate(SETS):
            for i, (b, _) in enumerate(subset):
                F[u][i] += rate * value(d, b)
        if t in stops:
            trace[t] = tuple(sum((F[u][i] > 0) == y for i, (_, y) in enumerate(subset)) / len(subset)
                             for u, subset in enumerate(SETS))
    return trace


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


STOPS = (1, 5, 10, 25, 50, 100, 200)
TRACE = boost(0.15, 200, 2, set(STOPS))
print(f"baseline             validation {baseline(B_VAL):.4f}  test {baseline(B_TEST):.4f}")
print(f"{'rounds':>6} {'train':>9} {'validation':>10} {'test':>9}")
for t in STOPS:
    print(f"{t:>6} {TRACE[t][0]:>9.4f} {TRACE[t][1]:>10.4f} {TRACE[t][2]:>9.4f}")

baseline             validation 0.8135  test 0.7579
rounds     train validation      test
     1    0.7778     0.8135    0.7579
     5    0.7804     0.8095    0.7579
    10    0.8082     0.8373    0.7738
    25    0.8280     0.8214    0.7937
    50    0.8439     0.8135    0.7897
   100    0.8532     0.8016    0.7778
   200    0.8638     0.8056    0.7817

The table is a separation. In the first round the training number is 0.7778 and validation 0.8135; the held-out set is ahead. In round ten validation peaks at 0.8373. After round twenty-five the directions part: the training number climbs without stopping to 0.8638 while validation falls to 0.8056. The gap between them is 0.0357 in the first round, changes sign in round two hundred and becomes 0.0582.

The source is visible: each round writes a larger gradient to the subscribers who remain on the wrong side, and the new weak learner is built on them; after a hundred rounds the sum is chasing individual subscribers. The number of rounds is a capacity knob and its limit is read from the held-out set: what comes after round ten is a gain for training and a loss for validation.

The Trade-off Between Learning Rate and Number of Rounds

The second knob is the learning rate. In how many rounds the same target is reached is counted separately for four rates; in this section the weak learner is a one-split tree.

TARGET, ROUNDS = 208 / 252, 300
print(f"{'rate':>6} {'to target':>11} {'best round':>11} {'best val':>11} "
      f"{'test there':>12} {'train at 300':>13}")
TRADEOFF = {}
for rate in (0.02, 0.05, 0.15, 0.45):
    trace = boost(rate, ROUNDS, 1, set(range(1, ROUNDS + 1)))
    first = next((t for t in range(1, ROUNDS + 1) if trace[t][1] >= TARGET), 0)
    best = max(range(1, ROUNDS + 1), key=lambda t: trace[t][1])
    TRADEOFF[rate] = (first, best, trace[best][1], trace[best][2])
    print(f"{rate:>6.2f} {first:>11} {best:>11} {trace[best][1]:>11.4f} "
          f"{trace[best][2]:>12.4f} {trace[ROUNDS][0]:>13.4f}")
print(f"target {TARGET:.4f} (208 of 252 subscribers), weak learner is a one-split tree")

  rate   to target  best round    best val   test there  train at 300
  0.02          79         204      0.8294       0.7897        0.8135
  0.05          30          84      0.8333       0.8016        0.8148
  0.15          10          36      0.8333       0.7976        0.8280
  0.45           4           8      0.8294       0.7976        0.8307
target 0.8254 (208 of 252 subscribers), weak learner is a one-split tree

The second column is the lesson’s measure. The 208 subscribers in the validation set are reached in 79 rounds with a rate of 0.02, in 30 with 0.05, in 10 with 0.15 and in 4 with 0.45. The product of rate and rounds is 1.58, 1.50, 1.50 and 1.80 respectively: about the same in all four. The two tuning variables are two faces of one knob and must be read together; “two hundred rounds” alone is not a tuning recipe.

Even though the product is constant, the result is not. The best validation number is 0.8333 at the middle two rates and 0.8294 at the ends; the test numbers of the same candidates wander between 0.7897 and 0.8016. The training number at round three hundred is 0.8135 at rate 0.02 and 0.8307 at 0.45: a large rate goes to the same place faster and memorizes more.

Budget, Cost and the Difference from Bagging

The last section combines the two knobs and the number of rounds in a single grid, reads the choice from validation, then compares the cost of boosting with the bagged ensemble of the previous lesson.

def split_count(d):
    return 0 if type(d) is not tuple else 1 + split_count(d[2]) + split_count(d[3])


def forest(seed, count, m, depth):          # the bagged ensemble of the previous lesson
    r, trees = 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][0], B_TRAIN[i][1], 1.0) for i in chosen],
                          depth, sorted(columns)))
    return trees


FOREST = forest(SEED, 41, 6, 4)
GRID, STOPS3 = {}, (5, 10, 25, 50, 100, 200)
print(f"{'rate':>6} {'depth':>9}" + "".join(f"{'round ' + str(t):>14}" for t in STOPS3))
for rate in (0.02, 0.05, 0.15, 0.45):
    for depth in (1, 2, 3):
        trace = boost(rate, 200, depth, set(STOPS3))
        for t in STOPS3:
            GRID[(rate, depth, t)] = trace[t][1:]
        print(f"{rate:>6.2f} {depth:>9}"
              + "".join(f"{trace[t][1]:>7.4f}/{trace[t][2]:.4f}" for t in STOPS3))
ORDER = [(a, d, t) for a in (0.02, 0.05, 0.15, 0.45) for d in (1, 2, 3) for t in STOPS3]
for name, column in (("from validation", 0), ("from test", 1)):
    e = max(GRID[k][column] for k in ORDER)
    a, d, t = next(k for k in ORDER if GRID[k][column] == e)
    print(f"choice {name:<15} rate={a:<5} depth={d}  rounds={t:<4} "
          f"validation {GRID[(a, d, t)][0]:.4f}  test {GRID[(a, d, t)][1]:.4f}")
e = max(GRID[k][0] for k in ORDER)
a, d, t = next(k for k in ORDER if GRID[k][0] == e)
print(f"boosting {t} rounds x depth {d} = {t * (2 ** d - 1)} splits, "
      f"test {GRID[(a, d, t)][1]:.4f}")
print(f"bagging  41 trees x depth 4 = {sum(map(split_count, FOREST))} splits, "
      f"test {sum((sum(value(x, b) > 0.5 for x in FOREST) * 2 > 41) == y for b, y in B_TEST) / len(B_TEST):.4f}")
print(f"candidates tried {7 + 4 * ROUNDS + len(ORDER)}, family number {GRID[(a, d, t)][1]:.4f}, "
      f"above baseline {GRID[(a, d, t)][1] - baseline(B_TEST):+.4f}")

  rate     depth       round 5      round 10      round 25      round 50     round 100     round 200
  0.02         1 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8254/0.7817 0.8254/0.7857
  0.02         2 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8135/0.7659 0.8294/0.7817 0.8214/0.7937
  0.02         3 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8214/0.7857 0.8135/0.7778 0.8254/0.7817
  0.05         1 0.8135/0.7579 0.8135/0.7579 0.8135/0.7579 0.8175/0.7857 0.8294/0.7976 0.8294/0.7937
  0.05         2 0.8135/0.7579 0.8135/0.7579 0.8294/0.7738 0.8175/0.7897 0.8294/0.7937 0.8175/0.7857
  0.05         3 0.8135/0.7579 0.8135/0.7579 0.8175/0.7817 0.8254/0.7778 0.8254/0.7817 0.8095/0.7857
  0.15         1 0.8135/0.7579 0.8254/0.7817 0.8254/0.7897 0.8333/0.7937 0.8175/0.8016 0.8135/0.8056
  0.15         2 0.8095/0.7579 0.8373/0.7738 0.8214/0.7937 0.8135/0.7897 0.8016/0.7778 0.8056/0.7817
  0.15         3 0.8254/0.7817 0.8056/0.7817 0.8095/0.7817 0.8056/0.7778 0.8016/0.7778 0.8016/0.7817
  0.45         1 0.8254/0.7857 0.8294/0.7897 0.8135/0.7897 0.8175/0.7937 0.8175/0.8016 0.8214/0.7897
  0.45         2 0.8135/0.7857 0.8214/0.7778 0.8254/0.7778 0.7976/0.7698 0.7857/0.7659 0.7976/0.7659
  0.45         3 0.8175/0.7778 0.7937/0.7738 0.7817/0.7540 0.7897/0.7659 0.7698/0.7619 0.7778/0.7738
choice from validation rate=0.15  depth=2  rounds=10   validation 0.8373  test 0.7738
choice from test       rate=0.15  depth=1  rounds=200  validation 0.8135  test 0.8056
boosting 10 rounds x depth 2 = 30 splits, test 0.7738
bagging  41 trees x depth 4 = 568 splits, test 0.7897
candidates tried 1279, family number 0.7738, above baseline +0.0159

The highest validation number the grid gives is 0.8373, and in a single cell: rate 0.15, depth 2, round 10. That candidate’s test number is 0.7738. Had it been read from the test set, rate 0.15, depth 1, round 200 would have been chosen and the number would be 0.8056. The difference is 0.0318, that is, eight subscribers. In the previous lesson the same difference was 0.0040, one subscriber.

The cause is the grid itself. In this lesson the number of triples measured on the validation set is 1,279; in the previous lesson it was 31. When this many candidates are tried on a set of 252 rows, the highest cell is the cell not of the best setting but of the luckiest setting. The course’s rule finds its full counterpart here: a model’s number cannot be read without writing how many candidates were tried to find that number.

The last two lines give the difference between the families as a number. Boosting chosen from validation builds 30 splits and gives 0.7738; the previous lesson’s bagged ensemble builds 568 splits and gives 0.7897. Boosting is nineteen times cheaper and four subscribers behind. The difference changing the family adds is −0.0159; the difference the budget inflates within the same grid is +0.0318. The budget’s difference is twice the family’s difference.

The family’s number is 0.7738, 0.0159 above the baseline. It is also below the single tree’s 0.7778 and is not corrected: this is the grid’s best validation cell.

Summary

• Over two hundred rounds the training number climbs from 0.7778 to 0.8638 while validation peaks at 0.8373 and falls to 0.8056; the gap between the two numbers changes sign and becomes 0.0582.
• The same validation target is reached in 79 rounds with a rate of 0.02, in 30 with 0.05, in 10 with 0.15 and in 4 with 0.45; the product of rate and rounds stays between 1.50 and 1.80.
• Even though the product is constant, the result is not: the best validation number of the end rates is 0.8294, of the middle ones 0.8333; a large rate memorizes training up to 0.8307 at round three hundred.
• The choice read from validation gives 0.7738 on the test set, the one read from the test set 0.8056; the difference is 0.0318 and 1,279 candidates were tried. In the previous lesson the same difference with 31 candidates was 0.0040.
• Boosting gives 0.7738 with 30 splits, bagging 0.7897 with 568 splits: the family difference is −0.0159, the budget difference +0.0318.

Next Step

Two combinations were tried and both were fed from the same family, the decision tree: bagging had independent trees vote, boosting stacked them into a sum. There is a third form: a second layer that takes the outputs of models from different families as its input. This immediately raises a question: from which set will the second layer be learned. If it is learned from the first layer’s outputs on the training set, the layer sees memorized outputs and the number inflates. The next lesson puts the three combinations side by side, counts the inflation and prints the number of subscribers on whom the ensembles err together.