Разбиение и размерность Вапника–Червоненкиса

Когда пространства гипотез становятся бесконечными

Граница m ≥ (1/ε)(ln|H| + ln(1/δ)) перестаёт работать, когда |H| = ∞. Большинство полезных классов гипотез (линейные классификаторы в ℝᵈ, деревья решений, нейронные сети) содержат бесконечно много кандидатов. Вапник и Червоненкис решили эту проблему около 1971 года, введя более богатую меру сложности: VC-размерность.

Разбиение (Shattering)

Класс гипотез H разбивает (shatters) набор из n точек, если H способен воспроизвести любую возможную разметку этих n точек (все 2ⁿ дихотомий). Линейные классификаторы в ℝ² разбивают любые 3 точки в общем положении: для каждой из 8 возможных разметок (+/−) этих трёх точек найдётся прямая, которая правильно их разделяет.

Но линейные классификаторы в ℝ² не могут shatter 4 точки, расположенные в конфигурации XOR. Ни одна прямая линия не разделяет диагональную пару от антидиагональной пары.

Размерность VC

VC(H) = наибольшее n, такое что H shatter’ит некоторое множество из n точек. Для линейных классификаторов в 2D: VC = 3. Для осесимметричных прямоугольников в 2D: VC = 4. Для нейронных сетей с W весами: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Оценка размера выборки через размерность VC

Заменим ln|H| в нашей PAC-оценке на размерность VC d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

VC-размерность выступает как наша «эффективная сложность» бесконечного класса. Гипотезный класс с низкой VC-размерностью обобщается по небольшому числу примеров; класс с высокой VC-размерностью требует значительно больше данных.

VC-размерность как эффективное число гипотез

Нейросеть имеет W = 10⁹ весов. По границе Бартлетта-Энтони VC ≤ O(W² log W). Приближаем VC ≈ W² log₂ W.

Отказ от реализуемости, апостериорные распределения над гипотезами

Две важные обобщения

Классический PAC предполагает, что целевая концепция c лежит внутри класса гипотез H. Реальные данные содержат шум, ошибки разметки и концепции, которые наш класс не может представить. Два расширения решают эту проблему.

Agnostic PAC

Откажемся от предположения, что c ∈ H. Теперь будем соревноваться с нашей лучшей в классе гипотезой h* = argmin_{h ∈ H} risk(h). Форма границы меняется: вместо приближения к идеальному результату мы приближаемся к наилучшему возможному в рамках H.

Агностическая граница: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ с выборочной сложностью m = O(1/ε² × (VC(H) + log(1/δ))). Обратите внимание на ε² вместо ε в знаменателе: агностическое обучение требует больше примеров для той же точности.

PAC-Байес (McAllester 1999)

Переходим от выбора одной гипотезы к выбору распределения над гипотезами. Начинаем с априорного распределения P. Наблюдаем данные. Получаем апостериорное распределение Q. PAC-Байес ограничивает ожидаемый риск относительно Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) измеряет, насколько наша апостериорная мера отклонилась от априорной. Две интерпретации:

1. С точки зрения сжатия. Апостериорная мера, близкая к априорной (малый KL), хорошо обобщается — небольшая информационная стоимость = небольшая разница между обобщением и эмпирическим риском.

2. С байесовской точки зрения. Сильный априор + слабое обновление по данным = жёсткая граница; слабый априор + сильное обновление по данным = более мягкая граница.

Почему PAC-Байес важен. Эмпирические PAC-Байес границы (Catoni 2007, Dziugaite & Roy 2017) дают численно значимые гарантии обобщения для реальных нейронных сетей, где классические PAC-границы оказываются пустыми. Они остаются нашим самым точным теоретическим инструментом для анализа обобщения в перепараметризованных моделях.

Чтение PAC-Bayes-границы

Предположим, мы обучили сеть на n = 50 000 размеченных примеров. После обучения наша апостериорная Q над весами имеет KL(Q‖P) = 200 нат относительно гауссовского априорного P. Эмпирический риск под Q равен 0,10. Установим δ = 0,05.

Перепараметризация и двойной спуск

Классический PAC предсказывает катастрофу

Классический PAC предсказывает: больше параметров, чем примеров = катастрофическое переобучение. Идеальное запоминание обучающих данных и случайное обобщение на тестовых. VC-граница предсказывает запоминание без обучения.

Современные нейросети регулярно имеют в 10–1000 раз больше параметров, чем обучающих примеров, и всё равно обобщаются. По классической теории этого не должно происходить. Но это происходит.

U-образная кривая, которой нас учили

Классическая кривая смещения-дисперсии: по мере роста ёмкости модели ошибка на обучении монотонно падает; ошибка на тесте сначала падает (меньше недообучения), достигает минимума, а затем растёт (переобучение). U-образная форма, предсказываемая теорией VC.

Что происходит на самом деле — двойной спуск

Belkin et al (2019) показали, что ошибка на тесте следует классической U-кривой вплоть до порога интерполяции (ёмкость = число примеров), а затем СНОВА ПАДАЕТ после этого порога. Сильно перепараметризованные модели обобщаются лучше, чем модели «точно достаточной» ёмкости.

Почему классическая PAC-теория этого не учитывает

1. Предположение об отсутствии распределения слишком пессимистично. Реальные данные имеют структуру (низкую внутреннюю размерность, геометрию многообразия). PAC-границы справедливы для наихудших распределений; реальные распределения используют структуру, которую также использует SGD.

2. Неявная регуляризация. SGD на перепараметризованных сетях находит интерполирующие решения с минимальной нормой или минимальной сложностью, а не произвольные. Классическая теория предполагает наихудший эмпирический минимизатор риска; реальные алгоритмы выбирают «доброкачественные».

3. Неверное определение класса гипотез. Эффективный класс гипотез, исследуемый SGD, намного меньше номинального пространства весов. PAC-Байесовские апостериорные распределения это учитывают; VC-размерность — нет.

Современные теоретические работы (Bartlett, Long, Lugosi, Tsigler 2020 по доброкачественному переобучению; Nakkiran et al 2020 по двойному спуску) создают пост-PAC теорию обобщения, учитывающую режим перепараметризации.

Диагностика неудачи классической PAC

Исследовательская группа обучает сеть с 1 миллиардом параметров на 100 000 размеченных примерах. Классическая PAC предсказывает пустые границы. Эмпирически точность на тесте достигает 95 %.

Kaplan, Chinchilla и Размер Автоматизированного Общего Интеллекта

От границ к эмпирическим законам масштабирования

Классический PAC теоретически предсказывает размер набора данных и даёт бесполезные результаты. Эмпирические законы масштабирования предсказывают размер набора данных из наблюдений и реально работают. Они заменили PAC в качестве практического инструмента определения размера больших моделей.

Kaplan et al (2020)

Потери подчиняются степенному закону по параметрам N, токенам датасета D и вычислениям C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Удвоение числа параметров снижает потери на фиксированный мультипликативный коэффициент. Удвоение данных снижает потери на другой фиксированный коэффициент. Эти показатели (αN, αD, αC) измеряют и предсказывают поведение frontier-моделей на многих порядках величины.

Hoffmann et al 2022 (Chinchilla)

Chinchilla показала, что экспоненты Каплана переоценивали важность параметров по сравнению с данными. Оптимальное по вычислениям обучение требует примерно 20 токенов на параметр:

D_opt ≈ 20 × N

GPT-3 (175 млрд параметров) обучалась на ~300 млрд токенов — сильно недообучена по расчётам Chinchilla. Оптимальная по вычислениям модель на 175 млрд параметров требует ~3,5 триллиона токенов.

The Data Wall

Масштабирование количества параметров требует пропорционального увеличения количества токенов. Публичный веб-краулинг даёт ~10¹³ полезных токенов. Гипотетический автоматизированный общий интеллект с 10¹⁵ параметрами потребовал бы ~2×10¹⁶ токенов — на три порядка больше доступных веб-данных.

Это наша стена данных. Законы масштабирования предсказывают, что мы столкнёмся с нехваткой корпуса задолго до нехватки вычислительных ресурсов. Синтетические данные, мультимодальные корпуса (видео, аудио, сенсорные потоки) и RL-from-environment направлены на преодоление этого барьера.

Классическая PAC говорила нам (ошибочно), что нужно 10²¹ примеров. Законы масштабирования говорят (с учётом реальности), что нужно 2×10¹⁶. Оба числа превышают доступный текст. Современные исследования на переднем крае направлены на закрытие этого разрыва.

Оценка корпуса для автоматизированного общего интеллекта

Предположим, что передовая лаборатория предлагает модель с 10¹⁴ параметрами и утверждает, что она достигнет автоматизированного общего интеллекта. Мы хотим определить размер её обучающего корпуса по правилу Chinchilla.

От теоретических границ к производственным измерениям

Перестать вычислять границы; начать их измерять

Классические PAC-границы оказываются пустыми. PAC-Bayes-границы оказываются плотными при предположениях, которые трудно проверить. Практическая альтернатива: измерять ε эмпирически на реальном распределении и обновлять его по мере работы системы.

Идея 1 — Сделать покрытие эмпирическим PAC

Цель make coverage пропускает N отложенных вопросов через вашу систему запросов и измеряет две метрики:

- cache_hit_rate — доля запросов, для которых система нашла известный ответ

- i_dont_know_rate — доля запросов, на которые система честно ответила отказом

Каждое измерение = испытание Бернулли. По наблюдаемым частотам вычисляем интервал Уилсона для истинной доли. Пример: N = 1000 запросов, наблюдаемая i_dont_know_rate = 0.20 → 95% ДИ ≈ [0.177, 0.226]. Верхняя граница 0.226 работает точно так же, как PAC-ε при δ = 0.05, но получена из реальных данных на реальном распределении, а не из теоретического анализа в худшем случае.

Классическая PAC-терминология применима (ε, δ, доверие). Используется другой математический аппарат (концентрация биномиального распределения вместо VC-теории). Результат более точный, поскольку реальные распределения обладают структурой, которую можно использовать.

Идея 2 — PAC-Байес аудит через события фальсификации

Каждое событие фальсификации (когда ответ системы заведомо неверен) рассматривается как свидетельство, обновляющее апостериорное распределение истинной доли ошибок ε:

1. Априорное распределение: ε ~ Beta(α₀, β₀). Выбираем слабый априор, например Beta(1, 1) = равномерное.

2. Каждый запрос даёт исход по схеме Бернулли: фальсифицирован (1) или не фальсифицирован (0).

3. Апостериорное распределение после k фальсификаций в n запросах: Beta(α₀ + k, β₀ + n − k).

4. Апостериорное среднее: (α₀ + k) / (α₀ + β₀ + n) → эмпирическая частота фальсификаций при n → ∞.

5. 95%-ный credible interval для ε сужается как 1/√n.

Что это даёт

- Оценка реального ε₀ из фактического развёртывания, а не из теории наихудшего случая

- Anytime-valid тревога: когда апостериорный credible interval пересекает порог контракта, уведомить дежурного

- Монотонная уверенность: чем больше запросов проанализировано → уже CI → сильнее гарантия

Родственные методы: conformal prediction с онлайн-перекалибровкой (Vovk), последовательные вероятностные отношения (Wald), онлайн PAC-Bayes (Haddouche & Guedj 2022). Одна семья, разные математические инструменты.

Вычисление апостериорного Beta-распределения по фальсификациям

Наша команда проводит аудит покрытия на продакшн-системе запросов. Априорное распределение истинной доли ошибок ε: Beta(1, 1) (равномерное). После 200 отложенных запросов мы зафиксировали 8 фальсификаций.