Энтропия Шеннона

Энтропия Шеннона — это мера неопределённости (или информационной ёмкости) случайной величины, введённая Клодом Шенноном в 1948 году в статье «Математическая теория связи». Является фундаментальным понятием теории информации, статистической физики и машинного обучения. Энтропия Шеннона количественно определяет среднее количество информации, содержащееся в одном сообщении из источника, или, эквивалентно, минимальное количество бит, необходимое для кодирования сообщений без потерь.

Определение

Для дискретной случайной величины \(X\) с множеством возможных значений \(\{x_1, x_2, \dots, x_n\}\) и вероятностями \(p_i = P(X = x_i)\), где \(\sum_{i=1}^n p_i = 1\), энтропия Шеннона \(H(X)\) определяется как:

\[ H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i \]

Если основание логарифма равно 2, энтропия измеряется в битах. При использовании натурального логарифма (e) — в натах, десятичного (10) — в дитах или хартли. Для непрерывных случайных величин используется дифференциальная энтропия, определяемая через интеграл.

Свойства

• Неотрицательность: \(H(X) \ge 0\). Равенство нулю достигается, когда одна из вероятностей равна 1, а остальные — 0 (полная определённость).
• Максимум: Для фиксированного числа исходов \(n\) энтропия максимальна при равномерном распределении (\(p_i = 1/n\)) и равна \(\log_2 n\).
• Субалдитивность: Для двух случайных величин \(X\) и \(Y\) выполняется \(H(X,Y) \le H(X) + H(Y)\), где \(H(X,Y)\) — совместная энтропия.
• Условная энтропия: \(H(X|Y) = H(X,Y) - H(Y)\) — мера неопределённости \(X\) при известном \(Y\).
• Взаимная информация: \(I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)\) — количество информации, которое одна случайная величина содержит о другой.

История

Понятие энтропии как меры неопределённости впервые появилось в термодинамике (Людвиг Больцман, 1877) и статистической физике (Джозайя Гиббс, 1902). В 1928 году Ральф Хартли предложил логарифмическую меру количества информации для равновероятных событий (\(H = \log_2 n\)). Клод Шеннон обобщил эту меру на случай произвольных вероятностей, введя формулу с суммой взвешенных логарифмов. Шеннон консультировался с Джоном фон Нейманом по поводу названия, и тот предложил «энтропия» из-за её сходства с термодинамической энтропией, а также потому, что «никто точно не знает, что такое энтропия, поэтому в споре вы всегда будете иметь преимущество».

Классификация и виды

### Энтропия дискретного источника

Основная форма, применяемая для дискретных сообщений (символы, буквы, коды). Например, для источника с двумя символами (0 и 1) с вероятностями \(p\) и \(1-p\) энтропия равна \(H = -p \log_2 p - (1-p) \log_2 (1-p)\). Эта функция (бинарная энтропия) достигает максимума 1 бит при \(p=0.5\).

### Дифференциальная энтропия

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

\[ h(X) = -\int_{-\infty}^{\infty} f(x) \log_2 f(x) \, dx \]

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

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

Показывает, сколько информации остаётся в \(X\) после того, как известна \(Y\). Используется в теории кодирования и каналах связи.

### Совместная энтропия

Энтропия пары (или более) случайных величин: \(H(X,Y) = -\sum_{x,y} p(x,y) \log_2 p(x,y)\).

Применение

Теория кодирования

Энтропия Шеннона задаёт нижнюю границу среднего числа бит на символ при сжатии данных без потерь (теорема Шеннона о кодировании источника). Например, алгоритмы Хаффмана и арифметического кодирования стремятся достичь этой границы.

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

Энтропия используется для оценки стойкости паролей и ключей шифрования. Высокая энтропия (например, 128 бит для AES) означает, что ключ практически невозможно угадать перебором.

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

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

Статистическая физика

Формула Больцмана \(S = k \ln W\) является частным случаем энтропии Шеннона для равновероятных микросостояний (где \(W\) — число микросостояний, \(k\) — постоянная Больцмана). В термодинамике энтропия Шеннона совпадает с термодинамической энтропией для систем в равновесии.

Лингвистика и анализ текстов

Энтропия языка — среднее количество информации на букву в тексте. Для русского языка энтропия оценивается примерно в 1.5–2 бита на букву (с учётом контекста), что значительно меньше 5 бит, соответствующих 32 буквам алфавита.

Примеры

Пример 1: Подбрасывание монеты

Для честной монеты (орёл и решка с вероятностью 0.5) энтропия равна \(H = -0.5 \log_2 0.5 - 0.5 \log_2 0.5 = 1\) бит. Для нечестной монеты с вероятностью орла 0.9 энтропия равна \(H = -0.9 \log_2 0.9 - 0.1 \log_2 0.1 \approx 0.469\) бит.

Пример 2: Текст на русском языке

Рассмотрим фразу «Привет, мир!» с 11 символами (включая пробел). Если считать все символы равновероятными (33 буквы + пробел + знаки препинания), энтропия была бы \(\log_2 37 \approx 5.2\) бит на символ. Однако реальная энтропия русского языка ниже из-за неравномерности частот букв (например, «о» встречается чаще «ф») и контекстных зависимостей.

Критика и ограничения

• Энтропия Шеннона не учитывает семантику (смысл) сообщения — два сообщения одинаковой длины могут иметь одинаковую энтропию, но нести разную информацию для человека.
• Для непрерывных распределений дифференциальная энтропия не является абсолютной мерой — она зависит от выбора системы координат.
• В некоторых задачах (например, в квантовой информации) используется квантовая энтропия фон Неймана, обобщающая энтропию Шеннона на квантовые состояния.

Интересные факты

• Клод Шеннон первоначально назвал свою меру «неопределённостью» (uncertainty), но по совету фон Неймана переименовал в «энтропию».
• В 1950-х годах Шеннон провёл эксперимент по оценке энтропии английского языка, предлагая испытуемым угадывать следующие буквы в тексте.
• Энтропия Шеннона лежит в основе понятия «информационная ёмкость» Вселенной, оцениваемой в \(10^{120}\) бит.

Источники

• Клод Шеннон, «Математическая теория связи», 1948.
• Томас М. Ковер, Джой А. Томас, «Элементы теории информации», 2006.
• Джон фон Нейман, «Математические основы квантовой механики», 1932.
• Ральф Хартли, «Передача информации», 1928.