Теория вероятностей
Информационно-теоретические методы
Почему нейронная сеть с $10^{10}$ параметров обобщается на новые данные? Информационно-теоретический ответ: взаимная информация между весами сети и обучающей выборкой ограничена - это ограничивает обобщающую ошибку. Энтропия, KL-дивергенция и взаимная информация - язык, на котором говорит современная теория обобщения.
- Bottleneck информации (IB): оптимальное промежуточное представление в нейросети максимизирует взаимную информацию с меткой $I(Z; Y)$ и минимизирует с входом $I(Z; X)$ - trade-off между сжатием и предсказанием. Теория IB Тишби используется для анализа слоёв BERT.
- VAE (Variational Autoencoder): ELBO $= \mathbb{E}[\log p(x|z)] - \mathrm{KL}(q(z|x) \| p(z))$ - это буквально нижняя оценка log-likelihood через взаимную информацию и энтропию.
- Метод типов (method of types): используется для доказательства формулы канальной ёмкости Шеннона $C = \max_{p(x)} I(X;Y)$ и в анализе алгоритмов сжатия.
Цели урока
- Вычислять энтропию, KL-дивергенцию и взаимную информацию для дискретных и непрерывных распределений
- Применять неравенство Фано для нижних оценок вероятности ошибки классификатора
- Объяснять метод типов и его роль в доказательстве формулы канальной ёмкости
Предварительные знания
- Совместные и условные распределения
- Интеграл Лебега и измеримые функции
- Неравенство Йенсена для выпуклых функций
Энтропия и KL-дивергенция
Энтропия Шеннона: $H(X) = -\sum_x p(x) \log p(x) \geq 0$. Дифференциальная энтропия: $h(X) = -\int p(x) \log p(x) \, dx$ (может быть отрицательной). KL-дивергенция: $\mathrm{KL}(P \| Q) = \sum_x p(x) \log \frac{p(x)}{q(x)} \geq 0$ (по неравенству Йенсена). Взаимная информация: $I(X;Y) = \mathrm{KL}(P_{XY} \| P_X \otimes P_Y) = H(X) - H(X|Y) \geq 0$. Цепное правило: $I(X;Y,Z) = I(X;Y) + I(X;Z|Y)$.
Неравенство Фано: для классификатора $\hat Y$ по наблюдению $X$, $P_e = P(\hat Y \neq Y)$ удовлетворяет $H(Y|X) \leq H(P_e) + P_e \log(|\mathcal{Y}|-1)$, или грубее: $P_e \geq (H(Y|X)-1)/\log|\mathcal{Y}|$. Смысл: если $Y$ трудно предсказать (большая условная энтропия), то и любой классификатор будет делать ошибки. Это нижняя граница, не зависящая от архитектуры.
KL-дивергенция не симметрична: $\mathrm{KL}(P\|Q) \neq \mathrm{KL}(Q\|P)$. В вариационном выводе выбор направления имеет значение: $\mathrm{KL}(q\|p)$ (используется в VI) минимизирует моды-seeking поведение и может подогнать одну моду многомодального $p$. $\mathrm{KL}(p\|q)$ ведёт к mean-seeking поведению. GAN обходит это через дивергенцию Йенсена-Шеннона.
Взаимная информация и нелинейная зависимость
Клод Шеннон в 1948 году в Bell Labs ввёл взаимную информацию $I(X;Y)$ как меру зависимости двух случайных величин. В 2021 году DeepMind использовал InfoNCE - нижнюю оценку $I(X;Y)$ - для тренировки моделей на 1.6 миллиарда изображений: модели, максимизирующие $I$ между разными аугментациями одного изображения, обходят supervised baselines.
$X$ - справедливая монета (0/1), $Y = X$ - точная копия. Чему равно $I(X;Y)$?
Неравенство Фано как нижняя оценка ошибки
Роберто Фано около 1952 года при работе над теорией кодирования вывел неравенство, ставшее главным инструментом доказательства минимаксных нижних оценок в статистике. Например, для оценки плотности с точностью $\varepsilon$ в $L_2$-норме на пространстве $C^\beta(\mathbb{R}^d)$ Фано даёт минимаксную скорость $n^{-2\beta/(2\beta+d)}$ - точно совпадающую с верхней оценкой ядерных оценок.
Неравенство Фано даёт $P_e \ge (H(X \mid Y) - 1)/\log|\mathcal{X}|$. Когда оценка нетривиальна (положительна)?
Метод типов Чернова
Имре Чисар в 1984 году систематизировал метод типов: вероятность эмпирического распределения убывает экспоненциально со скоростью $D(Q \| P)$. На этом построена ANS-кодирование (asymmetric numeral systems, Дуда 2014), которое сжимает данные за один проход и используется в Zstd, JPEG XL и Facebook Zstandard для 4 миллиардов устройств.
Тест на справедливость монеты: $P = \mathrm{Ber}(0.5)$, тест отвергает при наблюдении $\hat{p} \ge 0.6$. Как ведёт себя вероятность ошибочного отклонения с ростом $n$?
VAE ELBO как информационный баланс
$\log p(x) \geq \mathbb{E}_{q(z|x)}[\log p(x|z)] - \mathrm{KL}(q(z|x) \| p(z))$. Первый член - reconstruction loss (взаимная информация между $x$ и $z$); второй - regularization (KL к априорному). Максимизация ELBO одновременно минимизирует ошибку реконструкции и «сжимает» латентный код к нормальному распределению. При $\beta$-VAE: второй член умножается на $\beta > 1$ для большего сжатия.
Итоги
- Энтропия измеряет неопределённость, KL-дивергенция - расстояние между распределениями, взаимная информация - зависимость переменных.
- Неравенство Фано даёт нижнюю оценку ошибки любого классификатора.
- VAE ELBO, информационный bottleneck и mutual information bounds в теории обобщения строятся на этом фундаменте.
Связь с другими темами
Байесовские сети (prob-27) используют взаимную информацию для отбора признаков и структурного обучения. PAC-обучение (prob-26) имеет информационно-теоретические аналоги через mutual information bounds. Статистическая физика (prob-28): энтропия Больцмана $S = k_B \ln \Omega$ - тот же концепт в другой нотации.
- Prob 27 — связан
- Prob 26 — связан
- Prob 28 — связан
Вопросы для размышления
- Теорема Шеннона о кодировании источника: $H(X)$ - минимальное число бит на символ для сжатия без потерь. Алгоритмы Хаффмана и арифметического кодирования приближают этот предел. Как метод типов формализует понятие 'типичной последовательности' и связывает его с $H(X)$?