Неравенства и концентрация

Почти каждое число, которое измеряют в машинном обучении, — среднее по выборке: доля правильных ответов (accuracy) на валидационной выборке, средняя функция потерь, кликабельность (click-through rate). Насколько далеко такое среднее может оказаться от математического ожидания, которое оно оценивает? Распределение обычно неизвестно, поэтому полезные ответы — это неравенства, верные для любого распределения с некоторым свойством: известным средним, известной дисперсией, ограниченным диапазоном значений. В этой заметке мы выводим три главных неравенства — Маркова, Чебышёва и Хёфдинга (Hoeffding’s inequality), — сравниваем их с точным ответом и применяем последнее вместе с оценкой объединения (неравенством Буля, union bound), чтобы получить первую гарантию для модели, выбранной на валидационной выборке.

Обозначения. $X_1, \dots, X_n$ — независимые величины со средним $\mu$; $\bar X_n$ — их среднее. $\varepsilon > 0$ — отклонение, $\delta$ — малая вероятность неудачи.

Неравенство Маркова#

Для неотрицательной случайной величины $X$ и любого $a > 0$

$$P(X \ge a) \le \frac{E[X]}{a} .$$

Доказательство — одно сравнение: $a \mathbb 1_{\{X \ge a\}} \le X$ при любом исходе, и переход к математическим ожиданиям даёт $a P(X \ge a) \le E[X]$. Одно лишь среднее ограничивает, сколько вероятности может находиться далеко в хвосте. Если запрос в среднем обрабатывается 0.2 с, то не более 10% запросов могут занимать 2 с или больше, каким бы ни было распределение. Оценка часто груба: для экспоненциального времени ответа с тем же средним истинная доля равна $e^{-10} = 4.5 \cdot 10^{-5}$. Но без дополнительной информации её нельзя улучшить: величина, равная $a$ с вероятностью $E[X]/a$ и 0 в остальных случаях, её достигает.

Неравенство Чебышёва#

Неравенство Маркова, применённое к $(X - \mu)^2$, использует ещё и дисперсию:

$$P(\lvert X - \mu \rvert \ge k\sigma) \le \frac{1}{k^2} .$$

У любого распределения с конечной дисперсией не более 25% вероятности лежит на расстоянии двух стандартных отклонений от среднего или дальше и не более 11.1% — на расстоянии трёх или дальше. У нормального распределения это $4.55\%$ и $0.27\%$; оценка снова верна для любого распределения и далека от типичного.

В применении к среднему, дисперсия которого равна $\sigma^2 / n$, неравенство Чебышёва даёт

$$P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le \frac{\sigma^2}{n \varepsilon^2} \to 0 ,$$

а это уже слабый закон больших чисел: средние приближаются к математическому ожиданию. Но скорость $1/n$ слишком пессимистична.

Неравенство Хёфдинга#

Если величины ещё и ограничены, $a \le X_i \le b$, вероятность отклонения убывает экспоненциально:

$$P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le 2 \exp\Big(-\frac{2 n \varepsilon^2}{(b - a)^2}\Big) .$$

Функции потерь со значениями в $[0, 1]$, индикаторы верного ответа и клики ограничены, поэтому это неравенство — стандартный инструмент теории обучения. Для доли орлов в $n$ бросках честной монеты и отклонения $0.1$ обе оценки и точная биномиальная вероятность соотносятся так:

Рисунок

Две оценки хвоста и точная вероятность

Если обратить неравенство Хёфдинга, оно даёт объём выборки. Чтобы оценить долю правильных ответов с погрешностью $\pm 0.02$ с вероятностью не меньше $0.95$, положим $2 e^{-2n \cdot 0.02^2} \le 0.05$:

Метод	Нужно примеров	Предположения
Чебышёв, с $\sigma^2 \le 1/4$	12 500	конечная дисперсия
Хёфдинг	4612	независимость, ограниченность
Нормальное приближение	2401	$n$, достаточно большое для центральной предельной теоремы

Нормальное приближение требует меньше всего примеров, и именно им пользуются доверительные интервалы; оценке Хёфдинга нужно примерно вдвое больше примеров, зато она гарантированно выполняется при любом $n$.

Откуда берётся показатель экспоненты#

Дополнительный материал: набросок доказательства неравенства Хёфдинга. Остальная часть заметки на него не опирается.

Доказательство — неравенство Маркова, применённое к экспоненте, — метод Чернова (Chernoff method). Для любого $t > 0$

$$P(\bar X_n - \mu \ge \varepsilon) = P\big(e^{t n (\bar X_n - \mu)} \ge e^{t n \varepsilon}\big) \le e^{-t n \varepsilon}\, E\big[e^{t n (\bar X_n - \mu)}\big] = e^{-t n \varepsilon} \prod_{i=1}^n E\big[e^{t (X_i - \mu)}\big] ,$$

где независимость превратила математическое ожидание произведения в произведение математических ожиданий — производящих функций моментов из заметки о математическом ожидании. Для величины со значениями в $[a, b]$ лемма Хёфдинга (Hoeffding’s lemma) ограничивает каждый множитель величиной $e^{t^2 (b-a)^2 / 8}$. Квадратичным показатель делает именно ограниченность. Пусть $\psi(t) = \log E[e^{t(X - \mu)}]$. Тогда $\psi(0) = 0$ и $\psi'(0) = E[X - \mu] = 0$, а $\psi''(t)$ — дисперсия $X$ при её распределении, перевзвешенном множителем $e^{tx}$ и заново нормированном, которое по-прежнему сосредоточено на $[a, b]$; дисперсия величины со значениями в $[a, b]$ не больше $(b - a)^2/4$. Формула Тейлора вместе с этими тремя фактами даёт $\psi(t) \le \frac{t^2}{2} \cdot \frac{(b-a)^2}{4} = t^2 (b-a)^2/8$. Оценка $\exp(-tn\varepsilon + n t^2 (b-a)^2/8)$ минимальна при $t = 4\varepsilon/(b-a)^2$, что даёт $\exp(-2n\varepsilon^2/(b-a)^2)$; то же рассуждение для нижнего хвоста даёт множитель 2. Неравенство Маркова, применённое к $X^k$, даёт полиномиальные оценки хвостов, а применённое к $e^{tX}$ — экспоненциальные, если производящая функция моментов существует.

Первая граница обобщения#

Риск модели $R(h)$ — её ожидаемая функция потерь на новых данных, а её ошибка на валидационной выборке $\hat R(h)$ — среднее по $n$ независимым валидационным примерам. Для одной модели, зафиксированной заранее, неравенство Хёфдинга с функцией потерь в $[0, 1]$ даёт $P(\lvert \hat R(h) - R(h) \rvert \ge \varepsilon) \le 2 e^{-2n\varepsilon^2}$. Но обычно модель выбирают на валидационной выборке — лучшую из $K$ кандидатов, полученных при подборе гиперпараметров. Оценка объединения по $K$ событиям «модель $k$ отклоняется на $\varepsilon$» даёт сразу для всех $K$ моделей

$$P\big(\exists k : \lvert \hat R(h_k) - R(h_k) \rvert \ge \varepsilon\big) \le 2K e^{-2n\varepsilon^2} .$$

Приравняем правую часть к $\delta$: с вероятностью не меньше $1 - \delta$ каждая из $K$ моделей, а значит, и выбранная, удовлетворяет неравенству

$$\lvert \hat R(h) - R(h) \rvert \le \sqrt{\frac{\ln K + \ln(2/\delta)}{2n}} .$$

Для $K = 1\,000$ моделей и $n = 10\,000$ валидационных примеров при $\delta = 0.05$ запас равен $0.023$. Число кандидатов входит только через $\ln K$, поэтому в тысячу раз больше кандидатов обходится лишь в несколько раз большим объёмом данных. Рисунок показывает этот запас рядом с типичным эффектом выбора, когда все $K$ моделей на самом деле одинаково хороши:

Рисунок

Насколько лучшая из K одинаково точных моделей выглядит лучше, чем есть

У лучшей из 1000 одинаково точных моделей с независимыми ошибками доля правильных ответов на валидационной выборке в среднем на 1.3 процентного пункта выше истинной. Это и есть механизм переобучения на валидационной выборке (overfitting to a validation set) и причина, по которой итоговую модель оценивают на тестовой выборке, никак не участвовавшей в её выборе. Рассуждение предполагает, что $K$ кандидатов зафиксированы до того, как просмотрена валидационная выборка; поиск, который предлагает новых кандидатов по валидационным результатам, например байесовская оптимизация, требует большей осторожности. Для бесконечного числа кандидатов, например всех значений весов нейросети, $\ln K$ заменяется мерами ёмкости класса моделей; на практике курс машинного обучения вместо этого оценивает ошибку на отложенных данных.

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

	Без неравенств	С ними
Ошибка среднего	«мала при большом $n$»	Чебышёв: $P \le \sigma^2/(n\varepsilon^2)$; Хёфдинг: $P \le 2e^{-2n\varepsilon^2/(b-a)^2}$
Объём выборки для $\pm 0.02$ с вероятностью 95%	на глаз	4612 гарантированно (Хёфдинг), 2401 приближённо (по нормальному закону)
Модель, выбранная из $K$	её валидационный результат принимают за чистую монету	запас $\sqrt{(\ln K + \ln(2/\delta))/(2n)}$ сразу для всех $K$

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

• Оценки рассчитаны на худший случай. Они верны для любого распределения с указанным свойством и потому грубы для каждого конкретного; для нормальных хвостов оценка Чебышёва ошибается на порядки.
• Неравенству Хёфдинга нужны ограниченность и независимость. Функции потерь с тяжёлыми хвостами или примеры, которые приходят коррелированными группами (несколько от одного пользователя, почти дубликаты), нарушают эти предположения; тогда нужны другие инструменты: оценки медианы средних (median-of-means) для тяжёлых хвостов, оценки по независимым блокам для сгруппированных данных и неравенство Бернштейна, когда дисперсия много меньше размаха.
• Оценка объединения не учитывает, насколько похожи кандидаты. Модели из подбора гиперпараметров делают сильно коррелированные предсказания, поэтому реальный эффект выбора меньше, чем подсказывает оценка с $\ln K$.

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

• Неравенство Маркова: $P(X \ge a) \le E[X]/a$ при $X \ge 0$. Неравенство Чебышёва: $P(\lvert X - \mu \rvert \ge k\sigma) \le 1/k^2$.
• Неравенство Хёфдинга: для независимых $X_i \in [a, b]$ выполняется $P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le 2e^{-2n\varepsilon^2/(b-a)^2}$ — экспоненциально мало по $n$.
• Все три — неравенство Маркова, применённое к функции от $X$: к самой величине, к её квадрату, к её экспоненте.
• Чтобы оценить долю с погрешностью $\pm 0.02$ с вероятностью 95%, нужно 4612 примеров по Хёфдингу и около 2401 по нормальному приближению.
• При $K$ кандидатах каждый валидационный результат с вероятностью не меньше $1 - \delta$ отличается от истинного значения не более чем на $\sqrt{(\ln K + \ln(2/\delta))/(2n)}$; лучший из многих выглядит лучше, чем есть.

Код#

Оценки против точных значений, объёмы выборок и эффект выбора в симуляции:

import numpy as np, math
from scipy import stats

# Markov and Chebyshev against the truth
print(round(0.2 / 2, 2), f'{math.exp(-10):.1e}')                  # 0.1 4.5e-05: Markov's bound vs Exp(mean 0.2)
print([round(1 / k**2, 3) for k in (2, 3)], [round(float(2 * stats.norm.sf(k)), 4) for k in (2, 3)])   # [0.25, 0.111] [0.0455, 0.0027]

# the share of heads in n flips off by at least 0.1: exact, Chebyshev, Hoeffding
for n in (100, 1000):
    S = stats.binom(n, 0.5)
    exact = S.cdf(int(0.4 * n)) + S.sf(int(0.6 * n) - 1)
    print(n, f'{exact:.1e}', 25 / n, f'{2 * math.exp(-0.02 * n):.1e}')
# 100 5.7e-02 0.25 2.7e-01
# 1000 2.7e-10 0.025 4.1e-09

# examples needed to estimate an accuracy within 0.02 with probability 0.95: Hoeffding, Chebyshev, normal approximation
print(math.ceil(math.log(2 / 0.05) / (2 * 0.02**2)), math.ceil(0.25 / (0.02**2 * 0.05)), math.ceil((1.96 * 0.5 / 0.02) ** 2))   # 4612 12500 2401

# the best of K = 1,000 identical models (true accuracy 0.8), each on 10,000 validation examples, 2,000 times
rng = np.random.default_rng(0)
best = (rng.binomial(10_000, 0.8, size=(2000, 1000)) / 10_000).max(axis=1)
eps = math.sqrt((math.log(1000) + math.log(40)) / (2 * 10_000))
print(round(float(best.mean()), 4), round(eps, 4), float((best - 0.8 > eps).mean()))   # 0.8129 0.023 0.0

Дальше#

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

Литература#

• W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301), 1963.
• S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. Глава 2 (основные неравенства, метод Чернова, лемма Хёфдинга).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Главы 2–4 (конечные классы гипотез и равномерная сходимость).
• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Глава 10 (неравенства и предельные теоремы).