PAC-Bayes: первая нон-вакуусная граница для нейросетей

2017 год. ResNet-50 достигает 4.9% top-5 ошибки на ImageNet. 25 миллионов параметров. Обучающая выборка - 1.2 миллиона примеров. VC-теория даёт гарантию обобщения: ошибка на тестовой выборке не превышает ошибку на обучающей плюс сложность класса гипотез. Для сети с W параметрами VC-размерность не меньше W. Подставляем: sqrt(W * log(em/W) / m) = sqrt(25M * log(e * 1.2M / 25M) / 1.2M) Логарифм отрицателен при W > m. Берём абсолютное значение - получаем число больше 4. Граница равна 400%. Ошибка не может превышать 1 по определению - это 100%. Математика права, но бесполезна: вакуусный bound. Gabriel Dziugaite и Daniel Roy в 2017 году сделали то, что считалось невозможным: доказали математически строго, что та же сеть обобщается с гарантией 16% при фактической ошибке 2%. Первая нон-вакуусная граница для глубокого обучения в истории. Инструмент: PAC-Bayes теорема McAllester 1998 года. Вместо одной гипотезы - распределение над гипотезами. Вместо VC-размерности - KL-дивергенция между prior и posterior.

• **Глубокое обучение без теоретических гарантий:** до 2017 года не было ни одного строгого математического доказательства что нейросети обобщаются. VC bounds для 25M параметров давали >100% - хуже случайного угадывания в качестве гарантии. PAC-Bayes закрыл этот пробел
• **SAM (Sharpness-Aware Minimization, Foret et al. 2021):** оптимизатор, явно ищущий flat minima. Работает потому что flat minimum = малый KL в PAC-Bayes = tight bound = хорошее обобщение. Использован в EfficientNetV2, ViT, DALL-E
• **Bayesian deep learning (Graves 2011, Blundell 2015):** weight uncertainty, variational inference - прямое следствие PAC-Bayes view. Posterior над весами вместо точечной оценки
• **ELBO в VAE:** Evidence Lower BOund = ожидаемое правдоподобие минус KL(q(z|x)||p(z)). Это ровно PAC-Bayes objective с другими обозначениями. Posterior collapse в VAE = нарушение баланса между fit и KL-penalty

Предварительные знания

• VC-размерность и PAC-learning: R(h) <= R_hat(h) + O(sqrt(VC-dim / m))
• KL-дивергенция: KL(Q||P) = E_Q[log(Q/P)] >= 0
• NFL-теорема: без prior невозможно обобщение на всех задачах

• No-Free-Lunch: зачем нужен prior
• Rademacher complexity: data-dependent bounds

Концепт 1: почему VC bounds вакуусны для нейросетей

Концепт 1: почему VC bounds вакуусны для нейросетей

VC-теория измеряет сложность класса гипотез $\mathcal{H}$ через максимальное число точек, которые $\mathcal{H}$ может разметить произвольно. Для нейронной сети классический результат Bartlett et al. 1998 даёт: $\text{VCdim}(\mathcal{H}) \geq W$, где $W$ - число весов. Это нижняя оценка: сеть с 25M параметров имеет VC-размерность не меньше 25M.

**VC generalization bound (классический):** $$R(h) \leq \hat{R}(h) + \sqrt{\frac{\text{VCdim}(\mathcal{H}) \cdot \log(em/\text{VCdim}) + \log(1/\delta)}{2m}}$$ Для ResNet-50: $\text{VCdim} \geq W = 25 \times 10^6$, $m = 1.2 \times 10^6$. При $W > m$ логарифм отрицателен, и в корне оказывается отрицательное число. Любая корректная версия bound даёт значение $> 1$: вакуусная граница.

Проблема не в размере сети. Проблема в том, что VC-теория измеряет наихудший случай: насколько плох класс гипотез в целом. Но конкретная гипотеза $h^*$, найденная SGD, может быть значительно проще, чем наихудшая в классе. VC-граница не умеет это использовать. PAC-Bayes идёт другим путём: вместо наихудшей гипотезы в классе - распределение Q над гипотезами, сосредоточенное вблизи $h^*$. Сложность измеряется не размером класса, а тем, насколько Q отличается от prior P.

Концепт 2: PAC-Bayes теорема McAllester 1998

Концепт 2: PAC-Bayes теорема McAllester 1998

Ключевая идея: вместо одной гипотезы $h \in \mathcal{H}$ рассматриваем распределение $Q$ над $\mathcal{H}$ - стохастический классификатор. При классификации нового примера $x$ сэмплируем $h \sim Q$ и применяем $h(x)$. Ошибка такого классификатора: $R(Q) = \mathbb{E}_{h \sim Q}[R(h)]$. Prior $P$ - фиксированное распределение над $\mathcal{H}$, выбранное до просмотра данных. Это формализация NFL-требования к prior: нужно зафиксировать beliefs до того как увидим обучающую выборку.

**PAC-Bayes теорема (McAllester 1998).** Пусть $P$ - prior на $\mathcal{H}$, фиксированный до обучения. Тогда с вероятностью $\geq 1 - \delta$ над выбором обучающей выборки $S$ одновременно для всех распределений $Q$ на $\mathcal{H}$: $$R(Q) \leq \hat{R}(Q) + \sqrt{\frac{KL(Q \| P) + \ln(m/\delta)}{2m}}$$ где $R(Q) = \mathbb{E}_{h \sim Q}[R(h)]$ - ожидаемая ошибка, $\hat{R}(Q) = \mathbb{E}_{h \sim Q}[\hat{R}(h)]$ - эмпирическая ошибка, $KL(Q \| P) = \mathbb{E}_{h \sim Q}[\log \frac{Q(h)}{P(h)}]$ - дивергенция Кульбака-Лейблера.

Почему $KL(Q \| P)$ - правильная мера сложности? $KL$ измеряет информационное расстояние от prior к posterior: сколько информации из данных потребовалось, чтобы обновить $P$ до $Q$. Если $Q$ близко к $P$ - данные мало изменили beliefs, $KL$ мал. Если $Q$ далеко от $P$ - данные сильно изменили beliefs, $KL$ велик. Принцип: чем больше данных нужно чтобы обосновать $Q$ - тем хуже гарантия обобщения. Это принцип Оккама в математической форме. Для гауссовых распределений: $KL(\mathcal{N}(\mu_1, \sigma_1^2) \| \mathcal{N}(\mu_2, \sigma_2^2)) = \ln(\sigma_2/\sigma_1) + (\sigma_1^2 + (\mu_1 - \mu_2)^2) / (2\sigma_2^2) - 1/2$

Концепт 3: нон-вакуусная граница Dziugaite-Roy 2017

Концепт 3: нон-вакуусная граница Dziugaite-Roy 2017

Dziugaite и Roy применили PAC-Bayes к нейронным сетям напрямую. Архитектура: 2-слойная FCN, около $6 \times 10^4$ параметров, MNIST. Prior: $P = \mathcal{N}(0, \lambda I)$ - изотропный гауссов prior на пространстве весов. Posterior: $Q = \mathcal{N}(w^*, \text{diag}(\sigma^2))$ - гауссов с центром в обученных весах $w^*$ и диагональной ковариацией. Вместо стандартного обучения (минимизация кросс-энтропии) они минимизируют PAC-Bayes objective напрямую: $$\mathcal{L}_{BPAC}(Q) = \hat{R}(Q) + \sqrt{\frac{KL(Q \| P) + \ln(m/\delta)}{2m}}$$ Параметры оптимизации: $w^*$ (веса) и $\sigma^2$ (дисперсия posterior). Оба дифференцируемы через reparameterization trick.

**Результаты Dziugaite-Roy (NeurIPS 2017):** - Сеть: 2-слойная FCN, ~$6 \times 10^4$ параметров - Dataset: MNIST, $m = 60{,}000$ - Test error: 2% - $KL(Q \| P) \approx 10^6$ суммарный - PAC-Bayes bound: **16%** при $\delta = 0.05$ - Первая нон-вакуусная граница в истории для нейросетей VC bound для той же сети: $W = m$, логарифм около нуля, bound $\approx 1$ - вакуусный.

16% против 2% test error - граница неплотная, но конечная. Это принципиально: математика впервые подтвердила то, что практики знали эмпирически - глубокие сети обобщаются. Разрыв между 2% и 16% объясняется тем, что PAC-Bayes bound - гарантия наихудшего случая с вероятностью 0.95: в 95% случаев ошибка не превысит 16%. Фактическая ошибка может быть значительно лучше.

Концепт 4: flat minima, SAM и связь с Bayesian DL

Концепт 4: flat minima, SAM и связь с Bayesian DL

KL для гауссового posterior над весами раскладывается аналитически. Для одного веса $w_i$ с posterior $\mathcal{N}(w_i, \sigma_i^2)$ и prior $\mathcal{N}(0, \lambda)$: $$KL_i = \frac{w_i^2 + \sigma_i^2}{2\lambda} - \frac{1}{2}\ln\frac{\sigma_i^2}{\lambda} - \frac{1}{2}$$ Малый $KL_i$ достигается когда: 1. $|w_i|$ мал - веса близки к нулю 2. $\sigma_i^2$ велика - posterior размыт, неопределён. Условие 2 - математическое определение flat minimum: классификатор нечувствителен к возмущениям весов $w^* + \epsilon$ при небольшом $\epsilon$. Именно поэтому flat minima обобщаются лучше - это не интуиция, а теорема.

**Flat minimum = малый KL = tight PAC-Bayes bound.** Flat minimum: функция потерь вблизи $w^*$ меняется медленно при малых возмущениях. Формально: малый след Гессиана $\text{tr}(\nabla^2 \mathcal{L}(w^*))$. Связь: если сеть нечувствительна к возмущениям весов (flat), то стохастический классификатор $h \sim \mathcal{N}(w^*, \sigma^2 I)$ даёт почти ту же ошибку что и детерминированный при большом $\sigma^2$. Значит $\hat{R}(Q) \approx \hat{R}(h^*)$, и можно взять большой $\sigma^2$ - уменьшив KL. SGD с маленьким batch size неявно находит flat minima (Keskar et al. 2017). SAM делает это явно.

SAM (Sharpness-Aware Minimization, Foret et al. 2021) явно оптимизирует: $$\min_w \max_{\|\epsilon\| \leq \rho} \mathcal{L}(w + \epsilon)$$ Это поиск весов, вокруг которых функция потерь не растёт резко - flat minimum по определению. SAM даёт tighter PAC-Bayes bound без явной байесовской оптимизации. Используется в EfficientNetV2, ViT, DALL-E 2 именно для улучшения обобщения. Unified view через PAC-Bayes: - **L2 регуляризация** = гауссов prior $\mathcal{N}(0, 1/\alpha)$ с $\sigma_q \to 0$ - **Dropout** = prior о независимости нейронов; стохастический классификатор через Bernoulli маски - **Variational inference (BBB, Graves 2011)** = явная минимизация $KL(Q \| P)$ через reparameterization - **ELBO в VAE** = PAC-Bayes с latent space вместо hypothesis space - **Posterior collapse в VAE** = $KL$-член доминирует, $Q \to P$, модель игнорирует данные

Что забрать из урока

• **VC bounds вакуусны для DL:** при $m < W$ (данных меньше параметров) bound $> 1$. VC измеряет наихудший случай по всему классу, SGD находит конкретную простую гипотезу
• **PAC-Bayes (McAllester 1998):** $R(Q) \leq \hat{R}(Q) + \sqrt{(KL(Q\|P) + \ln(m/\delta)) / 2m}$ - bound одновременно для всех posterior Q. Сложность = $KL(Q\|P)$: насколько далеко posterior от prior
• **Prior P фиксируется до данных** - иначе $KL = 0$ автоматически. KL измеряет реальное информационное обновление beliefs. Формализует NFL-требование к prior
• **Dziugaite-Roy 2017:** первая нон-вакуусная граница для DL. 16% bound при 2% test error. Ключ: минимизация PAC-Bayes objective = явная оптимизация под гарантию обобщения
• **Flat minima = малый KL:** большой $\sigma_q$ (неопределённость posterior) = малый KL = лучший bound. SAM явно ищет flat minima, SGD small-batch - неявно
• **Unified view:** L2 = гауссов prior. Dropout = Bernoulli prior. ELBO в VAE = PAC-Bayes objective. Posterior collapse = KL доминирует над fit

Что дальше

PAC-Bayes - мост между классической теорией обобщения и современным глубоким обучением:

• Margin bounds — Margin как flat minimum: классификатор с большим margin имеет малый KL относительно N(0, 1/||w||^2) prior
• Generalization paradox в deep learning — PAC-Bayes объясняет почему overparameterized сети обобщаются: SGD находит flat minima с малым KL
• Rademacher complexity — Rademacher - data-dependent bound для класса. PAC-Bayes - data-dependent bound для конкретной гипотезы через posterior
• No-Free-Lunch — NFL требует prior; PAC-Bayes формализует prior как P и штрафует за удаление от него через KL

Вопросы для размышления

• PAC-Bayes bound для ResNet-50 с гауссовым prior N(0, 0.01*I) и posterior N(w*, 0.001*I) при KL ~ 10^8 и m = 1.2M даёт sqrt(10^8 / 2.4M) ~ 6. Всё ещё вакуусный. Как Dziugaite-Roy добились 16% при похожих параметрах сети? Что особенного в их prior и в том как они выбирают lambda?
• ELBO в VAE: E_q[log p(x|z)] - KL(q(z|x) || p(z)). Posterior collapse - это когда q(z|x) -> p(z) для всех x, то есть KL -> 0. Через линзу PAC-Bayes: что это означает для обобщения VAE? Почему collapse - это плохо, даже если bound становится tight?
• SAM минимизирует max_{||eps|| <= rho} L(w + eps). При rho -> 0 это обычный GD. При rho -> inf - полный игнор данных. Существует ли теоретически обоснованный выбор rho через параметры обучения (m, delta, sigma_prior) из PAC-Bayes framework?

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

• lt-08-no-free-lunch — NFL объясняет зачем нужен prior P - PAC-Bayes формализует его как распределение
• lt-06-rademacher — Rademacher - data-dependent bound для класса; PAC-Bayes - data-dependent bound для распределения
• lt-07-uniform-convergence — Uniform convergence даёт bounds для одной гипотезы; PAC-Bayes - одновременно для всех постериоров Q
• lt-11-margin-bounds — Margin bounds через PAC-Bayes: margin как flat minimum = малый KL
• lt-13-deep-generalization — PAC-Bayes объясняет почему flat minima от SGD ведут к лучшему обобщению
• prob-04-bayes