Валидация и переобучение

Предыдущая заметка устранила утечки: ни один признак не несёт ответа, и каждый обучаемый шаг конвейера видит только обучающие строки. Но чистое разбиение — ещё не измерение риска. Оценка на валидации — среднее по конечному набору примеров, то есть случайное число с разбросом; модель, о которой сообщают, обычно лучшая из многих, опробованных на тех же примерах, поэтому её оценка смещена вверх; а разбиение должно имитировать то, как модель будут применять, иначе оценка отвечает на другой вопрос. Эта заметка строит протокол: какие данные для чего используются, как экономно переиспользовать их с помощью кросс-валидации, насколько велика погрешность и как не дать выбору модели загрязнить итоговую оценку.

Обозначения. Данные $D$ содержат $n$ размеченных пар. Модель, обученная на множестве $T$, — $\hat f_T$; её риск — $R(\hat f_T)$, а её средняя потеря на непересекающемся с ним множестве $V$ — $\hat R_V(\hat f_T) = \frac{1}{\lvert V \rvert}\sum_{i \in V} L(y_i, \hat f_T(x_i))$. В $K$-кратной кросс-валидации $D$ делится на фолды $D_1, \dots, D_K$, а $D_{-k}$ — всё, кроме $D_k$. Гиперпараметр, например степень многочлена или число соседей, обозначается $\lambda$.

Три выборки и назначение каждой#

Ошибка на обучении бесполезна как оценка риска: вводная заметка показала, как она падает до нуля, пока риск взрывается. Поэтому стандартный протокол использует три непересекающиеся части:

• обучающую выборку (training set), на которой подбираются параметры модели;
• валидационную выборку (validation set), на которой делается выбор, не входящий в процедуру обучения: гиперпараметры, признаки, семейство моделей, момент остановки;
• тестовую выборку (test set), которую трогают один раз, в конце, чтобы сообщить риск окончательного выбора.

Почему три, а не две? Каждое решение, принятое с оглядкой на выборку, расходует часть её честности. Если на валидационной выборке сравнить двадцать значений гиперпараметра, оценка победителя на валидации включает везение этого сравнения; несмещённую оценку даёт только выборка, не участвовавшая ни в одном решении. Курс NLP формулирует то же правило для текстовых корпусов в разделе «Три выборки и назначение каждой».

Оценка на $m$ независимых тестовых примерах — среднее $m$ потерь, поэтому её погрешность даёт центральная предельная теорема. Разобранный пример. Доля правильных ответов (accuracy) $0.85$ на $m = 500$ тестовых примерах имеет стандартную ошибку $\sqrt{0.85 \cdot 0.15 / 500} = 0.016$, так что 95-процентный интервал равен $0.85 \pm 0.031$. Чтобы сузить интервал вдвое, нужно вчетверо больше тестовых примеров, а две модели, доли правильных ответов которых различаются на этой тестовой выборке на 0.02, нельзя различить по непарным интервалам; парный бутстрэп сравнивает их на одних и тех же примерах и гораздо чувствительнее.

Кросс-валидация: каждый пример валидирует один раз#

Отложенная выборка (hold-out) тратит данные дважды: валидационные примеры не обучают модель, а обучающие её не проверяют. При нескольких сотнях строк обе половины малы. $K$-кратная кросс-валидация (K-fold cross-validation; Stone, 1974) делит данные на $K$ фолдов, обучает $K$ моделей, каждую на $D_{-k}$, оценивает каждую на её фолде и усредняет:

$$\hat R_{\mathrm{CV}} = \frac1K \sum_{k=1}^K \hat R_{D_k}\big(\hat f_{D_{-k}}\big) .$$

Рисунок

Кросс-валидация и вложенная кросс-валидация

Каждый пример ровно один раз попадает в валидацию, и проверяет его модель, которая его не видела. Цена — $K$ обучений вместо одного. Каждая модель обучается на доле $(K - 1)/K$ данных, поэтому оценка описывает чуть меньшую обучающую выборку и слегка пессимистична; при $K = n$, в схеме leave-one-out, это смещение почти исчезает ценой $n$ обучений. Обычный компромисс — $K = 5$ или $10$. После того как кросс-валидация выбрала гиперпараметры, окончательная модель заново обучается на всех данных.

Что оценивает кросс-валидация. Хотелось бы, чтобы $\hat R_{\mathrm{CV}}$ оценивала риск модели, обученной на этих данных. С этим она справляется плохо: она оценивает средний риск моделей, обученных на похожих обучающих выборках из того же распределения (Bates, Hastie and Tibshirani, 2024; Hastie, Tibshirani and Friedman, 2009, раздел 7.12). Для выбора модели этого достаточно, поскольку вопрос в том, какая процедура работает лучше; это важно, когда число читают как гарантию для одной развёрнутой модели.

Разбиения, соответствующие применению#

Случайное разбиение предполагает, что строки — независимые наблюдения и что будущие случаи приходят из того же распределения. Когда одно из предположений нарушено, разбиение нужно строить так, чтобы оно имитировало применение модели (Roberts et al., 2017).

• Стратифицированные фолды (stratified folds) сохраняют в каждом фолде доли классов всех данных. Для редких классов это важно: при 5 положительных объектах из 100 и случайных фолдах по 20 число положительных в фолде имеет гипергеометрическое распределение, и фолд не содержит ни одного положительного с вероятностью $\binom{95}{20} / \binom{100}{20} = 0.319$. На таком фолде полнота (recall) не определена: её знаменатель TP + FN считает фактические положительные объекты и равен 0. У точности (precision) знаменатель TP + FP — предсказанные положительные: она не определена, только если модель не отметила в фолде ни одного объекта, и равна 0, как только отметила хоть один, ведь каждая отметка тогда — ложная тревога.
• Разбиения по группам (group splits) держат все строки одной группы (пациента, пользователя, магазина, документа) по одну сторону. Если несколько снимков одного пациента попали и в обучение, и в валидацию, модель может узнавать пациента, а не болезнь, и оценка измеряет запоминание. Если модель будет встречать новые группы, в валидации должны быть группы, которых она не видела.
• Разбиения по времени (time splits) обучают на прошлом и валидируют на будущем: расширяющееся окно обучается на месяцах $1, \dots, t$ и валидируется на месяце $t + 1$ для нескольких $t$. Случайное разбиение упорядоченных по времени данных позволяет модели учиться на будущем, и признаки вроде «трат за последние 30 дней» становятся утечками. Зазор между периодом обучения и периодом валидации имитирует задержку перед развёртыванием модели.

Переобучение и недообучение#

По мере того как семейство моделей становится богаче, ошибка на обучении стабильно падает, а ошибка на валидации падает, достигает минимума и растёт: это U-образная кривая с рисунка вводной заметки. Слева от минимума модель недообучена (underfitting): обе ошибки высоки и близки друг к другу, потому что семейство не может представить закономерности данных. Справа от него модель переобучена (overfitting): ошибка на обучении намного ниже ошибки на валидации, потому что модель подгоняется под шум своей выборки. Заметка о смещении и разбросе даёт разложение, стоящее за этими двумя режимами.

Кривая обучения (learning curve) показывает обе ошибки в зависимости от размера обучающей выборки и говорит, в каком режиме находится модель. Для полиномиального примера из вводной заметки (синусоида с дисперсией шума 0.09, равноотстоящие входы) точные ожидаемые ошибки таковы:

Обучающих точек	Степень 1: обучение	Степень 1: новые данные	Степень 9: обучение	Степень 9: новые данные
12	0.329	0.318	0.015	0.208
24	0.308	0.298	0.053	0.124
48	0.297	0.291	0.071	0.107
192	0.289	0.287	0.085	0.095

Прямая недообучена: её две ошибки близки с самого начала и обе сходятся примерно к 0.29, намного выше уровня шума 0.09, так что больше данных не поможет; поможет более богатое семейство. (Её ошибка на обучении даже чуть выше ошибки на новых данных, потому что равноотстоящие входы включают оба конца отрезка, где прямая сильнее всего промахивается мимо синусоиды.) Многочлен степени 9 переобучен на 12 точках, с разрывом 0.19 между двумя ошибками, и разрыв закрывается с ростом данных: на 192 точках обе ошибки отличаются от уровня шума меньше чем на 0.01. Больше данных — лекарство от переобучения; от недообучения оно не помогает.

Насколько шумна оценка на валидации?#

Оценка по кросс-валидации — случайная величина: она зависит от того, какие примеры оказались в выборке и как их разбили. Рисунок измеряет этот разброс в постановке, где истинный риск известен точно:

Рисунок

Насколько точны оценки риска

Бросаются в глаза три вещи. Ошибка на обучении смещена на $-0.10$ при истинном риске около 0.21: это вообще не оценка риска. Отложенная выборка из 20% данных почти несмещена, но её 8 валидационных примеров дают разброс 0.15 — столько же, сколько эффект, который хотелось бы обнаружить. Кросс-валидация использует для валидации каждый пример и вдвое сокращает разброс, до 0.07, что близко к $\sqrt{0.21 \cdot 0.79 / 40} = 0.064$ — стандартной ошибке доли ошибок, измеренной на 40 независимых примерах. Это ориентир для данной постановки, а не универсальный нижний предел: он описывает долю независимых ошибок 0–1, а у оценок, использующих больше, чем ошибки 0–1, или у коррелированных и стратифицированных наблюдений разброс может быть другим. Перетасовка тех же 40 примеров не создаёт новой информации, поэтому кросс-валидация остаётся около этого ориентира.

Погрешность кросс-валидации. Естественная погрешность берёт стандартное отклонение $K$ оценок по фолдам и делит его на $\sqrt K$. В постановке рисунка она в среднем равна 0.059, тогда как фактический разброс 5-кратной оценки — 0.074. Оценки по фолдам не независимы: обучающие выборки любых двух фолдов делят большую часть строк, поэтому их модели ошибаются похоже, а наивная формула игнорирует эту корреляцию. Bengio and Grandvalet (2004) доказали, что не существует несмещённой оценки дисперсии $K$-кратной кросс-валидации, верной для всех распределений, а Bates, Hastie and Tibshirani (2024) показывают, что наивные интервалы могут накрывать истинное значение гораздо реже номинального уровня, и предлагают исправляющую их вложенную схему. На практике: повторять кросс-валидацию с несколькими случайными разбиениями, чтобы убрать шум самого разбиения, сравнивать модели на одних и тех же фолдах (парное сравнение) и ожидать, что наивная погрешность окажется слишком узкой, как в этой постановке и в постановках, которые изучают Bates, Hastie и Tibshirani; гарантированной нижней границей неопределённости она тоже не является.

Повторное использование тестовой выборки#

Каждый взгляд на тестовую выборку, за которым следует решение, делает следующий взгляд менее честным. Когда на одной валидационной выборке сравнивают $M$ моделей, лучшая оценка смещена вверх, даже если все модели одинаково хороши: курс теории вероятностей вычисляет, что лучшая из 1000 моделей с одинаковой долей правильных ответов, оценённых на 10 000 примеров, в среднем выглядит на 1.3 процентного пункта доли правильных ответов лучше, чем она есть, и что неравенство Хёфдинга вместе с оценкой объединения (union bound) гарантирует запас $\sqrt{(\ln M + \ln(2/\delta))/(2n)}$ сразу для всех. Эта оценка предполагает, что кандидаты зафиксированы заранее. Исследователь, который пробует модель, смотрит на тестовую оценку, что-то меняет и смотрит снова, выбирает кандидатов адаптивно, и оценка больше не применима; Dwork et al. (2015) показывают, как быстро такое адаптивное переиспользование может переобучить отложенную выборку и как это ограничить. Насколько велик эффект на практике, зависит от области: когда Recht et al. (2019) собрали новые тестовые выборки для CIFAR-10 и ImageNet, доли правильных ответов упали на 3–15 и 11–14 пунктов, но ранжирование моделей почти не изменилось, и авторы объясняют падение немного более трудной новой тестовой выборкой, а не адаптивным переобучением.

Отсюда простое правило: решения принимаются на валидационных данных (или кросс-валидацией), а тестовая выборка используется один раз. Тестовая выборка, по которой выбирали между моделями, становится валидационной.

Вложенная кросс-валидация#

Кросс-валидацию часто используют и для выбора гиперпараметров, и для отчёта о результате, что возвращает смещение отбора (selection bias). Лучшая оценка кросс-валидации среди многих значений гиперпараметра оптимистична по той же причине, что и лучшая из $M$ моделей (Varma and Simon, 2006; Cawley and Talbot, 2010). Вложенная кросс-валидация (nested cross-validation) разделяет эти две задачи:

1. Внешний цикл делит данные на $K$ фолдов. Для каждого внешнего фолда $k$:
2. внутренняя кросс-валидация только на $D_{-k}$ выбирает $\lambda$;
3. модель с этим $\lambda$ заново обучается на $D_{-k}$ и оценивается на $D_k$.
4. Среднее $K$ внешних оценок оценивает риск всей процедуры, включая выбор.

Правая половина рисунка выше показывает один внешний раунд. На чистом шуме, где у каждой модели истинная доля правильных ответов 0.5, выбор числа соседей $k$ классификатора ближайших соседей среди 20 значений по 5-кратной кросс-валидации с отчётом о лучшей доле правильных ответов по кросс-валидации даёт в среднем 0.567 по 200 наборам данных из 100 объектов; вложенная кросс-валидация даёт 0.504 (раздел «Код»). Внешняя оценка описывает процедуру, а не одно значение $\lambda$: разные внешние фолды могут выбрать разные значения, а окончательная модель получается, если ещё раз запустить внутренний выбор на всех данных.

Что изменилось#

	Ошибка на обучении	Отложенная выборка	$K$-кратная CV	Вложенная CV
Смещение в постановке рисунка	$-0.10$	$+0.01$	$+0.01$
Разброс в постановке рисунка	0.05	0.15	0.07
Нужно обучений	1	1	$K$	$K \times K_{\text{inner}}$ на кандидата
Можно одновременно выбирать и отчитываться	нет	нет	нет	да

Ограничения#

• Любая оценка предполагает, что разбиение имитирует применение. Если будущее отличается от прошлого (новый рынок, смена политики), никакая повторная выборка из прошлого этого не измерит; измерят только данные из нового режима.
• Малые данные остаются шумными. Доля ошибок $p$, измеренная на $n$ независимых примерах, имеет стандартную ошибку $\sqrt{p(1-p)/n}$, и кросс-валидация на тех же $n$ примерах обычно остаётся около этого ориентира: она не создаёт информацию.
• Кросс-валидация дорога. $K$ обучений на кандидата и $K \times K$ во вложенных схемах; для больших нейронных сетей обычно можно позволить себе лишь одну отложенную выборку, и это допустимо, когда валидационная выборка велика.
• Наивная погрешность часто слишком узка, и универсальной несмещённой замены ей нет; помогают повторные и вложенные схемы.

Что нужно запомнить#

• Обучающие данные подбирают параметры, валидационные делают выбор, тестовые используются один раз для отчёта.
• Оценка на $m$ независимых примерах имеет стандартную ошибку $\sqrt{p(1-p)/m}$: 0.85 на 500 примерах — это $\pm 0.031$ при уровне 95%.
• $K$-кратная кросс-валидация валидирует каждый пример один раз; она слегка пессимистична и оценивает риск процедуры на похожих обучающих выборках.
• Стратифицируйте для редких классов, держите группы вместе, разбивайте упорядоченные по времени данные по времени.
• Недообучение: обе ошибки высоки и близки; переобучение: большой разрыв, который сокращается с ростом данных.
• Погрешность кросс-валидации по разбросу между фолдами обычно занижает её фактический разброс (0.059 против 0.074 в постановке рисунка).
• Лучшая из многих оценок на валидации оптимистична; вложенная кросс-валидация честно оценивает процедуру выбора.

Код#

Погрешность доли правильных ответов на тесте, пустой фолд, точные кривые обучения, разброс оценок риска и вложенная кросс-валидация против обычной:

import numpy as np
from numpy.polynomial import legendre as L
from scipy import stats

rng = np.random.default_rng(0)

# the error bar of a test accuracy: 0.85 on 500 independent examples
se = np.sqrt(0.85 * 0.15 / 500)
print(round(float(se), 3), round(float(1.96 * se), 3))                                    # 0.016 0.031

# 100 objects, 5 positives, 5 folds of 20: the chance that a random fold has no positive at all
print(round(float(stats.hypergeom(100, 5, 20).pmf(0)), 3))                         # 0.319

# learning curves, exact: polynomials of degree 1 and 9 on n equally spaced points of sin(2 pi x) + N(0, 0.3^2)
m, s2 = (lambda x: np.sin(2 * np.pi * x)), 0.09
gx, gw = L.leggauss(200); gx, gw = (gx + 1) / 2, gw / 2
def expected_errors(n, deg):
    x = np.linspace(0, 1, n)
    A = np.linalg.pinv(L.legvander(2 * x - 1, deg))
    G = L.legvander(2 * gx - 1, deg) @ A
    train = (((m(x) - L.legvander(2 * x - 1, deg) @ A @ m(x)) ** 2).sum() + s2 * (n - deg - 1)) / n
    return round(float(train), 3), round(float(s2 + gw @ (G @ m(x) - m(gx)) ** 2 + s2 * gw @ (G ** 2).sum(axis=1)), 3)
for deg in (1, 9):
    print(deg, [expected_errors(n, deg) for n in (12, 24, 48, 192)])
# 1 [(0.329, 0.318), (0.308, 0.298), (0.297, 0.291), (0.289, 0.287)]
# 9 [(0.015, 0.208), (0.053, 0.124), (0.071, 0.107), (0.085, 0.095)]

# how far risk estimates fall from the true risk: nearest centroid, 40 objects in 20 dimensions, signal in one
n, d, R = 40, 20, 2000
y = np.repeat([0, 1], n // 2)
mu = np.zeros((2, d)); mu[0, 0], mu[1, 0] = -1, 1
def fit(X, yy): return np.array([X[yy == 0].mean(0), X[yy == 1].mean(0)])
def error(c, X, yy): return float(((((X - c[1]) ** 2).sum(1) < ((X - c[0]) ** 2).sum(1)) != yy).mean())
def true_risk(c):
    w, mid = c[1] - c[0], c.mean(0)
    return 0.5 * stats.norm.cdf(w @ (mu[0] - mid) / np.linalg.norm(w)) + 0.5 * stats.norm.cdf(-w @ (mu[1] - mid) / np.linalg.norm(w))
def folds(K):
    f = np.empty(n, int)
    for cl in (0, 1):
        f[rng.permutation(np.flatnonzero(y == cl))] = np.arange(n // 2) % K
    return f
out = {k: [] for k in ('train', 'hold', 'cv5', 'loo', 'se5', 'risk')}
for _ in range(R):
    X = rng.normal(size=(n, d)) + mu[y]
    c = fit(X, y); risk = true_risk(c); out['risk'].append(risk)
    out['train'].append(error(c, X, y) - risk)
    f = folds(5)
    out['hold'].append(error(fit(X[f != 0], y[f != 0]), X[f == 0], y[f == 0]) - risk)
    e = [error(fit(X[f != k], y[f != k]), X[f == k], y[f == k]) for k in range(5)]
    out['cv5'].append(np.mean(e) - risk); out['se5'].append(np.std(e, ddof=1) / np.sqrt(5))
    out['loo'].append(np.mean([error(fit(np.delete(X, i, 0), np.delete(y, i)), X[i:i + 1], y[i:i + 1]) for i in range(n)]) - risk)
for k in ('train', 'hold', 'cv5', 'loo'):
    print(k, round(float(np.mean(out[k])), 3), round(float(np.std(out[k], ddof=1)), 3))
print(round(float(np.mean(out['risk'])), 3), round(float(np.mean(out['se5'])), 3))
# train -0.101 0.048 | hold 0.011 0.147 | cv5 0.01 0.073 | loo 0.004 0.069
# 0.21 0.059: the mean true risk and the mean naive standard error of the 5-fold estimate

# choosing k for kNN on pure noise: the best cross-validated accuracy against nested cross-validation
ks = np.arange(1, 40, 2)                                                    # 20 candidate values of k
def knn_errors(Xtr, ytr, Xte, yte):
    D = ((Xte[:, None, :] - Xtr[None, :, :]) ** 2).sum(-1)
    votes = np.cumsum(ytr[np.argsort(D, axis=1)], axis=1)[:, ks - 1]        # positives among the k nearest, every k
    return ((votes > ks / 2) != yte[:, None]).mean(0)
def cv_errors(X, yy, K=5):
    f = rng.permutation(len(yy)) % K
    return np.mean([knn_errors(X[f != k], yy[f != k], X[f == k], yy[f == k]) for k in range(K)], axis=0)
flat, nested = [], []
for _ in range(200):
    X, yy = rng.normal(size=(100, 10)), rng.integers(0, 2, 100)            # labels carry no information
    flat.append(1 - cv_errors(X, yy).min())
    f, acc = rng.permutation(100) % 5, []
    for k in range(5):
        tr, te = f != k, f == k
        best = np.argmin(cv_errors(X[tr], yy[tr]))                          # the inner loop picks k
        acc.append(1 - knn_errors(X[tr], yy[tr], X[te], yy[te])[best])
    nested.append(np.mean(acc))
print(round(float(np.mean(flat)), 3), round(float(np.mean(nested)), 3))       # 0.567 0.504

Дальше#

Протокол валидации теперь может честно измерить любую модель. Но модели до сих пор были лишь мысленными экспериментами: запоминающая модель и многочлен. Следующая заметка вводит первый практический метод, ближе всего стоящий к запоминанию: предсказывать для нового объекта то, что произошло с самыми похожими объектами обучающей выборки. Ему нужно только понятие расстояния, он состоятелен при росте данных и ломается в большой размерности так, что это мотивирует глобальные модели остальной части курса.

Литература#

• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 1: введение (отложенная выборка и кросс-валидация).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Разделы 7.2 и 7.10 (сложность модели, кросс-валидация), раздел 7.12 (условная и ожидаемая ошибка на тесте).
• M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society B, 36(2), 1974.
• Y. Bengio, Y. Grandvalet. No unbiased estimator of the variance of K-fold cross-validation. Journal of Machine Learning Research, 5, 2004.
• S. Bates, T. Hastie, R. Tibshirani. Cross-validation: what does it estimate and how well does it do it? Journal of the American Statistical Association, 119(546), 2024. arXiv: 2104.00673.
• D. R. Roberts et al. Cross-validation strategies for data with temporal, spatial, hierarchical, or phylogenetic structure. Ecography, 40(8), 2017.
• S. Varma, R. Simon. Bias in error estimation when using cross-validation for model selection. BMC Bioinformatics, 7, 2006.
• G. C. Cawley, N. L. C. Talbot. On over-fitting in model selection and subsequent selection bias in performance evaluation. Journal of Machine Learning Research, 11, 2010.
• C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, A. Roth. The reusable holdout: preserving validity in adaptive data analysis. Science, 349(6248), 2015.
• B. Recht, R. Roelofs, L. Schmidt, V. Shankar. Do ImageNet classifiers generalize to ImageNet? ICML, 2019.