Количество информации энтропийный способ

Теория алгоритмов и программ — Практика

4.2. Энтропия и информация

Разность Н(β) и Н_α(β), очевидно, показывает, какие новые сведения относительно β получаем, про­изведя опыт α. Эта величина называется информацией относи­тельно опыта β, содержащейся в опыте α.

Данное выражение открывает возможность численного изме­рения количества информации. Запишем ряд следствий:

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

Следствие 2 . Пусть опыт α = β, т.е. просто произведен опыт β. Поскольку он несет полную информацию о себе самом, неопреде­ленность его исхода полностью снимается, т.е. Ηᵦ(β)=0. Тогда I(β,β)=Η(β). Исходя из этого, можно считать, что:

энтропия равна информации относительно опыта, которая со­держится в нем самом.

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

1. Информация всегда положительна и равна нулю тогда и только тогда, когда опыты независимы.

2.Информация симметрична относительно последовательности опытов.

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

Какое количество информации требуется, чтобы узнать исход броска монеты?

В данном случае n=2 и события равновероятны, т.е. р₁ = р₂ = 0,5.

Игра «Угадай-ка-4». Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет» Какое количество информации должны получить, чтобы узнать задуманное число, т.е полностью снять начальную неопределенность? Как правильно построить процесс угадывания?

Исходами в данном случае являются: а) А1 — «задуман О», А2 — «задума­на 1», Аз- «задумана 2», А4 — «задумана З». Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы.

Поскольку n = 4, следовательно, р(Аᵢ) = 1/4,log2p(Aᵢ) = -2 и I= 2 бит. Таким обра­зом, для полного снятия неопределенности опыта (угадывания заду­манного числа) нам необходимо 2 бит информации. Теперь выясним, какие вопросы необходимо задать, чтобы процесс угадывания был оптимальным, т е. содержал минимальное их число. Здесь удобно воспользоваться так называемым выборочным каскадом:

Рис. 1.5. Выборочный каскад

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

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

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

Легко получить следствие формулы (1.24) для случая, когда все n исходов равновероятны (собственно, именно такие и рассматри­вались в примерах 1.10 и 1.13). В этом случае все

Эта формула была выведена в 1928 г. американским инжене­ром Р. Хартли. Она связывает количество равно­вероятных состояний (n) и количество информации в сообщении (I), что любое из этих состояний реализовалось. Ее смысл в том, что, если некоторое множество содержит n элементов и х принад­лежит данному множеству, то для его выделения (однозначной идентификации) среди прочих требуется количество информации, равное log2n.

Частным случаем применения формулы (1.27) является си­туация, когда n=2ᵏ, подставляя это значение в (1.27), получим:

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

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

Для данной ситуации n=2 5 , значит, k=5 и, следовательно, I=5 бит. Последовательность вопросов придумайте самостоятельно.

Следуя из ранее рассмотренного, справедливы следующие утверждения:

Утверждение 1. Выражение (1.24) является статистическим определением понятия «информация», поскольку в него входят вероятности воз­можных исходов опыта. По сути, дается операционное определе­ние новой величины, т.е. устанавливается процедура (способ) из­мерения величины.

Выражение (1.23) можно интерпретировать следующим образом:

если начальная энтропия опыта H1, а в результате сообщения ин­формации I энтропия становится равной H2 (очевидно, Н1≥ Н2), то I=H1-H2, т.е. информация равна убыли энтропии. В частном случае, если изначально равновероятных исходов было n1, а в результате пе­редачи информации I неопределенность уменьшилась, и число исходов стало n2 (очевидно, n2≤n1), то из (1.27) получается:

Таким образом, справедливо следующее определение:

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

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

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

Утверждение 3 . Следствием аддитивности энтропии независимых опытов (1.13) оказывается аддитивность информации. Пусть с выбором од­ного из элементов (X_A) множества А, содержащего n_A элементов, связано формула, информации, а с выбором Х_B из В с n_B элемен­тами информации связано формула и второй выбор никак не свя­зан с первым, то при объединении множеств число возможных со­стояний (элементов) будет n=n_A∙n_B и для выбора комбинации Х_AХ_B потребуется количество информации:

Утверждение 4. Вернемся к утверждению о том, что количество информации может быть измерено числом вопросов с двумя равновероятными ответами. Означает ли это, что I должна быть всегда величиной целой? Из формулы Хартли (1.27), как было показано, I = k бит (т.е. целому числу бит) только в случае n=2ᵏ. А в остальных си­туациях? Например, при игре «Угадай-ка — 7» (угадать число от 0 до 6) нужно в выборочном каскаде задать m≥log₂(7)=2.807, т.е. необходимо задать три вопроса, поскольку количество вопросов — это целое число.

Однако представим, что одновременно играем в шесть таких же игр (кубик). Тогда необходимо отгадать одну из возможных комбинаций, которых всего

Следовательно, для угадывания всей шестизначной комбинации требуется I = 17 бит информации, т.е. нужно задать 17 вопросов. В среднем на один элемент (одну игру) приходится 17/6 = 2,833 вопроса, что близко к значению log₂(7).

Таким образом, справедливо следующее утверждение:

Величина I, определяемая описанным выше образом, показы­вает, сколько в среднем необходимо сделать парных выборов для установления результата (полного снятия неопределенно­сти), если опыт повторить многократно (n→∞).

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

При угадывании результата броска игральной кости задается вопрос «Выпало 6?». Какое количество информации содержит ответ?

р=1/6, 1-р=5/6, следовательно из (1.24):

Утверждение 6 . Формула (1.24) приводит еще к одному выводу.

Пусть неко­торый опыт имеет два исхода А и В, причем р(А)= 0,99 , а р(В)= 0,01. В случае исхода А получим количество информации I(A)= -log₂(0,99)=0,0145бит. В случае исхода В количество информа­ции оказывается равным I(B)= — log₂(0,01)=0,644 бит. Другими сло­вами, больше информации связано с теми исходами, которые менее вероятны. Действительно, то, что наступит именно А, почти наверняка знали и до опыта; поэтому реализация такого исхода очень мало добавляет к нашей осведомленности. Наоборот, исход B — весьма редкий; информации с ним связано больше (осуществилось трудно ожидаемое событие). Однако такое большое коли­чество информации будем при повторах опыта получать редко, поскольку мала вероятность В. Среднее же количество информа­ции согласно (1.24) равно I=0,99∙I(A)+0,01∙I(B)=0,081бит.

Утверждение 7. Нами рассмотрен вероятностный подход к определению ко­личества информации. Он не является единственным. Количество информации можно связать с числом знаков в дискретном сообщении — такой способ измерения назы­вается объемным. Можно доказать, что при любом варианте коди­рования информации Iвер

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

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

Утверждение 9. Информация и знание. На бытовом уровне, в науках социаль­ной направленности, например в педагогике «информация» отожде­ствляется с «информированностью», т.е. человеческим знанием, которое, в свою очередь, связано с оценкой смысла информации.

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

Источник

Количество информации энтропийный способ

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

Понятие неопределенности

Первым специфическим понятием теории информации является понятие неопределенности случайного объекта, для которого удалось ввести количественную меру, названную энтропией. Начнем с простейшего примера — со случайного события. Пусть, например, некоторое событие может произойти с вероятностью 0,99 и не произойти с вероятностью 0,01, а другое событие имеет вероятности соответственно 0,5 и 0,5. Очевидно, что в первом случае результатом опыта «почти наверняка» является наступление события, во втором же случае неопределенность исхода так велика, что от прогноза разумнее воздержаться.

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

Энтропия и ее свойства

Примем (пока без обоснования) в качестве меры неопределенности случайного объекта А с конечным множеством возможных состояний А1. Аn с соответствующими вероятностями P₁,P₂. P_n величину

которую и называют энтропией случайного объекта А (или распределения < >. Убедимся, что этот функционал обладает свойствами, которые вполне естественны для меры неопределенности.

1. Н(p₁. p_n)=0 в том и только в том случае, когда какое-нибудь одно из i > равно единице (а остальные — нули). Это соответствует случаю, когда исход опыта может быть предсказан с полной достоверностью, т.е. когда отсутствует всякая неопределенность. Во всех других случаях энтропия положительна. Это свойство проверяется непосредственно.
2. Н(p₁. p_n) достигает наибольшего значения при p₁=. p_n=1/n т.е. в случае максимальной неопределенности. Действительно, вариация Н по p_i при условии ∑p_i = 1 дает p_i = const = 1/n.
3. Если А и В — независимые случайные объекты, то H(A∩B) = H(iq_k>) = H(i>) + H(k>) = H(A) + H(B). Это свойство проверяется непосредственно.
4. Если А и В — зависимые случайные объекты, то H(A∩B) = H(A) + H(B/A) = H(B) + H(A/B), где условная энтропия H(А/В) определяется как математическое ожидание энтропии условного распределения. Это свойство проверяется непосредственно.
5. Имеет место неравенство Н(А) > Н(А/В), что согласуется с интуитивным предположением о том, что знание состояния объекта В может только уменьшить неопределенность объекта А, а если они независимы, то оставит ее неизменной.

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

Дифференциальная энтропия

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

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

Теперь величину К можно принять равной единице измерения х, что приводит к функционалу

который получил название «дифференциальной энтропии». Это аналог энтропии дискретной величины, но аналог условный, относительный: ведь единица измерения произвольна. Запись (3) означает, что мы как бы сравниваем неопределенность случайной величины, имеющей плотность p(x), с неопределенностью случайной величины, равномерно распределенной в единичном интервале. Поэтому величина h(X) в отличие от Н(Х) может быть не только положительной. Кроме того, h(X) изменяется при нелинейных преобразованиях шкалы х, что в дискретном случае не играет роли. Остальные свойства h(X) аналогичны свойствам Н(Х), что делает дифференциальную энтропию очень полезной мерой.

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

Фундаментальное свойство энтропии случайного процесса

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

Назовем каждое такое состояние «символом», множество возможных состояний — «алфавитом», их число m — «объемом алфавита». Число возможных последовательностей длины n, очевидно, равно mn. Появление конкретной последовательности можно рассматривать как реализацию одного из mn возможных событий. Зная вероятности символов и условные вероятности появление следующего символа, если известен предыдущий (в случае их зависимости), можно вычислить вероятность P(C) для каждой последовательности С. Тогда энтропия множества , по определению, равна

На множестве можно задать любую числовую функцию f_n(C), которая, очевидно, является случайной величиной. Определим f_n(C) c помощью соотношения f_n(C) = -[1/n]⋅logP(C).

Математическое ожидание этой функции

Это соотношение является одним из проявлений более общего свойства дискретных эргодических процессов. Оказывается, что не только математическое ожидание величины f_n(C) при n стремящемся к бесконечности имеет своим пределом H, но и сама эта величина f_n(C) стремится к H при n стремящемся к бесконечности. Другими словами, как бы малы ни были e > 0 и s > 0, при достаточно большом n справедливо неравенство

P <|[1/n]⋅log(P(C))+H| >ε> 0 и s > 0 можно найти такое no, что реализация любой длины n > no распадаются на два класса:

группа реализаций, вероятность P(C) которых удовлетворяет неравенству |[1/n]⋅log(P(C))+H| nH

Число N всех возможных реализаций есть

N = m n = σ n⋅log(m)

Доля реализаций высоковероятной группы в общем числе реализаций выражается формулой

и при H -25 = (3⋅10 7 ) -1

т.е. к высоковероятной группе относится лишь одна тридцати миллионная доля всех реализаций!

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

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

Подведем итог

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

Количество информации

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

Количество информации как мера снятой неопределенности

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

1. полезный (передаваемый) сигнал является последовательностью статистически независимых символов с вероятностями p(x_i),i = 1,m ;
2. принимаемый сигнал является последовательностью символов Y_k того же алфавита;
3. если шумы (искажения) отсутствуют, то принимаемый сигнал совпадает с отправленным Y_k=X_k ;
4. если шум имеется, то его действие приводит к тому, что данный символ либо остается прежним (i-м), либо подменен любым другим (k-м) с вероятностью p(y_k/x_i) ;
5. искажение данного символа является событием статистически независимым от того, что произошло с предыдущим символом.

Итак, до получения очередного символа ситуация характеризуется неопределенностью того, какой символ будет отправлен, т.е. априорной энтропией Н(Х). После получения символа y_k неопределенность относительно того, какой символ был отправлен, меняется: в случае отсутствия шума она вообще исчезает (апостериорная энтропия равна нулю, поскольку точно известно, что был передан символ y_k=x_i), а при наличии шума мы не можем быть уверены, что принятый символ и есть переданный, т.е. возникает неопределенность, характеризуемая апостериорной энтропией H(X/y_k)=H(i/y_k)>)>0.

В среднем после получения очередного символа энтропия H(X/Y)=M_yk)>

Определим теперь количество информации как меру снятой неопределенности: числовое значение количества информации о некотором объекте равно разности априорной и апостериорной энтропии этого объекта, т.е. I(X,Y) = H(X)-H(X/Y). (1)

Используя свойство 2 энтропии, легко получить, что I(X,Y) = H(Y) — H(Y/X) (2)

В явной форме равенство (1) запишется так:

а для равенства (2) имеем:

Количество информации как мера соответствия случайных процессов

Представленным формулам легко придать полную симметричность: умножив и разделив логарифмируемое выражение в (3) на p(y_k), а в (4) на p(x_i) сразу получим, что

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

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

Формула (5) обобщается на непрерывные случайные величины, если в отношении (1) и (2) вместо Н подставить дифференциальную энтропию h; при этом исчезает зависимость от стандарта К и, значит, количество информации в непрерывном случае является столь же безотносительным к единицам измерения, как и в дискретном:

где р(x), p(y) и p(x,y) — соответствующие плотности вероятностей.

Свойства количества информации

Отметим некоторые важные свойства количества информации.

1. Количество информации в случайном объекте Х относительно объекта Y равно количеству информации в Y относительно Х: I(X,Y) = I(Y,X)
2. Количество информации неотрицательно: I(X,Y) > 0. Это можно доказать по-разному. Например, варьированием p(x,y) при фиксированных p(x) и p(y) можно показать, что минимум I, равный нулю, достигается при p(x,y) = p(x) p(y).
3. Для дискретных Х справедливо равенство I(X,X) = H(X).
4. Преобразование y (.) одной случайной величины не может увеличить содержание в ней информации о другой, связанной с ней, величине: I[y (X),Y]

Источник