Fitting with Cross-Validation

The previous lesson bound the preparation chain to an object and guaranteed that the whole chain was learned from the training set only. The measurement was still read from a single split: 756 rows of training, 252 rows of testing. Those 252 rows were used once and gave a single number. Another split would have given another number, and there was no way of saying which one was right.

Cross-validation answers this problem: the data left in hand is divided into folds, each fold becomes the measurement set in turn, the rest becomes the training set, and in the end several numbers and their spread are obtained. When the preparation chain enters the work a new question arises, and the second rule of the course takes its final form here: is the chain learned once outside the folds, or again inside each fold. The two procedures give two separate numbers; this lesson measures which one comes out close to the actual number on the held-out set.

• FS36. The cross-validation pool is the training and validation sets of the Introduction to Machine Learning course: 1,008 rows. The 252 rows of the test set enter no fold, no preparation step and no selection.
• FS37. The number of folds is four; in each fold 252 rows become the measurement set, that is, the same size as the test set. The number of folds was not chosen by looking at the result.
• FS38. The chain is the chain of the previous lesson with the scaling step removed: imputation, target encoding, feature selection. The contribution of scaling in the decision tree was measured there as exactly zero.
• FS39. The number of steps learned outside the folds is varied from 0 to 3. Zero means the whole chain is learned inside the folds.
• FS40. The actual number is the number for which the chain is learned from 1,008 rows and measured on the test set: it is the single number of this course that is read once.
• FS41. The spread is the mean distance of the four fold numbers from their own average and is the measure of dispersion of the Data Analytics curriculum.
• FS42. The tuning budget calculation is not the subject of this lesson and is left to the Supervised Learning course; no model tuning is chosen here, and the model is the decision tree of depth 6 that stays fixed throughout the course.

Outside the Folds and Inside the Folds

# COMMON — MODEL: the FICTIONAL subscriber table of the Introduction to Machine Learning course is rebuilt with the same seed;
# the model is a decision tree of depth 6. The only new column left from the previous lesson is per_person.
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 = {"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),
         "region_name": k["region"][0]}
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)

BASE = ["mean_consumption", "volatility", "household", "satisfaction", "period",
        "zero_readings", "area_north", "area_south", "area_east", "area_west", "area_central"]
BASE_FIELDS = BASE + ["per_person"]
for x in DATA:
    x["per_person"] = round(x["mean_consumption"] / x["household"], 3)


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, fields, min_size=2):
    p, best = sum(x["suspicious"] for x in rows) / len(rows), 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, fields, min_size),
            "right": tree(best[4], depth - 1, fields, 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)

The pipeline is the object of the previous lesson. This time the fit method takes two extra values: the source outside the folds and the number of steps that will learn from that source. When zero is given, the whole chain learns from the inner fold set it is given.

for x in DATA:
    r = rng(SEED + 61000 + x["id"])
    r(), r()
    x["kw_seal"] = int(r() < (0.42 if x["suspicious"] else 0.10))
    r = rng(SEED + 21000 + x["id"])
    x["tariff_code"] = (24 * [b[0] for b in REGION].index(x["region_name"])
                        + 4 * (x["household"] - 1) + int(r() * 4))
    x["satisfaction"] = None if r() < 0.08 else x["satisfaction"]
POOL = BASE_FIELDS + ["kw_seal", "tariff_target"]


class Imputer:
    name = "imputation"

    def fit(self, rows):
        v = sorted(x["satisfaction"] for x in rows if x["satisfaction"] is not None)
        self.state = {"median": v[len(v) // 2]}

    def apply(self, rows):
        for x in rows:
            if x["satisfaction"] is None:
                x["satisfaction"] = self.state["median"]


class TargetEncoder:
    name = "target encoding"

    def fit(self, rows):
        g, self.overall = {}, sum(x["suspicious"] for x in rows) / len(rows)
        for x in rows:
            g.setdefault(x["tariff_code"], []).append(x["suspicious"])
        self.state = {k: sum(v) / len(v) for k, v in g.items()}

    def apply(self, rows):
        for x in rows:
            x["tariff_target"] = round(self.state.get(x["tariff_code"], self.overall), 4)


class Selector:
    name = "selection"

    def __init__(self, pool):
        self.pool = pool

    def fit(self, rows):
        g0, self.state = gini(rows), []
        for f in self.pool:
            values, top = sorted({x[f] for x in rows}), 0.0
            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)) >= 20:
                    top = max(top, g0 - (len(left) * gini(left)
                                         + len(right) * gini(right)) / len(rows))
            if top >= 0.004:
                self.state.append(f)

    def apply(self, rows):
        pass


class Pipeline:
    def __init__(self, steps, depth=6):
        self.steps, self.depth = steps, depth

    def fit(self, train, outside_source=None, outside_count=0):
        train = [dict(x) for x in train]
        outside = [dict(x) for x in (outside_source or [])]
        for i, step in enumerate(self.steps):
            if i < outside_count:
                step.fit(outside)
                step.apply(outside)
            else:
                step.fit(train)
            step.apply(train)
        self.model = tree(train, self.depth, self.steps[-1].state)
        self.train_score = accuracy(self.model, train)
        return self

    def measure(self, rows):
        rows = [dict(x) for x in rows]
        for step in self.steps:
            step.apply(rows)
        return accuracy(self.model, rows)


def chain(pool=None):
    return [Imputer(), TargetEncoder(), Selector(pool or POOL)]


REST, FOLDS = K[:1008], 4


def split_fold(data, i, k=FOLDS):
    n = len(data) // k
    return ([x for j, x in enumerate(data) if not i * n <= j < (i + 1) * n],
            data[i * n:(i + 1) * n])


def cross_validate(outside_count):
    scores = []
    for i in range(FOLDS):
        inner, outer = split_fold(REST, i)
        scores.append(Pipeline(chain()).fit(inner, REST, outside_count).measure(outer))
    return scores


def average(scores):
    return sum(scores) / len(scores)


def spread(scores):
    m = average(scores)
    return (sum((q - m) ** 2 for q in scores) / len(scores)) ** 0.5


ACTUAL = Pipeline(chain()).fit(REST).measure(TEST)
SINGLE = Pipeline(chain()).fit(K[:756]).measure(K[756:1008])
print(f"{'outside folds':<14} " + " ".join(f"{'fold ' + str(i + 1):>7}" for i in range(FOLDS))
      + f" {'average':>9} {'spread':>8} {'diff':>8}")
for d in range(4):
    scores = cross_validate(d)
    print(f"{'steps: ' + str(d):<14} " + " ".join(f"{q:>7.4f}" for q in scores)
          + f" {average(scores):>9.4f} {spread(scores):>8.4f} {average(scores) - ACTUAL:>+8.4f}")
print(f"\nsingle split 756/252 {SINGLE:.4f}, diff {SINGLE - ACTUAL:+.4f}")
print(f"actual number on the test set {ACTUAL:.4f}, baseline {baseline(REST, TEST):.4f}")

outside folds   fold 1  fold 2  fold 3  fold 4   average   spread     diff
steps: 0        0.7976  0.7738  0.7897  0.8254    0.7966   0.0187  +0.0149
steps: 1        0.7976  0.7738  0.7897  0.8254    0.7966   0.0187  +0.0149
steps: 2        0.8016  0.8135  0.8333  0.7976    0.8115   0.0139  +0.0298
steps: 3        0.8016  0.8056  0.8452  0.7897    0.8105   0.0209  +0.0288

single split 756/252 0.8254, diff +0.0437
actual number on the test set 0.7817, baseline 0.7579

The last column is the answer of the lesson. When the whole chain is learned inside the folds, cross-validation gives 0.7966 and stays 0.0149 above the actual number. When the whole chain is learned outside the folds it gives 0.8105 and the deviation rises to 0.0288, that is, almost doubles. Preparation inside the folds is the procedure that comes out close to the actual number.

Where the jump comes from can be seen in the middle rows. When imputation moves outside the folds nothing changes; the moment target encoding moves outside the folds the average jumps from 0.7966 to 0.8115. Selection adds to this a drop below the measurement resolution. The whole cost of preparing outside the folds comes from a single step, and that step is the one that uses the label.

This has the same structure as the table in the previous lesson and arises for the same reason. Target encoding learned outside the folds mixes the labels of the measurement rows of each fold into the number those rows will see. As the number of folds grows the share of the measurement rows falls and the inflation shrinks; as it falls the inflation grows. For this reason a cross-validation number prepared outside the folds cannot be read independently of its own number of folds.

The sign of the deviation also deserves attention. Preparation inside the folds exceeds the actual number by 0.0149, that is, it is still optimistic; the reason is not leakage but the chain looking at the data once more in every fold. Cross-validation does not measure the actual number, it measures an interval around the actual number.

The Single Number of a Single Split

The single split gives 0.8254 and is 0.0437 away from the actual number. This number equals the highest of the four fold numbers prepared inside the folds. The single split did not make a wrong calculation; it happened to land on one end of this interval, and since it is a single number it could not say which end it landed on.

The spread of the four folds is 0.0187. A number read from one split carries a fluctuation of this size, and separating a contribution of 0.0119 from this fluctuation is impossible with a single split. For this reason the contributions of 0.0119 measured in the first three lessons of the course were written as “measured and could not be told apart from zero”.

What cross-validation adds is not a bigger number but an interval next to the number. And that interval is the true interval only when the preparation chain is learned inside the folds.

Summary

• The actual number on the test set is 0.7817; preparation inside the folds gives 0.7966 (deviation 0.0149), preparation outside the folds gives 0.8105 (deviation 0.0288).
• The whole deviation comes from a single step: when imputation moves outside the folds the number does not change, when target encoding moves outside the folds the average jumps from 0.7966 to 0.8115.
• A cross-validation number prepared outside the folds cannot be read independently of the number of folds, because the size of the inflation depends on the share of the measurement rows.
• The 0.8254 given by the single split equals the highest of the four folds and is 0.0437 away from the actual number; a single number cannot say which end it landed on.
• The spread of the folds is 0.0187; with a fluctuation of this size, a contribution of 0.0119 cannot be told apart from zero with a single split.

Course Wrap-Up

The accounts of twelve lessons stand in a single table, and every number was read from its own lesson. The before-decision and after-decision columns were always measured on the held-out set; the baseline is 0.7579 in all the lessons.

The rows of the second and sixth preparation lessons are read from the gradient-based linear model, the remaining ten rows from the fixed decision tree of the course; the row of the fifth preparation lesson is the accuracy column, and the same decision raises the number of suspicious subscribers caught from 21 to 33.

The first rule of the course is the table itself: a preparation step exists to the extent of its contribution measured on the held-out set. In the contribution column four rows are zero or negative. If these four had not been measured they would have stayed in the set, and all four would have been defended with a reasonable justification.

The second rule of the course is read in the last two rows: every preparation step is learned from the training set only and applied to the held-out set. The minus signs in those two rows are not a loss but an inflation taken back; the pipeline lowered the number by 0.0476, preparation inside the folds by 0.0139, and none of the numbers that fell came from learning. Before looking at the sign of a measured contribution, one has to look at where it comes from.

One account opened at the start of the course remains. The first lesson wrote that every look at the test set accumulates a selection share and left the accounting of the share to the end of the course. The table itself gives that account: each of the twelve rows carries two numbers, that is, the test set was looked at at least 24 times, and with the sweeps inside the lessons this number is much higher. For this reason no number in the table is an estimate of generalization; all of them are a comparison. The actual number can only be read on a set that was never touched during this course, and that set no longer exists.

In twelve lessons the features were built and the contribution of each step was measured on the held-out set. But throughout all these measurements the model was always chosen from the same two or three families: a decision tree of depth 6, beside it a gradient-based linear model and a distance-based method. What the family itself adds was never asked; why the depth is six, why the number of neighbors is fifteen and from which set these numbers should be read was never measured. The next course, Supervised Learning, takes up these questions.