VC-размерность и sample complexity

GPT-4 обучается на 45TB текста (~13 триллионов токенов). VC-теория объясняет: при VCdim=d нужно O(d/ε²) примеров для ε-ошибки. Для современных LLM d ~ число параметров, но bounds через Rademacher с norm constraints дают конечные гарантии. Amazon использует PAC bounds для оценки минимальных датасетов в AutoML. Google Brain применяет Rademacher complexity для выбора regularization strength в production моделях.

• **AutoML sample size estimation:** Amazon SageMaker Autopilot оценивает минимальный датасет через VC bounds перед запуском поиска архитектуры - экономит часы compute.
• **SVM в биоинформатике:** SVM с RBF kernel классифицирует экспрессию генов (20000+ признаков, 100-1000 образцов). VCdim=∞, но Rademacher bounds объясняют обобщение.
• **Neural scaling laws:** Chinchilla (DeepMind 2022) - n_tokens ≈ 20·n_params оптимально. Это согласуется с PAC sample complexity O(d/ε²) при d~параметры.

VC-размерность: shattering и growth function

**GPT-4 обучается на 45TB текста, но VC-теория объясняет: при VC-размерности d нужно O(d/ε) примеров для ε-точности с вероятностью 95%.** Почему полупространство в ℝ² требует всего 3 точки для shattering, а линейный классификатор в ℝ¹⁰⁰⁰⁰ - 10001? Эта разница управляет тем, сколько данных нужно ImageNet vs MNIST.

**VC dim популярных классов:** Пороговые функции на ℝ - 1. Полупространства в ℝᵈ - d+1. Нейросеть с W параметрами - O(W log W). SVM с RBF kernel - ∞ (но Rademacher complexity конечна).

PAC-обучение: фундаментальная теорема

**Probably Approximately Correct (PAC) обучение** - формализм Валианта 1984 года: алгоритм A PAC-обучает класс H, если для любых ε, δ > 0 при достаточно большой выборке выдаёт h с err(h) ≤ ε с вероятностью ≥ 1-δ. Фундаментальная теорема: класс PAC-обучаем тогда и только тогда, когда его VC-размерность конечна.

**No Free Lunch:** без предположений о распределении никакой алгоритм не обучается лучше случайного. PAC-обучаемость зависит от того, что класс H имеет конечную VCdim - это и есть inductive bias.

Rademacher complexity: uniform convergence без VC

**Rademacher complexity** - мера выразительности класса функций через способность подстраиваться под случайный шум. В отличие от VC dim, она data-dependent и даёт более точные bounds для конкретных распределений. Именно Rademacher bounds используются в современных гарантиях для нейронных сетей.

**Когда Rademacher лучше VC:** когда норма весов ограничена (L2 regularization), когда данные low-dimensional, когда VCdim = ∞ (RBF SVM, deep networks). Modern deep learning bounds используют Rademacher с spectral norm constraints.

Ключевые идеи

• **VC dimension:** VCdim(H) = max размер раздробляемого множества. Halfplanes в ℝᵈ: d+1. Нейросеть с W весами: O(W log W).
• **Лемма Сауэра-Шелы:** Pi_H(m) ≤ (em/d)^d - полиномиальная граница growth function делает uniform convergence возможным.
• **PAC sample complexity:** n = O(d·log(1/ε)/ε² + log(1/δ)/ε²) примеров достаточно для ε-точности с вероятностью 1-δ.
• **Фундаментальная теорема:** H PAC-обучаем ⟺ VCdim(H) < ∞.
• **Rademacher complexity:** data-dependent мера, не зависит от размерности при ограниченных весах. Для RBF SVM строже VC bounds.

Связанные темы

VC dim и PAC - фундамент всей теории обобщения:

• Rademacher и uniform convergence — Уроки 6-7: детали доказательств
• Kernel Methods — Предыдущий урок: RKHS где VCdim=∞ но обобщение есть

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

• lt-04-vc-dimension — Новый взгляд с позиции PAC и Rademacher
• lt-06-rademacher — Rademacher complexity - альтернатива VC для modern ML
• lt-07-uniform-convergence — Uniform convergence - ключевой инструмент доказательства