Меню Рубрики

Что означает энтропия с точки зрения информации

Информация и энтропия

Обсуждая понятие информация, невозможно не затронуть другое смежное понятие – энтропия[1]. Впервые понятия энтропия и информация связал К.Шеннон.

Клод Элвуд Шеннон (Claude Elwood Shannon), 1916-2001 — дальний родственник Томаса Эдисона, американский инженер и математик, был сотрудником Bell Laboratories с 1941 дo 1972 г. В его работе «Математическая теория связи» (http://cm.bell-labs.com/cm/ms/what/shannonday/), опубликованной в 1948 г., впервые определялась мера информационного содержания любого сообщения и понятие кванта информации — бита. Эти идеи легли в основу теории современной цифровой связи. Другая работа Шеннона «Communication Theory of Secrecy Systems», опубликованная в 1949 г., способствовала превращению криптографии в научную дисциплину. Он является основателем теории информации, нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления — науки, объединяемые понятием «кибернетика».

Физическое определение энтропии

Впервые понятие энтропии ввел Клаузиус в 1865 г. как функцию термодинамического состояния системы

где Q – теплота, T — температура.

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

Л.Больцман (1872г.) методами статистической физики вывел теоретическое выражение энтропии

где К – константа; W – термодинамическая вероятность (количество перестановок молекул идеального газа, не влияющее на макросостояние системы).

Энтропия Больцмана выведена для идеального газа и трактуется как мера беспорядка, мера хаоса системы. Для идеального газа энтропии Больцмана и Клаузиуса тождественны. Формула Больцмана стала настолько знаменитой, что начертана в качестве эпитафии на его могиле. Сложилось мнение, что энтропия и хаос есть одно и то же. Несмотря на то, что энтропия описывает только идеальные газы, ее некритично стали привлекать для описания более сложных объектов.

Сам Больцман в 1886г. попытался с помощью энтропии объяснить, что такое жизнь. По мнению Больцмана, жизнь это явление, способное уменьшать свою энтропию. Согласно Больцману и его последователям, все процессы во Вселенной изменяются в направлении хаоса. Вселенная идет к тепловой смерти. Этот мрачный прогноз долго господствовал в науке. Однако углубление знаний об окружающем Мире постепенно расшатали эту догму.

Классики не связывали энтропию с информацией.

Энтропия как мера информации

Заметим, что понятие «информация» часто трактуется как «сведения», а передача информации осуществляется с помощью связи. К. Шеннон рассматривал энтропию как меру полезной информации в процессах передачи сигналов по проводам.

Для расчета энтропии Шеннон предложил уравнение, напоминающее классическое выражение энтропии, найденное Больцманом. Рассматривается независимое случайное событие x с N возможными состояниями и pi—вероятность i-го состояния. Тогда энтропия события x

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

называется частной энтропией, характеризующей только i-e состояние.

Поясним на примерах. При бросании монеты выпадает орел или решка[2], это определенная информация о результатах бросания.

Для монеты число равновероятных возможностей N = 2. Вероятность выпадения орла (решки) равна 1/2.

1

При бросании кости получаем информацию о выпадении определенного количества очков (например, трех). В каком случае мы получаем больше информации?

Для кости число равновероятных возможностей N = 6. Вероятность выпадения трех очков кости равна 1/6. Энтропия равна 2.58. Реализация менее вероятного события дает больше информации. Чем больше неопределенность до получения сообщения о событии (бросание монеты, кости), тем большее количество информации поступает при получении сообщения.

Такой подход к количественному выражению информации далеко не универсален, т. к. принятые единицы не учитывают таких важных свойств информации, как ее ценность и смысл. Абстрагирование от конкретных свойств информации (смысл, ценность ее) о реальных объектах, как в дальнейшем выяснилось, позволило выявить общие закономерности информации. Предложенные Шенноном для измерения количества информации единицы (биты) пригодны для оценки любых сообщений (рождение сына, результаты спортивного матча и т. д.). В дальнейшем делались попытки найти такие меры количества информации, которые учитывали бы ее ценность и смысл. Однако тут же терялась универсальность: для разных процессов различны критерии ценности и смысла. Кроме того, определения смысла и ценности информации субъективны, а предложенная Шенноном мера информации объективна. Например, запах несет огромное количество информации для животного, но неуловим для человека. Ухо человека не воспринимает ультразвуковые сигналы, но они несут много сведений для дельфина и т. д. Поэтому предложенная Шенноном мера информации пригодна для исследования всех видов информационных процессов, независимо от «вкусов» потребителя информации.

Измерение информации

Из курса физики вы знаете, что прежде, чем измерять значение какой-либо физической величины, надо ввести единицу измерения. У информации тоже есть такая единица — бит, но смысл ее различен при разных подходах к определению понятия “информация”.

Существует несколько разных подходов к проблеме измерения информации.

источник

Основоположенник теории информации Клод Шеннон определил информацию, как снятую неопределенность. Точнее сказать, получение информации — необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности – уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.

Представьте, что вы зашли в магазин и попросили продать вам жевательную резинку. Продавщица, у которой, скажем, 16 сортов жевательной резинки, находится в состоянии неопределенности. Она не может выполнить вашу просьбу без получения дополнительной информации. Если вы уточнили, скажем, — «Orbit», и из 16 первоначальных вариантов продавщица рассматривает теперь только 8, вы уменьшили ее неопределенность в два раза (забегая вперед, скажем, что уменьшение неопределенности вдвое соответствует получению 1 бита информации). Если вы, не мудрствуя лукаво, просто указали пальцем на витрине, — «вот эту!», то неопределенность была снята полностью. Опять же, забегая вперед, скажем, что этим жестом в данном примере вы сообщили продавщице 4 бита информации.

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

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

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия.

Энтропия (H)мера неопределенности, выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.

Рис. 8. Поведение энтропии для случая двух альтернатив.

На рисунке 8. показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (p, (1-p)).

Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны ½, нулевое значение энтропии соответствует случаям (p=0, p1=1) и (p=1, p1=0).

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I – это количество информации, которое требуется для снятия неопределенности H. По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия).

Рис. 9. Связь между энтропией и количеством информации.

Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H.

При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. Ht + It = H.

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

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

В общем случае, энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P:

0, p1, …pN-1>, т.е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье «Математическая теория связи».

В частном случае, когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов, т.е. H=F(N). В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. не 20 лет раньше.

Формула Шеннона имеет следующий вид:

(1)

Знак минус в формуле (1) не означает, что энтропия – отрицательная величина. Объясняется это тем, что pi£1 по определению, а логарифм числа меньшего единицы — величина отрицательная. По свойству логарифма , поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

интерпретируется как частное количество информации , получаемое в случае реализации i-ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины 0, I1, … IN-1>.

Приведем пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ¾ — женщины, ¼ — мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.

pi 1/pi Ii=log2(1/pi), бит pi*log2(1/pi), бит
Ж 3/4 4/3 log2(4/3)=0,42 3/4 * 0,42=0,31
М 1/4 4/1 log2(4)=2 1/4 * 2=0,5
å 1 H=0,81 бит

Если же априори известно, что мужчин и женщин в учреждении поровну (два равновероятных варианта), то при расчете по той же формуле мы должны получить неопределенность в 1 бит. Проверка этого предположения проведена в таблице 2.

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

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

Формула Хартли

Мы уже упоминали, что формула Хартли – частный случай формулы Шеннона для равновероятных альтернатив.

Подставив в формулу (1) вместо pi его (в равновероятном случае не зависящее от i)значение , получим:

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

(2)

Из нее явно следует, что чем больше количество альтернатив (N), тем больше неопределенность (H). Эти величины связаны в формуле (2) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации – битам.

Заметьте, что энтропия будет являться целым числом лишь в том случае, если N является степенью числа 2, т.е. если N принадлежит ряду:

Рис. 10. Зависимось энтропии от количества равновероятных вариантов выбора (равнозначных альтернатив).

Напомним, что такое логарифм.

Рис. 11. Нахождение логарифма b по основанию a — это нахождение степени, в которую нужно возвести a, чтобы получить b.

Логарифм по основанию 2 называется двоичным:

Логарифм по основанию 10 –называется десятичным:

Основные свойства логарифма:

1. log(1)=0, т.к. любое число в нулевой степени дает 1;

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

(3)

Например, если известно, что в результате определения того, что интересующий нас Коля Иванов живет на втором этаже, было получено 3 бита информации, то количество этажей в доме можно определить по формуле (3), как N=2 3 =8 этажей.

Если же вопрос стоит так: “в доме 8 этажей, какое количество информации мы получили, узнав, что интересующий нас Коля Иванов живет на втором этаже?”, нужно воспользоваться формулой (2): I=log2(8)=3 бита.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9454 — | 7442 — или читать все.

195.133.146.119 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

источник

2. Что измерил Клод Шеннон?

3. Пределы эволюционной изменчивости информационных систем.

4. Ограниченность адаптации биологических видов.

5. Этапы развития теории энтропии.

6. Методы исчисления количества структурной информации и информационной энтропии текстов.

7. Информационно-энтропийные соотношения процессов адаптации и развития.

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

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

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

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

Используя метафору, можно сказать, что до введения в науку единой информационной количественной меры представленный в естественно-научных понятиях мир как бы «опирался на двух китов»: энергию и вещество. «Третьим китом» оказалась теперь информация, участвующая во всех протекающих в мире процессах, начиная от микрочастиц, атомов и молекул и кончая функциониро­ванием сложнейших биологических и социальных систем.

Естественно, возникает вопрос: подтверждают или опровергают эволюционную парадигму происхождения жизни и биологических видов новейшие данные современной науки?

Для ответа на этот вопрос необходимо прежде всего уяснить, какие именно свойства и стороны многогранного понятия «ин­формация» отражает та количественная мера, которую ввел в науку К.Шеннон.

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

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

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

В основу теории информации положен предложенный К.Шенноном метод исчислений количества новой (непредска­зуемой) и избыточной (предсказуемой) информации, содержащейся в сообщениях, передаваемых по каналам техничес­кой связи.

Предложенный Шенноном метод измерения количества ин­формации оказался настолько универсальным, что его применение не ограничивается теперь узкими рамками чисто технических приложений.

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

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

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

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

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

Еще один важный вывод заключается в том, что

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

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

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

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

Сам того не подозревая, Шеннон вооружил науку универсальной мерой, пригодной в принципе (при условии выявления значенй всех вероятностей) для оценки степени упорядоченности всех существующих в мире систем.

Опредеделив введенную Шеноном информационную меру как меру упорядоченности движения , можно установить взаимосвязь информации и энергии, считая энергию мерой интенсивности движения . При этом ко­личество сохраняемой в структуре систем информации пропорционально суммарной энергии внутренних связей этих систем.

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

Так, например, все физические объекты, в отличие от биологических, не обладают специальными органами памяти, пере­кодировки поступающих из внешнего мира сигналов, информаци­онными каналами связи. Хранимая в них информация как бы «размазана» по всей их структуре. Вместе с тем, если бы кристаллы не способны были сохранять информацию в определяющих их упо­рядоченность внутренних связях, не было бы возможности создавать искусственную память и предназначенные для обработки информации технические устройства на основе кристаллических структур.

Читайте также:  Точки зрения а также ее дальнейшего

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

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

источник

Энтропи́я (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Так, возьмём, например, последовательность символов, составляющих какое-либо предложение на русском языке. Каждый символ появляется с разной частотой, следовательно, неопределённость появления для некоторых символов больше, чем для других. Если же учесть, что некоторые сочетания символов встречаются очень редко, то неопределённость ещё более уменьшается (в этом случае говорят об энтропии n-ого порядка, см. Условная энтропия).

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

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n) рассчитывается по формуле:

Эта величина также называется средней энтропией сообщения. Величина $ \log_2 $ называется частной энтропией, характеризующей только i-e состояние.

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

Шеннон вывел это определение энтропии из следующих предположений:

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

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме:

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (H = − p1 log2p1 − … − pn log2pn), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д. См. Цепи Маркова.

$ H_b(\mathcal) = — \sum_^n p_i \log_b p_i $

Определение энтропии Шеннона очень связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (т.е. вероятности двухбуквенных сочетаний):

$ H_1(\mathcal) = — \sum_i p_i \sum_j \ p_i (j) \log_2 p_i (j) $

где $ \displaystyle i $ — это состояние, зависящее от предшествующего символа, и $ \displaystyle p_i(j) $ — это вероятность $ \displaystyle j $ , при условии, что $ \displaystyle i $ был предыдущим символом.

Так, для русского алфавита без буквы «ё» $ H_0=5,\ H_1=4,358,\ H_2=3,52,\ H_3=3,01 $ [1]

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются т.н. канальные матрицы. Так, для описания потерь со стороны источника (т.е. известен посланный сигнал), рассматривают условную вероятность $ \displaystyle p(b_j|a_i) $ получения приёмником символа $ \displaystyle b_j $ при условии, что был отправлен символ $ \displaystyle a_i $ . При этом канальная матрица имеет следующий вид:

$ \displaystyle b_1 $ $ \displaystyle b_2 $ . $ \displaystyle b_j $ . $ \displaystyle b_m $
$ \displaystyle a_1 $ $ \displaystyle p(b_1|a_1) $ $ \displaystyle p(b_2|a_1) $ . $ \displaystyle p(b_j|a_i) $ . $ \displaystyle p(b_m|a_1) $
$ \displaystyle a_2 $ $ \displaystyle p(b_1|a_2) $ $ \displaystyle p(b_2|a_2) $ . $ \displaystyle p(b_j|a_2) $ . $ \displaystyle p(b_m|a_2) $
. . . . . . .
$ \displaystyle a_i $ $ \displaystyle p(b_1|a_i) $ $ \displaystyle p(b_2|a_i) $ . $ \displaystyle p(b_j|a_i) $ . $ \displaystyle p(b_m|a_i) $
. . . . . . .
$ \displaystyle a_m $ $ \displaystyle p(b_1|a_m) $ $ \displaystyle p(b_2|a_m) $ . $ \displaystyle p(b_j|a_m) $ . $ \displaystyle p(b_m|a_m) $

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а сумма всех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника — $ \displaystyle p(b_j) $ . Потери, приходящиеся на предаваемый сигнал $ \displaystyle a_i $ , описываются через частную условную энтропию:

$ H(B|a_i)=-\sum_^m p(b_j|a_i)\log_2 p(b_j|a_i) $

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

$ \displaystyle H(B|A)=\sum_i p(a_i)H(B|a_i) $

$ \displaystyle H(B|A) $ означает энтропию со стороны источника, аналогично рассматривается $ \displaystyle H(A|B) $ — энтропия со стороны приёмника: вместо $ \displaystyle p(b_j|a_i) $ всюду указывается $ \displaystyle p(a_i|b_j) $ (суммируя элементы строки можно получить $ \displaystyle p(a_i) $ , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, т.е. вероятность правильной передачи).

Взаимная энтропия, или энтропия объединения, предназначена для рассчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается $ \displaystyle H(AB) $ , где $ \displaystyle A $ , как всегда, характеризует передатчик, а $ \displaystyle B $ — приёмник.

Взаимосязь переданных и полученных сигналов описывается вероятностями совместных событий $ \displaystyle p(a_i b_j) $ , и для полного описания характеристик канала требуется только одна матрица:

$ \displaystyle p(a_1 b_1) $ $ \displaystyle p(a_1 b_2) $ $ \displaystyle p(a_i b_j) $ $ \displaystyle p(a_1 b_m) $
$ \displaystyle p(a_2 b_1) $ $ \displaystyle p(a_2 b_2) $ $ \displaystyle p(a_2 b_j) $ $ \displaystyle p(a_2 b_m) $
$ \displaystyle p(a_i b_1) $ $ \displaystyle p(a_i b_2) $ $ \displaystyle p(a_i b_j) $ $ \displaystyle p(a_i b_m) $
$ \displaystyle p(a_m b_1) $ $ \displaystyle p(a_m b_2) $ $ \displaystyle p(a_m b_j) $ $ \displaystyle p(a_m b_m) $

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером $ \displaystyle j $ даст $ \displaystyle p(b_j) $ , сумма строки с номером $ \displaystyle i $ есть $ \displaystyle p(a_i) $ , а сумма всех элементов матрицы равна 1. Совместная вероятность $ \displaystyle p(a_ib_j) $ событий $ \displaystyle a_i $ и $ \displaystyle b_j $ вычисляется как произведение исходной и условной вероятности,

Условные вероятности производятся по формуле Байеса. Таким образом имеются все данные для вычисления энтропий источника и приёмника:

$ H(A)=-\sum_i \left( \sum_j p(a_i b_j) \log \sum_j p(a_i b_j) \right) $ $ H(B)=-\sum_j \left( \sum_i p(a_i b_j) \log \sum_i p(a_i b_j) \right) $

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

$ \displaystyle H(AB)=-\sum_i \sum_j p(a_i b_j) \log p(a_i b_j) $

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов — отправленного и полученного. Путём несложных преобразований также получаем

$ \displaystyle H(AB)= H(A)+H(B|A) = H(B)+H(A|B). $

Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины.

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию $ -2(0,5\log_2 0,5)=1 $ бита на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: $ -\sum_^\infty \log_2 1 = 0 $ . Так, к примеру, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет пунктам 1)—3):

1) H(p1, …, pn) определена и непрерывна для всех p1, …, pn, где pi $ \in $ [0,1] для всех i = 1, …, n и p1 + … + pn = 1. (Заметьте, что эта функция зависит только от распределения вероятностей, а не от алфавита.)

2) Для целых положительных n, должно выполняться следующее неравенство:

3) Для целых положительных bi, где b1 + … + bn = n, должно выполняться равенство:

$ H\left(\frac, \ldots, \frac\right) = H\left(\frac, \ldots, \frac\right) + \sum_^k \fracH\left(\frac, \ldots, \frac\right). $

Исходный алфавит, встречающийся на практике, имеет вероятностное распределение, которое далеко от оптимального. Если исходный алфавит имел n символов, тогда он может может быть сравнён с «оптимизированным алфавитом», вероятностное распределение которого однородно. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах.

Читайте также:  Точки зрения базарова и павла петровича таблица

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

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля-Зива или арифметического кодирования.

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

Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

  1. ↑ Д.С. Лебедев, В.А. Гармаш. О возможности увеличения скорости передачи телеграфных сообщений. — М.:Электросвязь, 1958, №1. с.68-69

2.Цымбал В.П. Теория информации и кодирование. — К.:Выща Школа, 1977. — 288 с.

  • Энтропийное кодирование
  • Цепь Маркова
  • Для понимания информационной энтропии можно прибегнуть к примеру из области термодинамической энтропии получившему широко известное название Демона Максвелла.

Эта статья содержит материал из статьи Информационная энтропия русской Википедии.

источник

Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X , имеющей конечное число значений:

Тогда энтропия будет определяться как:

От основания логарифма зависит единица измерения информации и энтропии: бит, нат или хартли.

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n ) рассчитывается по формуле:

Эта величина также называется средней энтропией сообщения. Величина называется частной энтропией, характеризующей только i -e состояние.

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

Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид:

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. См.: Цепи Маркова.

В общем случае b -арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где pi является вероятностью ai ( pi = p(ai) ) определяется формулой:

Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет условиям:

  1. определена и непрерывна для всех , где для всех и . (Заметьте, что эта функция зависит только от распределения вероятностей, а не от алфавита.)
  2. Для целых положительных n , должно выполняться следующее неравенство:
  3. Для целых положительных bi , где , должно выполняться равенство:

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию − 2(0,5log20,5) = 1 бит на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: . Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

  1. Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
  2. Количество энтропии не всегда выражается целым числом бит.
  1. Неотрицательность: .
  2. Ограниченность: . Равенство, если все элементы из X равновероятны.
  3. Если независимы, то H(XY) = H(X) + H(Y) .
  4. Энтропия — выпуклая вверх функция распределения вероятностей элементов.
  5. Если имеют одинаковое распределение вероятностей элементов, то H(X) = H(Y) .

Исходный алфавит, встречающийся на практике, имеет вероятностное распределение, которое далеко от оптимального. Если исходный алфавит имел n символов, тогда он может быть сравнён с «оптимизированным алфавитом», вероятностное распределение которого однородно. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах.

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

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):

где i — это состояние, зависящее от предшествующего символа, и pi(j) — это вероятность j , при условии, что i был предыдущим символом.

Так, для русского языка без буквы «ё» . [2]

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Так, для описания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условную вероятность получения приёмником символа bj при условии, что был отправлен символ ai . При этом канальная матрица имеет следующий вид:

b1 b2 bj bm
a1
a2
ai
am

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а сумма всех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника — p(bj) . Потери, приходящиеся на передаваемый сигнал ai , описываются через частную условную энтропию:

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можно получить p(ai) , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия, или энтропия объединения, предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H(AB) , где A , как всегда, характеризует передатчик, а B — приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий p(aibj) , и для полного описания характеристик канала требуется только одна матрица:

p(a1b1) p(a1b2) p(a1bj) p(a1bm)
p(a2b1) p(a2b2) p(a2bj) p(a2bm)
p(aib1) p(aib2) p(aibj) p(aibm)
p(amb1) p(amb2) p(ambj) p(ambm)

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p(bj) , сумма строки с номером i есть p(ai) , а сумма всех элементов матрицы равна 1. Совместная вероятность p(aibj) событий ai и bj вычисляется как произведение исходной и условной вероятности,

Условные вероятности производятся по формуле Байеса. Таким образом имеются все данные для вычисления энтропий источника и приёмника:

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

H(AB) = − p(aibj)logp(aibj).
i j

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов — отправленного и полученного. Путём несложных преобразований также получаем

Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины.

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

Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

источник