Формула энтропии в информатике

Формула энтропии в информатике

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

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

Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: <1/N, 1/N, … 1/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: , p1, …pN-1>, т.е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье "Математическая теория связи".

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

Читайте также:  Чем отличаются шины isa и eisa

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

(1)

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

интерпретируется как частное количество информации , получаемое в случае реализации i-ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины , 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.

pi 1/pi Ii=log2(1/pi), бит pi*log2(1/pi), бит
Ж 1/2 log2(2)=1 1/2 * 1=1/2
М 1/2 log2(2)=1 1/2 * 1=1/2
å 1 H=1 бит

Формула Шеннона (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 этажей.

Читайте также:  Роутер с юсб портом для 4g модема

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

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

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9418 — | 7463 — или читать все.

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

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

Пусть информационная система может порождать ансамбль (алфавит) сообщений аг, а2, . ат. Вероятности каждого сообщения следующие: Р(а <),Р(а2), . Р(аш). Так как вероятности сообщений не одинаковы, то они несут разное количество информации, определяемое формулой Шеннона:

Среднее количество информации (математическое ожидание количества информации) ансамбля сообщений вычисляется по известной формуле:

Совершенно аналогично вводится энтропия сообщений:

Энтропия не зависит от конкретного сообщения. Это характеристика информационной системы (источника, приемника сообщений или канала передачи сообщений). Энтропия в таком виде является априорной характеристикой и может быть вычислена до эксперимента, если известны вероятностные характеристики сообщений. Энтропия характеризует неопределенность ситуации до передачи сообщения, поскольку заранее неизвестно, какое сообщение из ансамбля будет передано. Чем больше энтропия, тем сильнее неопределенность и тем большую информацию в среднем несет одно сообщение источника. Сравнивая формулы (2.8) и (2.6) видим, что / = п • Я.

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

Обсуждая понятие информация, невозможно не затронуть другое смежное понятие – энтропия[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. Реализация менее вероятного события дает больше информации. Чем больше неопределенность до получения сообщения о событии (бросание монеты, кости), тем большее количество информации поступает при получении сообщения.

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

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

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

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

Ссылка на основную публикацию
Филипс диамонд вижн h7
Заказав на экзисте лампы для ближнего света Philips Blue Vision Ultra (пост удалил), понял, что сильно поторопился, поскольку ничего не...
Усилитель сигнала для тв антенны отзывы
Характеристика в рейтинге 1 Alcad AL-200 Высокое качество во всех аспектах эксплуатации. Самый популярный усилитель в России 2 Eurosky SWA-105...
Усилитель сотового сигнала отзывы
Нашел вот еще информацию что Mobi-900 стал занял 1 место в рейтинге репитеров по версии журнала Provider-Review: http://provider-review.ru/reyting-usiliteley-sotovoy-svyazi.html А вот...
Фигуры для оформления текста
Методические рекомендации В Word 2007 можно добавлять два типа графики – Рисунки и Фигуры. Рисунок – изображение, созданное в другом...
Adblock detector