Статистическая теория обучения

VC dimension: сколько 'информации' в гипотезе

Shattering: что значит 'разбить' множество точек

**GPT-4: 1.7 триллиона параметров, VC dimension примерно $10^{12}$.** ImageNet: 1.2 миллиона примеров. Классическая PAC-теория через VC выдаёт гарантию хуже подбрасывания монеты. Реальность: 89% top-1 accuracy, SOTA на 2024 год. Разрыв между теорией и практикой - не баг. Это сигнал, что VC dimension - необходимый, но не достаточный инструмент. Сначала разберём что он говорит. Потом - где ломается.

1971 год. Владимир Вапник в советском ЦЭМИ публикует теорему о сжатии: для бесконечного класса гипотез $H$ PAC-гарантия зависит от конечного числа - максимального числа точек, которые $H$ может разбить любым способом. Это число назовут VC dimension. На перфокартах, без GPU, без ImageNet - и за 40 лет до того, как нейросети перевернут всё.

**Проблема $\log|H|$**: предыдущий урок даёт sample complexity $m \geq \frac{1}{\varepsilon}\log\frac{|H|}{\delta}$ - но только для конечных классов. Линейный классификатор в $\mathbb{R}^{100}$ - бесконечный класс. $|H| = \infty$, $\log|H| = \infty$, формула рассыпается. VC dimension решает именно это.

Shattering: что значит 'разбить' множество точек

Класс гипотез $H$ **shatter** (разбивает) множество точек $C = \{x_1, \ldots, x_d\}$, если для **каждой** из $2^d$ возможных разметок $\{0, 1\}^d$ существует гипотеза $h \in H$, которая реализует эту разметку. Иначе говоря - $H$ достаточно богат, чтобы любое распределение меток на $d$ точках выразить одной гипотезой.

Интервалы на прямой: VC = 2

Класс гипотез - все интервалы [a, b] на числовой прямой; метка 1 если точка внутри

Три точки: $x_1 < x_2 < x_3$. Разметка (1, 0, 1) - нужно накрыть $x_1$ и $x_3$, но не $x_2$. Один связный интервал не может. Значит, 3 точки не shatter. Две точки $x_1 < x_2$: все 4 разметки реализуются: - (0, 0): интервал [x_2+1, x_2+2] - не накрывает ни одну - (1, 0): интервал [x_1-0.5, x_1+0.5] - (0, 1): интервал [x_2-0.5, x_2+0.5] - (1, 1): интервал [x_1-0.5, x_2+0.5] VC dim(интервалы) = 2.

Полуплоскости в $\mathbb{R}^d$: VC = d+1

Линейные классификаторы - хребет ML

Линейный классификатор в $\mathbb{R}^d$: $h(x) = \text{sign}(w^\top x + b)$. VC dim = $d+1$. В $\mathbb{R}^2$ (плоскость) - shatter любые 3 точки в общем положении, 4 нельзя (XOR-паттерн). В $\mathbb{R}^{784}$ (MNIST пикселей) - VC dim = 785. PyTorch однострочник: ```python nn.Linear(784, 1) # VC dimension = 785 ``` На 60,000 обучающих примерах MNIST - PAC-bound даёт гарантию. Но нейросеть с VC ~ 10^8 на тех же 60K - нет.

Самопроверка: что лучше всего обобщает раздел "Shattering: что значит 'разбить' множество точек"?

VC dimension: определение

**VC dimension** класса $H$ - это наибольший размер $d$ такого множества точек $C$, что $H$ shatter $C$. Формально:

Таблица VC dimension для реальных классов:

Класс гипотез	VC dimension	Применение в ML
Константы $\{0, 1\}$	0	Тривиальный baseline
Пороговые функции на $\mathbb{R}$	1	Простейшие правила
Интервалы на $\mathbb{R}$	2	1D аномалии
Полуплоскости в $\mathbb{R}^d$	$d+1$	Logistic regression, SVM
Круги в $\mathbb{R}^2$	3	RBF-ядра (специальный случай)
Нейросети (W параметров)	$O(W \log W)$	Все современные LLM

**Интуиция VC**: чем больше VC dimension, тем 'гибче' класс гипотез - больше разметок выразимо. Но гибкость стоит: нужно больше примеров для гарантии обобщения. VC - это мера выразительности в единицах 'сколько точек контролируем полностью'.

Класс $H$ состоит из всех синглтонов: $h_a(x) = \mathbf{1}[x = a]$ на $\mathbb{R}$. Чему равен VCdim(H)?

Одна точка $x_1$: разметка (1) - $h_{x_1}$, разметка (0) - любой $h_a$ с $a \neq x_1$. Две точки $\{x_1, x_2\}$: разметка (1, 1) нереализуема - синглтон не может покрыть сразу две точки. VCdim = 1. Важно: бесконечный класс не обязательно имеет бесконечный VCdim.

PAC bound через VC: sample complexity

Теорема Вапника-Червоненкиса даёт sample complexity для реализуемого случая через VC dimension - заменяя $\log|H|$ на $d = \text{VCdim}(H)$:

Это работает для **любого** класса с конечным VC dimension - включая все бесконечные классы линейных классификаторов, деревьев решений, SVM. Константа $C$ - универсальная, не зависит от $H$. Только $d$ и $\varepsilon, \delta$.

Sample complexity для SVM в $\mathbb{R}^{10}$

Реальные числа

SVM с линейным ядром в $\mathbb{R}^{10}$: VCdim = 11. Хотим: $\varepsilon = 0.05$, $\delta = 0.01$. $m \geq \frac{8}{\varepsilon^2}\left(\ln\frac{2|H|}{\delta}\right)$ - старая формула: $|H| = \infty$, не работает. С VC: $m \gtrsim \frac{11}{0.05}\left(\ln\frac{1}{0.05} + \ln\frac{1}{0.01}\right) \approx 220 \cdot (3 + 4.6) \approx 1{,}670$ примеров. Hands-on: sklearn SVC на 1700 примерах с VC-гарантией обобщения.

**Нижняя оценка тоже верна**: существует дистрибуция, на которой любой алгоритм с менее чем $\Omega(d/\varepsilon)$ примерами не даст PAC-гарантию. VC dimension - **точная** характеристика, не просто верхняя оценка.

Самопроверка: что лучше всего обобщает раздел "PAC bound через VC: sample complexity"?

Где классика ломается: double descent

VC говорит: больше VC - хуже обобщение при фиксированных данных. Классический bias-variance tradeoff: переобучение при $d \gg m$. Это работало для SVM, деревьев, линейных моделей.

Потом пришли нейросети. В 2019 году Belkin et al. показали: если увеличить сеть за точку интерполяции обучающей выборки - ошибка на тесте снова начинает падать. Это назвали **double descent**.

Режим	Параметров	Тест-ошибка	VC-предсказание
Underfitting	мало	высокая	верно
Классическое переобучение	умеренно	сначала падает, потом растёт	верно
Интерполяция	= числу примеров	максимум	верно
Over-parameterized (deep learning)	>> данных	снова падает, SOTA	неверно

GPT-4 живёт в последней строке. VC-теория молчит - не потому что неверна, а потому что её bound перестаёт быть tight. Реальное обобщение определяется имплицитной регуляризацией SGD, плоскостью loss landscape, структурой данных - а не VC dimension сети.

Большой VC dimension означает плохое обобщение

VC dimension - верхняя оценка сложности; tight только в worst case

VC bound: при $d$ огромном и $m$ конечном - гарантии нет. Но гарантия нет $\neq$ не обобщается. Реальное обобщение зависит от алгоритма (SGD implicit bias), распределения (структура реальных данных), архитектуры. VC описывает worst-case - а нейросети на реальных данных работают в best-case режиме, который теория пока не захватила.

Самопроверка: что лучше всего обобщает раздел "Где классика ломается: double descent"?

Функция роста: путь к лемме Сауэра

Shattering - бинарный вопрос: shatter или нет. Но между 'полностью shatter' и 'вообще не shatter' есть спектр. **Функция роста** $\Pi_H(m)$ считает максимальное число различных разметок, которые $H$ реализует на $m$ точках:

Если $\text{VCdim}(H) = d$, то лемма Сауэра-Шелы говорит: $\Pi_H(m) \leq \sum_{i=0}^{d} \binom{m}{i}$. При $m > d$ это полином по $m$ степени $d$ - а не $2^m$. Именно этот переход от экспоненты к полиному делает VC-теорию содержательной: бесконечный класс с конечным VC ведёт себя как 'конечный' с точки зрения разметок.

**ML-следствие**: нейросеть с $10^9$ параметрами (VC ~ $10^9 \log 10^9$) на 1M примерах - функция роста полиномиальна. Не $2^{10^9}$, а примерно $(10^6)^{10^9 \log 10^9}$... что всё равно огромно. Tight bound из леммы Сауэра нужен для следующего урока про uniform convergence.

Самопроверка: что лучше всего обобщает раздел "Функция роста: путь к лемме Сауэра"?

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

**Shattering**: $H$ shatter $C$, если для каждой разметки $C$ существует $h \in H$, её реализующий
**VCdim(H)** = максимальный размер shatter-ируемого множества. Конечен для большинства ML-классов
**Интервалы** = 2, **полуплоскости в $\mathbb{R}^d$** = d+1, **нейросети** ~ $O(W \log W)$
**PAC bound**: $m = O(d/\varepsilon)$ примеров достаточно (и необходимо) для обобщения с VC dimension $d$
**Double descent**: deep learning нарушает VC-предсказание. VC - worst-case, реальное - average-case через implicit bias SGD
**Функция роста** $\Pi_H(m)$: переход от $2^m$ к полиному по $m$ при $m > d$ - ключ к uniform convergence

Что дальше

VC dimension - фундамент. Дальше - уточнения и современные альтернативы:

Growth function и лемма Сауэра — Полиномиальный рост функции роста при конечном VC - ключ к доказательству sample complexity
Rademacher complexity — Data-dependent мера сложности, работает в over-parameterized режиме где VC молчит
Generalization paradox в deep learning — Double descent подробно - что SGD implicit bias делает с обобщением

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

GPT-4 с VC ~ $10^{12}$ и 1.2M примерами ImageNet - PAC-теория не даёт гарантию. Что, по мнению текущей теории, объясняет его обобщение?
Класс деревьев решений глубины $k$ в $\mathbb{R}^d$ - как примерно оценить VC dimension через $k$ и $d$?
Double descent: в какой точке ('точка интерполяции') VC-предсказание и реальность расходятся? Что происходит после неё?

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

lt-05-growth-sauer — Лемма Сауэра связывает рост VC с sample complexity - продолжение этого урока
lt-06-rademacher — Rademacher complexity - современная альтернатива VC для data-dependent bounds
lt-13-deep-generalization — Paradox deep learning: VC предсказывает провал, реальность показывает SOTA
prob-04-bayes — PAC-Bayes связывает VC-мышление с байесовскими prior - мост между теориями
calc-01-sequences — Асимптотический анализ sample complexity требует предельного мышления
stat-01-sampling

Статистическая теория обучения

VC dimension: сколько 'информации' в гипотезе

Shattering: что значит 'разбить' множество точек

Интервалы на прямой: VC = 2

Класс гипотез - все интервалы [a, b] на числовой прямой; метка 1 если точка внутри

Полуплоскости в $\mathbb{R}^d$: VC = d+1

Линейные классификаторы - хребет ML

Самопроверка: что лучше всего обобщает раздел "Shattering: что значит 'разбить' множество точек"?

VC dimension: определение

**VC dimension** класса $H$ - это наибольший размер $d$ такого множества точек $C$, что $H$ shatter $C$. Формально:

Таблица VC dimension для реальных классов:

Класс гипотез	VC dimension	Применение в ML
Константы $\{0, 1\}$	0	Тривиальный baseline
Пороговые функции на $\mathbb{R}$	1	Простейшие правила
Интервалы на $\mathbb{R}$	2	1D аномалии
Полуплоскости в $\mathbb{R}^d$	$d+1$	Logistic regression, SVM
Круги в $\mathbb{R}^2$	3	RBF-ядра (специальный случай)
Нейросети (W параметров)	$O(W \log W)$	Все современные LLM

Класс $H$ состоит из всех синглтонов: $h_a(x) = \mathbf{1}[x = a]$ на $\mathbb{R}$. Чему равен VCdim(H)?

PAC bound через VC: sample complexity

Sample complexity для SVM в $\mathbb{R}^{10}$

Реальные числа

Самопроверка: что лучше всего обобщает раздел "PAC bound через VC: sample complexity"?

Где классика ломается: double descent

Режим	Параметров	Тест-ошибка	VC-предсказание
Underfitting	мало	высокая	верно
Классическое переобучение	умеренно	сначала падает, потом растёт	верно
Интерполяция	= числу примеров	максимум	верно
Over-parameterized (deep learning)	>> данных	снова падает, SOTA	неверно

Большой VC dimension означает плохое обобщение

VC dimension - верхняя оценка сложности; tight только в worst case

Самопроверка: что лучше всего обобщает раздел "Где классика ломается: double descent"?

Функция роста: путь к лемме Сауэра

Самопроверка: что лучше всего обобщает раздел "Функция роста: путь к лемме Сауэра"?

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

**Shattering**: $H$ shatter $C$, если для каждой разметки $C$ существует $h \in H$, её реализующий
**VCdim(H)** = максимальный размер shatter-ируемого множества. Конечен для большинства ML-классов
**Интервалы** = 2, **полуплоскости в $\mathbb{R}^d$** = d+1, **нейросети** ~ $O(W \log W)$
**PAC bound**: $m = O(d/\varepsilon)$ примеров достаточно (и необходимо) для обобщения с VC dimension $d$
**Double descent**: deep learning нарушает VC-предсказание. VC - worst-case, реальное - average-case через implicit bias SGD
**Функция роста** $\Pi_H(m)$: переход от $2^m$ к полиному по $m$ при $m > d$ - ключ к uniform convergence

Что дальше

VC dimension - фундамент. Дальше - уточнения и современные альтернативы:

Growth function и лемма Сауэра — Полиномиальный рост функции роста при конечном VC - ключ к доказательству sample complexity
Rademacher complexity — Data-dependent мера сложности, работает в over-parameterized режиме где VC молчит
Generalization paradox в deep learning — Double descent подробно - что SGD implicit bias делает с обобщением

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

GPT-4 с VC ~ $10^{12}$ и 1.2M примерами ImageNet - PAC-теория не даёт гарантию. Что, по мнению текущей теории, объясняет его обобщение?
Класс деревьев решений глубины $k$ в $\mathbb{R}^d$ - как примерно оценить VC dimension через $k$ и $d$?
Double descent: в какой точке ('точка интерполяции') VC-предсказание и реальность расходятся? Что происходит после неё?

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

lt-05-growth-sauer — Лемма Сауэра связывает рост VC с sample complexity - продолжение этого урока
lt-06-rademacher — Rademacher complexity - современная альтернатива VC для data-dependent bounds
lt-13-deep-generalization — Paradox deep learning: VC предсказывает провал, реальность показывает SOTA
prob-04-bayes — PAC-Bayes связывает VC-мышление с байесовскими prior - мост между теориями
calc-01-sequences — Асимптотический анализ sample complexity требует предельного мышления
stat-01-sampling