Статистика
Теория Вапника-Червоненкиса
Почему нейросеть с миллиардом параметров обобщается? Почему линейная модель с тысячей не переобучается? Теория Вапника-Червоненкиса даёт математические ответы на вопросы, которые каждый ML-инженер задаёт интуитивно.
- SVM: максимизация margin = минимизация effective VCdim через ||w||; теория VC объясняет, почему это работает
- Регуляризация в нейросетях: weight decay, dropout снижают effective complexity → улучшают VC-границы
- AutoML: NAS выбирает архитектуру с нужным balance-ом bias-variance через implicit VCdim контроль
Предварительные знания
VC-размерность
В 1968 году Вапник и Червоненкис связали обобщающую способность с одним числом - VC-размерностью. Сегодня этот ход считается фундаментальной теоремой ML и объясняет, почему GPT-4 с 10^12 параметров вообще обучается.
**Бесконечный VCdim - не конец:** некоторые классы с VCdim=∞ всё равно обобщаются на практике (1-NN при правильной мере близости, нейросети с неявной регуляризацией). Это противоречие с классической теорией VC объясняет феномен double descent: переобученные нейросети нередко лучше обобщаются, чем «правильно» регуляризованные. Современная теория: uniform convergence недостаточна - нужно учитывать алгоритм (SGD bias, implicit regularization).
Класс гипотез H имеет VCdim=5. Можно ли разбить (shatter) 6 точек гипотезами из H?
Сложность Радемахера и обобщение
**Эмпирическая сложность Радемахера:** R̂ₙ(H) = E_σ[sup_{h∈H} (1/n)∑ᵢ σᵢh(xᵢ)], где σᵢ ~ Uniform{±1} - случайные метки Радемахера. Мера: насколько хорошо H может «подогнаться» к случайному шуму. **Обобщённая ошибка:** L(h) ≤ L̂(h) + 2Rₙ(H) + √(log(1/δ)/(2n)) с вероятностью 1−δ. Связь с VC: Rₙ(H) = O(√(VCdim(H)·log(n)/n)).
**VC-граница неплотная для нейросетей:** GPT-4 имеет ~10¹² параметров - VCdim огромен, граница VC бессмысленна. Тем не менее нейросети обобщаются. Объяснения: implicit regularization SGD, inductive biases архитектуры, overparameterized interpolation (benign overfitting), compression bounds. Современная теория PAC-Bayes даёт более плотные границы для нейросетей.
Сложность Радемахера R̂ₙ(H) = E_σ[sup_h (1/n)∑σᵢh(xᵢ)], σᵢ~{±1}. Что означает R̂ₙ(H) ≈ 0?
PAC-обучаемость и fundamental theorem of ML
**PAC-обучаемость** (Probably Approximately Correct, Valiant 1984): класс H PAC-обучаем, если ∃ алгоритм A и функция m(ε,δ), что для любого D и ε,δ∈(0,1): при n≥m(ε,δ) с вероятностью ≥1−δ алгоритм выдаёт h с L(h) ≤ min_{h*∈H} L(h*) + ε. **Fundamental Theorem:** (Конечный VCdim) ↔ (PAC-обучаемость). Минимальная выборка: m(ε,δ) = O((VCdim(H) + log(1/δ))/ε²).
**Bias-variance через VC:** ERM минимизирует эмпирическую ошибку (variance↑ при сложном H), простой класс H имеет высокий approximation error (bias↑). Fundamental theorem: выбираем H с VCdim ~ O(√n/log n) для оптимального баланса. Это мотивирует регуляризацию: эффективный VCdim уменьшается, граница становится плотнее. SVM минимизирует ||w||² - явное уменьшение effective complexity.
По Fundamental Theorem of ML: какое условие необходимо и достаточно для PAC-обучаемости класса H?
Ключевые идеи
- VCdim(H) = max n, при котором H разбивает хоть одно множество из n точек
- Лемма Зауэра: Πₕ(m) ≤ ∑C(m,i) - полиномиальный рост при конечном VCdim
- R̂ₙ(H): способность H коррелировать с случайным шумом; = O(√(VCdim·log n/n))
- Граница: L(h) ≤ L̂(h) + 2Rₙ(H) + √(log(1/δ)/(2n))
- Fundamental Theorem: PAC-обучаемость ↔ VCdim(H) < ∞
VC-теория и курс
VC-теория объединяет статистику (обобщение) и вычислительную теорию (PAC). Связь с bias-variance trade-off через approximation + estimation error. Регуляризация = контроль effective VCdim.
- Статистика в ML: теоретические основы — Bias-variance decomposition - конкретное выражение approximation vs estimation error в VC
- Робастная статистика — Breakdown point и VC-сложность связаны через robust M-оценки и их effective размерность
Вопросы для размышления
- GPT-4 имеет ~10¹² параметров и огромный VCdim. VC-граница обобщения бессмысленна для него. Но нейросеть обобщается. Что не учитывает классическая VC-теория? Как это связано с феноменом double descent?
- No Free Lunch теорема говорит: нет универсально лучшего алгоритма. Почему тогда нейросети доминируют на большинстве реальных задач? Что является «специфическим знанием» о задаче, которое нейросети используют неявно?
- Линейный классификатор обучается линейный классификатор и SVM на одних данных. SVM явно минимизирует ||w||², что снижает VCdim. Как это влияет на граничную кривую PAC? При каком n SVM теоретически гарантированно лучше?