Model Selection and Cross-Validation: Pick the Right Model Fairly

Every battery degrades, and a company that sells battery packs wants to predict the remaining capacity after a given number of charge cycles. Should it fit a straight line, a gentle curve or a wiggly eleventh-degree polynomial? Training error will always vote for the wiggliest, because a flexible model can bend toward every point. The question that matters is which model will do best on batteries it has not measured yet. Cross-validation is the tool for answering it when you do not have data to spare.

Why one split is not enough

A single validation set gives one noisy number. If you only have 25 measurements, a handful of lucky or unlucky points in the validation part can flip which model looks best. K-fold cross-validation reduces that luck. Split the data into k parts (folds), then k times train on k-1 folds and score on the remaining one. Every row is used for validation exactly once, and you get k scores whose average is steadier than any single one, and whose spread tells you how much to trust it.

The experiment below generates a battery-fade curve (a slow decline that speeds up) with measurement noise from a seeded generator, then fits polynomials of different degrees by solving the normal equations with a small Gaussian-elimination routine, so it needs no libraries. For each degree it reports the training error and the cross-validated error across five folds.

# Battery fade: capacity left (%) after N charge cycles. Which polynomial degree fits best?
class Lcg:
    def __init__(self, seed):
        self.state = seed
    def next(self):
        self.state = (1103515245 * self.state + 12345) % (2 ** 31)
        return self.state / 2 ** 31

rng = Lcg(11)
cycles = [i * 25 for i in range(0, 25)]                       # 0 .. 600 cycles
# true curve falls slowly, then faster; plus measurement noise of about +/- 1.5 points
data = [(c, 100 - 0.01 * c - 0.00006 * c * c + (rng.next() - 0.5) * 3) for c in cycles]
for i in range(len(data) - 1, 0, -1):                          # seeded shuffle
    j = int(rng.next() * (i + 1))
    data[i], data[j] = data[j], data[i]

def solve(A, rhs):
    """Gaussian elimination with partial pivoting."""
    n = len(A)
    M = [row[:] + [r] for row, r in zip(A, rhs)]
    for col in range(n):
        piv = max(range(col, n), key=lambda r: abs(M[r][col]))
        M[col], M[piv] = M[piv], M[col]
        for r in range(col + 1, n):
            f = M[r][col] / M[col][col]
            for c in range(col, n + 1):
                M[r][c] -= f * M[col][c]
    x = [0.0] * n
    for r in range(n - 1, -1, -1):
        x[r] = (M[r][n] - sum(M[r][c] * x[c] for c in range(r + 1, n))) / M[r][r]
    return x

def features(x, degree):
    t = x / 300 - 1                                            # scale 0..600 to -1..1
    return [t ** p for p in range(degree + 1)]

def fit(rows, degree):
    F = [features(x, degree) for x, _ in rows]
    y = [v for _, v in rows]
    k = degree + 1
    A = [[sum(f[i] * f[j] for f in F) for j in range(k)] for i in range(k)]
    rhs = [sum(f[i] * v for f, v in zip(F, y)) for i in range(k)]
    return solve(A, rhs)

def rmse(coef, rows, degree):
    errs = [(sum(c * f for c, f in zip(coef, features(x, degree))) - v) ** 2 for x, v in rows]
    return (sum(errs) / len(errs)) ** 0.5

K = 5
folds = [data[i::K] for i in range(K)]
print("degree  train RMSE   CV RMSE (mean +/- std over 5 folds)")
for degree in (1, 2, 3, 5, 8, 11):
    train_scores, val_scores = [], []
    for i in range(K):
        val = folds[i]
        train = [r for j, f in enumerate(folds) if j != i for r in f]
        coef = fit(train, degree)
        train_scores.append(rmse(coef, train, degree))
        val_scores.append(rmse(coef, val, degree))
    m = sum(val_scores) / K
    s = (sum((v - m) ** 2 for v in val_scores) / K) ** 0.5
    print(f"{degree:>5}   {sum(train_scores) / K:9.3f}   {m:7.3f} +/- {s:.3f}")

degree  train RMSE   CV RMSE (mean +/- std over 5 folds)
    1       1.983     2.244 +/- 0.358
    2       0.869     0.960 +/- 0.070
    3       0.863     0.972 +/- 0.071
    5       0.795     0.957 +/- 0.093
    8       0.656     2.000 +/- 1.389
   11       0.628     2.433 +/- 1.901

Compare the two error columns. Training error falls every time the degree rises (1.98 down to 0.63), as it always will. Cross-validated error tells a different story: a straight line is clearly too simple (2.24), degrees 2, 3 and 5 are all around 0.96, and degrees 8 and 11 are worse than a straight line, with a huge spread between folds (1.4 to 1.9), which is the instability of an overfit model. The measurement noise was about plus or minus 1.5 points uniformly, whose standard deviation is roughly 0.87, so 0.96 is close to the best any model could do on this data.

Choosing between models that look tied

Degrees 2, 3 and 5 differ by about 0.015 in mean CV error, but the spread across folds is 0.07 to 0.09, five times larger. Statistically they are indistinguishable. When models are tied within noise, choose the simplest: degree 2. It has fewer parameters to estimate, extrapolates less wildly and is easier to explain. This is sometimes called the one-standard-error rule, and it protects you from picking a complex model because of a lucky fold.

Practical rules for cross-validation

• Choose k to match the data size. Five or ten folds is a common compromise; with tiny datasets you can go to leave-one-out, at the cost of more training runs.
• Shuffle before folding, unless the data is time-ordered. For forecasting, use expanding-window splits where each validation fold lies after its training data.
• Stratify for classification so each fold has roughly the same class proportions; otherwise a rare class may be missing from a fold entirely.
• Put every learned step inside the loop: scaling, imputation and feature selection must be fitted on the training folds only. The final lesson shows how badly this goes when you forget.

Common mistakes and the symptoms they cause

How this shows up in real projects and interviews

Real projects use library helpers for folds and for grid or random search, but the logic is the one above, and you should be able to explain it without the helper. Interviewers like the question "how would you choose between two models?" A good answer covers cross-validation, reporting both mean and spread, preferring the simpler model when scores are tied, and keeping a final test set untouched. They also like "why not just pick the best training score?", for which the table above is the answer. The earlier lesson on train, validation and test sets sets up the vocabulary used here.