PAC как плоскость двух осей
Две оси, одна поверхность подсчета образцов
Постройте ε на горизонтальной оси (допуск ошибки, диапазон от 0 до 1). Постройте δ на вертикальной оси (вероятность отказа, диапазон от 0 до 1). Каждая точка в этом единичном квадрате соответствует паре спроса (ε, δ).
Выше каждой точки находится значение числа образцов m(ε, δ) = (1/ε)(ln|H| + ln(1/δ)). Вместе эти m значения отслеживают изогнутую поверхность выше нашего квадрата. Более жесткие требования (меньший ε, меньший δ) поднимают нашу поверхность вверх; более мягкие требования её уплощают.
Линии контура равного числа образцов
Спроектируйте нашу поверхность обратно на плоскость как изолинии-m контуры. Каждая пара (ε, δ) на одном контуре требует один и тот же бюджет образцов. Двигайтесь вдоль контура, чтобы обменять допуск ошибки на уверенность при фиксированной стоимости.
Уменьшение оси вдвое
Уменьшение ε вдвое по горизонтали перемещает m вверх в 2 раза (линейное по 1/ε). Уменьшение δ вдвое по вертикали перемещает m вверх на ln(2) ≈ 0,69 (логарифмическое по 1/δ). Геометрия говорит нам: допуск ошибки несёт более крутую стоимость, чем уверенность.
Чтение поверхности бюджета
Мы находимся в точке (ε = 0,05, δ = 0,05) для класса гипотез |H| = 10⁶. Требование числа образцов m₀ = (1/0,05)(ln(10⁶) + ln(20)) = 20 × (13,8 + 3,0) = 336.
Дихотомии на облаках точек
Как выглядит разрушение
Разместите n точек на плоскости. Выберите класс гипотез (линейные классификаторы = прямые линии). Подсчитайте, сколько различных способов ваш класс может обозначить эти n точек (+/− с каждой стороны линии). Назовите этот счёт Π_H(n).
Если Π_H(n) = 2ⁿ, ваш класс разрушает это множество точек — он может производить каждую возможную разметку. Если Π_H(n) < 2ⁿ, некоторые разметки не могут произойти.
Три точки в общей позиции
Линейные классификаторы в ℝ² разрушают любые 3 неколлинеарные точки. 2³ = 8 разметок; все 8 достижимы какой-либо линией. Выберите любые 3 точки; для каждой разметки ±/±, нарисуйте линию, которая отделяет положительные от отрицательных.
Четыре точки отказываются разрушаться
Разместите 4 точки в углах квадрата. Попробуйте обозначить диагональную пару как положительную & антидиагональную пару как отрицательную (разметка XOR). Ни одна прямая линия их не отделяет. Так что Π_H(4) ≤ 14 < 16 = 2⁴.
VC-размерность как максимальный размер разрушения
VC(линейный ℝ²) = 3. Мы можем разрушить 3 точки; мы не можем разрушить 4. VC считает максимальную мощность дихотомии вашего класса гипотез.
Геометрическая интуиция
Более высокий VC = ваш класс рисует более сложные границы решения. Линейный (VC = d+1 в d измерениях) рисует гиперплоскости. Полиномы рисуют кривые. Нейронные сети рисуют высоко складчатые многообразия. Больше складчатости = больше дихотомий = выше VC = выше требование образцов.
Подсчёт дихотомий
Рассмотрите линейные классификаторы в ℝ² (линии). У вас есть 5 точек, размещённых в общей позиции (не 3 коллинеарные, ничего избыточного).
Вероятностная масса на многообразии гипотез
Представление PAC-Bayes
Представьте пространство гипотез как высокомерное многообразие. Каждая точка на этом многообразии соответствует одной конфигурации весов нейронной сети. Априор P назначает распределение вероятности по нашему многообразию (часто Гауссова, центрированная на инициализации). Апостериор Q концентрирует вероятностную массу там, где данные тренировки направили наши веса.
KL-дивергенция как геометрическое расстояние
KL(Q‖P) измеряет, насколько далеко Q отклонилась от P. Геометрическое прочтение: на сколько наше апостериорное облако переместилось из облака априора, взвешено тем, как маловероятна каждая апостериорная область была под нашим априором.
Малая KL = Q сильно перекрывает P. Апостериор едва переместился. Разрыв обобщения остаётся малым.
Большая KL = Q сконцентрирована в областях, которым P назначил мало массы. Апостериор переместился много. Разрыв обобщения растёт.
Почему эта геометрия имеет значение
Представьте SGD как траекторию поиска по многообразию гипотез. Траектория заканчивается в бассейне низкой потери на тренировке. PAC-Bayes спрашивает: насколько широк этот бассейн?
Широкий бассейн = много соседних конфигураций весов также достигают низкой потери на тренировке. Апостериор Q может распространяться над широкой областью & всё ещё иметь низкий риск. KL(Q‖P) остаётся ограниченным. Разрыв обобщения малый.
Узкий бассейн = только тонкий набор весов достигает низкую потерю. Апостериор должен сконцентрироваться резко. KL растёт. Разрыв обобщения расширяется.
Это связывает напрямую с дискуссией плоских-vs-острых минимумов (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Плоские минимумы обобщаются лучше, потому что они поддерживают более широкие апостериоры с меньшей KL.
Чтение ширины бассейна
Два обученных модели достигают идентичную потерю на тренировке, но живут в разных бассейнах:
- Модель A: плоский бассейн, апостериор распространяется над областью с KL(Q_A‖P) = 50 натс.
- Модель B: острый бассейн, апостериор концентрируется с KL(Q_B‖P) = 500 натс.
Обе обучены на n = 10 000 примеров с эмпирической потерей 0,05, δ = 0,05.
Кривая, которая падает там, где теория предсказывала подъём
Классическая U-кривая
Постройте мощность модели на горизонтальной оси. Постройте тестовый риск на вертикальной оси. Классическая теория смещения-дисперсии предсказывает:
- Низкая мощность: высокое смещение, высокий тестовый риск (недостаточное подгонка)
- Средняя мощность: низкое смещение + низкая дисперсия, низкий тестовый риск (оптимальная точка)
- Высокая мощность: низкое смещение, высокая дисперсия, высокий тестовый риск (переоснащение)
Результат: U-образная кривая. Выберите мощность в нашем дне.
Что наблюдали Белкин и др. (2019)
За пределами порога интерполяции (мощность, где модель точно подгоняет данные тренировки с нулевой ошибкой), тестовый риск ПАДАЕТ снова. Кривая читается: спуск → пик у интерполяции → второй спуск. Два спуска, одна кривая.
Геометрическое чтение второго спуска
На пороге интерполяции модель имеет ровно столько мощности, чтобы подогнать данные тренировки — существует только одно (или несколько) интерполирующих решения & они, как правило, зубчатые. Обобщение страдает, потому что выбранное решение вынуждено.
За пределами порога интерполяции существует МНОГО интерполирующих решений. SGD имеет свободу выбрать гладкое (минимальное норма, низкая кривизна). Геометрическое представление: многообразие решений становится шире & пложе. Неявная регуляризация SGD выбирает безобидные решения из этого плоского многообразия. Тестовый риск падает.
Почему классическая теория это пропускает
VC-размерность считает мощность множества решений, но игнорирует, какое решение выбирается. Классическое ограничение предполагает наихудший случай эмпирического минимизатора риска. Реальность: SGD надёжно выбирает САМОЕ плоское, САМОЕ гладкое интерполирующее решение. Один раз мы считаем решения, ВЫБРАННЫЕ РЕШАТЕЛЕМ вместо всех решений, второй спуск имеет смысл.
Геометрический итог
Мощность имеет значение меньше, чем геометрия бассейна. Широкие плоские бассейны (после интерполяции) обобщаются лучше, чем узкие острые (у интерполяции). Современная теория пытается ограничить обобщение шириной бассейна, а не числом параметров.
Локализация двух спусков
На кривой двойного спуска три области имеют значение: (1) недо-параметризованный режим, (2) пик интерполяции, (3) над-параметризованный режим.
Степенная поверхность в пространстве параметр-токен
3D поверхность
Постройте параметры N на одной горизонтальной оси. Постройте токены D на второй горизонтальной оси. Постройте потерю L на вертикали. Эмпирическая потеря вырезает степенную поверхность по всей плоскости (N, D):
L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞
Поверхность наклоняется вниз при росте N или D. Наклоны следуют логарифмически-линейным степенным законам (прямые линии в логарифмическом графике). Асимптота L∞ остаётся положительной — неразложимая потеря, которую наша модель не может сокращать далее.
Гребень вычислительной оптимальности
Зафиксируйте бюджет вычислений C ∝ N × D (параметры × токены, примерно). Нарежьте нашу поверхность вдоль этого ограничения. Срез отслеживает 2D-кривую сквозь 3D-поверхность. Дно этой кривой = точка вычислительной оптимальности.
Chinchilla (Hoffmann et al 2022) вычислила это дно аналитически: D_opt ≈ 20 × N. Кривая вдоль бюджета вычисления = гребень. Ходьба вдоль гребня: одинаковые вычисления, убывающая потеря. Ходьба вне гребня (более параметров, чем 20× токенов, или меньше): потраченные вычисления.
Геометрическое прочтение GPT-3 vs Chinchilla
GPT-3: 175B параметров, 300B токенов. Chinchilla-оптимальное хотело бы 175B × 20 = 3500B токенов. GPT-3 находится далеко от вычислительно-оптимального гребня в нашем параметро-тяжелом направлении. Сам Chinchilla: 70B параметров, обученный на 1400B токенов. 1400 / 70 = 20 — ровно на гребне. Chinchilla побил GPT-3 с менее чем половиной числа его параметров, сидя на геометрическом оптимуме.
Стена данных как вертикальная плоскость
Публичная сеть ~10¹³ полезных токенов. Это наносится как вертикальная стена на D = 10¹³ на нашей плоскости параметр-токен. За этой стеной вычислительно-оптимальная тренировка требует N ≤ D / 20 = 5 × 10¹¹ параметров. Стены за N = 5 × 10¹¹ либо запускают недо-обученные (вне гребня) либо требуют синтетических / мультимодальных / RL данных, чтобы сдвинуть стену наружу.
Ходьба по вычислительно-оптимальному гребню
Мы находимся в координатах GPT-3: N = 175B параметров, D = 300B токенов. Прокси вычисления C = N × D = 5,25 × 10²² параметр-токенов.
Бета-апостериор, сжимающийся в иглу
Плотность вероятности на [0, 1]
Beta(α, β) — плотность вероятности на единичном интервале [0, 1]. Переменная: ε = истинная ошибка. Форма: α контролирует массу на стороне высокого-ε; β контролирует массу на стороне низкого-ε.
Beta(1, 1): равномерное — нет информации, плоская плотность через [0, 1].
Beta(α, β) с большим α + β: сконцентрированный пик на α / (α + β).
Ширина пика Beta сжимается как 1/√(α+β). Добавление 100 наблюдений к нашему апriору затягивает пик на множитель √100 = 10. Добавление 10000 наблюдений затягивает на √10000 = 100.
Геометрическое прочтение прохода аудита
Начало: Beta(1, 1) = плоский прямоугольник на [0, 1]. Максимальная неопределённость о ε.
После 200 запросов с 8 фальсификациями: Beta(9, 193). Среднее = 9/202 ≈ 0,045. Плотность теперь острый холм, сосредоточенный около 0,045 с характеристической шириной σ ≈ 0,014.
После 2000 запросов с 80 фальсификациями: Beta(81, 1921). Среднее всё ещё ≈ 0,045, но ширина σ ≈ 0,0046. Холм в три раза острее.
После 200 000 запросов с 8000 фальсификациями: Beta(8001, 192,001). Среднее ≈ 0,040, ширина σ ≈ 0,0004. Холм становится иглой.
Геометрическая сходимость к точечной массе
Как n → ∞, бета-апостериор коллапсирует к дельте Дирака при истинной ε. Геометрия: прямоугольник → широкий холм → узкий холм → игла → точка. Каждый запрос затягивает нашу распределение на 1/√n.
Почему это бьёт теоретические границы PAC
Теоретические границы PAC дают СТАТИЧЕСКУЮ оценку ε на основе размера класса гипотез. Бета-апостериор даёт ДИНАМИЧЕСКУЮ оценку ε, которая затягивается с каждым наблюдением, калиброванную против вашего реального распределения. Теоретическая граница = гарантия при наихудших предположениях. Эмпирический аудит = измерение реальности.
Сколько запросов, чтобы уполовинить доверительный интервал?
Мы в настоящее время находимся в Beta(9, 193) после 200 запросов: среднее ε ≈ 0,045, σ ≈ 0,014. Мы хотим уполовинить ширину доверительного интервала на σ ≈ 0,007.