Шеннон: вероятность становится информацией

Статья

Клод Элвуд Шеннон (1916–2001), сотрудник Bell Telephone Laboratories в Мюррей-Хилле (Нью-Джерси), публикует в «Bell System Technical Journal» за июль и октябрь 1948 года:

«A Mathematical Theory of Communication»

Восемьдесят страниц, в которых с нуля создана целая дисциплина. В книжном издании 1949 года артикль заменили: «The Mathematical Theory of Communication» — сам Шеннон против этого возражал.

Постановка, которой не было раньше

Инженеры связи обсуждали качество сигнала, полосу, отношение сигнал/шум. Шеннон задал другой вопрос: что именно передаётся?

Его ответ: с инженерной точки зрения смысл сообщения не имеет значения. Значение имеет одно: сообщение выбрано из некоторого множества возможных, и задача приёмника — узнать, какое именно. Информация есть устранённая неопределённость.

А неопределённость — это свойство распределения вероятностей на множестве возможных сообщений. Отсюда всё.

Энтропия

Определение. Для дискретного распределения $p_1,\ldots,p_n$

$$\boxed{\;H(X) = -\sum_{i=1}^{n} p_{i}\log_{2}p_{i}\;}$$

измеряется в битах (термин предложил Тьюки, работавший в тех же Bell Labs).

Почему именно так. Шеннон доказал теорему единственности: если потребовать от меры неопределённости трёх естественных свойств —

1. непрерывность по $p_i$;
2. при равновероятных исходах монотонный рост с числом исходов;
3. аддитивность при разбиении выбора на этапы (неважно, выбираем ли мы сразу из восьми вариантов или трижды из двух),

— то $H$ определена однозначно с точностью до множителя. Логарифм не выбран для удобства, он вынужден третьим требованием.

Простые примеры.

• Честная монета: $H = -2\cdot\tfrac12\log_2\tfrac12 = 1$ бит.
• Монета с $p=0{,}9$: $H = -0{,}9\log_2 0{,}9 - 0{,}1\log_2 0{,}1 \approx 0{,}469$ бита. Меньше — исход предсказуемее.
• Монета с $p=1$: $H=0$. Никакой неопределённости, никакой информации.
• Равномерное распределение на $n$ исходах: $H=\log_2 n$ — максимум при данном $n$.

Последнее — общий факт: энтропия максимальна при равномерном распределении. Доказывается неравенством Йенсена; это и математическое выражение «принципа недостаточного основания» ЛапласаПьер-Симон Лапласфранцузский математик, астроном и физик · 1749–1827Свёл небесную механику в пять томов, а теорию вероятностей — в один, и на полтора столетия задал образ мира, в котором будущее вычисляется из настоящего..

Две теоремы, ради которых всё писалось

Теорема о кодировании источника (первая теорема Шеннона). Сообщения источника с энтропией $H$ бит на символ можно закодировать в среднем $H$ битами на символ — и нельзя короче.

Это точная граница сжатия. Текст на русском языке имеет энтропию порядка 1–1,5 бита на букву (при наивном подсчёте по 33 буквам было бы $\log_2 33 \approx 5$ бит) — отсюда следует, что естественный язык избыточен примерно на 70–80%, и архиваторы этим пользуются. Сам Шеннон оценивал энтропию английского экспериментально, заставляя людей угадывать следующую букву текста.

Практическое воплощение — коды Хаффмана (1952), арифметическое кодирование, и в конечном счёте все форматы сжатия.

Теорема о кодировании канала (вторая теорема Шеннона). Вот результат, который современникам показался невероятным.

У канала с шумом есть пропускная способность

$$C = \max_{p(x)} I(X;Y), \qquad I(X;Y) = H(X)-H(X\mid Y),$$

где $I$ — взаимная информация. Утверждение:

При любой скорости передачи $R < C$ существуют коды, позволяющие передавать со сколь угодно малой вероятностью ошибки. При $R > C$ — не существует.

До Шеннона считалось очевидным, что борьба с шумом требует жертвовать скоростью: хочешь надёжнее — повторяй сообщение, скорость падает к нулю. Шеннон доказал, что это не так: до самой границы $C$ можно передавать почти безошибочно, не теряя скорости.

Для канала с гауссовым шумом:

$$C = W\log_{2}\left(1+\frac{S}{N}\right) \ \text{бит/с},$$

где $W$ — полоса, $S/N$ — отношение мощностей сигнала и шума. Формула Шеннона — Хартли — до сих пор основа проектирования любой системы связи, от модема до 5G.

Доказательство неконструктивно. Шеннон показал существование хороших кодов усреднением по случайно выбранным кодам: если средняя вероятность ошибки по всем случайным кодам мала, то хотя бы один хороший код существует. Он не предъявил ни одного. Поиск конструктивных кодов, достигающих границы, занял полвека и завершился турбокодами (1993) и LDPC-кодами (Галлагер, 1962, переоткрыты в 1990-е).

Заметим приём: вероятностный метод, тот же, что у БореляЭмиль Борельфранцузский математик, министр и участник Сопротивления · 1871–1956Придумал меру, на которой стоит вся современная теория вероятностей, а потом ушёл в политику — был министром флота, депутатом и сидел в тюрьме при Виши. (нормальные числа) и вскоре у ЭрдёшаПал Эрдёшвенгерский математик · 1913–1996Полторы тысячи статей, пятьсот соавторов, ни дома, ни семьи, ни постоянной работы — сорок лет он ездил из университета в университет с одним чемоданом. (следующая точка). Существование доказывается через случайный выбор.

Связь с остальной линией

С Больцманом и Гиббсом. Формула $H=-\sum p\log p$ — с точностью до множителя энтропия статистической физики. Совпадение не случайно: обе величины измеряют «число микросостояний, совместимых с наблюдаемым». Легенда (со слов Шеннона) о том, что название «энтропия» ему посоветовал фон НейманДжон фон Нейманвенгеро-американский математик · 1903–1957Аксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь., добавив, что никто толком не знает, что такое энтропия, и в споре это будет преимуществом, — вероятно, приукрашена, но передаёт суть.

С БайесомТомас Байесанглийский пресвитерианский священник и математик · 1702–1761Решил обратную задачу вероятности — как от наблюдений перейти к вероятности причины. Работу нашли в бумагах покойного и напечатали через два года после смерти; при жизни он не опубликовал по математике ничего… и ТьюрингомАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. (предыдущая точка). Взаимная информация $I(X;Y)$ — это в точности среднее значение веса свидетельства. Дивергенция Кульбака — Лейблера

$$D(p\|q) = \sum_{i} p_{i}\log\frac{p_{i}}{q_{i}}$$

есть математическое ожидание логарифмического отношения правдоподобия. Тьюринговский «бан» и шенноновский «бит» — одна величина в разных основаниях.

С Колмогоровым. КолмогоровАндрей Николаевич Колмогороврусский и советский математик · 1903–1987Дал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы., узнав о теории информации, глубоко ей занялся и в 1965 году предложил альтернативу: колмогоровская сложность — длина кратчайшей программы, порождающей объект. Это определение информации без вероятности вообще, для одного конкретного объекта. Связь двух подходов (сложность случайной строки в среднем равна её энтропии) — одна из красивейших теорем XX века.

Со статистикой. Энтропийные критерии (AIC Акаике, MDL Риссанена), метод максимальной энтропии Джейнса, взаимная информация как мера зависимости — всё это стандартный инструментарий, и всё выросло отсюда.

Человек

Шеннон защитил в 1937 году магистерскую диссертацию, в которой показал, что булева алгебра описывает релейные схемы, — её называют самой значимой магистерской работой XX века и фундаментом цифровой техники. В войну занимался криптографией (секретная работа 1945 года «A Mathematical Theory of Cryptography» содержит доказательство абсолютной стойкости шифра Вернама).

Он же строил механическую мышь, решающую лабиринт, машину для жонглирования, «бесполезную машину» (её единственная функция — выключить саму себя), и вместе с Эдвардом Торпом сделал первый носимый компьютер для игры в рулетку. Ездил по коридорам Bell Labs на одноколёсном велосипеде, жонглируя.