Статистическая теория обучения
Информационно-теоретическая теория обучения
Почему шумный SGD обобщает лучше, чем точный решатель с той же обучающей ошибкой? Информационно-теоретический ответ: шум уменьшает I(W;S) - количество информации о выборке в весах модели.
- **Ланжевеновский SGD:** Добавление гауссового шума к градиентам ограничивает I(W;S) - теоретически обоснованная причина, почему шумный SGD обобщает лучше точных методов
- **Dropout в нейросетях:** Dropout неявно уменьшает I(W;S): случайное отключение нейронов не позволяет весам «запомнить» конкретные примеры
- **Дифференциальная приватность:** DP-SGD добавляет шум для приватности; это одновременно ограничивает I(W;S) и даёт гарантии обобщения через информационно-теоретическую границу
- **PAC-Bayes для трансформеров:** KL-граница Мак-Аллестера применяется для анализа fine-tuning больших языковых моделей: маленькое KL(постериор||приор) означает хорошее обобщение
Предварительные знания
- Оценки через сжатие
- Взаимная информация и энтропия
- SGD и стохастическая оптимизация
Границы через взаимную информацию
Дэниел Мак-Аллестер в 2017 году показал: обобщающий разрыв алгоритма A ограничен через I(W; S) - взаимную информацию весов W и обучающей выборки S. SGD с шумом Ланжевена при шаге η и дисперсии шума σ^2 даёт I(W; S) <= η^2 m / σ^2. Это объяснило феномен: шумный SGD обобщает лучше точных решателей при одинаковой обучающей ошибке.
Что утверждает граница обобщения через MI?
Xu-Raginsky (2017): |E[R(W) - R_hat(W)]| <= sqrt(2*sigma² * I(W; S) / n), где I(W; S) - взаимная информация между обученными весами и обучающим набором. Если алгоритм "запоминает" мало о S, обобщение хорошее. Объясняет, почему compression и стохастичность улучшают generalization.
KL-границы и information bottleneck
Какую цель оптимизирует Information Bottleneck (IB) в representation learning?
Tishby IB principle (1999, deep IB 2017): представление T должно быть минимально достаточной статистикой для предсказания Y. Сжимать X (low I(X; T)), но сохранять предсказательность Y (high I(T; Y)). Tishby-Shwartz объясняли через IB генерализацию DNN: training имеет 2 фазы - подгонка (max I(T; Y)) и сжатие (min I(X; T)).
PAC-Bayes: байесовская перспектива
I(W;S) как след пальцев на весах модели - Криминалист проверяет, остались ли следы конкретной жертвы (примеров из S) на орудии преступления (весах W). Если следов мало (I мало) - модель «не запомнила» выборку. Если следы явные (I велико) - переобучение. Маленькое I(W;S) не означает плохую модель - это означает, что модель извлекла общие паттерны, а не запомнила конкретные примеры.
Что устанавливает граница PAC-Bayes McAllester?
McAllester (1998): для prior P и posterior Q над гипотезами с вероятностью 1-delta: средний риск под Q не превышает среднего эмпирического риска плюс sqrt(KL(Q||P)/n). KL заменяет "размер класса" более тонко: апостериор Q может концентрироваться, но штраф зависит от его расстояния от априора.
Связи с другими темами
Информационно-теоретический подход связывает теорию обобщения с теорией информации, дифференциальной приватностью и PAC-Bayes.
- PAC-Bayes — Связанная тема
- Дифференциальная приватность — Связанная тема
- Алгоритмическая устойчивость — Связанная тема
- Минимальная длина описания (MDL) — Связанная тема
Итоги
- I(W;S) - взаимная информация весов W и выборки S: чем меньше, тем лучше обобщение
- Граница Xu-Raginsky: |gen| не хуже sqrt(2σ²I(W;S)/m) - обобщение гарантировано при малом I
- CMI-граница Steinke-Zakynthinou: острее через условную взаимную информацию
- Ланжевеновский SGD: шум σ уменьшает I(W;S) - формальное объяснение, почему шумный SGD лучше обобщает
- PAC-Bayes: KL(Q||P) играет роль I(W;S) в стохастических классификаторах
Что означает маленькое I(W;S) для обобщения?
I(W;S) ~ 0 означает W статистически независим от S. Алгоритм выучил общие паттерны, а не конкретные примеры.