Теория вероятностей
PAC-обучение
Нейронная сеть с миллиардом параметров обучается на миллионе примеров и обобщается. Классическая теория PAC-обучения предсказывает катастрофу: нужно экспоненциально много данных. VC-теория и современные bound через нормы показывают, что на самом деле работает и почему глубокое обучение избегает переобучения.
- SVM: обобщение гарантируется через margin - алгоритм минимизирует VC-размерность «мягко» через максимизацию отступа. Bounds через margin не зависят от числа признаков $d$, только от отступа.
- Регуляризация L2 (weight decay): добавление $\lambda\|w\|^2$ ограничивает норму весов и через PAC-Bayes bounds гарантирует обобщение пропорционально $\|w\|^2/n$.
- Double descent: классическая теория предсказывает рост ошибки при числе параметров $> n$, но интерполирующие нейросети обобщаются. Новые теории (implicit regularization, neural tangent kernel) объясняют это через иные bounds.
Цели урока
- Формулировать PAC-модель обучения и доказывать bounds для конечного гипотезного класса
- Определять VC-размерность и применять теорему Вапника-Червоненкиса
- Вычислять VC-размерность для гиперплоскостей, решающих деревьев и нейронных сетей
Предварительные знания
- Концентрация меры: неравенство Хоффдинга
- Основы статистического обучения: эмпирический риск
- Комбинаторика: лемма Саауэра
PAC-модель и bounds для конечного класса
PAC (Probably Approximately Correct): алгоритм $A$ PAC-обучает класс $\mathcal{H}$ если для любых $\varepsilon, \delta > 0$ существует $m_0(\varepsilon, \delta)$ такое, что при $m \geq m_0$ и $S \sim D^m$: с вероятностью $\geq 1-\delta$ по выборке $S$, $R(h_S) - \min_h R(h) \leq \varepsilon$. Для конечного $|\mathcal{H}| < \infty$: достаточно $m \geq \frac{\log(|\mathcal{H}|/\delta)}{2\varepsilon^2}$ (из Хоффдинга + union bound). Логарифмическая зависимость от $|\mathcal{H}|$ - ключевой результат.
VC-теорема (Вапник-Червоненкис, 1971): для класса $\mathcal{H}$ с VC-размерностью $d$, с вероятностью $1-\delta$: $\sup_h |\hat R(h) - R(h)| \leq \sqrt{\frac{8d \ln(em/d) + 8\ln(4/\delta)}{m}}$. Это равномерный bound по всему классу - ключевое отличие от простого применения Хоффдинга. Лемма Саауэра: $|\mathcal{H}|$ на $m$ точках $\leq \sum_{k=0}^d \binom{m}{k} \leq (em/d)^d$.
VC-теория даёт bounds, которые становятся вакуумными для нейронных сетей: VC-размерность сети с $W$ весами $\Omega(W \log W)$ - при $W = 10^{10}$ и $n = 10^6$ bound хуже 1. Современные теории (PAC-Bayes, margin bounds, compression bounds) дают осмысленные гарантии через другие complexity measures.
Владимир Вапник и Алексей Червоненкис разработали свою теорию в Москве в 1968-19
Владимир Вапник и Алексей Червоненкис разработали свою теорию в Москве в 1968-1971 годах, публикуя в советских журналах. На Западе она стала известна только в 1990-х через монографию Вапника «Природа статистического обучения». Лесли Валиант независимо предложил PAC-модель в 1984 году, получив за неё Тьюринговскую премию в 2010 году.
PAC-модель и конечный класс гипотез
Лесли Вэлиант в 1984 году опубликовал «A Theory of the Learnable» в Communications of the ACM - статью, за которую он получил премию Тьюринга в 2010 году. Введённая там PAC-модель связала обучаемость с числом образцов: для класса из $|\mathcal{H}| = 10^6$ гипотез достаточно $m \approx 1680$ примеров, чтобы найти гипотезу с ошибкой $\le 0.01$ и доверием $0.95$.
Класс из $|\mathcal{H}| = 10^6$ гипотез. При $\varepsilon = 0.01$, $\delta = 0.05$ минимальное $m$ для PAC?
VC-размерность и разбиение
Владимир Вапник и Алексей Червоненкис в 1971 году в Институте проблем управления АН СССР ввели меру сложности гипотетического класса, не зависящую от числа гипотез. VC-размерность нейросети с $W$ весами оценивается как $O(W \log W)$: для GPT-3 с $1.75 \cdot 10^{11}$ параметров классическая граница VC бессмысленна, а на практике обобщение работает - это парадокс, объясняемый феноменом double descent.
Какова VC-размерность класса полупространств в $\mathbb{R}^d$?
Теорема VC и граница обобщения
Антон Блюмер, Эндрю Эренфойхт, Дэвид Хаусслер и Манфред Вармут в 1989 году доказали фундаментальную теорему: $\mathcal{H}$ PAC-обучаема тогда и только тогда, когда $\mathrm{VC\text{-}dim}(\mathcal{H}) < \infty$. Эта эквивалентность управляет проектированием современных моделей: ResNet-152 на ImageNet с 60 миллионов параметров обобщает на 1.28 миллиона образцов лучше, чем предсказывает классическая граница VC.
VC-размерность линейного классификатора в $\mathbb{R}^{100}$ равна 101. При $\varepsilon = 0.05$, $\delta = 0.05$ оценка минимального $m$?
VC-размерность перцептрона
Гиперплоскости в $\mathbb{R}^d$: VC-размерность = $d+1$. Доказательство нижней оценки: $d+1$ точек в общем положении можно разбить любым способом. Верхняя оценка: $d+2$ точек нельзя разбить произвольно. Следствие (теорема VC): $m \geq C(d \log(d/\varepsilon) + \ log(1/\delta))/\varepsilon$ достаточно для PAC-обучения. Заметим: не экспоненциально в $d$, а линейно - это делает обучение перцептрона практичным.
Итоги
- PAC-обучение: с вероятностью $1-\delta$, ошибка $\leq \varepsilon$ при $m = O(\log(|\mathcal{H}|/\delta)/\varepsilon^2)$ для конечных классов.
- VC-размерность характеризует сложность бесконечных классов: $m = O(d/\varepsilon^2 \cdot \log(1/\varepsilon\delta))$ достаточно.
- Современная теория уходит от VC к margin bounds, PAC-Bayes и implicit regularization.
Связь с другими темами
Концентрация меры (prob-22) - главный инструмент: PAC bounds строятся через Хоффдинг + union bound. Информационно-теоретические bounds (prob-25): PAC-Bayes bounds используют KL-дивергенцию между априорным и апостериорным распределением весов. Байесовский взгляд на обобщение связывает margin bounds с регуляризацией.
- Prob 22 — связан
- Prob 25 — связан
Вопросы для размышления
- SVM с $d = 10^6$ признаков имеет VC-размерность $10^6$, но bound через margin $\gamma$: $R(h) \leq \hat R(h) + O(\|w\|^2/(\gamma^2 m))$, не зависящий от $d$. Почему margin-bound не зависит от числа признаков?
- Какой принцип лежит в основе этого - и как weight decay реализует его на практике?