Разложение на смещение и разброс

Заметка о решающих деревьях закончилась двумя наблюдениями. Полностью выращенное дерево идеально подгоняется под обучающую выборку и всё же проигрывает на новых данных дереву глубины 3; а два дерева, выращенные на выборках из одного распределения, расходятся почти везде. Оба утверждения касаются метода обучения — процедуры, превращающей обучающую выборку в модель, — а не одной обученной модели, потому что обучающая выборка случайна. Эта заметка делает их точными. По случайности обучающей выборки ожидаемая квадратичная ошибка метода раскладывается на три слагаемых: шум в значениях целевой переменной, квадрат смещения (bias) метода и его разброс (variance). Это разложение объясняет, как работает каждая ручка сложности в курсе, от $k$ в методе ближайших соседей до глубины дерева, и показывает, что именно усреднение может исправить, а что нет; этому посвящены следующие две заметки.

Обозначения. Данные — пары $(X, Y)$ из фиксированного распределения. $m(x) = E[Y \mid X = x]$ — функция регрессии, а $\sigma^2(x) = \operatorname{Var}(Y \mid X = x)$ — шум в точке $x$. Обучающая выборка $D = \{(x_i, y_i)\}_{i=1}^n$ состоит из $n$ независимых наблюдений, и метод обучения отображает её в функцию $\hat f_D$. Математические ожидания $E_D$ и дисперсии $\operatorname{Var}_D$ берутся по обучающим выборкам размера $n$. $\bar f(x) = E_D[\hat f_D(x)]$ — средняя модель (average model): предсказание в $x$, усреднённое по всем обучающим выборкам, которые мог бы увидеть метод.

Разложение по обучающим выборкам#

Зафиксируем тестовую точку $x$ и выберем в ней новое значение целевой переменной $Y$, независимое от обучающей выборки. Ошибка $(Y - \hat f_D(x))^2$ случайна и через $Y$, и через $D$. Её математическое ожидание раскладывается в два шага, каждый из которых — результат курса теории вероятностей.

Шаг 1: отделяем шум. Прибавим и вычтем $m(x)$:

$$\begin{aligned} E\big[(Y - \hat f_D(x))^2\big] ={}& E\big[(Y - m(x))^2\big] + E_D\big[(m(x) - \hat f_D(x))^2\big] \\ &+ 2\,E\big[(Y - m(x))(m(x) - \hat f_D(x))\big] . \end{aligned}$$

Перекрёстное слагаемое равно нулю: $Y$ не зависит от $D$, поэтому математическое ожидание произведения равно произведению математических ожиданий, а $E[Y - m(x)] = 0$ по определению $m$. Первое слагаемое равно $\sigma^2(x)$. Это разложение для наилучшего предсказателя из заметки об условном математическом ожидании, применённое к случайной функции $\hat f_D$ вместо фиксированной $g$.

Шаг 2: раскладываем ошибку оценивания. При фиксированном $x$ значение $\hat f_D(x)$ — оценка числа $m(x)$, случайная через $D$. Её среднеквадратичная ошибка равна квадрату смещения плюс дисперсия, как выведено в заметке об оценках (прибавим и вычтем $\bar f(x)$; перекрёстное слагаемое имеет нулевое среднее):

$$E_D\big[(\hat f_D(x) - m(x))^2\big] = \big(\bar f(x) - m(x)\big)^2 + \operatorname{Var}_D\big(\hat f_D(x)\big) .$$

Объединяя шаги и усредняя по тестовой точке $x$, получаем:

$$\underbrace{E_{X, Y, D}\big[(Y - \hat f_D(X))^2\big]}_{\text{ожидаемая ошибка на тесте}} = \underbrace{E_X\big[\sigma^2(X)\big]}_{\text{шум}} + \underbrace{E_X\big[(\bar f(X) - m(X))^2\big]}_{\text{смещение}^2} + \underbrace{E_X\big[\operatorname{Var}_D \hat f_D(X)\big]}_{\text{разброс}} .$$

Три замечания удерживают разложение в честных рамках. Оно верно для квадратичной ошибки; для функции потерь 0–1 есть разложения со слагаемыми того же смысла, но они не складываются так просто (Domingos, 2000). Смещение и разброс принадлежат методу и размеру выборки: больше данных обычно снижает разброс любого метода. Смещение тоже может падать: с ростом числа точек $k$ ближайших соседей при фиксированном $k$ подходят ближе к $x$, а фиксированный штраф гребневой регрессии $\lambda$ весит меньше на фоне растущей $\sum_i x_i^2$. От размера выборки не зависит только смещение лучшего представителя класса моделей — его ошибка аппроксимации. И на практике обучающая выборка одна, поэтому три слагаемых никогда не наблюдаются; их оценивают моделированием, как в этой заметке, или оценивают их сумму валидацией, как в заметке о валидации.

Оценка слагаемых моделированием#

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

Рисунок

Смещение и разброс регрессионных деревьев

Панели с пучками показывают, что означают эти два слова. Неглубокие деревья согласны друг с другом и ошибаются одинаково, огрубляя пики синусоиды; глубокие деревья правы в среднем, а каждое ошибается по-своему. Панель с кривыми показывает компромисс (trade-off): от глубины 1 до глубины 8 квадрат смещения падает с $0.072$ до $0.001$, разброс растёт с $0.043$ до $0.094$ ($0.095$ у полностью выращенного дерева), а их сумма с шумом минимальна на глубине 3. Разброс полностью выращенного дерева, $0.095$, близок к дисперсии шума $\sigma^2 = 0.09$ по простой причине: лист с одной обучающей точкой предсказывает значение целевой переменной в этой точке, а оно несёт весь шум. Для этого нужны плотно расположенные обучающие точки: при 40 точках на отрезке точка, оставшаяся одна в листе $x$, лежит близко к $x$, и $m$ в них почти не различается. Поэтому ожидаемая ошибка полностью выращенного дерева на тесте в этом примере близка к $2\sigma^2$ плюс его смещение, здесь $0.187$.

Что разложение говорит о каждой модели#

У каждой модели курса есть ручка, которая двигает её вдоль одной и той же кривой.

Ближайшие соседи. Если обучающие входы зафиксированы и случайны только значения целевой переменной, предсказание $k$ ближайших соседей в $x$ — среднее $k$ независимых зашумлённых значений, поэтому его разброс равен ровно $\sigma^2 / k$ (Hastie, Tibshirani and Friedman, 2009, формула 7.10): $0.25$, $0.05$ и $0.01$ при $\sigma = 0.5$ и $k = 1, 5, 25$. Его смещение — разность между $m(x)$ и средним $m$ по $k$ соседям, и оно растёт по мере удаления соседей. Малое $k$ — гибкий край, большое $k$ — жёсткий: на функции Фридмана в 10 измерениях (ниже), где обучающие входы заново разыгрываются для каждой обучающей выборки и соседи сдвигаются вместе с ними, разброс превышает $\sigma^2/k$: у $k = 1$ разброс $12.24$ при $\sigma^2 = 1$, у $k = 50$ — $0.41$, а квадрат смещения растёт с $4.61$ до $13.00$, и наименьшая сумма у $k = 5$.

Гребневая регрессия. Игрушечный пример с точными числами: один признак, фиксированный план эксперимента (design) с $\sum_i x_i^2 = 10$, без свободного члена, истинный наклон $\beta = 1$, шум $\sigma^2 = 1$, предсказание в $x_0 = 1$. Гребневая оценка наклона равна $\hat\beta_\lambda = \sum_i x_i y_i / (\sum_i x_i^2 + \lambda)$, поэтому $E \hat\beta_\lambda = \beta \cdot 10/(10 + \lambda)$ и $\operatorname{Var} \hat\beta_\lambda = \sigma^2 \cdot 10/(10 + \lambda)^2$. Метод наименьших квадратов ($\lambda = 0$) несмещён, его разброс равен $0.1$. При $\lambda = 1$ квадрат смещения равен $(1/11)^2 = 0.0083$, а разброс — $10/121 = 0.0826$, в сумме $0.0909$: небольшое смещение покупает большее сокращение разброса, и ошибка опускается ниже ошибки несмещённой оценки. При $\lambda = 5$ берёт верх смещение: $0.111 + 0.044 = 0.156$. Минимизация отношения $\beta^2\lambda^2 + 10\sigma^2$ к $(10 + \lambda)^2$ даёт лучший штраф $\lambda = \sigma^2 / \beta^2$ — отношение шума к сигналу, и это ровно штраф гауссовского априорного распределения с дисперсией $\beta^2$ в MAP-трактовке гребневой регрессии. На функции Фридмана гребневая регрессия на всех 286 мономах степени не выше 3 показывает кривую целиком: от $\lambda = 0.001$ до $\lambda = 1000$ разброс падает с $9.93$ до $0.39$, квадрат смещения растёт с $0.75$ до $6.81$, а сумма минимальна около $\lambda = 10$.

Деревья. Ручка — глубина, как на рисунке. На функции Фридмана у дерева глубины 2 квадрат смещения $9.79$ и разброс $5.36$; у полностью выращенного дерева квадрат смещения $3.08$ и разброс $9.34$, намного больше $\sigma^2 = 1$: в 10 измерениях 200 точек расположены редко, обучающая точка, оставшаяся одна в листе $x$, лежит далеко от $x$ и меняется от выборки к выборке, поэтому предсказание колеблется не только из-за шума, но и вместе с $m$ в этой точке. Глубокие деревья — хрестоматийный пример метода с малым смещением и большим разбросом.

Ансамбли. Усредним $B$ моделей, обученных одной и той же рандомизированной процедурой. Их среднее имеет то же математическое ожидание, что и каждая из них, поэтому смещение не меняется; уменьшиться может только разброс. Если бы модели были независимы, разброс уменьшился бы в $B$ раз; модели, обученные на одних и тех же данных, коррелированы, и заметка о бэггинге показывает, сколько остаётся. Процедура здесь — дерево, выращенное на бутстрэп-выборке, поэтому усреднение сохраняет смещение бутстрэп-дерева, а не дерева, выращенного на всей обучающей выборке: бутстрэп-выборка содержит лишь около 63% различных точек, и её дерево немного грубее. У пятидесяти полностью выращенных деревьев на бутстрэп-выборках из одной обучающей выборки квадрат смещения $3.61$, по этой причине чуть выше, чем $3.08$ у дерева на всей выборке, и разброс $1.32$ вместо $9.34$, а также наименьшая ошибка на тесте среди методов на основе деревьев в таблице ниже; на этой гладкой функции гребневая регрессия на кубических признаках работает ещё лучше. Бустинг из заметки о градиентном бустинге атакует другое слагаемое: он комбинирует модели с большим смещением так, чтобы у суммы смещение было меньше.

Метод на функции Фридмана ($n = 200$, $\sigma^2 = 1$)	Смещение²	Разброс	Ошибка на тесте
kNN, $k = 1$ / $5$ / $50$	4.61 / 6.47 / 13.00	12.24 / 2.90 / 0.41	17.85 / 10.36 / 14.41
гребневая регрессия на кубических признаках, $\lambda = 0.001$ / $10$ / $1000$	0.75 / 1.97 / 6.81	9.93 / 1.38 / 0.39	11.68 / 4.36 / 8.19
дерево, глубина 2 / 4 / без ограничения	9.79 / 4.74 / 3.08	5.36 / 5.98 / 9.34	16.15 / 11.72 / 13.42
бэггинг 50 полных деревьев	3.61	1.32	5.93

Курс теории вероятностей показал то же самое для оценок: в заметке об оценках смещённая оценка конца равномерного распределения обошла несмещённую, а оценка со сжатием (shrinkage) — выборочные средние. Регуляризация в любой форме — штраф гребневой регрессии, минимальный размер листа, ранняя остановка — это сознательная покупка смещения ценой разброса.

Оговорка о двойном спуске#

U-образная кривая — не закон. Belkin et al. (2019) заметили, что когда ёмкость класса моделей растёт за точку, в которой он может точно подогнаться под обучающие данные (порог интерполяции, interpolation threshold), ошибка на тесте после пика вблизи этого порога может снова упасть, иногда ниже дна U-образной кривой. Они показали это для моделей на случайных признаках, обученных методом наименьших квадратов с минимальной нормой, для нейросетей и для случайных лесов, ёмкость которых измеряется сначала числом листьев, а затем числом полностью выращенных деревьев. Само разложение этому не противоречит: оно тождество. Неверным оказывается предположение, что разброс должен расти вместе с числом параметров, потому что среди многих интерполирующих решений процедура обучения выбирает определённое — с малой нормой или усреднённое по многим деревьям, — и этот выбор управляет разбросом. Небольшой пример в разделе «Код» показывает пик: метод наименьших квадратов с минимальной нормой на первых $p$ из 400 гауссовских признаков при $n = 40$ точках имеет медианную избыточную ошибку $0.26$ при $p = 10$, $23.7$ на пороге $p = 40$ и $0.78$ при $p = 80$; в этом примере второй спуск не опускается ниже первого минимума. Двойной спуск (double descent) важен для перепараметризованных моделей, таких как большие нейросети. Большинство значений ручек этого раздела остаются ниже порога, где правильная картина — классическая кривая. Гибкие края — нет: 1-NN, полностью выращенное дерево и гребневая регрессия с $\lambda = 0.001$ на 286 признаках подгоняются под 200 обучающих точек точно (гребневая — почти точно) и потому стоят на пороге, а бэггинг 50 полных деревьев лежит за ним на оси ёмкости Belkin et al., которая продолжается числом усредняемых полностью выращенных деревьев.

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

	Одна обученная модель	Метод обучения
Случайный объект	тестовая точка	тестовая точка и обучающая выборка
Ошибка	$E[(Y - f(X))^2]$	шум + смещение² + разброс
Переобучение	ошибка на обучении ≪ ошибки на тесте	преобладает разброс
Недообучение	обе ошибки велики	преобладает смещение
Ручка сложности		$k$, $\lambda$, глубина, число усредняемых моделей

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

• Только квадратичная ошибка. Для функций потерь классификации разложение принимает другие формы, и смещение и разброс могут взаимодействовать (большой разброс может даже помочь смещённому классификатору).
• Не наблюдается. Слагаемым нужны истинная $m$ и много обучающих выборок; на реальных данных оценивается только их сумма, валидацией.
• Ёмкость — не одно число. «Число параметров» не упорядочивает модели по разбросу, когда процедура обучения выбирает среди многих точных подгонок, как показывает двойной спуск.

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

• Ожидаемая ошибка на тесте по обучающим выборкам = шум + смещение² + разброс; перекрёстные слагаемые исчезают, потому что новое значение целевой переменной не зависит от обучающей выборки, а средняя модель — среднее обученных моделей.
• Смещение — ошибка средней модели. Разброс — рассеяние обученных моделей по обучающим выборкам. Шум — нижняя граница $E[\operatorname{Var}(Y \mid X)]$.
• Гибкость (малое $k$, малое $\lambda$, глубокие деревья) снижает смещение и повышает разброс; лучшая настройка уравновешивает их и зависит от $n$.
• Разброс kNN при фиксированных обучающих входах равен $\sigma^2/k$; лучший штраф гребневой регрессии в одномерном случае — $\sigma^2/\beta^2$; у полностью выращенного дерева разброс около $\sigma^2$, когда обучающие точки расположены плотно. При случайных и редких входах оба разброса гораздо больше.
• Усреднение одинаково распределённых моделей сохраняет смещение и снижает разброс; бустинг снижает смещение.
• За порогом интерполяции ошибка на тесте может снова падать (двойной спуск); разложение при этом остаётся верным.

Код#

Точные числа для гребневой регрессии, смещение и разброс моделированием для ближайших соседей, гребневой регрессии, деревьев и бэггинга, и пик двойного спуска:

import numpy as np
from sklearn.ensemble import BaggingRegressor
from sklearn.linear_model import Ridge
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import PolynomialFeatures, StandardScaler
from sklearn.tree import DecisionTreeRegressor

# гребневая регрессия с одним признаком, фиксированный план (сумма x_i^2 = 10), beta = 1, sigma^2 = 1, в x0 = 1: точные квадрат смещения и разброс
S, beta, s2 = 10.0, 1.0, 1.0
for lam in (0, 1, 5):
    b2, var = (beta * lam / (S + lam)) ** 2, s2 * S / (S + lam) ** 2
    print(lam, round(b2, 4), round(var, 4), round(b2 + var, 4))
# 0 0.0 0.1 0.1 | 1 0.0083 0.0826 0.0909 | 5 0.1111 0.0444 0.1556

# функция Фридмана в 10 измерениях (5 из них не влияют), n = 200, шум sigma = 1, 50 обучающих выборок
rng = np.random.default_rng(0)
f = lambda X: 10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2 + 10 * X[:, 3] + 5 * X[:, 4]
n, d, sigma, R = 200, 10, 1.0, 50
Xtest = rng.random((500, d))

def decompose(make):
    """Squared bias and variance at the test points, over R independent training sets."""
    P = []
    for _ in range(R):
        X = rng.random((n, d)); y = f(X) + sigma * rng.normal(size=n)
        P.append(make().fit(X, y).predict(Xtest))
    P = np.array(P)
    return ((P.mean(0) - f(Xtest)) ** 2).mean(), P.var(0).mean()

models = [('kNN, k =', k, lambda k=k: KNeighborsRegressor(k)) for k in (1, 5, 20, 50)]
models += [('ridge on cubic features, lambda =', lam, lambda lam=lam: make_pipeline(PolynomialFeatures(3), StandardScaler(), Ridge(lam))) for lam in (0.001, 1, 10, 100, 1000)]
models += [('tree, depth =', depth, lambda depth=depth: DecisionTreeRegressor(max_depth=depth, random_state=0)) for depth in (2, 4, 6, None)]
models += [('bagged full trees, B =', 50, lambda: BaggingRegressor(DecisionTreeRegressor(), n_estimators=50, random_state=0))]
for name, knob, make in models:
    b2, v = decompose(make)
    print(f'{name} {knob}: bias2 {b2:.2f} variance {v:.2f} total {b2 + v + sigma ** 2:.2f}')
# kNN, k = 1: bias2 4.61 variance 12.24 total 17.85
# kNN, k = 5: bias2 6.47 variance 2.90 total 10.36
# kNN, k = 20: bias2 9.54 variance 0.90 total 11.44
# kNN, k = 50: bias2 13.00 variance 0.41 total 14.41
# ridge on cubic features, lambda = 0.001: bias2 0.75 variance 9.93 total 11.68
# ridge on cubic features, lambda = 1: bias2 1.08 variance 2.41 total 4.50
# ridge on cubic features, lambda = 10: bias2 1.97 variance 1.38 total 4.36
# ridge on cubic features, lambda = 100: bias2 4.30 variance 0.93 total 6.23
# ridge on cubic features, lambda = 1000: bias2 6.81 variance 0.39 total 8.19
# tree, depth = 2: bias2 9.79 variance 5.36 total 16.15
# tree, depth = 4: bias2 4.74 variance 5.98 total 11.72
# tree, depth = 6: bias2 3.56 variance 7.81 total 12.38
# tree, depth = None: bias2 3.08 variance 9.34 total 13.42
# bagged full trees, B = 50: bias2 3.61 variance 1.32 total 5.93

# двойной спуск: метод наименьших квадратов с минимальной нормой на первых p из 400 гауссовских признаков, n = 40, 200 обучающих выборок
n, P = 40, 400
w = rng.normal(size=P) / np.arange(1, P + 1); w /= np.linalg.norm(w)      # истинные веса, убывающие, норма 1
for p in (10, 30, 40, 50, 80, 400):
    excess = []
    for _ in range(200):
        X = rng.normal(size=(n, P)); y = X @ w + 0.5 * rng.normal(size=n)
        b = np.linalg.pinv(X[:, :p]) @ y                 # МНК при p < n, интерполяция с минимальной нормой при p > n
        excess.append(np.sum((b - w[:p]) ** 2) + np.sum(w[p:] ** 2))   # E(x'b - x'w)^2 для x ~ N(0, I)
    print(p, round(float(np.median(excess)), 2))
# 10 0.26 | 30 0.83 | 40 23.7 | 50 1.41 | 80 0.78 | 400 0.93

Дальше#

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

Литература#

• S. Geman, E. Bienenstock, R. Doursat. Neural Networks and the Bias/Variance Dilemma. Neural Computation, 4(1), 1992.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 7.3 (разложение на смещение и разброс; формула 7.10 для ближайших соседей, формула 7.11 для линейных моделей и гребневой регрессии).
• P. Domingos. A Unified Bias-Variance Decomposition and its Applications. Proceedings of the 17th International Conference on Machine Learning (ICML), 2000.
• M. Belkin, D. Hsu, S. Ma, S. Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS, 116(32), 2019 (arXiv:1812.11118). Раздел 2 (случайные признаки и нейросети), раздел 3 (решающие деревья и ансамбли).
• J. H. Friedman. Multivariate Adaptive Regression Splines. Annals of Statistics, 19(1), 1991. Тестовая функция, используемая здесь (первая функция Фридмана, make_friedman1 в scikit-learn).
• E. Sokolov et al. Машинное обучение (HSE). Конспект, лекция 10: бэггинг, случайный лес и разложение на смещение и разброс; семинар 10: разложение на смещение и разброс.