?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

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


Oct. 12th, 2013 01:35 am Ликбез об информационной энтропии

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

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

ИНФОРМАЦИЯ
(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) это информация, содержащаяся в файле, определяемая в рамках этой модели.

22 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:archaicos
Date:October 12th, 2013 09:05 am (UTC)
(Link)
Приём и передача информации увеличивают энтропию (не в той информации, если мы говорим о безошибочном процессе). :)

А ещё в интернете много информации. И это великая помойка! :)
From:morfizm
Date:October 12th, 2013 09:27 am (UTC)
(Link)
Ну давай уж быть немного точнее: ведь не увеличивают, а всего лишь "не уменьшают" :)
From:archaicos
Date:October 12th, 2013 09:39 am (UTC)
(Link)
Лампы, транзисторы, резисторы, провода и т.д. греются, всё рассеивает энергию в пространство в виде излучения.
From:eternele
Date:October 12th, 2013 10:42 am (UTC)
(Link)
за пять лет изучения физики никто так и не смог мне внятно объяснить, что такое энтропия
From:morfizm
Date:October 12th, 2013 11:37 am (UTC)
(Link)
У энтропии есть идея (зачем она? что она измеряет?) и есть множество разных "реализаций" - разных определений для разных ситуаций. Наверное, это может сбивать с толку. В физике чаще всего концепции однозначные, немного разные вещи описываются разными словами.
From:eternele
Date:October 12th, 2013 04:11 pm (UTC)
(Link)
что она измеряет?
From:dennyrolling
Date:October 12th, 2013 05:06 pm (UTC)
(Link)
количество энтропии конечно же.

это как вопрос "что изменяет электрический заряд"? природа так устроена что в сложных системах проявляется такая мера как энтропия, и ее полезно использовать в ряде задач.
From:morfizm
Date:October 12th, 2013 07:32 pm (UTC)
(Link)
Ну Денни правильно сказал, это такая мера, физический смысл которой совсем не обязательно легко объяснить, но которая полезна для задач.

В википедии очень хорошо показан практичный аспект, формула энтропии не "дана свыше", а выбрана, чтобы подогнаться под нужды:

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

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

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

Энтропия английского текста это сколько бит надо в среднем на букву, чтобы зашифровать английский текст, исходя из известных статистических свойств языка (допустим, для простоты, что мы смотрим только на частотный ряд). Если мы возьмём конкретный текст вроде "SANTA EATS" (слова составлены из наиболее частых букв), то количество информации в нём (измеренное в битах) будет намного меньше, чем количество информации в "FUCK XEROX" (буквы "K", "U", "X" довольно редки). Энтропия подобных сообщений - одинаковая величина, измеренная в модели, в которой мы можем посмотреть на все возможные слова, и посчитать вероятностью каждой буквы. В этой же модели мы можем измерять количество информации в конкретных сообщениях. Например, в какой-то другой модели, не основанной тривиальным образом на частотном ряду английского текста, может быть, "FUCK XEROX" будет нести куда меньше информации, чем "SANTA EATS". Но в модели, основанной на частотном ряду, будет нести больше.
From:eternele
Date:October 12th, 2013 07:38 pm (UTC)
(Link)
у меня была трехмесячная стажировка, связанная с теорией информации
From:morfizm
Date:October 12th, 2013 10:41 pm (UTC)
(Link)
Я не очень понимаю, какое это имеет отношение к обсуждаемому вопросу.
From:eternele
Date:October 13th, 2013 07:13 am (UTC)
(Link)
Эм. "Определения" я знаю наизусть, что никак не приближает к пониманию энтропии. Мои руководители мне сказали "по секрету", что никто не понимает, что это, но оно работает.
From:morfizm
Date:October 13th, 2013 08:22 am (UTC)
(Link)
Понятно, ну, да, мне сложно не согласиться, т.к. даже в моём посте всё не очень последовательно. Т.е. я интуитивно понимаю, что по изначальной ссылке на ветку комментов с chura24 была ошибка (правильно, что низкая энтропия текстов ~= мало полезной информации, а не "много", не смотря на то, что в некотором другом смысле информация противопоставляется энтропии), но я не чувствую, что смог бы провести абсолютно строгие рассуждения со всеми точными определениями.

Может, проблема в том, что понятие информации плохо определено. Если информацию определить через изменение энтропии, а энтропию дать строгой формулой, то как бы теряется "физический смысл" энтропии (т.е. как бы понятно, что это мера хаоса, но что такое хаос?) - информация всё-таки бытовое понятное слово, а энтропия строго научное. Если же сказать, что энтропия это мера информации, то возникает цикл в определниях - так нельзя.

В общем, тут где-то на интуитивном уровне всё хорошо ясно, в конкретных моделях и с конкретными формулами тоже всё ясно (определнения становятся точными), а сформулировать строго, но в общем виде, не получается.


Edited at 2013-10-13 08:23 am (UTC)
From:eternele
Date:October 13th, 2013 08:35 am (UTC)
(Link)
Exactly.

Мы знаем, что энтропия Шаннона постоянной дискретной величины равна нулю, а случайных равновозможных величин - максимальна, но как это объясняет, что энтропия сигналов мозга крыс увеличивается или уменьшается?... Во время защиты стажировки я всячески пыталась замаскировать факт отсутствия понимания абсолютного смысла энтропии и подчеркнуть факт наличия её изменения при разных опытных условиях. А для расчёта главной величины: "entropy transfert" вообще понимание не нужно, важно лишь, что энтропия рассчитывается через вероятность, что говорит нам, повышается ли вероятность предсказания одного сигнала, если мы знаем другой.
From:morfizm
Date:October 13th, 2013 08:27 am (UTC)
(Link)
Ну и ещё тот факт, что как понятие энтропия, так и информация, строго завязаны на выбор моделей, тот факт, что этих моделей много, и тот факт, что информация может позволить нам использовать одни модели, а не другие, измерить в них энтропию, и потом сравнивать числа, полученные в разных моделях и строить какие-то суждения на основе этого сравнения, это всё значительно усложняет дело.

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

Здесь же имеем много моделей, одна не является частным случаем другой, и имеем разные измерения в разных моделях. Упс. Сразу сложно :)
From:eternele
Date:October 13th, 2013 08:37 am (UTC)
(Link)
Как замечательно, что вы сами поняли, что я хотела сказать =))))
From:rezkiy
Date:October 15th, 2013 05:11 am (UTC)
(Link)
>> меньше, чем 415241 никто не даст.

кажется, кому-то надо почитать про колмогоровскую сложность.
From:dennyrolling
Date:October 15th, 2013 05:55 am (UTC)
(Link)
ну что ты сразу спойлишь-то!
From:morfizm
Date:October 15th, 2013 05:59 am (UTC)
(Link)
Ну ты же не думаешь, что general purpose архиваторы будут распознавать как special cases вещи вроде десятичной записи числа пи?

From:rezkiy
Date:October 15th, 2013 06:20 am (UTC)
(Link)
Архиваторы не могут, а криптоаналитики -- еще как могут.
From:morfizm
Date:October 15th, 2013 06:56 am (UTC)
(Link)
Ну ты же понимаешь, что если где-то убавить, то где-то прибавится :) Придётся дополнительной строкой "двоичный файл" префиксовать то, с чем несмогли разобраться.

Я, например, могу сжать первые миллион знаков числа Пи в 1 бит: 1.
(А всё, что не миллион знаков числа Пи, сжимать в 0, после которого следует обычный архив).

И что я этим кому доказал? :)
From:rezkiy
Date:October 15th, 2013 07:00 am (UTC)
(Link)
>> если где-то убавить, то где-то прибавится

я все-таки повторю свою первоначальную рекомендацию.
From:morfizm
Date:October 15th, 2013 07:30 am (UTC)
(Link)
Ну ладно, почитал.