Энтропия: объяснение

В 1948 году инженер Bell Labs Клод Шеннон задался вопросом, который до него никто не формулировал точно: сколько информации содержит сообщение? Его ответом стало число, измеряемое в битах, которое зависит не от смысла сообщения, а от того, насколько оно неожиданно. Это число — энтропия — задаёт пределы для любой программы сжатия, любого сетевого канала и любого устройства хранения и объясняет, почему одни тексты сжимаются до малой доли своего размера, а другие не сжимаются вовсе.

Столбики вероятностей букв, бледнеющие от частых к редким, и кривая энтропии, падающая по мере того, как известно больше контекста
Столбики вероятностей букв, бледнеющие от частых к редким, и кривая энтропии, падающая по мере того, как известно больше контекста

Информация — это неожиданность

Идея Шеннона состояла в том, чтобы измерять информацию тем, насколько сообщение неожиданно, а не тем, что оно означает. Если вы уже знаете ответ, услышав его, вы ничего не узнаёте; если он мог оказаться одним из тысячи вариантов, он сообщает многое. Сообщение, выделяющее одну из двух равновероятных возможностей, несёт один бит. Одна из четырёх требует двух битов, одна из восьми — трёх, а в общем случае одна из N равновероятных возможностей требует log₂ N бит. Поэтому символ, встречающийся с вероятностью p, несёт −log₂ p бит: чем он реже, тем больше сообщает.

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

Энтропия — это средняя информация на символ: H = −Σ p log₂ p, где сумма берётся по всем символам с их вероятностями p. Для честной монеты H равна 1 биту. Для монеты, которая в 90% случаев падает орлом, — всего 0,47 бита, потому что исход обычно не становится неожиданностью. Энтропия максимальна, когда все символы равновероятны, — log₂ n бит для n символов — и равна нулю, когда один символ достоверен. Название Шеннон выбрал по совету Джона фон Неймана, потому что та же формула встречается в физике, где энтропия измеряет беспорядок.

Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.
Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.

Предел сжатия

Теорема Шеннона о кодировании источника гласит, что никакой код без потерь не может в среднем использовать меньше битов на символ, чем энтропия источника, и что коды могут подойти к ней сколь угодно близко. Код Хаффмана, придуманный студентом Дэвидом Хаффманом в 1952 году, даёт частым символам короткие коды, а редким — длинные и отстаёт от энтропии меньше чем на один бит на символ; арифметическое кодирование подходит ещё ближе. Таким образом, энтропия — не просто описание, а жёсткий предел: файл из случайных байтов, с 8 битами энтропии на байт, сжать невозможно.

Дэвид Хаффман, сфотографированный в годы работы профессором Калифорнийского университета в Санта-Крузе. Аспирантом MIT в 1951 году он нашёл свой оптимальный код в курсовой работе для курса Роберта Фано.
Дэвид Хаффман, сфотографированный в годы работы профессором Калифорнийского университета в Санта-Крузе. Аспирантом MIT в 1951 году он нашёл свой оптимальный код в курсовой работе для курса Роберта Фано.

Контекст и избыточность

Буквы в тексте не независимы. В английском после Q идёт U, после точки — заглавная буква, а слово, начинающееся с INFORMA, почти наверняка продолжится как TION. Учёт предыдущих символов даёт условную энтропию, которая ниже энтропии символов, подсчитанных по одному. Разница — это избыточность: та часть сообщения, которую можно было предсказать. Программы сжатия, такие как ZIP, использующий метод deflate, находят повторяющиеся строки и заменяют их короткими ссылками, а современные компрессоры предсказывают каждый символ по его контексту.

Сколько информации в английском языке?

При побуквенном подсчёте с частотами английского языка буква несёт около 4,1 бита против 4,7 для букв, выбранных случайно. В 1951 году Шеннон пошёл дальше: он показывал людям начало текста и просил угадать следующую букву, подсчитывая, сколько попыток им понадобилось. По их ответам он оценил, что английский несёт лишь около 0,6–1,3 бита на букву. Иными словами, примерно три четверти письменного английского — избыточность, и поэтому текст с пропущенными буквами обычно всё равно удаётся прочитать.

Случайность и пароли

Энтропия измеряет и непредсказуемость, от которой зависит безопасность. Ключ или пароль, выбранный равномерно из N возможностей, имеет log₂ N бит энтропии, и атакующему в среднем придётся перебрать примерно половину из них. Случайный пароль из 12 строчных латинских букв (их 26) имеет около 56 бит; у распространённого слова их гораздо меньше, какой бы длины оно ни было. Генераторы случайных чисел проверяют, убеждаясь, что их выход обладает полной энтропией случайного источника, а операционные системы собирают энтропию из временного шума, чтобы их инициализировать.

Где встречается энтропия

Энтропия определяет, сколько битов нужно телефонному звонку, фотографии или видеопотоку и насколько близко модем или соединение Wi-Fi может подойти к пропускной способности своего канала. Биологи с её помощью измеряют информацию в ДНК, где каждое из четырёх оснований может нести не более 2 бит, и разнообразие экосистемы. В машинном обучении деревья решений выбирают вопрос, сильнее всего снижающий энтропию, а функция потерь на основе перекрёстной энтропии используется для обучения большинства нейронных сетей. Лингвисты сравнивают языки по энтропии на символ и на слово.

Попробуйте сами

Откройте калькулятор энтропии, чтобы измерить любой текст по символам, словам или байтам. Сравните абзац со случайными буквами, битами, цифрами и ДНК, посмотрите неожиданность каждого символа, сколько информации содержит текст в сравнении с объёмом хранения и как число битов на символ падает по мере того, как известно больше контекста, — рядом с тем, чего на самом деле достигает ZIP.

Часто задаваемые вопросы

Почему энтропию измеряют в битах?

Потому что Шеннон использовал логарифмы по основанию 2, чтобы один выбор «да или нет» между равными вариантами считался одной единицей. С натуральным логарифмом единицей служит нат, около 1,44 бита, а с основанием 10 — хартли, около 3,32 бита; ими пользуются физики и некоторые статистики.

Может ли энтропия текста быть больше log₂ размера его алфавита?

Нет. При n различных символах энтропия не превышает log₂ n бит на символ и достигает этого значения, только когда все символы встречаются одинаково часто. Любой перекос и любая предсказуемость из контекста её снижают.

Энтропия в теории информации — то же самое, что в физике?

Формулы совпадают по виду: Больцман и Гиббс записали физическую энтропию как сумму по вероятностям микроскопических состояний системы. Смысл тоже родственный — обе измеряют, чего мы не знаем, — а позднее физики показали, что стирание одного бита информации обязательно сопровождается выделением небольшого количества тепла.

Почему повторное сжатие сжатого файла не помогает?

Хороший компрессор удаляет бо́льшую часть избыточности, поэтому его выходные данные близки к случайным, с почти 8 битами энтропии на байт. Удалять больше нечего, и повторное сжатие обычно даже немного увеличивает размер из-за собственных накладных расходов компрессора.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть калькулятор энтропии