Формула энтропии Шеннона. Помоги моему замешательству

Question

Насколько я понимаю, формула энтропии заключается в том, что она используется для вычисления минимального количества битов, необходимых для представления некоторых данных. Обычно это формулируется иначе, когда определяется, но предыдущее понимание - это то, на что я опирался до сих пор.

Вот моя проблема. Предположим, у меня есть последовательность 100 '1', за которой следует 100 '0' = 200 бит. Алфавит равен {0,1}, основа энтропии равна 2. Вероятность символа «0» равна 0,5, а «1» равна 0,5. Таким образом, энтропия составляет 1 или 1 бит для представления 1 бита.

Однако вы можете кодировать его по длине прогона, например, 100/1/100/0, где это число битов для вывода, за которым следует бит. Кажется, у меня есть представление меньше, чем данные. Особенно, если вы увеличите число до 100.

Я использую: http://en.wikipedia.org/wiki/Information_entropy в качестве эталона на данный момент. Где я неправ? Это вероятность, присвоенная символам? Я не думаю, что это неправильно. Или я неправильно понял связь между сжатием и энтропией? Что-нибудь еще?

Спасибо.

Редактировать

Следуя некоторым из ответов, которые я оставлю после ответа: примените ли вы формулу энтропии к конкретному экземпляру сообщения, чтобы попытаться выяснить его информационное содержание? Будет ли правильно взять сообщение «aaab» и сказать, что энтропия составляет ~ 0,811. Если да, то какова энтропия 1 ... 10 .... 0, где 1 и 0 повторяются n раз, используя формулу энтропии. Ответ 1?

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

Answer 1

Или я неправильно установил связь между сжатием и энтропией?

Вы довольно близки, но этот последний вопрос, где была ошибка. Если вы можете сжимать что-то в форму, которая была меньше его исходного представления, это означает, что исходное представление имело по крайней мере некоторую избыточность. Каждый бит в сообщении действительно не передавал 1 бит информации.

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

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

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

Однако вы можете кодировать его по длине прогона с помощью чего-то вроде 100/1/100/0, где это число битов для вывода, за которым следует бит. Кажется, у меня есть представление меньше, чем данные. Особенно, если вы увеличите число до 100.

Подводя итог, можно сказать, что тот факт, что вы могли бы разработать схему, чтобы кодирование данных было меньше, чем исходные данные , говорит вам о чем-то важном. А именно, он говорит, что ваши исходные данные содержали очень мало информации .

<Ч />

Дальнейшее чтение

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

Answer 2

Взгляните на Колмогорова сложности

Минимальное количество бит, в которое можно сжать строку без потери информации. Это определяется в отношении фиксированной, но универсальной схемы декомпрессии, предоставляемой универсальной машиной Тьюринга.

И в вашем конкретном случае не ограничивайте себя алфавитом {0,1}. Для вашего примера используйте {0 ... 0, 1 ... 1} (сто 0 и сто 1)

Answer 3

Джон Феминелла понял все правильно, но я думаю, что есть еще что сказать.

Энтропия Шеннона основана на вероятности, а вероятность всегда в глазах смотрящего.

Вы сказали, что 1 и 0 одинаково вероятны (0,5). Если это так, то строка 100 1 с, за которой следует 100 0, имеет вероятность 0,5 ^ 200, из которых -log (основание 2), как и ожидалось, составляет 200 бит. Однако энтропия этой строки (в терминах Шеннона) - ее информационное содержание, умноженное на ее вероятность, или 200 * 0,5 ^ 200, все еще очень небольшое число.

Это важно, потому что если вы выполняете кодирование длины серии для сжатия строки, в случае этой строки она получит небольшую длину, но усреднена по всем 2 ^ 200 строкам, это не будет хорошо. Если повезет, оно составит в среднем около 200, но не менее.

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

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

Надеюсь, это поможет, и спасибо за ваш вопрос.

Answer 4

Ваше кодирование работает в этом примере, но возможно представить одинаково действительный регистр: 010101010101 ... который будет закодирован как 1/0/1/1 / ...

Энтропия измеряется по всем возможным сообщениям, которые могут быть построены в данном алфавите, а не только по патологическим примерам!