Часть 4. Элементы теории информации

ЧАСТЬ 4. ЭЛЕМЕНТЫ ТЕОРИИ ИНФОРМАЦИИ

 

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

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

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

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

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

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

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

ГЛАВА 1. ЭНТРОПИЯ

Комбинаторный подход к вычислению количества

Информации. Формула Хартли

 

Обозначим через I количество информации, n – число состояний физической системы, тогда I = I (n) – функция количества информации. И повторим рассуждения Р.Хартли, позволившие ему получить меру количества информации. Предварительно примем, что информация – это устраненная неопределенность.

Предположим, что какое-то событие имеет m равновероятных исходов. Таким событием может быть, например, появление любого символа из алфавита, содержащего m таких символов. Как измерить количество информации, которое может быть передано при помощи такого алфавита? Это можно сделать, определив число N возможных комбинаций букв алфавита, то есть число возможных сообщений, которые могут быть переданы при помощи этого алфавита. Если сообщение формируется из одного символа, то N = m, если из двух, то N = m ². Если сообщение содержит n символов (n – длина сообщения), то N = mⁿ. Казалось бы, искомая мера количества информации найдена. Ее можно понимать как меру неопределенности исхода опыта, если под событием подразумевать случайный выбор какого-либо сообщения из некоторого числа возможных. Однако эта мера не совсем удобна. При наличии алфавита, состоящего из одного символа, т.е. когда m = 1, возможно появление только этого символа. Следовательно, неопределенности в этом случае не существует, и появление этого символа не несет никакой информации. Между тем, значение N при m = 1 не обращается в нуль. Для двух независимых источников сообщений (или алфавита) с N ₁ и N ₂ числом возможных сообщений общее число возможных сообщений , в то время как логичнее было бы считать, что количество информации, получаемое от двух независимых источников, должно быть не произведением, а суммой составляющих величин.

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

. (1.1)

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

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

Аксиомы теории информации

1. Мера неопределенности есть непрерывная функция вероятности исходов некоторого опыта.

2. Если исходы опыта равновероятны, то мера неопределенности – монотонно возрастающая функция от числа исходов.

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

 

Вывод формулы Шеннона

Рассмотрим ряд чисел , где i = 1,.., n, а m_i – целые положительные числа, такие что .

Для кодового слова длиной m_i меру неопределенности закодированного состояния можно представить в виде:

_.

Для примера, приведенного в таблице, мера неопределенности будет равна:

– среднее количество знаков в кодовом слове (математическое ожидание).

Если взять не двоичную систему счисления, а систему счисления с основанием a, то для ряда чисел , закодированных кодовыми словами длиной m_i меру неопределенности закодированного состояния можно представить в виде:

_.

Если опять обратимся к таблице, то увидим, что – это вероятность состояния, закодированного кодовым словом длиной m_i, то есть p_i. При этом .

Поэтому, выражение для неопределенности (1.1) Шеннон записал, объединив формулу для любой системы счисления и получил:

,

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

То есть, в самом общем случае, на вероятностном языке дляопыта стаблицейвероятностей

 

исходы опыта	А 1	А 2	А 3	…	Аk
вероятности				…		(1.2)

 

меранеопределенностиравна

и называется энтропией опыта (или дискретного распределения (1.2). Напомним, что .

Итак, энтропия – это среднее количество информации, приходящееся на один исход опыта (для дискретных систем).

Аналогичная (1.3) формула имеет место и при в предположении сходимости соответствующего ряда.

Наряду с энтропией дискретного распределения рассматривается также и энтропия непрерывной случайной величины, которая определяется формулой

, (1.4)

где – плотность распределения вероятностей. В предположении сходимости интеграл (1.4) является мерой неопределенности непрерывной случайной величины.

Доказательство

На существует ограничение .

Найдем локальный экстремум. Для этого рассмотрим функционал

, где коэффициент по Лагранжу, а – из условия ограничения.

Берем первые частные производные по :

Поскольку правые части всех выражений одинаковые, можно сделать вывод о равновероятных состояниях исходов опыта, то есть:

.

Тогда .

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

 

Иными словами, среди всех опытов, имеющих k исходов, наиболее неопределенным является опыт с распределением вероятностей:

 

Исходы опыта	А 1	А 2	А 3	…	Аk
Вероятности				…

И функция растет с увеличением числа k (см. аксиому 3). Причем,

. (1.5)

Для одного же исхода опыта . Например это может касаться k букв алфавита при равновероятном их использовании. Энтропия появления одной буквы будет равна , а трех последовательно .

Свойство 6. Функция удовлетворяет соотношению

.

Это соотношение означает, что неопределенность опыта с распределением вероятностей

 

Исходы опыта	B	A 3	…	Ak
Вероятности		p 3	…	pk

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

Свойство 7. Математическое ожидание информации есть энтропия (без доказательства)

.

Пример 1. Пусть из многолетних наблюдений за погодой известно, что для определенного пункта вероятность того, что 15 июня будет идти дождь, равна 0,4, а вероятность того, что в указанный день дождя не будет, равна 0,6. пусть далее для этого же пункта вероятность того,что 15 ноябрябудет идти дождь равна 0,65, вероятность того, что 15 ноября будет идти снег, равна 0,15 и вероятность того, что 15 ноября вовсе не будет осадков, равна 0,2. Если из всех характеристик погоды интересоваться лишь вопросом о наличии и о характере осадков, то в какой из двух перечисленных дней погоду в рассматриваемом пункте следует считать более неопределенной?

Решение

Согласно тому, как понимается здесь слово «погода», опыта и , состоящие в выяснении того, какая погода имела место 15 июня и 15 ноября, характеризуются следующими таблицами вероятностей:

опыт :

исходы опыта	дождь	отсутствие осадков
вероятность	0,4	0,6

опыт :

исходы опыта	дождь	снег	отсутствие осадков
вероятность	0,65	0,15	0,2

Поэтому энтропии наших двух опытов равны

бита,

и

бита .

Следовательно, погоду 15 ноября в рассматриваемом пункте следует считать более неопределенной, чем 15 июня.

Полученный результат, разумеется, существенно зависит от того, как понимать слово «погода»; без точного разъяснения того, что под этим понимается, наша задача вообще не имеет смысла. В частности, если интересоваться только тем, будут ли в рассматриваемый день осадки или нет, то исходы «дождь» и «снег» опыта следует объединить. При этом вместо мы будем иметь опыт , энтропия которого равна

.

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

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

Пример 2. Найти энтропию непрерывной случайной величины, распределенной по показательному закону

.

Решение

Применяя одно из свойств плотности распределения, находим . Таким образом, по формуле (1.4)

[применяя формулу интегрирования по частям, получаем]

бит.

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

 

Буква	Вероятность	Буква	Вероят- ность	Буква	Вероят- ность	Буква	Вероят- ность
а	0,064	и	0,064	р	0,041	ш	0,006
б	0,015	й	0,010	с	0,047	щ	0,003
в	0,039	к	0,029	т	0,056	ъ, ь	0,015
г	0,014	л	0,036	у	0,021	ы	0,016
д	0,026	м	0,026	ф	0,002	э	0,003
е, ё	0,074	н	0,056	х	0,009	ю	0,007
ж	0,008	о	0,096	ц	0,004	я	0,19
з	0,015	п	0,024	ч	0,013	–	0,142

 

Решение

При одинаковых вероятностях появления всех 32 (считая промежутки между словами и буквы е,ё и ъ,ь за одну букву) букв алфавита неопределенность, приходящаяся на одну букву, равна (см. формулу (1.5)):

бит.

Энтропия источника, характеризующегося вышеуказанной таблицей, находится по формуле (1.3):

бит.

Таким образом, неравномерность распределения вероятностей использования букв снижает энтропию источника с 5 до 4,42 бит.

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

Решение

Общее число пятибуквенных сообщений .

Используя (1.5), получаем:

бит.

Пример 5. Заданы ансамбли U и V двух дискретных случайных величин :

	0,5	0,7	0,9	0,3
	0,25	0,25	0,25	0,25			0,25	0,25	0,25	0,25

Сравните их энтропии.

Решение

Поскольку энтропия не зависит от конкретных значений случайной величины, а вероятности их появления у одинаковы, то

бит.

 

ГЛАВА 2. ИНФОРМАЦИЯ

Понятие информации

 

Понятие информации весьма широко и многосторонне, поэтому оно имеет целый ряд определений и синонимов: информация – это обозначение содержания, полученного из внешнего мира, или отрицание энтропии (Винер) или негэнтропия (Бриллюэн); это коммутация, связь (Шеннон); ограничение разнообразия (Эшби); оригинальность, мера сложности (Моль); вероятность выбора (Майлз Мартин) и т. д. К этим «определениям» следует добавить понятие информации как данных, ценных для принятия решений.

Начиная с работ Н. Винера, К. Шеннона, Дж.(Яноша) фон Неймана до настоящего времени каждая попытка дать универсальное определение информации терпит крах из-за неразрешимости основного вопроса: един ли для всех «приемников» информации предлагаемый критерий отбора из всего множества воздействий материального мира тех и только тех воздействий, которые несут информацию для данного «приемника»?

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

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

.

Априорной энтропией называется неопределенность, которая высчитывается до наступления исхода опыта. Она равняется .

Апостериорной энтропией называют среднюю неопределенность опыта после наступления всех исходов. Она равна условной энтропии .

Таким образом,

(2.1)

Или согласно определению энтропии и правилу сложения вероятностей

Иначе

(2.2)

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

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

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

Для непрерывных случайных величин

. (2.3)

Разность между величиной максимальной энтропии Н_max и реальной энтропии Н соответствует количеству избыточной (предсказуемой) информации I_n.

Таким образом:

I_n = H_max – H. (2.4)

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

Эффективность кода, т.е. колическтво информации, передаваемое в среднем в единицу времени

, (2.5)

где , если символу алфавита соответствует символ кода . Эффективность измеряется в битах на время.

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

. (2.6)

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

Пример. Сообщение состоит из последовательности трех букв А, В и С. Вероятности их появления не зависят от предыдущего сочетания букв и равны Р (А) = 0,7, Р (В) = 0,2 и Р (С) = 0,1. Произвести кодирование по методу Шеннона-Фано отдельных букв и двухбуквенных сочетаний. Сравнить коды по их избыточности.

Буква Вероятность Код А 0,7 1   В 0,2 1   С 0,1 0

Решение

Для отдельных букв имеем.

Здесь фигурными скобками показано разбиение на группы.

Буква Вероятность Код АА 0,49 1   АВ 0,14 1   ВА 0,14 0   АС 0,07 1   СА 0,07 0   ВВ 0,04 1   ВС 0,02 1   СВ 0,02 1   СС 0,01 0

Для двухбуквенных сочетаний вначале высчитаем вероятности их появлений.

Максимальная энтропия равна . Для первого случая избыточность кода равна

.

Аналогично для второго .

 

Свойства информации

1. Информация относительно опыта , содержащаяся в событии , всегда равна информации относительно , содержащейся в

.

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

. (2.8)

3. Пусть теперь , и – три произвольных опыта. В таком случае всегда

.

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

4. Если равенство имеет место, то в этом случае всегда

.

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

5. Неравенство играет в теории информации значительную роль (см. [36]). Оно показывает, что при последовательной передаче информации об опыте , осуществляемой посредством цепочки опытов , , ,..., где только опыт непосредственно связан с , а всю содержащуюся в нем информацию об получает из связи с опытом (так что уже не содержит об дополнительной информации по сравнению с ), всю информацию об получает из связи с опытом и т. д., информация об может лишь уменьшаться:

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

Условная информация

 

Определение. Величину

(2.9)

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

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

Для сопоставления введенные меры информации представим в таблице.

 

Мера информации	Единицы измерения	Примеры (для компьютерной области)
Синтаксическая: шенноновский подход компьютерный подход	Степень уменьшения неопределенности Единицы представления информации	Вероятность события Бит, байт и т.д.
Семантическая	Тезаурус   Экономические показатели	Пакет прикладных программ, персональный компьютер, компьютерные сети и т.д. Рентабельность, производительность, коэффициент амортизации и т.д.
Прагматическая	Ценность использования	Емкость памяти, производительность компьютера, скорость передачи данных и т.д. Время обработки информации и принятия решений

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

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

· Репрезентативность информации связана с правильностью ее отбора и формирования в целях адекватного отражения свойств объекта. Важнейшее значение здесь имеют:

· правильность концепции, на базе которой сформулировано исходное понятие;

· обоснованность отбора существенных признаков и связей отображаемого явления.

· Нарушение репрезентативности информации приводит нередко к существенным ее погрешностям.

· Содержательность информации отражает семантическую емкость, равную отношению количества семантической информации в сообщении к объему обрабатываемых данных, т.е. C = Ic/Vд.

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

Наряду с коэффициентом содержательности С, отражающим семантический аспект, можно использовать и коэффициент инфор