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

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

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

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

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

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

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

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

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

---

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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