Overfitting and Underfitting

The previous lesson measured a decision tree on three sets and found three numbers, but it chose the depth of the tree without justification. Depth 6 was not a preference but a gap. Depth is the capacity of the tree: it determines how many distinct rules it can learn and into how many pieces it can split the set. Capacity alone is neither good nor bad; it moves two numbers at once, and it moves them in opposite directions.

This lesson raises capacity from 1 to 14, prints the training and held-out numbers side by side at every step and writes down the point where the two diverge. The two ends of the divergence are two separate deteriorations: underfitting when capacity is not enough, overfitting when capacity is too much. The test set will not be looked at at all in this lesson; the validation set is used as the held-out set.

• GE9. The dataset, the label and the split continue unchanged from the previous lesson: 1,260 subscribers, 756 training, 252 validation, 252 test, seed 20260218. The label is fictional.
• GE10. Capacity is measured by two numbers: the depth of the tree and the number of leaves. The number of leaves gives how many distinct regions the model splits the set into.
• GE11. The baseline is a tree with a single leaf: the procedure that does not split at all and tells everyone the most frequent class of the training set. It is the zeroth step of the capacity series.
• GE12. The held-out set is the validation set. The test set is not opened in this lesson; by the rule of the previous lesson it is looked at once, at the close.
• GE13. The minimum leaf size is a second capacity knob: the smallest number of observations a leaf may fall to. The default is 2.
• GE14. The learning curve is not drawn, it is printed as numbers: the values the two numbers take while the training set is enlarged make a table.
• GE15. The held-out set has 252 rows; one subscriber is worth 0.0040 accuracy. Differences below two points are therefore not counted as evidence of a ranking.

Capacity Rises, the Two Numbers Diverge

The setup is the same as in the previous lesson and produces the same dataset with the same seed. A single addition is made on top of it: a leaf counter.

# generalization.py — MODEL: the regional measurement network (a fictional setup) of the Data Analytics curriculum is generated with the same
# seed; readings are summarized at the subscriber level and a FICTIONAL illicit-use/fault suspicion label
# is added on top.
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 = []
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})
READINGS = {}
for k in SUBSCRIBERS:
    r = rng(SEED + 7000 + k["id"])
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        READINGS.setdefault(k["id"], []).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()

DATA = []
for k in SUBSCRIBERS:
    v = READINGS.get(k["id"])
    if v is None:
        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 = {"id": k["id"], "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["reg_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)

FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period",
          "zero_readings", "reg_north", "reg_south", "reg_east", "reg_west", "reg_central"]


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:]


def gini(rows):
    p = sum(x["suspicious"] for x in rows) / len(rows) if rows else 0.0
    return 2 * p * (1 - p)


def tree(rows, depth, min_size=2):
    p = sum(x["suspicious"] for x in rows) / len(rows)
    best = None
    if depth and len(rows) >= 2 * min_size and 0.0 < p < 1.0:
        for f in FIELDS:
            values = sorted({x[f] for x in rows})
            for v in (values[1:] if len(values) < 10 else
                      [values[int(i * len(values) / 10)] for i in range(1, 10)]):
                left = [x for x in rows if x[f] < v]
                right = [x for x in rows if x[f] >= v]
                if min(len(left), len(right)) < min_size:
                    continue
                k = gini(rows) - (len(left) * gini(left) + len(right) * gini(right)) / len(rows)
                if best is None or k > best[0]:
                    best = (k, f, v, left, right)
    if best is None or best[0] <= 1e-9:
        return {"prediction": int(p > 0.5)}
    return {"field": best[1], "threshold": best[2],
            "left": tree(best[3], depth - 1, min_size),
            "right": tree(best[4], depth - 1, min_size)}


def predict(node, x):
    while "prediction" not in node:
        node = node["left"] if x[node["field"]] < node["threshold"] else node["right"]
    return node["prediction"]


def accuracy(node, rows):
    return sum(predict(node, x) == x["suspicious"] for x in rows) / len(rows)


def baseline(train, rows):
    c = int(sum(x["suspicious"] for x in train) * 2 > len(train))
    return sum(x["suspicious"] == c for x in rows) / len(rows)


def leaves(node):
    return 1 if "prediction" in node else leaves(node["left"]) + leaves(node["right"])


print(f"{'capacity':>10} {'leaves':>7} {'train':>8} {'held-out':>9} {'difference':>10}")
print(f"{'baseline':>10} {1:>7} {baseline(TRAIN, TRAIN):>8.4f} {baseline(TRAIN, VAL):>9.4f} "
      f"{baseline(TRAIN, TRAIN) - baseline(TRAIN, VAL):>+10.4f}")
for dp in (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14):
    m = tree(TRAIN, dp)
    e, h = accuracy(m, TRAIN), accuracy(m, VAL)
    print(f"{'depth ' + str(dp):>10} {leaves(m):>7} {e:>8.4f} {h:>9.4f} {e - h:>+10.4f}")

  capacity  leaves    train  held-out difference
  baseline       1   0.7778    0.8135    -0.0357
   depth 1       2   0.7778    0.8135    -0.0357
   depth 2       4   0.8016    0.8214    -0.0198
   depth 3       8   0.8135    0.8135    +0.0000
   depth 4      16   0.8201    0.8175    +0.0026
   depth 5      30   0.8360    0.8095    +0.0265
   depth 6      46   0.8466    0.7897    +0.0569
   depth 7      64   0.8611    0.7698    +0.0913
   depth 8      81   0.8770    0.7778    +0.0992
  depth 10     112   0.9061    0.7698    +0.1362
  depth 12     133   0.9299    0.7619    +0.1680
  depth 14     139   0.9352    0.7302    +0.2050

The third column is one-directional: as capacity rises, the training accuracy rises uninterruptedly from 0.7778 to 0.9352. This column is not a measure of success but a measure of capacity — the more splits the model is allowed, the more of the data it has seen it memorizes, and the column rises under every condition.

The fourth column is two-directional. The held-out accuracy peaks at 0.8214 at depth 2, then begins to fall and drops to 0.7302 at depth 14. The fifth column is the difference between the two and gives where the divergence begins: the difference crosses zero at depth 3, grows after depth 5 without ever turning back and reaches 0.2050 at depth 14. The point where the divergence begins lies between depth 4 and 5: at the fourth step the difference is still 0.0026, while at the fifth it rises to 0.0265 and at the sixth to 0.0569.

Read together with the baseline, the table says something harsher. On the held-out set the baseline is 0.8135. Only four of the eleven capacities — depth 1, 2, 3 and 4 — reach this number or exceed it; two of them match it exactly, two exceed it and the best beats the baseline by 0.0079. From depth 5 on, every model is below the baseline, and what is more, the training column is still rising. At depth 14, the moment the model reads 0.9352 on the training set, it is 8.3 points worse than saying “none is suspicious” on the held-out set.

The leaves column shows how the memorization grows. At depth 14 the tree has 139 leaves and the training set has 756 rows: an average of 5.4 subscribers per leaf. A rule built by looking at five subscribers classifies those five subscribers correctly and says nothing about anything else.

The Rule the Tree Builds

Where the divergence comes from becomes visible when one looks at what the model has learned. The code below writes out the rules of the tree at the top explicitly and counts how many subscribers the leaves of the tree at the bottom looked at.

def rules(node, rows, path=""):
    if "prediction" in node:
        print(f"  {path or '(no split)':<50} {len(rows):>4} subscribers -> {node['prediction']}")
        return
    f, v = node["field"], node["threshold"]
    rules(node["left"], [x for x in rows if x[f] < v], f"{path}{f} < {v} ")
    rules(node["right"], [x for x in rows if x[f] >= v], f"{path}{f} >= {v} ")


print("rules of the depth 2 tree")
rules(tree(TRAIN, 2), TRAIN)


def sizes(node, rows, c):
    if "prediction" in node:
        c.append(len(rows))
        return
    f, v = node["field"], node["threshold"]
    sizes(node["left"], [x for x in rows if x[f] < v], c)
    sizes(node["right"], [x for x in rows if x[f] >= v], c)


c = []
sizes(tree(TRAIN, 14), TRAIN, c)
c.sort()
print(f"\ndepth 14: {len(c)} leaves, smallest {c[0]}, median {c[len(c) // 2]}, "
      f"largest {c[-1]} subscribers")
print(f"leaves that set a rule after seeing fewer than 5 subscribers: {sum(1 for n in c if n < 5)}")
print(f"training subscribers covered by these leaves: {sum(n for n in c if n < 5)}")

rules of the depth 2 tree
  volatility < 11.69 mean_consumption < 18.54         262 subscribers -> 0
  volatility < 11.69 mean_consumption >= 18.54        249 subscribers -> 0
  volatility >= 11.69 reg_east < 1                    185 subscribers -> 0
  volatility >= 11.69 reg_east >= 1                    60 subscribers -> 1

depth 14: 139 leaves, smallest 2, median 3, largest 141 subscribers
leaves that set a rule after seeing fewer than 5 subscribers: 112
training subscribers covered by these leaves: 300

Three of the four leaves of the tree at the top say the same thing as the baseline. The only place where the model departs from the baseline is the 60-row leaf made up of east subscribers whose volatility is above 11.69 m³. The whole of the 0.0079 gain on the held-out set comes from this single rule. A model beating the baseline is often not a matter of beating the baseline everywhere but of finding the narrow region where the baseline is wrong.

The tree at the bottom is the opposite. The median of the hundred and thirty-nine leaves looks at three subscribers, 112 leaves have seen fewer than five subscribers, and these leaves cover 300 rows of the training set, that is, 40%. A large part of the 0.9352 in the training column consists of knowing those three subscribers correctly with rules drawn from three subscribers. On the held-out set these rules have no counterpart.

The Two Deteriorations Have Separate Signatures

The two ends of the table are two separate deteriorations and their symptoms do not mix.

Underfitting is in the upper rows. The depth 1 tree builds two leaves, but both leaves say the same class: the tree has split, the model has not. Its numbers are exactly the same as the baseline (0.7778 and 0.8135). Its signature is this: the training number sticks to its own baseline. If the model cannot explain even the data it has seen, it cannot explain the data it has not seen at all, and to understand this one does not even need to look at the held-out set.

Overfitting is in the lower rows. Its signature requires reading two numbers together: a high training number, a low held-out number, a large difference. On its own, 0.9352 says nothing — it is neither good nor bad, because it cannot be interpreted unless it is written with which capacity produced it.

The sign of the difference is not enough on its own either. At depth 1 the difference looks “safe” at -0.0357, yet that row is the row where the model has learned nothing. A negative difference is not good news; it is often news of underfitting. Three numbers are read together: baseline, training, held-out.

The Measure of the Correction

There are two known corrections for overfitting: enlarging the training set and restricting capacity. Both can be measured. The code below fixes the depth at 12 and changes first the training set, then the minimum leaf size.

print("training set grows, capacity fixed (depth 12)")
print(f"{'train rows':>13} {'leaves':>7} {'train':>8} {'held-out':>9} {'difference':>10}")
for n in (100, 200, 400, 756):
    m = tree(TRAIN[:n], 12)
    e, h = accuracy(m, TRAIN[:n]), accuracy(m, VAL)
    print(f"{n:>13} {leaves(m):>7} {e:>8.4f} {h:>9.4f} {e - h:>+10.4f}")

print("\ncapacity is restricted, training set fixed (depth 12, leaf minimum)")
print(f"{'leaf min_size':>13} {'leaves':>7} {'train':>8} {'held-out':>9} {'difference':>10}")
for z in (2, 5, 10, 20, 40, 80):
    m = tree(TRAIN, 12, z)
    e, h = accuracy(m, TRAIN), accuracy(m, VAL)
    print(f"{z:>13} {leaves(m):>7} {e:>8.4f} {h:>9.4f} {e - h:>+10.4f}")

training set grows, capacity fixed (depth 12)
   train rows  leaves    train  held-out difference
          100      15   0.9600    0.7381    +0.2219
          200      34   0.9500    0.7500    +0.2000
          400      68   0.9450    0.7659    +0.1791
          756     133   0.9299    0.7619    +0.1680

capacity is restricted, training set fixed (depth 12, leaf minimum)
leaf min_size  leaves    train  held-out difference
            2     133   0.9299    0.7619    +0.1680
            5      81   0.8624    0.7540    +0.1085
           10      44   0.8307    0.7937    +0.0370
           20      23   0.8148    0.7500    +0.0648
           40      13   0.8042    0.7897    +0.0146
           80       7   0.7937    0.8135    -0.0198

The first table is the learning curve, and its direction is right, its strength limited. When the training set is raised from 100 to 756 rows, that is, by a factor of 7.6, the difference falls from 0.2219 to 0.1680: only a quarter of the initial gap has closed. The held-out number rises from 0.7381 to 0.7619 but is still 5.2 points below the baseline of 0.8135. Adding data pays part of the debt of an overchosen capacity, not all of it. The second reading of the same curve is the training column: it falls from 0.9600 to 0.9299, because memorizing more rows with the same capacity is harder.

The second table touches capacity directly, and its two ends are clear. When the minimum leaf size is raised from 2 to 80, the number of leaves falls from 133 to 7 and the difference from 0.1680 to -0.0198. The last row is striking: when capacity is restricted enough, the model reads exactly 0.8135 on the held-out set, that is, it turns into the baseline itself. Restricting capacity to correct overfitting, when carried far enough, ends in underfitting. The two deteriorations bound the usable region from both sides.

The rows in between are read with care. The held-out column falls from 0.7937 to 0.7500 and returns to 0.7897; these are swings of 11 and 10 subscribers and stay within the margin of variation measured in the Statistical Analysis and Exploratory Data Analysis course. To count the ranking in the middle of this column as evidence of capacity would be, once again, to take a selected number for performance. The reliable reading is at the two ends and in the difference column.

Summary

• As capacity rises the training accuracy rises in one direction (from 0.7778 to 0.9352), the held-out accuracy peaks at 0.8214 at depth 2 and falls to 0.7302; the difference between the two numbers widens from -0.0357 to +0.2050 and the divergence begins between depth 4 and 5.
• Of the eleven capacities only four match the baseline of 0.8135 on the held-out set; after depth 5 every model is below the baseline, and what is more, the training column keeps rising.
• The signature of underfitting is the training number sticking to its own baseline and it is seen without looking at the held-out set; the signature of overfitting becomes visible only when two numbers are read together.
• Enlarging the training set by a factor of 7.6 lowers the difference from 0.2219 to 0.1680, that is, closes a quarter of the gap; adding data does not pay the whole debt of an overchosen capacity.
• Raising the minimum leaf size from 2 to 80 lowers the number of leaves from 133 to 7 and the difference to -0.0198, and the model turns into exactly the baseline on the held-out set: the correction of overfitting, when it goes far enough, ends in underfitting.

Next Step

In this lesson the difference was measured on a single training set. Yet that set of 756 rows is one sample drawn from among 1,260 subscribers; on another draw another tree would have been built. This is what lies beneath overfitting: the model produced by a high-capacity procedure swings a lot when the training sample changes; a low-capacity procedure always stands in the same place but is always wrong in the same place. The next lesson splits the error into these two components — systematic deviation and the swing from sample to sample — and counts each separately by building multiple training sets with sampling with replacement.