Growth function и лемма Сауэра

1971 год. Владимир Вапник и Алексей Червоненкис задают вопрос: сколько различных способов класс гипотез H может разбить m точек на два класса? Ответ - не бесконечность. Для линейного классификатора в R^d это в точности полином степени d. Именно эта полиномиальность делает обобщение возможным: бесконечный класс гипотез ведёт себя как конечный.

• **ImageNet training:** 1.28 млн примеров, модель с 10^9 параметрами - growth function в теории астрономическая, но double descent объясняет обобщение там, где VC-теория уже ничего не говорит
• **Neural scaling laws (Kaplan 2020):** test loss ~ (data/params)^alpha - эмпирическая кривая, которая воспроизводит предсказания PAC-теории для малых моделей и уходит от них для больших
• **Sample complexity:** PAC-bound через growth function даёт m >= O(d log(1/eps)/eps) - именно это число обучающих примеров нужно для гарантии обобщения с VC-размерностью d

Предварительные знания

• VC-размерность: максимальный размер множества точек, которые H может разбить произвольно
• Shattering: H shatters S, если реализует все 2^|S| разбиений

• VC dimension: мера сложности гипотезного класса

Growth function: считаем паттерны

Growth function: считаем паттерны

Пусть H - класс гипотез, X - пространство признаков. **Growth function** $\Pi_H(m)$ считает максимальное число различных паттернов разбиения, которое H реализует на m точках:

Проще: берём m точек в произвольном положении, смотрим сколько различных "раскрасок" класс H умеет на них нарисовать. Максимум по всем возможным расположениям m точек - это и есть $\Pi_H(m)$. Простейшая верхняя граница: не более $2^m$ паттернов. Вопрос - насколько далеко реальный рост от этого потолка?

**Три класса - три судьбы growth function.** Конечный класс $|H| = N$: $\Pi_H(m) \leq N$, рост ограничен константой. Линейные классификаторы в $\mathbb{R}^d$: $\Pi_H(m) = O(m^d)$, полиномиальный рост. Класс всех функций: $\Pi_H(m) = 2^m$, экспоненциальный рост. Лемма Сауэра объясняет, почему второй случай - норма для разумных гипотезных классов.

Лемма Сауэра-Шелаха: полином побеждает экспоненту

Лемма Сауэра-Шелаха: полином побеждает экспоненту

1972 год. Норберт Сауэр и независимо Сахарон Шела доказывают одну лемму. Через 20 лет она становится фундаментом PAC-learning.

**Лемма Сауэра-Шелаха.** Если $\text{VCdim}(H) = d$, то для всех $m \geq 1$: $$\Pi_H(m) \leq \sum_{i=0}^{d} \binom{m}{i}$$ При $m \geq d$ правая часть равна $O(m^d)$ - полиномиальный рост степени d.

Что это означает на практике: класс с VC-размерностью $d = 10$ может реализовать не $2^{1000}$, а порядка $1000^{10} \approx 10^{30}$ паттернов на 1000 точках. Это много - но конечно. Логарифм growth function ($\log \Pi_H(m) \leq d \log m$) заменяет $\log |H|$ в generalization bounds - именно так бесконечный класс гипотез получает конечную гарантию обобщения.

При $m = 100$ разрыв между реальным ростом и теоретическим потолком - $10^{24}$ раз. Именно это расстояние превращает бесконечный класс гипотез в управляемый с точки зрения generalization.

PAC-bound через growth function

PAC-bound через growth function

Growth function замещает $|H|$ в union bound. Стандартный generalization bound для конечного класса: $$\mathbb{P}[\sup_{h \in H} |R(h) - \hat{R}(h)| > \epsilon] \leq 2|H| e^{-2m\epsilon^2}$$ Для бесконечного класса H заменяем $|H|$ на $\Pi_H(2m)$ - growth function на $2m$ точках (двойная выборка нужна для аккуратной симметризации):

Подставляя лемму Сауэра ($\Pi_H(2m) \leq (2m)^d$) и решая неравенство на $m$, получаем PAC sample complexity:

**Читать эту формулу буквально:** чтобы линейный классификатор в $\mathbb{R}^d$ обобщился с ошибкой не хуже $\epsilon$ с вероятностью $1 - \delta$, нужно $\Theta(d / \epsilon^2)$ примеров - линейно по VC-размерности. Для логистической регрессии в $\mathbb{R}^{1000}$ это порядка $10^4$ примеров при $\epsilon = 0.05$. Для нейросети с $d \sim 10^9$ - теория говорит $\sim 10^{10}$ примеров. ImageNet имеет 1.28 млн. Что-то идёт не так.

Double descent: где VC-теория умолкает

Double descent: где VC-теория умолкает

GPT-3 имеет 175 млрд параметров. По VC-теории ему нужны сотни миллиардов примеров. По факту - хватило Common Crawl плюс Books3 (порядка 300 млрд токенов, но это не labeled data для конкретной задачи). BERT fine-tuning на GLUE работает при нескольких тысячах примеров. VC-theory молчит.

**Double descent (Belkin et al. 2019, Nakkiran et al. 2020):** когда количество параметров превышает количество примеров, тест-ошибка не растёт монотонно - она падает снова. Классическая U-образная кривая bias-variance tradeoff существует только в левой части. Neural scaling laws (Kaplan 2020) описывают правую часть:

Growth function и лемма Сауэра остаются правильными - они просто недостаточно точны для overparameterized режима. Bounds через VC-размерность для нейросетей вакуумно верны и практически бесполезны. Rademacher complexity и PAC-Bayes дают более tight bounds, но фундаментально проблема не решена: лучшие теоретические гарантии для современных нейросетей хуже эмпирических результатов на порядки.

Что забрать из урока

• **Growth function** $\Pi_H(m)$ - максимальное число паттернов разбиения H на m точках. Верхний потолок $2^m$, реальный рост зависит от VC-размерности
• **Лемма Сауэра-Шелаха:** $\Pi_H(m) \leq \sum_{i=0}^{d} \binom{m}{i} = O(m^d)$ при VCdim $= d$. Бесконечный класс ведёт себя как полиномиально большой конечный
• **PAC sample complexity через growth function:** $m \geq O(d \log(1/\epsilon) / \epsilon^2)$ - линейно по VC-dim, полулогарифмически по точности
• **Double descent:** для overparameterized нейросетей VC-bounds слишком слабые на 5-10 порядков. Neural scaling laws (Kaplan 2020) дают эмпирическую замену
• **Практический итог:** growth function объясняет обобщение классических методов (SVM, логистическая регрессия). Для глубоких сетей - необходимое, но недостаточное условие

Что дальше

Growth function - один инструмент в арсенале теории обобщения:

• Rademacher complexity — Более tight мера: учитывает распределение данных, а не только комбинаторную сложность
• Uniform convergence — Теорема, для доказательства которой используется лемма Сауэра как ключевой ингредиент
• PAC-Bayes bounds — Стохастические bounds, дающие более tight гарантии для нейросетей через prior/posterior
• Deep generalization — Эмпирические феномены за пределами VC-теории: double descent, grokking, neural scaling

Вопросы для размышления

• Линейный классификатор в R^100 имеет VC-dim около 101. PAC-bound требует порядка 2000 примеров при eps=0.1. Нейросеть с 10^7 параметрами на той же задаче работает с 500 примерами. Как согласовать эти два факта?
• Sauer bound даёт Pi_H(m) = O(m^d). Что происходит с bounds когда d растёт вместе с m (например, d = m/2)?
• Neural scaling laws говорят: test_loss ~ (data/params)^0.076. Как это связано с O(d log(1/eps)/eps^2) из PAC-теории для маленьких моделей?

Связанные уроки

• lt-04-vc-dimension — VC-размерность как граница, где рост переключается с полиномиального на экспоненциальный
• lt-06-rademacher — Rademacher complexity - более тонкая мера, заменяющая growth function в современных bounds
• lt-07-uniform-convergence — Uniform convergence theorem строится поверх леммы Сауэра
• lt-13-deep-generalization — Double descent и neural scaling laws - эмпирический ответ на то, где VC-теория ломается
• lt-03-agnostic-pac — PAC-bounds через growth function продолжают agnostic learning framework
• stat-01-sampling