Формула Шеннона

Учимся измерять информацию через вероятность события, а не только через число равновозможных вариантов.

Количество информации в сообщении о наступившем событии с вероятностью $p$ равно $i=-\log_2 p$ бит: чем менее вероятно событие, тем больше информации несёт сообщение о нём.

До этого раздела мы измеряли информацию через формулу Хартли $i=\log_2 N$, где $N$ — число равновозможных исходов. Но в жизни исходы редко равновероятны. Сообщение «завтра в Сахаре пойдёт снег» удивляет нас гораздо сильнее, чем «завтра в Сахаре будет солнечно», — и интуитивно несёт больше информации. Вероятностный подход Клода Шеннона как раз и формализует эту интуицию: информация тем больше, чем неожиданнее событие.

Зачем это нужно

Подход Хартли отвечает на вопрос «сколько вариантов было?», а подход Шеннона — на вопрос «насколько неожиданным оказался конкретный исход?». Это нужно, чтобы честно мерить информацию там, где буквы, символы или события встречаются с разной частотой: в естественном языке буква «о» встречается куда чаще буквы «ф», и сообщение о появлении редкой буквы информативнее. На этой идее построены алгоритмы сжатия (архиваторы), оценка пропускной способности каналов и многие задачи ЕГЭ.

От Хартли к Шеннону

Возьмём кубик. Исходов $N=6$, все равновероятны, $p=\tfrac{1}{6}$. По Хартли информация одного броска:

$$ i = \log_2 6 \approx 2{,}585 \ \text{бит} $$

А теперь посчитаем то же самое через вероятность. Подставим $p=\tfrac{1}{6}$ в формулу Шеннона:

$$ i = -\log_2 \frac{1}{6} = \log_2 6 \approx 2{,}585 \ \text{бит} $$

Результат совпал! Это не случайность: при равновероятных исходах $p=\tfrac{1}{N}$, и формула Шеннона превращается в формулу Хартли:

$$ i = -\log_2 \frac{1}{N} = \log_2 N $$

Значит, формула Хартли — это частный случай формулы Шеннона для равновероятных событий. Шеннон просто шире: он работает и тогда, когда вероятности разные.

Почему именно логарифм

Логарифм выбран не случайно — он делает информацию аддитивной. Если два независимых события имеют вероятности $p_1$ и $p_2$, то вероятность их совместного наступления равна $p_1\cdot p_2$, а информация должна складываться. Логарифм как раз превращает произведение в сумму:

$$ -\log_2(p_1\cdot p_2) = -\log_2 p_1 + (-\log_2 p_2) = i_1 + i_2 $$

Поэтому информация двух бросков монеты — это $1+1=2$ бита, как и подсказывает здравый смысл.

Расчёты в битах

Разберём конкретные числа. Пусть прогноз погоды сообщает один из исходов с такими вероятностями: солнечно $p=0{,}5$, облачно $p=0{,}25$, дождь $p=0{,}125$, гроза $p=0{,}125$. Сколько информации несёт каждое сообщение?

Видно главное: редкие события (дождь, гроза) несут по 3 бита, а самое частое (солнечно) — всего 1 бит. Сообщение «сегодня солнечно» почти не удивляет, поэтому информации в нём мало.

Проверим расчёты на Python. Стандартного модуля math достаточно: функция math.log2(x) считает логарифм по основанию 2.

import math

prob = {"солнечно": 0.5, "облачно": 0.25, "дождь": 0.125, "гроза": 0.125}

for event, p in prob.items():
    i = -math.log2(p)
    print(f"{event}: p={p}, i={i:.3f} бит")

Вывод:

солнечно: p=0.5, i=1.000 бит
облачно: p=0.25, i=2.000 бит
дождь: p=0.125, i=3.000 бит
гроза: p=0.125, i=3.000 бит

Обратная задача: из информации в вероятность

Иногда в условии дают количество информации и просят найти вероятность. Формулу легко обратить. Из $i=-\log_2 p$ следует:

$$ p = 2^{-i} $$

Например, если сообщение о вынутом из урны шаре несёт $i=4$ бита, то вероятность достать такой шар равна $p=2^{-4}=\tfrac{1}{16}=0{,}0625$. А если в урне шары только одного цвета, то событие достоверно, $p=1$, и информации в сообщении $i=-\log_2 1 = 0$ бит — мы и так знали ответ заранее.

Как это работает

Под капотом формула опирается на простую модель: источник выдаёт сообщения, и у каждого есть своя вероятность. Величину $i=-\log_2 p$ называют собственной информацией (или «неожиданностью») события. Чем меньше $p$, тем больше $-\log_2 p$, потому что логарифм дроби меньше единицы отрицателен, а минус перед ним делает результат положительным. На границах: при $p\to 1$ информация стремится к нулю (ожидаемое событие неинформативно), а при $p\to 0$ информация неограниченно растёт (почти невозможное событие, если оно всё-таки случилось, несёт огромную информацию).

Эта же логика стоит за сжатием данных. Архиватор кодирует частые символы короткими цепочками битов, а редкие — длинными, стараясь, чтобы длина кода символа была близка к его собственной информации $-\log_2 p$. Так общий размер файла уменьшается.

Частые ошибки

• Путать $-\log_2 p$ и $\log_2 p$. Вероятность всегда $\le 1$, поэтому $\log_2 p \le 0$. Информация не бывает отрицательной — минус в формуле обязателен.
• Использовать формулу Хартли $i=\log_2 N$, когда исходы НЕравновероятны. Хартли годится только для равновозможных вариантов.
• Брать логарифм по основанию 10 или натуральный. Для измерения информации в битах основание строго 2.
• Забывать, что у достоверного события ($p=1$) информация равна нулю, а не «бесконечности».
• Складывать вероятности независимых событий вместо умножения. Складывается именно информация, перемножаются вероятности.

Итоги

• Количество информации о событии с вероятностью $p$: $i=-\log_2 p$ бит.
• Чем реже событие, тем больше информации несёт сообщение о нём; у достоверного события информация равна нулю.
• При равновероятных исходах $p=\tfrac{1}{N}$ формула Шеннона совпадает с формулой Хартли $i=\log_2 N$.
• Обратная формула: $p=2^{-i}$.
• Логарифм делает информацию аддитивной: для независимых событий $i_1+i_2$.