Cross-Validation

All the numbers of the previous lesson were read from a single split. The difference between the two linear models came out as 0.0326 on the mean absolute error and 0.0823 on the mean squared error, and there was no measure of fluctuation next to these numbers. The question of whether another split would give the same ranking was not answered, because there was a single number at hand.

Cross-validation closes this gap: the remaining data is split into folds, each fold in turn becomes the measurement set, and instead of a single number a few numbers and their spread are obtained. The procedure itself and the discipline of preparing within the fold were established in the Data Preparation and Feature Engineering course; here they are assumed and not repeated. What this lesson measures is k itself: as the number of folds grows, how much the estimate fluctuates, how many trainings are done in return, and why the choice at the extreme — leaving a single row in each fold — is not always better.

• ET43. The pool is the train and validation sets of the Introduction to Machine Learning course: 1,008 rows. The 252 rows of the test set do not enter any fold and are used only once, to read the true number.
• ET44. The model is a linear classifier fitted to the 0/1 label by least squares; the output is cut at the 0.5 threshold. The reason it is small in scale is that it will be trained 1,008 times, and this is the model, not an imitation of a library.
• ET45. The model has no learned preparation step; the only thing learned within a fold is the model itself. The measure of the preparation discipline belongs to the Data Preparation and Feature Engineering course.
• ET46. The folds are assigned by the remainder of the row number divided by k in the shuffled pool; this way each row is a measurement row exactly once and the fold sizes part by at most one row.
• ET47. The unit of cost is the number of trainings and the number of rows processed (the total size of the training sets of the folds). These units do not change from run to run.
• ET48. The per-fold spread is the mean distance of the folds from their own mean and is the measure of variability of the Data Analytics curriculum. It is not the uncertainty of the estimate.
• ET49. The number of candidates tried in this lesson is one: the number of folds is not a hyperparameter but part of the measurement procedure and does not change the model itself.

What Moves When k Is Swept

# COMMON — MODEL: The FICTIONAL subscriber table of the Introduction to Machine Learning course
# is rebuilt with the same seed; the model is a linear classifier fitted to the 0/1 label by
# least squares.
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 d 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 - d * 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)


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)
TEST = K[1008:]
FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period",
          "zero_readings", "area_east", "area_west", "area_south"]
D = len(FIELDS) + 1


def solve(A, b):
    n = len(A)
    M = [list(A[i]) + [b[i]] for i in range(n)]
    for i in range(n):
        p = max(range(i, n), key=lambda r: abs(M[r][i]))
        M[i], M[p] = M[p], M[i]
        for r in range(n):
            if r != i:
                f = M[r][i] / M[i][i]
                for c in range(i, n + 1):
                    M[r][c] -= f * M[i][c]
    return [M[i][n] / M[i][i] for i in range(n)]


def fit(s, penalty=1e-4):
    A = [[0.0] * D for _ in range(D)]
    b = [0.0] * D
    for x in s:
        v = [1.0] + [float(x[a]) for a in FIELDS]
        y = x["suspicious"]
        for i in range(D):
            b[i] += v[i] * y
            for j in range(i, D):
                A[i][j] += v[i] * v[j]
    for i in range(D):
        for j in range(i):
            A[i][j] = A[j][i]
        if i:
            A[i][i] += penalty
    return solve(A, b)


def accuracy(w, s):
    d = 0
    for x in s:
        p = w[0] + sum(w[i + 1] * x[a] for i, a in enumerate(FIELDS))
        d += (1 if p >= 0.5 else 0) == x["suspicious"]
    return d / len(s)


POOL = K[:1008]
TRUE_NUMBER = accuracy(fit(POOL), TEST)
c = int(sum(x["suspicious"] for x in POOL) * 2 > len(POOL))
BASELINE = sum(x["suspicious"] == c for x in TEST) / len(TEST)
print(f"pool {len(POOL)} rows, test {len(TEST)} rows")
print(f"true number {TRUE_NUMBER:.4f}, baseline {BASELINE:.4f}")

pool 1008 rows, test 252 rows
true number 0.8056, baseline 0.7579

The true number is the number of the model learned from the whole pool on the test set: 0.8056, 0.0477 above the baseline. The job of cross-validation is to estimate this number without looking at the test set. Below, k is swept from 2 to 10 and the last row holds the choice at the extreme: 1,008 folds, that is, a single row in each fold.

def cross_validate(data, k):
    results = []
    for i in range(k):
        inner = [x for j, x in enumerate(data) if j % k != i]
        held = [x for j, x in enumerate(data) if j % k == i]
        results.append((accuracy(fit(inner), held), len(inner), held))
    return results


def mean(v):
    return sum(v) / len(v)


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


print(f"{'k':>5} {'mean':>9} {'spread':>8} {'trainings':>9} {'train rows':>14} "
      f"{'rows processed':>14} {'difference':>10} {'two-class folds':>16}")
for k in list(range(2, 11)) + [1008]:
    results = cross_validate(POOL, k)
    s = [q[0] for q in results]
    both = sum(1 for q in results if 0 < sum(x["suspicious"] for x in q[2]) < len(q[2]))
    print(f"{k:>5} {mean(s):>9.4f} {spread(s):>8.4f} {k:>9} {results[0][1]:>14} "
          f"{1008 * (k - 1):>14} {mean(s) - TRUE_NUMBER:>+10.4f} {both:>16}")

    k      mean   spread trainings     train rows rows processed difference  two-class folds
    2    0.8135   0.0099         2            504           1008    +0.0079                2
    3    0.8165   0.0014         3            672           2016    +0.0109                3
    4    0.8115   0.0278         4            756           3024    +0.0060                4
    5    0.8185   0.0239         5            806           4032    +0.0129                5
    6    0.8145   0.0237         6            840           5040    +0.0089                6
    7    0.8175   0.0243         7            864           6048    +0.0119                7
    8    0.8204   0.0359         8            882           7056    +0.0149                8
    9    0.8175   0.0286         9            896           8064    +0.0119                9
   10    0.8194   0.0280        10            907           9072    +0.0139               10
 1008    0.8175   0.3863      1008           1007        1015056    +0.0119                0

The mean column wanders between 0.8115 and 0.8204: the total movement among nine different values of k is 0.0089. The difference column shows that all of them are positive; cross-validation systematically gives a number above the true number, and this is in the same direction as the +0.0149 deviation measured with in-fold preparation in the Data Preparation and Feature Engineering course. The cause is not leakage but the pool being seen again in every round.

The expected pattern is that the training set grows as k grows and the estimate approaches the true number. The train rows column shows this growth: from 504 to 907, then to 1,007. But the difference column does not follow this pattern. The closest estimate to the truth comes from k=4 (+0.0060) and the farthest one from k=8 (+0.0149). The ranking in between comes more from the chance of how the folds were divided than from the size of the training set. Raising k from 4 to 10 did not improve the estimate; it made the procedure do three times more training.

The spread column cannot be read alone either. 0.0014 at k=3, 0.0359 at k=8 — a difference of about twenty-six times. The spread of three numbers and the spread of ten numbers are each noisy on their own; the spread is not an estimate of uncertainty but a rough summary of the distribution across the folds.

The irregularity of the difference column comes from the superposition of two tendencies, and the two pull in opposite directions. The first is pessimism: when k is small, the model learns from fewer rows than the model that will be put to use. At k=2 the training is 504 rows, that is, half of the rows seen by the model that will finally be built; the measured number is the number of that weak model. The second is optimism: each row of the pool is in training in k−1 of the k rounds and in measurement in one, and the same 1,008 rows are reused from start to finish. As k grows, the first tendency weakens and the second stays as it is. Their sum does not cancel at any value of k, and which k will fall close to the truth cannot be known in advance — marking the closest row in the table is possible only after the test set has been read, and that removes the very reason for cross-validation to exist.

The Price Paid by the Extreme Choice

The last row is leave-one-out: each row in turn becomes the measurement set alone, and the model is learned from the remaining 1,007 rows. The estimate is 0.8175, 0.0119 above the truth. This number is exactly the same as the number given by k=7 and k=9, and it is farther from the truth than the one given by k=4.

Its cost is read in three columns. 1,008 trainings are done and a total of 1,015,056 rows are processed; 111.89 times the 9,072 rows processed by k=10. The difference gained is a 0.0020 shift in the estimate.

The second price is in the spread column: 0.3863. This number is not uncertainty. In a one-row fold the accuracy can only be 0 or 1, so the spread necessarily settles at $\sqrt{p(1-p)}$; here $p = 0.8175$ and $\sqrt{0.8175 \times 0.1825} = 0.3863$. The number says nothing about the stability of the model; it only rewrites the mean itself.

The third price is in the last column: the number of two-class folds is zero. A one-row fold carries a single label, so in that fold the counts of true positives, false positives and false negatives cannot all be found at once. Precision, recall, the F1 score and the area under the curve cannot be computed per fold. When k is between 2 and 10, every fold carries both classes and all of these measures can be computed per fold. If one is working with a measure other than accuracy, leave-one-out ceases to be an option.

Dependence on the Shuffle

While measuring the effect of the number of folds, one thing was held fixed: the order of the pool. Since the fold assignment depends on the row number, had the pool been shuffled differently, the estimate would also have changed. Below, the same values of k are measured again with three separate shuffles.

print(f"{'k':>5} " + " ".join(f"{'seed ' + str(i + 1):>9}" for i in range(3))
      + f" {'spread':>9}")
for k in (2, 4, 10, 1008):
    m = []
    for i in range(3):
        h = shuffle(POOL, SEED + 300 + i * 17)
        m.append(mean([q[0] for q in cross_validate(h, k)]))
    print(f"{k:>5} " + " ".join(f"{q:>9.4f}" for q in m) + f" {spread(m):>9.4f}")

    k    seed 1    seed 2    seed 3    spread
    2    0.8145    0.8175    0.8125    0.0020
    4    0.8194    0.8194    0.8185    0.0005
   10    0.8194    0.8164    0.8164    0.0014
 1008    0.8175    0.8175    0.8175    0.0000

The zero in the last row is the real advantage of leave-one-out. Because the folds are single rows, shuffling does not change the folds; the same 1,008 folds, even if not in the same order, are the same set. The estimate is completely deterministic and the choice of seed cannot move the result. The same measurement at k=2 wanders between 0.8125 and 0.8175 across the three shuffles, a spread of 0.0020.

This also says when leave-one-out is worth what it costs: when data is scarce, while the share of a single shuffle in moving the estimate is large, and when the measure is a number that can be collected from a single row per fold, like accuracy. With a pool of 1,008 rows none of these conditions holds, and a choice between k=4 and k=10 gives the same estimate tens of thousands of times cheaper.

The size of the shuffle spreads is also a warning: the 0.0020 movement of k=2 with the shuffle is one fifteenth of the 0.0326 difference measured between the two linear models in the previous lesson. When comparing two models with cross-validation, the difference between them has to be larger than this movement.

Summary

• When the number of folds is swept from 2 to 10, the estimate stays between 0.8115 and 0.8204; the total movement is 0.0089 and all nine values are above the true number (0.8056).
• The estimate does not improve regularly with k: the closest number to the truth comes from k=4 (+0.0060), the farthest from k=8 (+0.0149); despite the growth of the training set, the ranking comes from the chance of how the folds were divided.
• Leave-one-out gives 0.8175 and processes 1,015,056 rows with 1,008 trainings; in return for 111.89 times the work of k=10, it moves the estimate by 0.0020.
• The per-fold spread of leave-one-out is 0.3863 and this number is not uncertainty but the value $\sqrt{p(1-p)}$; moreover, because none of the 1,008 folds carries both classes, precision, recall and the area under the curve cannot be computed per fold.
• The real advantage of leave-one-out is that it is deterministic: its spread over three separate shuffles is exactly zero, that of k=2 is 0.0020.

Next Step

The number of candidates tried in this lesson is one. The model was built in a single form, no hyperparameter was swept, and the number of folds was treated as part of the measurement procedure, not as a tuning choice. The rule of the course has not been paid yet: a model’s number cannot be read without writing how many candidates were tried to find that number. The next lesson does that calculation — three search procedures are compared with the same budget, and as the number of candidates rises from 1 to 200, the gap that opens between the best number on the validation set and the number of the same candidate on the test set is printed. The difference added by changing the family and the difference inflated by the budget stand side by side there.