Теория вероятностей
Концентрация меры
Как доказать, что SGD обобщается? Неравенство Хоффдинга даёт $P(\bar X_n - \mu > \varepsilon) \leq e^{-2n\varepsilon^2/(b-a)^2}$ - вероятность «плохого» среднего убывает экспоненциально быстро. Это гораздо сильнее ЦПТ и является основой теоретического машинного обучения.
- Гарантии обобщения в ML: неравенство Хоффдинга + union bound даёт $P(\sup_{h\in\mathcal{H}} |\hat R(h) - R(h)| > \varepsilon) \leq 2|\mathcal{H}| e^{-2n\varepsilon^2}$ - основа PAC-learning bounds для конечных гипотезных классов.
- Случайный лес (Random Forest): теорема Азумы оправдывает стабильность оценок - выброс одного обучающего примера меняет предсказание не более чем на $c/\sqrt{n}$ с экспоненциальной вероятностью.
- Дифференциальная приватность: механизм Гаусса использует концентрацию гауссовского шума для гарантий приватности. Параметры $\varepsilon$-$\delta$-DP напрямую выводятся из хвостовых оценок.
Цели урока
- Доказывать и применять неравенства Маркова, Чебышёва, Хоффдинга для хвостовых оценок
- Формулировать неравенство Азумы для мартингалов и применять к функциям от независимых переменных
- Строить union bound и объяснять его роль в гарантиях обобщения
Предварительные знания
- Математическое ожидание и дисперсия
- Производящие функции моментов (MGF)
- Мартингалы и условное ожидание
Иерархия неравенств концентрации
Неравенство Маркова: $P(X \geq t) \leq \mathbb{E}[X]/t$ для $X \geq 0$ - полиномиальный хвост. Чебышёв: $P(|X-\mu| \geq t) \leq \sigma^2/t^2$ - использует дисперсию. Хоффдинг: для $X_i \in [a_i, b_i]$ независимых, $P(\bar X_n - \mu \geq \varepsilon) \leq \exp\left(-2n^2\varepsilon^2/\sum(b_i-a_i)^2\right)$ - экспоненциальный хвост. Каждое следующее неравенство требует больше информации о распределении, но даёт гораздо более резкую оценку.
Неравенство Азумы-Хоффдинга для мартингалов: если $|X_k - X_{k-1}| \leq c_k$ п.н. (ограниченные разности), то $P(X_n - X_0 \geq t) \leq \exp(-t^2/(2\sum c_k^2))$. Метод ограниченных разностей: для функции $f(X_1,\ldots,X_n)$ независимых переменных, где замена одной переменной меняет $f$ не более чем на $c_i$, Азума даёт $P(f - \mathbb{E}[f] \geq t) \leq \exp(-2t^2/\sum c_i^2)$.
Неравенство Хоффдинга требует ограниченности переменных. Для субгауссовских переменных (unbounded, но с лёгкими хвостами) используют sub-Gaussian concentration. Для тяжёлых хвостов (Pareto, Cauchy) ни Хоффдинг, ни Чебышёв с $p=2$ не дают экспоненциальных гарантий - нужны усечённые оценки или неравенства для $L^p$ моментов.
Василий Чебышёв доказал своё неравенство в 1867 году как инструмент доказательст
Василий Чебышёв доказал своё неравенство в 1867 году как инструмент доказательства закона больших чисел. Серж Хоффдинг получил своё экспоненциальное неравенство в 1963 году, работая в статистике. Теорема Азумы (1967) обобщила идею на мартингалы. В 1980-2000-х эти результаты стали центральными в теории вычислительной сложности и математическом ML.
Базовые неравенства: Марков и Чебышёв
Пафнутий Чебышёв в 1867 году доказал классическое неравенство, ставшее инструментом для строгого вывода закона больших чисел. Сегодня A/B-тесты Microsoft Bing на 100 миллионах пользователей используют эту иерархию: Марков → Чебышёв → Хёффдинг - для определения минимального размера выборки, гарантирующего отклонение оценки конверсии не более чем на 0.1% при доверии 99%.
$X$ - неотрицательная с $E[X] = 3$. Что даёт неравенство Маркова для $P(X \ge 15)$?
Марков: $P(X \ge t) \le E[X]/t = 3/15 = 1/5$.
Неравенство Хёффдинга
Вассилий Хёффдинг в 1963 году доказал экспоненциальную границу для сумм ограниченных независимых переменных, что стало революцией в математической статистике. PAC-обучение, разработанное Лесли Вэлиантом в 1984 году, опирается на эту границу: для классификатора с границей обобщения $0.01$ при $\delta = 0.05$ достаточно $n \ge 530$ примеров - на порядки меньше, чем по Чебышёву.
Монета с $P(H) = p$. По двустороннему Хёффдингу, какое $n$ обеспечит $P(|\hat p - p| \ge 0.05) \le 0.01$?
Двусторонний Хёффдинг: $P(|\hat p - p| \ge \varepsilon) \le 2 e^{-2n\varepsilon^2} \le \delta$, отсюда $n \ge \log(2/\delta)/(2\varepsilon^2) = \log(200)/0.005 \approx 1060$.
Неравенство Азумы для мартингалов
Казуоки Азума в 1967 году обобщил Хёффдинга на зависимые величины, что позволило анализировать рандомизированные алгоритмы. Анализ QuickSort (Hoare 1961) на массивах из 10000 элементов даёт сложность $O(n \log n)$ с экспоненциальной концентрацией: вероятность отклонения от $E[T]$ более чем на $10\%$ ограничена $e^{-c \log^2 n}$.
Функция $f(X_1,\dots,X_n)$ - $L$-Липшицева, $X \sim N(0,I_n)$. Гауссовская концентрация даёт:
Логарифмическое неравенство Соболева для гауссовской меры даёт безразмерную концентрацию Липшицевых функций.
Сравнение хвостов на задаче обобщения
Задача: $n=1000$, $\varepsilon=0.05$. Чебышёв (при $\sigma^2 \leq 1/4$): $P \leq 0.25/(1000 \cdot 0.0025) = 0.1$. Хоффдинг (при $X_i \in [0,1]$): $P \leq e^{-2\cdot 1000 \cdot 0.0025} = e^{-5} \approx 0.007$. Разница: 14x. При $n=10000$: Чебышёв даёт 0.01, Хоффдинг - $e^{-50} \approx 10^{-22}$. Для ML на больших данных важен именно Хоффдинг.
Итоги
- Маркова $\leq \mathbb{E}/t$, Чебышёв $\leq \sigma^2/t^2$, Хоффдинг $\leq e^{-2n\varepsilon^2/(b-a)^2}$: иерархия от полиномиального к экспоненциальному убыванию.
- Азума расширяет Хоффдинг на мартингалы с ограниченными разностями.
- Union bound + Хоффдинг = базовые гарантии обобщения для конечных гипотезных классов.
Связь с другими темами
PAC-обучение (prob-26) строится на этих неравенствах: VC-теория использует концентрацию для равномерных bound по всему гипотезному классу. Высокие размерности (prob-21): JL-лемма доказывается именно через хоффдинговскую концентрацию случайных проекций.
- Prob 26 — связан
- Prob 21 — связан
Вопросы для размышления
- Метод ограниченных разностей говорит: функция, нечувствительная к изменению одного аргумента, концентрируется. Как это связано с понятием алгоритмической стабильности в ML - и почему стабильные алгоритмы (как ridge regression) имеют лучшие гарантии обобщения?