morfizm (morfizm) wrote,
morfizm
morfizm

Category:

Ликбез об информационной энтропии

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

Мой собеседник привёл вот такое определение:

ИНФОРМАЦИЯ
(informatio — ознакомление, представление — лат.)
1) любые сведения, данные, сообщения, передаваемые посредством сигналов;
2) уменьшение неопределенности в результате передачи сведений, данных, сообщений — в этом качестве И. противопоставляется энтропии.


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

Определение верное, но раз оно приводит к противоположному понимаю смысла по недоразумению, оно весьма неудачное.
Интересно, кто автор словаря?

В википедии есть страничка про энтропию, а также есть страничка получше, хоть и не идеальна, в частности, про информационную энтропию.

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

Например, если мы возмём миллион десятичных знаков числа "пи" и сохраним в текстовый файл, его размер будет 1 мегабайт (точнее, 10^6 байт). Если вам даётся такой файл и вы рассматриваете модель, в которой все байты равновероятны (каждый может принимать любое доступное значение, 0-255), то количество информации этого файла будет именно 1 мегабайт, и энтропия каждого байта равна 1.0 (1 байт информации на 1 байт файла).

Если вы возьмёте модель, в которой допустимы только печатные ASCII символы, коих 95 из 256 (32-126). Получается, что полезной информации в каждом байте всего 6.5 бит из 8 (log2(95) ~= 6.5699), соответственно, средняя энтропия 0.82.

Если вы возмьёте модель, в которой разные буквы могут иметь разную частоту и эта частота заранее известна, то мы получим, что цифры встречаются примерно равновероятно, а все остальные символы не встречаются вовсе. Итого, имеем 10 равновероятных исходов из 256, полезной информации в каждом байте всего 3.3 бита из 8 (log2(10) ~= 3.32193), соответственно, средняя энтропия 0.415241. Именно это определение энтропии даётся как опорное в вышеупомянутой статье, но, мне кажется, повседневный смысл этого слова шире. Понятно, что данном случае мы разделили сообщение на "буквы", коими являются отдельные цифры. В случае текста, можно использовать буквы и смотреть на их частоты, а можно слова. Можно словосочетания (там в вики упоминается условная энтропия).

Кстати, если мы заархивируем этот текстовый файл с миллионом знаков числа пи, мы получим файл, чуть большего размера, чем 415241 - что будет близко к этому определению энтропии, просто потому что цифры числа пи действительно независимы и равновероятны, выжать больше, чем 0.415 обычный архиватор не может. Я только что заархивировал RAR-ом и получилось 477529, что ожидаемо, но могло быить и лучше. 7zip даёт 444343. Но мы знаем, что меньше, чем 415241 никто не даст.

Теперь рассмотрим модель, в которой известно, что нам дают не произвольный файл, а десятичную запись какой-нибудь известной математической константы, и ничего другого там точно не будет. Грубо говоря весь файл можно заменить на 23-буквенное сообщение "1000000 знаков числа пи". Мы получили сумасшедшее сжатие, и, по сути, усреднённая энтропия каждой буквы исходного текста это 23/1000000 = 0.000023. В этой модели можно закодировать ещё короче. Сколько там тех констант? Ну, допустим, 1000. Это влезает в 10 бит, пусть даже округлим к 2 байтам и позволим до 65536 разных констант. Сколько десятичных знаков влезет в файл? Ну, никак не больше 8-байтового числа (современные операционные системы не поддерживают файлы большего размера, да и железок таких нет, чтобы такой огромный файл влез). 2 байта на выбор константы плюс 8 байт на количество цифр, получаем 10 байт, ещё в 2.3 раза меньше, чем даже та строка.

Информация, о которой в вашем определении говорится, это *другая информация*, это не информация, которая объект измерения в рамках модели, а это информация о вероятностях букв и других свойствах исходного сообщения, которая позволяет вам предпочесть одну модель другой. Сказав мне о том, что в файле только цифры, вы, безусловно, этим сообщением передали мне информацию(1), которая уменьшила информацию(2), содержащуюся в файле (и, как следствие, уменьшили энтропию файла), потому что теперь я могу измерить энтропию по-новому, с учётом этой информации(1), и получу энтропию 0.42 вместо 1.0. Так вот, информация(1) и информация(2) это разные вещи. Информация(1) это ваше сообщение, в результате которого я по-новому, в другой модели смотрю на содержимое своего файла, а информация(2) это информация, содержащаяся в файле, определяемая в рамках этой модели.
Tags: 1, math, software development
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments