<< Предыдущая

стр. 2
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

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




Р и с . 2.1. Простейший источник источник информации ал-
фавита AT.

Аксиомы для определения количества информации [1]
1. Информация одиночного события Х{ ? X, происходящего с ве-
роятностью pi, имеет положительное значение
> 0. • (2.1)

2. Совместная информация двух независимых событий (xi,Xj) с
совместной вероятностью P(xi,Xj) = Pij = Pi • Pj> равна сумме
их информации
(2.2)
3. Информация является непрерывной функцией от вероятности
события.
Аксиомы 1 и 2 утверждают, что информация нескольких событий не
может взаимно уничтожаться. Аксиома 2 вводит понятие совмест-
ной информации событий. Из аксиомы 3 следует, что небольшое из-
менение вероятности события приводит к небольшому изменению ее
Глава 2. Информация, энтропия и избыточность


информации. Аксиома 2 определяет информацию двух независимых/
событий. Из (2.2) следует, что информация события определяется/
как логарифмическая функция ее вероятности. Следовательно, ин-
формацию можно определить следующим образом:
Информация события, происходящего с вероятностью р, равна

(2.3)
1(р) = -Iog 2 (p) с [/] = бит.

В данной формуле используется двоичный логарифм. Возможны сле-
дующие обозначения двоичного логарифма: Iog2(a;) = Id (x) = lb(a;),
где под Id подразумевается термин дуальный логарифм, а под 1Ь -
бинарный.1 Иногда используют натуральный логарифм с единицей
измерения наш, но можно использовать любую единицу измерения
информации. Можно также переходить от одной единице к другой,
применяя формулу пересчета:

k>go(z) = logb(ar)/logb(a) = logb(z) • loga(6).

Размерность бит используется в информационной технике при
двоичной системы исчисления. Как будет показано в следующих раз-
делах, двоичная система очень удобна при описании процесса приня-
тия решения, когда на любой вопрос существует только два ответа:
«да» или «нет». В [10] приведена наглядная интерпретация понятия
«бит».
10
Up) f Невозможное
событие
бит /. = 0
\
5 V—-
Неизбежное
событие



р
0 0,5 •1


Р и с . 2.2. Информация символа 7(р) с вероятностью появ-
ления р.

На рис. 2.2 показано поведение информации как функции вероят-
ности. Информация постоянно происходящего события равна нулю.
1
В отечественной математической литературе для обозначения двоичного и на-
турального логарифма принято использовать log2 и In. - Прим. перев.
\ 15,
2.2. Энтропия и избыточность
I
\ С ростом неопределенности информация также растет и для невоз-
\можного события стремится к бесконечности. Таким образом, ин-
формация соответствует всем приведенным ранее рассуждениям и
удовлетворяет аксиомам 1 - 3. С точки зрения теории вероятности,
определение информации можно рассматривать как некоторое отоб-
ражение событий. Аналогичное отображение имеют стохастические
переменные. В следующих разделах это будет поясняться на приме-
рах.


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

Элтропия простейшего источника без памяти X с алфавитом
X — {х\,х<2, • • • ,?JV} и соответствующим вероятностям Р\,Р2, • • • ,P
равна
N
(2.4)
H(x) = ^2-Pi\og2(Pi)6nT.
г

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

Пример: Оценка энтропии.

Поясним эту связь на примере простейшего дискретного источ-
ника без памяти из табл. 2.1. Информация источника представля-
ет собой результат эксперимента со случайными событиями а, Ь, с, d.
Пусть в результате повторения этого эксперимента мы получаем по-
следовательность

{а,Ъ,а,d t а,а,с,d,b,a,a,b,...}. (2.5)
Глава 2. Информация, энтропия и избыточность

Таблица 2.1. Дискретный источник без памяти с символами
алфавита X = {а, Ь, с, d} с вероятностью р* и
информацией I(pi).

Символ с d
b
а

1/8
1/2 1/8
1/4.
р.

3 бит
2 бит
1 бит 3 бит
ПР.)




Подставив на место каждого события его информацию, получим
типичную функцию стохастического процесса

(2.6)
{/[п]/бит} = {1,2,1,3,1,1,3,3,2,1,1,2,...}.
Предположим эргодичность (постоянство поведения) такого про-
цесса во времени. Такую эргодичность мы, например, предполагаем
при бросании монетки или игрального кубика. С ростом числа ис-
пытаний N среднее значение информации источника
JV-1
/ = lim -i у /[га] (2.7)
N->oo N t-*1
n=0
стремится к математическому ожиданию
4
(2.8)


Таким образом, учитывая сходимость ряда (2.7) к математическому
ожиданию, получаем практическую меру для информации источни-
ка. В рассмотренном нримере математическое ожидание Е{1) равно
1,75 бит. Из первых 12 испытаний мы также получаем оценку для
/(га) 1,75 бит.
Проводя аналогичные рассуждения, Шеннон [1] заложил в опре-
деление энтропии три следующие аксиомы.
Аксиоматическое определение энтропии
1. Энтропия Н{Х) = f(pi,P2, • • • ,PN) является непрерывной функ-
цией вероятностей р\,Р2,... ,ры-
2. Для источников с одинаковой вероятностью событий pi = jj
энтропия увеличивается с ростом числа событий N.
3. Разложение процедуры выбора событий на несколько этапов
не изменяет энтропию (процедуру выбора можно свести к последо-
вательным двоичным решениям).
2.2. Энтропия и избыточность

Пример: Разложение процедуры выбора.
I
\ Данный пример поясняет аксиому 3. Рассмотрим три события a, b
й с. которые происходят с соответственными вероятностями 1/2,1/3
и 1/6. Для того, чтобы выбрать одно из этих трех, мы можем поста-
вить два независимых вопроса (рис. 2.3).




1/6 " о ,


Рис. 2.3. Разложение процесса выбора символов.

На эти вопросы могут быть даны только два ответа: или «да» или
«нет». Согласно аксиоме (3), к энтропии предъявляется следующее
требование:



причем, второй вопрос задается с вероятностью 1/2. Мы покажем в
общем виде (рис. 2.4), что определение энтропии (2.8) удовлетворяет
требованию аксиомы (НЗ).
Оа


ОЬ
Рг(Ь)




Ь=с


Рис. 2.4. Разложение процедуры принятия решения.

Для разложенной энтропии получаем
Н(Х)
= -Pi(a)log 2 (pi(a)) -Pi(a)log 2 (pi(a))+
(2.10)
бит
+ Pi (о)[-рг(Ь) Iog2(p2(b)) - Mb) Iog2(p2(b))],
где вероятности определяются следующим образом
(2.11)
Pi(a) =р(Ь)+р(с),
18 Глава 2. Информация, энтропия и избыточность




Р2(6) Р(Ь)
=

(Ь) р(сУ
Р2




Замечание. Последнее равенство подтверждается постановкой экс-
перимента со случайными событиями. Пусть событие а произошло
300 раз, событие Ь - 200, а событие с - 100 раз. Частота каждого
события в данном примере, равна его вероятности. Если мы отбро-
сим событие а, то останется 300 выборок событий Ь и с, частоты
выборок этих событий удвоятся, но их отношение не изменится.

Из (2.11)- (2.13) следует, что вероятности на втором шаге можно
выразить как




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


- д — = -Pi(a)log 2 (pi(o)) -Pi(a)log 2 (pi(a))+


Pl(t

<< Предыдущая

стр. 2
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>