Модуль 12. Информационные границы обобщения: PAC-Bayes и взаимная информация

Как читать этот модуль. Основной маршрут — §§12.1–12.9. Сначала мы увидим, почему выбор лучшей модели по той же выборке делает её оценку оптимистичной. Затем построим два способа оплатить эту адаптивность: PAC-Bayes-сертификат через $D_{\mathrm{KL}}(Q\|P)$ и границу в среднем через $I(W;S)$. В §12.7 эти две записи встретятся в точном тождестве. §12.10 — математическое углубление про априорные распределения, зависящие от данных, MI по отдельным примерам и условную MI; его удобно оставить на второй проход.

12.1. Почему лучшая обучающая ошибка почти неизбежно слишком хороша

Представим 32 классификатора. У каждого одна и та же истинная вероятность ошибки:

$$L(w_j)=0.2, \qquad j=1,\ldots,32.$$

Ни один из них не лучше остальных. Но мы проверяем все 32 на одной выборке из 80 примеров и оставляем классификатор с минимальной эмпирической ошибкой. В воспроизводимом эксперименте этого модуля ошибка победителя в среднем получается около

$$0.113,$$

хотя его истинная ошибка по-прежнему равна $0.2$.

Алгоритм не обнаружил скрыто более сильную модель. Он обнаружил благоприятную случайную флуктуацию. Чем больше вариантов мы просмотрели, тем выше шанс, что один из них случайно окажется особенно удачным именно на этой выборке.

Та же механика работает в большом ML-пайплайне:

• мы подбираем архитектуру;
• запускаем несколько инициализаций;
• выбираем эпоху по метрике;
• настраиваем гиперпараметры;
• сравниваем варианты предобработки;
• иногда много раз смотрим на один и тот же валидационный набор.

Каждый отдельный результат может быть честной оценкой фиксированной модели. Но победитель выбирается после просмотра этих оценок. Поэтому его число уже содержит смещение выбора.

Запишем обучение как случайное отображение

$$S\longrightarrow W=A(S),$$

где

$$S=(Z_1,\ldots,Z_n)\sim\mathcal D^n$$

— обучающая выборка, а $W$ — индекс гипотезы, параметры сети или случайная модель, возвращённая алгоритмом.

Для функции потерь

$$0\le \ell(w,z)\le1$$

определим истинный и эмпирический риски:

$$L(w)=\mathbb E_{Z\sim\mathcal D}[\ell(w,Z)],$$ $$\widehat L_S(w) = \frac1n\sum_{i=1}^n\ell(w,Z_i).$$

Разность

$$\operatorname{gen}(w,S) = L(w)-\widehat L_S(w)$$

называется разрывом обобщения (generalization gap). Положительный разрыв означает, что обучающая оценка была оптимистичнее популяционной.

Если не сказано обратное, логарифмы в модуле натуральные, а KL и взаимная информация измеряются в натах.

Главная проблема здесь не в том, что алгоритму запрещено смотреть на данные. Обучение без данных было бы бессмысленным. Проблема в другом:

Адаптивность нужно оплатить: чем сильнее результат зависит от случайных деталей выборки, тем большую статистическую цену мы должны добавить к обучающей ошибке.

В этом модуле появятся две книги учёта.

1. PAC-Bayes сравнивает зависящее от данных распределение моделей $Q_S$ с заранее выбранным распределением $P$ и выставляет счёт $$D_{\mathrm{KL}}(Q_S\|P).$$
2. Информационная граница рассматривает обучение как канал $S\to W$ и измеряет $$I(W;S).$$

Обе конструкции локальнее грубого подсчёта всего класса гипотез. Но они отвечают на разные вопросы и дают разные типы гарантий. PAC-Bayes обычно сертифицирует конкретную выборку с высокой вероятностью. Базовая MI-граница контролирует ожидаемый разрыв по случайной выборке и случайности алгоритма.

Это различие будет важно на протяжении всего модуля.

12.2. От фиксированной модели к адаптивному выбору

Фиксированная модель

Пусть $w$ выбрано до того, как появилась выборка $S$. Тогда неравенство Хёфдинга даёт

$$\Pr\left( |L(w)-\widehat L_S(w)|\ge\varepsilon \right) \le 2e^{-2n\varepsilon^2}.$$

Здесь всё устроено просто: мы сравниваем среднее независимых ограниченных величин с их математическим ожиданием.

Но обученная модель

$$W=A(S)$$

не является заранее фиксированной. Она выбиралась именно потому, что хорошо выглядела на $S$. Подставить $W$ в границу для фиксированного $w$ нельзя: зависимость результата от выборки — и есть то, что требуется учесть.

Равномерная сходимость

Классический выход состоит в том, чтобы потребовать хорошую оценку одновременно для всех моделей класса $\mathcal H$. Если класс конечен, объединяющая оценка даёт

$$\Pr\left( \sup_{w\in\mathcal H} |L(w)-\widehat L_S(w)| \ge\varepsilon \right) \le 2|\mathcal H|e^{-2n\varepsilon^2}.$$

Следовательно, с вероятностью не меньше $1-\delta$:

$$\sup_{w\in\mathcal H} |L(w)-\widehat L_S(w)| \le \sqrt{ \frac{\ln(2|\mathcal H|/\delta)}{2n} }.$$

Цена выбора среди $|\mathcal H|$ вариантов входит как $\ln|\mathcal H|$. Это уже информационная подсказка: чтобы назвать одного победителя среди $M$ кандидатов, требуется порядка $\log M$ бит.

Для бесконечных классов роль размера играют VC-размерность, сложность Радемахера, нормы, отступы и другие меры сложности.

Здесь легко сделать слишком сильный вывод. Равномерные границы не «ошибаются на нейросетях». Они дают корректную гарантию наихудшего случая для всего класса. Проблема в том, что грубая глобальная сложность огромной сети часто делает численную границу вакуумной — больше единицы для риска в $[0,1]$.

Но реальный алгоритм не исследует весь класс одинаково. SGD, архитектура, предобучение, регуляризация и данные направляют его в малую часть пространства параметров. Поэтому естественно спросить не только

насколько велик весь класс?

но и

насколько сложен именно результат, который вернул этот алгоритм на этой выборке?

Адаптивный выбор в миниатюре

Вернёмся к 32 одинаково хорошим гипотезам. Жёсткий выбор

$$W=\arg\min_j\widehat L_S(w_j)$$

почти полностью определяется случайными различиями между эмпирическими ошибками. В эксперименте:

$$I(W;S)\approx3.24\ \text{ната},$$ $$\mathbb E[\operatorname{gen}]\approx0.087,$$

а информационная граница, которую мы выведем в §12.6, даёт около

$$0.142.$$

Если заменить argmin мягким Gibbs-выбором

$$\Pr(W=j\mid S) \propto \exp\left[-\frac{\widehat L_S(w_j)}{\tau}\right],$$

то с ростом температуры $\tau$ выбор становится менее чувствительным к конкретным флуктуациям. Одновременно уменьшаются и $I(W;S)$, и смещение выбора.

Этот пример не доказывает, что шум всегда улучшает обучение. Он показывает более точный механизм: рандомизация может ограничить объём выборочно-специфической информации, использованной при выборе результата.

12.3. PAC-Bayes: распределение до данных и распределение после обучения

PAC-Bayes меняет объект анализа. Вместо одной обученной гипотезы рассматривается распределение над гипотезами или параметрами.

• $P$ — априорное распределение (prior), фиксированное независимо от сертифицирующей выборки $S$;
• $Q_S$ — апостериорное распределение (posterior), которое может зависеть от всей выборки;
• при предсказании модель $W$ случайно выбирается из $Q_S$.

Названия prior и posterior пришли из байесовской статистики, но PAC-Bayes не требует, чтобы $Q_S$ был обычным байесовским апостериорным распределением. Это могут быть любые две вероятностные меры, удовлетворяющие условиям теоремы.

Определим риск Gibbs-предиктора:

$$L(Q) = \mathbb E_{W\sim Q}[L(W)],$$ $$\widehat L_S(Q) = \mathbb E_{W\sim Q}[\widehat L_S(W)].$$

Здесь нужно не потерять сертифицируемый объект. Базовая граница относится к Gibbs-предиктору: модель выбирается из $Q$ случайно, и риск усредняется по этому выбору.

Это не то же самое, что:

1. сеть со средними весами $\mathbb E_Q[W]$;
2. усреднение логитов или вероятностей ансамбля;
3. голосование большинства;
4. лучшая отдельная модель на носителе $Q$.

Иногда для этих объектов можно вывести дополнительные границы. Но заменить Gibbs-риск риском среднего предиктора одним словом «ансамбль» нельзя.

Что оплачивает KL

Член

$$D_{\mathrm{KL}}(Q_S\|P)$$

измеряет, насколько сильно распределение после обучения отклонилось от заранее выбранной точки отсчёта.

Если $P$ уже отдаёт большую массу областям, где находится хорошее решение, апостериорному распределению не требуется далеко уходить. Если же $Q_S$ концентрируется там, где $P$ почти не имеет массы, цена велика.

Это не просто расстояние между начальными и конечными весами. KL зависит от полных распределений, их дисперсий, носителей и параметризации.

Почему априорное распределение нельзя бесплатно обучить на той же выборке

PAC-Bayes-теорема будет одновременно верна для всех $Q$, поэтому апостериорное распределение разрешено выбирать после просмотра данных. Но $P$ используется внутри концентрационного аргумента как распределение, не зависящее от $S$.

Если сначала обучить $P$ на всей сертифицирующей выборке, затем выбрать $Q_S$ рядом с ним и просто подставить маленькую KL в стандартную формулу, данные будут использованы дважды:

• для выбора точки отсчёта;
• для выбора апостериорного распределения.

Второе использование оплачено KL, первое — нет.

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

12.4. PAC-Bayes-kl: сертификат для конкретной выборки

Для $a,b\in[0,1]$ обозначим бинарную KL-дивергенцию

$$\operatorname{kl}(a\|b) = a\ln\frac ab +(1-a)\ln\frac{1-a}{1-b}.$$

Малые буквы kl здесь важны: это KL между двумя распределениями Бернулли с параметрами $a$ и $b$.

Теорема

Пусть

• $S\sim\mathcal D^n$ i.i.d.;
• $0\le\ell\le1$;
• $P$ не зависит от $S$;
• $n\ge2$.

Тогда с вероятностью не меньше $1-\delta$ по выбору $S$ одновременно для всех апостериорных распределений $Q$ выполняется

$$\boxed{ \operatorname{kl} \bigl( \widehat L_S(Q)\|L(Q) \bigr) \le \frac{ D_{\mathrm{KL}}(Q\|P) + \ln\dfrac{2\sqrt n}{\delta} }{n} }.$$

Эту форму обычно называют PAC-Bayes-kl-границей; коэффициент $2\sqrt n$ соответствует уточнённой оценке экспоненциального момента Маурера.

На этом месте полезно прочитать формулу словами.

• Левая часть сравнивает наблюдаемый Gibbs-риск и неизвестный истинный Gibbs-риск.
• Первый член справа оплачивает отклонение апостериорного распределения от априорного.
• Второй задаёт уровень доверия.
• Деление на $n$ распределяет эту цену по размеру выборки.

Обозначим правую часть через

$$c(Q,S) = \frac{ D_{\mathrm{KL}}(Q\|P) + \ln(2\sqrt n/\delta) }{n}.$$

Тогда верхний сертификат получается численной инверсией бинарной KL:

$$L(Q) \le \operatorname{kl}^{-1}_{+} \bigl( \widehat L_S(Q),c(Q,S) \bigr).$$

Это не декоративная форма. Точная инверсия особенно полезна, когда эмпирический риск мал.

Почему квадратное следствие теряет точность

Неравенство Пинскера даёт

$$\operatorname{kl}(a\|b) \ge 2(a-b)^2.$$

Поэтому из PAC-Bayes-kl следует более простая граница

$$L(Q) \le \widehat L_S(Q) + \sqrt{ \frac{ D_{\mathrm{KL}}(Q\|P) + \ln(2\sqrt n/\delta) }{2n} }.$$

Она удобна для чтения, но заменяет точную геометрию бинарной KL параболой.

Если

$$\widehat L_S(Q)=0,$$

то

$$\operatorname{kl}(0\|L) =-\ln(1-L),$$

и потому

$$L(Q) \le 1-e^{-c} \approx c$$

при малом $c$. Точная граница имеет масштаб $1/n$, тогда как квадратное следствие даёт только $1/\sqrt n$.

Например, если $c=0.01$, то

$$1-e^{-c}\approx0.00995,$$

а Пинскер даёт

$$\sqrt{c/2}\approx0.0707.$$

Разница уже не косметическая.

Почему теорема верна: четыре шага

Полное доказательство остаётся в основном маршруте, потому что оно показывает центральный механизм PAC-Bayes — перенос концентрации с независимого априорного распределения на зависящее от данных апостериорное.

Шаг 1. Экспоненциальный момент для фиксированной гипотезы. Для каждого фиксированного $w$:

$$\mathbb E_S \exp\left[ n\operatorname{kl} \bigl( \widehat L_S(w)\|L(w) \bigr) \right] \le 2\sqrt n.$$

Это усиленная концентрационная оценка для средних ограниченных случайных величин.

Шаг 2. Усреднение по априорному распределению. Поскольку $P$ не зависит от $S$, можно поменять порядок ожиданий:

$$\mathbb E_S \mathbb E_{W\sim P} \exp\left[ n\operatorname{kl} \bigl( \widehat L_S(W)\|L(W) \bigr) \right] \le 2\sqrt n.$$

Шаг 3. Переход от среднего утверждения к событию высокой вероятности. По неравенству Маркова с вероятностью не меньше $1-\delta$:

$$\mathbb E_{W\sim P} \exp\left[ n\operatorname{kl} \bigl( \widehat L_S(W)\|L(W) \bigr) \right] \le \frac{2\sqrt n}{\delta}.$$

Шаг 4. Замена меры. Для любого $Q$ и измеримой функции $F$ неравенство Донскера—Варадана даёт

$$\mathbb E_Q[F(W)] \le D_{\mathrm{KL}}(Q\|P) + \ln\mathbb E_Pe^{F(W)}.$$

Подставим

$$F(w) = n\operatorname{kl} \bigl( \widehat L_S(w)\|L(w) \bigr).$$

Тогда на событии из шага 3:

$$\mathbb E_Q \operatorname{kl} \bigl( \widehat L_S(W)\|L(W) \bigr) \le \frac{ D_{\mathrm{KL}}(Q\|P) + \ln(2\sqrt n/\delta) }{n}.$$

Наконец, совместная выпуклость бинарной KL даёт

$$\operatorname{kl} \bigl( \widehat L_S(Q)\|L(Q) \bigr) \le \mathbb E_Q \operatorname{kl} \bigl( \widehat L_S(W)\|L(W) \bigr).$$

Граница доказана.

Вот и вся механика: концентрация для фиксированной модели переносится на выбранное после данных распределение ценой KL.

Обратите внимание, где использована независимость $P$: во втором шаге. Если $P=P_S$, обмен ожиданий уже не имеет прежнего смысла, и доказательство требует дополнительного члена.

12.5. От сертификата к обучаемому распределению

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

Рассмотрим для $\lambda>0$ регуляризованный функционал

$$\mathcal F_\lambda(Q) = \widehat L_S(Q) + \frac{1}{\lambda n} D_{\mathrm{KL}}(Q\|P).$$

Вариационный принцип Гиббса даёт точный оптимум:

$$\boxed{ Q_\lambda(dw) = \frac{ P(dw)e^{-\lambda n\widehat L_S(w)} }{ \mathbb E_{W\sim P} [e^{-\lambda n\widehat L_S(W)}] } }.$$

Эквивалентно,

$$Q_\lambda = \arg\min_Q\mathcal F_\lambda(Q).$$

Это та же экспоненциальная перенормировка, которую мы уже встречали в MaxEnt и KL-регуляризованных политиках:

• эмпирический риск наклоняет массу в сторону хороших моделей;
• априорное распределение задаёт исходную геометрию;
• KL назначает цену сильному отклонению;
• $\lambda$ задаёт обменный курс между подгонкой и сложностью.

Это не обязательно обычный байесовский апостериорный закон

Если

$$\lambda n\widehat L_S(w) = -\log p(S\mid w)$$

с точностью до не зависящей от $w$ константы, то $Q_\lambda$ совпадает с байесовским апостериорным распределением.

Для произвольной функции потерь это обобщённый Gibbs-апостериорный закон, а не результат обычного обновления по правдоподобию.

Кроме того, $Q_\lambda$ является точным оптимумом функционала $\mathcal F_\lambda$, но не автоматически точным минимизатором любой выбранной PAC-Bayes-границы. Практические методы могут напрямую минимизировать дифференцируемую форму сертификата, его инверсию или удобный суррогат. Общий мотив остаётся тем же: эмпирический риск плюс информационная цена.

Гауссовские распределения над весами

Пусть

$$P = \mathcal N \bigl( \mu_P, \operatorname{diag}(\sigma_P^2) \bigr),$$ $$Q = \mathcal N \bigl( \mu_Q, \operatorname{diag}(\sigma_Q^2) \bigr).$$

Тогда

$$\begin{aligned} D_{\mathrm{KL}}(Q\|P) = \frac12\sum_j \Bigg[ &\frac{\sigma_{Q,j}^2}{\sigma_{P,j}^2} + \frac{(\mu_{Q,j}-\mu_{P,j})^2}{\sigma_{P,j}^2} -1\\ &+ \ln\frac{\sigma_{P,j}^2}{\sigma_{Q,j}^2} \Bigg]. \end{aligned}$$

Квадратичный член по средним действительно напоминает $L_2$-регуляризацию. Но это только часть KL. Полная PAC-Bayes-постановка также учитывает дисперсии и относится к распределению предикторов.

Поэтому корректная формулировка такова:

У гауссовского PAC-Bayes-члена есть $L_2$-подобная составляющая, но обычное детерминированное затухание весов не равно полному PAC-Bayes-обучению.

То же относится к dropout. Он вводит стохастичность, но конкретная PAC-Bayes-гарантия требует явно задать $P$, $Q$, риск и способ сертификации.

Почему точечная модель часто имеет бесконечную KL

Если $P$ имеет непрерывную плотность, а

$$Q=\delta_{w_*},$$

то

$$D_{\mathrm{KL}}(\delta_{w_*}\|P)=\infty.$$

Точечная мера не абсолютно непрерывна относительно непрерывного априорного распределения.

Поэтому для практического сертификата обычно используют:

• стохастическое распределение вокруг весов;
• дискретизацию или квантизацию;
• априорное распределение с подходящими атомами;
• отдельную теорию для голосования большинства или детерминированного предиктора.

Рандомизация здесь не магический источник обобщения. Она делает сертифицируемый объект корректно определённым и позволяет торговать устойчивостью предсказаний против KL-цены.

12.6. MI-границы: обучение как канал от выборки к модели

Теперь откажемся от выбранного вручную априорного распределения и посмотрим на весь алгоритм обучения как на канал

$$S\longrightarrow W.$$

Алгоритм может быть случайным из-за инициализации, порядка мини-батчей, dropout, добавленного шума или явной выборки из апостериорного распределения.

Взаимная информация

$$I(W;S) = D_{\mathrm{KL}} \left( P_{W,S} \|P_W\otimes P_S \right)$$

измеряет, насколько распределение результата меняется при знании конкретной обучающей выборки.

Это близко к интуиции «сколько данных модель запомнила», но точнее говорить:

$I(W;S)$ измеряет статистическую зависимость результата алгоритма от всей выборки.

Она не сообщает напрямую, какие примеры можно восстановить, нарушена ли приватность и сохранены ли семантически важные факты. Для этих вопросов нужны отдельные операционные критерии.

Теорема Xu–Raginsky

Предположим, что для каждого фиксированного $w$ центрированная потеря

$$\ell(w,Z)-L(w)$$

$\sigma$-субгауссовская:

$$\ln \mathbb E_Z \exp\left[ \lambda(\ell(w,Z)-L(w)) \right] \le \frac{\lambda^2\sigma^2}{2}$$

для всех $\lambda\in\mathbb R$.

Тогда

$$\boxed{ \left| \mathbb E \left[ L(W)-\widehat L_S(W) \right] \right| \le \sqrt{ \frac{2\sigma^2 I(W;S)}{n} } }.$$

Если $0\le\ell\le1$, лемма Хёфдинга позволяет взять

$$\sigma^2=\frac14,$$

и получить

$$\left| \mathbb E\operatorname{gen} \right| \le \sqrt{ \frac{I(W;S)}{2n} }.$$

Откуда берётся формула

Под распределением произведения $P_S\otimes P_W$ модель $W$ независима от выборки. Для фиксированного $W$ средний эмпирический риск концентрируется вокруг популяционного с субгауссовским параметром $\sigma/\sqrt n$.

Но в реальном обучении используется совместное распределение $P_{S,W}$. Неравенство замены меры из Модуля 11 сравнивает ожидания одной функции под совместным распределением и под произведением маргиналов. Цена замены равна

$$D_{\mathrm{KL}} \left( P_{S,W} \|P_S\otimes P_W \right) = I(W;S).$$

Оптимизация по параметру экспоненциального момента даёт квадратный корень. Так же, как в PAC-Bayes, концентрация переносится с независимой постановки на зависимую. Но теперь роль стоимости играет не KL к выбранному априорному распределению, а сама взаимная информация алгоритма.

Численный пример адаптивного выбора

Для жёсткого выбора среди 32 одинаковых гипотез эксперимент даёт

$$I(W;S)\approx3.235\ \text{ната},$$ $$\sqrt{\frac{I(W;S)}{2n}} \approx0.142$$

при $n=80$, тогда как наблюдаемый ожидаемый разрыв равен примерно $0.087$.

Граница не точна, но она правильно отслеживает механизм: когда температура Gibbs-выбора увеличивается, зависимость от случайных деталей выборки уменьшается, и вместе с ней уменьшается смещение выбора.

Какой именно тип гарантии мы получили

Базовая MI-граница контролирует

$$\mathbb E_{S,W} \left[ L(W)-\widehat L_S(W) \right].$$

Это утверждение в среднем. Оно не является автоматически высоковероятностным сертификатом для конкретной обученной модели и конкретной выборки.

Кроме того, оно относится к выбранной функции потерь. Малый ожидаемый разрыв для кросс-энтропии не гарантирует малый разрыв по фактической корректности, безопасности или человеческим предпочтениям.

Почему детерминированная вещественная модель может иметь бесконечную MI

Если $W$ принимает конечное число значений и является детерминированной функцией $S$, то

$$I(W;S)=H(W)<\infty.$$

Но если $W$ — точный вещественный вектор, детерминированно вычисленный из непрерывной выборки, совместное распределение $(S,W)$ часто сингулярно относительно $P_S\otimes P_W$. Тогда

$$I(W;S)=\infty.$$

Алгоритм может хорошо обобщать, а базовая граница всё равно будет вакуумной. Это ограничение выбранной информационной меры, а не доказательство плохого обобщения.

Добавление шума способно сделать MI конечной, но при этом меняется сам алгоритм и его риск. Нельзя добавить шум только в доказательство и продолжать сертифицировать исходный детерминированный предиктор без отдельного аргумента.

MI по отдельным примерам

Более локальная оценка использует зависимости $I(W;Z_i)$:

$$\left| \mathbb E\operatorname{gen} \right| \le \frac1n \sum_{i=1}^n \sqrt{ 2\sigma^2 I(W;Z_i) }.$$

Она может быть существенно сильнее глобальной границы: каждый пример может влиять на результат слабо, даже если суммарная зависимость $I(W;S)$ велика или бесконечна.

12.7. Точное разложение, связывающее PAC-Bayes и MI

Пусть алгоритм задаёт условное распределение

$$Q_S=P_{W\mid S},$$

а $P_W$ — маргинальное распределение результата алгоритма при случайной выборке $S$.

Для любого фиксированного априорного распределения $P$, относительно которого соответствующие KL конечны, выполняется

$$\boxed{ \mathbb E_S D_{\mathrm{KL}}(Q_S\|P) = I(W;S) + D_{\mathrm{KL}}(P_W\|P) }.$$

Это точная бухгалтерия, а не аналогия.

• $I(W;S)$ — неизбежная средняя цена зависимости результата от выборки;
• $D_{\mathrm{KL}}(P_W\|P)$ — дополнительная цена несовпадения выбранной точки отсчёта с типичным распределением результатов алгоритма.

Доказательство

Добавим и вычтем логарифм плотности $P_W$:

$$\begin{aligned} \mathbb E_{S,W} \ln\frac{dQ_S}{dP}(W) &= \mathbb E_{S,W} \ln\frac{dQ_S}{dP_W}(W) + \mathbb E_{S,W} \ln\frac{dP_W}{dP}(W)\\ &= I(W;S) + D_{\mathrm{KL}}(P_W\|P). \end{aligned}$$

Оракульное априорное распределение

Среднюю величину

$$\mathbb E_S D_{\mathrm{KL}}(Q_S\|P)$$

минимизирует

$$P=P_W.$$

Тогда второй член исчезает, и средняя PAC-Bayes-сложность равна MI.

Почему же просто не использовать $P_W$? Теоретически, если распределение данных $\mathcal D$ и алгоритм полностью известны, $P_W$ фиксировано до текущей выборки и является валидной точкой отсчёта. Практическая проблема в том, что оно зависит от неизвестного распределения всех возможных обучающих выборок и обычно недоступно.

Если оценивать $P_W$ по той же сертифицирующей выборке, априорное распределение становится зависящим от данных, и стандартная теорема требует поправки.

Что объединено, а что осталось разным

Тождество объясняет, почему PAC-Bayes и MI часто дают похожие регуляризаторы. Но типы гарантий не совпадают.

Поэтому фраза «MI — это усреднённый PAC-Bayes» полезна как первая карта, но не заменяет теоремы.

12.8. Связи с MDL, Information Bottleneck и KL-регуляризованными политиками

Информационные конструкции предыдущих модулей действительно родственны. Самый безопасный способ увидеть родство — выписать случайные переменные и операционный смысл каждого KL.

PAC-Bayes и MDL

Пусть класс дискретен и

$$Q=\delta_w, \qquad P(w)>0.$$

Тогда

$$D_{\mathrm{KL}}(\delta_w\|P) =-\ln P(w).$$

В битах:

$$-\log_2P(w),$$

то есть идеальная длина кода гипотезы под априорным распределением.

Это точный мост: PAC-Bayes оплачивает описание выбранной модели относительно заранее объявленного кода.

Но MDL шире одной формулы. В нём есть двухчастные, смесевые и предиктивно-последовательные коды; непрерывные параметры требуют точности или стохастического кода; стоимость данных под моделью может учитываться иначе.

MI-границы и Information Bottleneck

В Information Bottleneck измеряется

$$I(X;T),$$

где $X$ — отдельный вход, а $T$ — его представление.

В теории обобщения измеряется

$$I(W;S),$$

где $S$ — весь обучающий набор, а $W$ — результат алгоритма.

Обе величины штрафуют зависимость от деталей исходного объекта. Но это разные объекты и разные задачи:

• IB спрашивает, сколько информации представление хранит о входе;
• MI-граница спрашивает, насколько обученный результат зависит от конкретной выборки.

Малое $I(X;T)$ само по себе не является доказательством малого $I(W;S)$ и не даёт автоматически границу обобщения. Старый лозунг «MI-границы строго доказывают IB» слишком силён. Корректнее сказать: обе теории используют общий принцип информационного ограничения, а прямой вывод требует дополнительной модели обучения.

PAC-Bayes KL и KL-якорь в RLHF

В PAC-Bayes:

$$D_{\mathrm{KL}} (Q_{\text{models}}\|P_{\text{models}})$$

сравнивает распределения над моделями или весами.

В KL-регуляризованном RLHF:

$$D_{\mathrm{KL}} \bigl( \pi(\cdot\mid x) \|\pi_{\mathrm{ref}}(\cdot\mid x) \bigr)$$

сравнивает распределения ответов при фиксированном контексте.

Алгебра похожа, потому что обе задачи используют экспоненциальный наклон относительно базовой меры. Но случайные объекты различны.

И ещё одна граница особенно важна после Модуля 8: PAC-Bayes контролирует переход от эмпирического риска к популяционному для заданной функции потерь. Если прокси-награда систематически расходится с истинной целью, маленький разрыв обобщения по прокси не исправит это смещение.

12.9. Как построить практический PAC-Bayes-сертификат

Теорема становится инженерным инструментом только после того, как все случайные объекты определены без двусмысленности.

Шаг 1. Зафиксировать сертифицируемый предиктор и функцию потерь

Нужно решить, что будет работать при эксплуатации:

• Gibbs-предиктор;
• апостериорный ансамбль;
• голосование большинства;
• детерминированная сеть.

Базовая граница относится к Gibbs-риску. Для другого объекта требуется отдельный переход.

Также нужно выбрать ограниченную функцию потерь. Нельзя обучать по кросс-энтропии, оценивать 0–1 риск и незаметно подставлять одно вместо другого.

Шаг 2. Зафиксировать валидное априорное распределение

Простейший вариант — выбрать $P$ до сертифицирующих данных.

Практически более сильный вариант — разделить выборку:

1. по $S_0$ построить информативное априорное распределение;
2. по независимой части $S_1$ обучить $Q$ и провести сертификацию условно на $S_0$.

Цена очевидна: априорное распределение становится лучше, но эффективная сертифицирующая выборка уменьшается.

Шаг 3. Обучить распределение, а не только точку

Для диагонального гауссовского $Q$ оптимизируются средние и дисперсии. Слишком малая дисперсия сохраняет хорошую подгонку, но создаёт большую KL. Слишком большая уменьшает часть сложности, но разрушает предсказания.

Поэтому сертификат ищет не просто «плоский минимум», а конкретный компромисс между робастностью стохастического предиктора и ценой относительно $P$.

Шаг 4. Сертифицировать эмпирический Gibbs-риск

Ожидание по $Q$ часто оценивается методом Монте-Карло. Тогда конечное число выборок из $Q$ добавляет ещё одну статистическую ошибку.

Просто усреднить десять сетей и подставить результат в формулу недостаточно для строгого сертификата. Нужна отдельная доверительная граница на эмпирический Gibbs-риск или аналитическое вычисление ожидания.

Шаг 5. Вычислить KL и инвертировать бинарную KL

Для диагональных гауссов $D_{\mathrm{KL}}(Q\|P)$ вычисляется аналитически. После этого PAC-Bayes-kl инвертируется численно.

В эксперименте модуля для стохастического линейного классификатора:

$$\widehat L_S(Q)\approx0.227,$$ $$D_{\mathrm{KL}}(Q\|P)\approx12.67\ \text{ната},$$ $$L(Q)\le0.272$$

при $\delta=0.05$. Диагностическая оценка тестового Gibbs-риска равна примерно

$$0.225.$$

Тестовый набор не участвует в сертификате; он нужен только для проверки эксперимента.

Что уже удавалось получить для глубоких сетей

Dziugaite и Roy показали, что прямой оптимизацией PAC-Bayes-границы можно получить невакуумные сертификаты для стохастических глубоких сетей с миллионами параметров. Более поздний метод PAC-Bayes with Backprop в своём протоколе на MNIST сообщал тестовую ошибку около $1.4\%$ и сертификат около $2.3\%$.

Это важный контрпример тезису «все теоретические границы для глубоких сетей обязательно больше единицы». Но он не является универсальным объяснением обобщения:

• результат зависит от архитектуры, параметризации и априорного распределения;
• сертифицируется стохастический предиктор;
• такая теснота границы на MNIST не переносится автоматически на LLM;
• вычислимый сертификат может оставаться значительно слабее отложенной оценки.

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

12.10. Математическое углубление: более локальные информационные цены

Этот раздел не требуется для основного маршрута. Он показывает, как теория смягчает две слабости базовых формул: априорное распределение трудно выбрать до данных, а $I(W;S)$ для детерминированной непрерывной модели может быть бесконечной.

Априорные распределения, зависящие от данных

Есть несколько корректных стратегий.

Разделение выборки. $P$ строится по $S_0$, а теорема условно применяется к независимой части $S_1$.

Иерархическое априорное распределение. Выбор одного из семейства априорных распределений кодируется верхним уровнем и оплачивается дополнительным KL или объединяющей оценкой.

Дифференциально-приватный выбор. Если механизм построения $P_S$ контролируемо зависит от данных, эта зависимость может быть включена в PAC-Bayes-гарантию.

Специализированные PAC-Bayes-теоремы для априорных распределений, зависящих от данных. Они напрямую добавляют член, измеряющий использование данных при выборе точки отсчёта.

Общий принцип не меняется:

Данные, использованные для уменьшения члена сложности, не исчезают из счёта бесплатно.

MI по отдельным примерам

Глобальная величина $I(W;S)$ может скрывать локальную структуру. По цепному правилу

$$I(W;S) = \sum_{i=1}^n I(W;Z_i\mid Z_{<i}),$$

но граница

$$\sqrt{I(W;S)}$$

сначала суммирует все вклады, а затем берёт один корень.

Граница по отдельным примерам использует

$$\frac1n \sum_{i=1}^n \sqrt{I(W;Z_i)}.$$

Если каждый пример влияет слабо, такая локальная агрегация может быть существенно меньше.

Условная взаимная информация

Построим сверхвыборку (supersample)

$$\widetilde S = \bigl( \widetilde Z_{i,0}, \widetilde Z_{i,1} \bigr)_{i=1}^n,$$

содержащую по два независимых кандидата на каждую позицию. Пусть

$$U=(U_1,\ldots,U_n), \qquad U_i\sim\operatorname{Bernoulli}(1/2),$$

и реальная обучающая выборка строится как

$$S_U = \bigl( \widetilde Z_{i,U_i} \bigr)_{i=1}^n.$$

Алгоритм возвращает

$$W=A(S_U).$$

Тогда условная информационная сложность измеряет

$$I(W;U\mid\widetilde S).$$

Её операционный смысл: если известны обе возможные выборки в каждой позиции, насколько по результату обучения можно восстановить биты $U_i$, сообщающие, какой пример действительно попал в обучение?

Для детерминированного алгоритма эта величина всё равно конечна:

$$I(W;U\mid\widetilde S) \le H(U) = n\ln2.$$

Именно поэтому CMI может оставаться содержательной там, где обычная $I(W;S)$ для точных вещественных весов бесконечна.

CMI связывает информационный взгляд с VC-размерностью, схемами сжатия и дифференциальной приватностью. Но она не становится автоматически простой вычислимой метрикой для большой нейросети. Это более точный объект теории, а не готовая строка в панели мониторинга.

12.12. Ключевые выводы модуля

Обучающая выборка выполняет две роли: по ней выбирают модель и по ней оценивают её качество. Именно повторное использование делает оценку победителя оптимистичной.

PAC-Bayes оплачивает адаптацию относительно заранее объявленной точки отсчёта:

$$\operatorname{kl} \bigl( \widehat L_S(Q)\|L(Q) \bigr) \lesssim \frac{ D_{\mathrm{KL}}(Q\|P) + \ln(1/\delta) }{n}.$$

MI-граница оплачивает среднюю зависимость результата алгоритма от выборки:

$$|\mathbb E\operatorname{gen}| \lesssim \sqrt{ \frac{I(W;S)}{n} }.$$

Их связывает точное тождество

$$\mathbb E_S D_{\mathrm{KL}}(Q_S\|P) = I(W;S) + D_{\mathrm{KL}}(P_W\|P).$$

Но итоговая карта важнее одного лозунга.

• PAC-Bayes обычно даёт высоковероятностный сертификат для Gibbs-предиктора.
• Базовая MI-граница обычно контролирует ожидаемый разрыв алгоритма.
• Априорное распределение, обученное на сертифицирующих данных, требует отдельной оплаты.
• $I(W;S)$ не равно $I(X;T)$ из Information Bottleneck.
• KL над весами не равна KL между политиками в RLHF.
• Малый разрыв обобщения по прокси-функции потерь не устраняет смещение самой прокси.
• Невакуумная граница доказывает нетривиальное утверждение, но не обязана быть достаточно тесной для выбора модели.

Это не набор защитных оговорок, а рабочая дисциплина. Информационная теория обобщения становится полезной, когда мы точно называем:

1. случайную выборку;
2. результат алгоритма;
3. сертифицируемый предиктор;
4. функцию потерь;
5. тип вероятностной гарантии;
6. цену адаптивности, которую действительно удалось вычислить.

В Модуле 13 эта дисциплина понадобится особенно сильно. Там слова «канал», «сжатие», «поиск» и «информация» будут применяться к рассуждению LLM, и каждый такой мост придётся отделять от прямой теоремы.

Основные источники

1. D. McAllester, «Some PAC-Bayesian Theorems», COLT 1998; «PAC-Bayesian Stochastic Model Selection», 2003.
2. A. Maurer, «A Note on the PAC Bayesian Theorem», 2004.
3. O. Catoni, «PAC-Bayesian Supervised Classification», 2007.
4. D. Russo, J. Zou, «Controlling Bias in Adaptive Data Analysis Using Information Theory», 2016.
5. A. Xu, M. Raginsky, «Information-Theoretic Analysis of Generalization Capability of Learning Algorithms», 2017.
6. G. K. Dziugaite, D. M. Roy, «Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks», 2017.
7. G. K. Dziugaite, D. M. Roy, «Data-Dependent PAC-Bayes Priors via Differential Privacy», 2018.
8. O. Rivasplata, V. M. Tankasali, C. Szepesvári, «PAC-Bayes with Backprop», 2019.
9. Y. Bu, S. Zou, V. V. Veeravalli, «Tightening Mutual Information Based Bounds on Generalization Error», 2019.
10. T. Steinke, L. Zakynthinou, «Reasoning About Generalization via Conditional Mutual Information», 2020.