Условная энтропия

Условная энтропия (также апостериорная энтропия) — это мера неопределённости одной случайной величины при условии, что известна другая случайная величина. В теории информации условная энтропия показывает, какое количество информации в среднем необходимо для описания значения одной случайной величины, если значение другой уже известно. Понятие является фундаментальным для анализа каналов связи, сжатия данных с учётом контекста и построения криптографических систем.

Определение

Пусть \(X\) и \(Y\) — две дискретные случайные величины с совместным распределением \(p(x,y)\). Условная энтропия \(H(Y|X)\) определяется как математическое ожидание по \(x\) от энтропии распределения \(Y\) при условии \(X = x\):

\[ H(Y|X) = \sum_{x \in \mathcal{X}} p(x) \, H(Y|X = x) = -\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log_2 p(y|x), \]

где \(p(y|x) = p(x,y)/p(x)\) — условная вероятность, а логарифм берётся по основанию 2, что даёт результат в битах. Если основание натуральное — результат в натах.

Условная энтропия всегда неотрицательна и не превосходит безусловной энтропии \(H(Y)\):

\[ 0 \le H(Y|X) \le H(Y). \]

Равенство \(H(Y|X) = H(Y)\) достигается тогда и только тогда, когда \(X\) и \(Y\) независимы. Равенство \(H(Y|X) = 0\) означает, что \(Y\) является детерминированной функцией от \(X\).

Свойства

Цепное правило (правило сложения энтропий)

Совместная энтропия двух случайных величин равна сумме безусловной энтропии одной и условной энтропии другой:

\[ H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y). \]

Это правило обобщается на любое конечное число величин:

\[ H(X_1, X_2, \dots, X_n) = \sum_{i=1}^n H(X_i | X_1, \dots, X_{i-1}). \]

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

Взаимная информация \(I(X;Y)\) определяется как разность между безусловной и условной энтропией:

\[ I(X;Y) = H(Y) - H(Y|X) = H(X) - H(X|Y). \]

Она показывает, сколько информации об \(Y\) содержится в \(X\) (и наоборот). Взаимная информация симметрична и неотрицательна.

Условная энтропия для непрерывных величин

Для непрерывных случайных величин с плотностью распределения \(f(x,y)\) условная дифференциальная энтропия определяется аналогично:

\[ h(Y|X) = -\int_{\mathcal{X}} \int_{\mathcal{Y}} f(x,y) \log_2 f(y|x) \, dy \, dx. \]

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

Примеры

Пример 1: Зависимые бинарные величины

Пусть \(X\) — результат подбрасывания симметричной монеты (0 или 1 с вероятностью 0,5). Пусть \(Y = X\) (полная зависимость). Тогда \(H(Y|X) = 0\), так как при известном \(X\) значение \(Y\) определено однозначно. Безусловная энтропия \(H(Y) = 1\) бит.

Пример 2: Независимые величины

Пусть \(X\) и \(Y\) — независимые симметричные монеты. Тогда \(H(Y|X) = H(Y) = 1\) бит, так как знание \(X\) не уменьшает неопределённости \(Y\).

Пример 3: Канал с шумом

Рассмотрим двоичный симметричный канал: на вход подаётся \(X\) (0 или 1), на выходе \(Y\) с вероятностью ошибки \(p\) (0,1). Тогда условная энтропия \(H(Y|X)\) равна энтропии двоичного распределения с вероятностью \(p\):

\[ H(Y|X) = -p \log_2 p - (1-p) \log_2 (1-p). \]

При \(p=0\) (канал без шума) \(H(Y|X)=0\); при \(p=0,5\) (канал полностью зашумлён) \(H(Y|X)=1\) бит.

Применение

Теория кодирования и сжатие данных

Условная энтропия используется для оценки минимальной средней длины кода при сжатии данных с учётом контекста. Например, в алгоритмах арифметического кодирования и кодирования Хаффмана с предсказанием (контекстное моделирование) достигаемая степень сжатия приближается к \(H(Y|X)\), где \(X\) — предыдущие символы, а \(Y\) — текущий.

Пропускная способность канала

Пропускная способность канала связи определяется как максимум взаимной информации по всем входным распределениям:

\[ C = \max_{p(x)} I(X;Y) = \max_{p(x)} [H(Y) - H(Y|X)]. \]

Условная энтропия \(H(Y|X)\) здесь играет роль ненадёжности канала (equivocation) — она показывает, сколько информации теряется из-за шума.

Криптография

В теории секретности, развитой Клодом Шенноном, условная энтропия \(H(M|C)\) (неопределённость сообщения при известной криптограмме) используется для оценки стойкости шифра. Система называется совершенно стойкой, если \(H(M|C) = H(M)\) — то есть знание шифротекста не уменьшает неопределённости сообщения.

Машинное обучение

В задачах классификации и регрессии условная энтропия применяется для оценки информативности признаков. Например, при построении деревьев решений критерий прироста информации (information gain) вычисляется как разность \(H(Y) - H(Y|X)\), где \(Y\) — целевая переменная, а \(X\) — признак.

Связь с другими понятиями

• Энтропия — мера неопределённости одной случайной величины.
• Совместная энтропия — мера неопределённости пары (или набора) величин.
• Взаимная информация — мера зависимости между величинами.
• Условная взаимная информация — обобщение на случай трёх и более величин.

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

Источники

• Клод Шеннон, «Математическая теория связи», 1948.
• Томас М. Ковер, Джой А. Томас, «Элементы теории информации», 2-е издание, 2006.
• Роберт Галлагер, «Теория информации и надёжная связь», 1968.