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

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

ОГЛАВЛЕНИЕ

Следующая >>

Р и с . 4.1. Модель двух связанных источников.
Глава 4- Энтропия связанных источников

Если оба источника каким-то образом связаны между собой, то
следует ожидать, что событие одного источника позволяет делать
некоторое предположение о событии другого. В терминах теории
информации это означает, что неопределенность второго источника
снижается, т.е. источники обмениваются взаимной информацией.
Введем условную вероятность р(х/у) - вероятность события х
при условии, что произошло событие у. Выразим совместную веро-
ятность p(xi, г/г) двух событий Х{ и j/j через их априорные и условные
вероятности

(4.1)
p{xi,yi)=p(xi/yi)p(yi)=p(yi/xi)p{Xi).

Используя логарифмическую функцию, сразу же получаем инфор-
мации Событий {Xi,yi), (Xi) И (у)



-Цим) бит i(Vi) бит




то есть

I{xi,Vi) = I(Vi) - ld(ii/3/j) бит = 1(ц) - \og2p{yi/xi) бит. (4.3)

Прибавляя и одновременно вычитая I(xi) в первой части (4.3) и,
соответственно, I{yi) во второй, получаем

'l(Xi, уг) = (Xi) + 1(уг) - log2 ^ ^ бит =




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



7 \
/ апостериорная вероятность \
= log2 ( I.
\ априорная вероятность /
4-1- Взаимная и условном информация

-Обратите внимание на то, что взаимная информация /(ж,; у,) все-
гда положительна. Важным свойством также является симметрия
взаимной информации относительно источников, т.к.


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

1. Источники независимы. Тогда для пары независимых событий
имеем
(4.7)
p(*i,Vi) = P{xi)p(yi), '
то есть источники не обмениваются информацией

(4.8)
1{Хг;Уг)=0.

2. Источники жестко связаны, то есть событие одного источника
однозначно определяет событие другого

• (4.9)
) = 1.

В этом случае происходит полный обмен информацией

ЦХГМ) = 1(ъ) = /(w). (4.10)


Из (4.4) следует, что информацию пары событий {xi,yi) можно ин-
терпретировать, как разность между информацией пары независи-
мых событий l{xi) + I(yi) и заранее предсказанной взаимной инфор-
мацией I(xi;yi), обусловленной связанностью источников X и Y

(4.11)
Цхит) = I(Xi) + 1{УГ) - 1{ХГ,1Н).

Рассмотрим еще раз (4.3) и введем понятие условной информации.
Условная информация (апостериорная неопределенность)

= - l o g a p f o / и ) бит. (4.12)
Iixilm)

Из (4.3) следует

/(*<;») = 1{Уг) + I(Xi/yi) = Цц) + НУг/Xi), (4.13)
,38 Глава 4- Энтропия связанных источников

то есть информацию пары событий можно определить как сумму
информации события у\ и информации события ж, при условии, что
событие yi уже известно, или, наоборот, как сумму информации со-
бытия Xi и информации события ;(/, при условии, что событие xt уже
известно.


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




Алфавит Х={х,,...,хи\ 1 ^ ( Ж I
Вероятность р(х,) I ^Символы
Ш^^^ШШ"^ЖЖ

Условная вероятность р(у} I Xj)
Д ^ Д ИТЧ И |
СО Н К
„,_^_^_ - I Вероятность пары
Алфавит К = ( ^ ,) ЯНи^иЛ с мо о р^,,у>)
и влв
Уд
Вероятность р(у*)
Связанные источники


Р и с . 4.2. Два связанных дискретных источника.

Совместная энтропия двух источников определяется как матема-
тическое ожидание информации всех пар событий.

Совместная энтропия двух дискретных источников без памяти
X HY
^т ). (4.14)

Замечание. Здесь подразумевается, что рассматриваются все па-
ры совместных событий, то есть

МN

t=i j=i
A: Y


Усредняя условные информации всех нар событий, получим услов-
ную энтропию.
4-2. Совместная и условная энтропия

Таблица 4.1. Оценка совместной вероятности пар символов
p(xi,yj) и вероятность отдельных символов




2/1 Vi

0,05 0 0,20
0,10 0,05
XI


0,05 0,15 0,15 0 0,35
Х2


0 0,10 0,30
0,10 0,10
хз
0 0,05 0,05 0,05 0,15
Х4


1
0,15 0,35 0,35 0,15
v(Vj)



Условная энтропия двух дискретных источников без памяти X и У




(4.15)
ЩХ/Y)
.
p{Xty)log2p{x/y)
бит
XY
Заменяя в (4.14) \og2p{x,y) ua.\og2(p(x/y)p(y)) и на Iog2(p(y/x)p{y)),
получим

(4.16)
Н(Х, Y) = H{Y) + H{X/Y) = Н{Х) + H(Y/X).

Таким образом, совместная энтропия может быть представлена
в виде суммы энтропии одного источника и некоторой части эн-
тропии другого источника. Для независимых источников энтропия
второго источника входит в сумму целиком, т.к. H(X/Y) — Н(Х)
и H(Y/X) = H(Y). Для связанных источников всегда H(X/Y) <
Н(Х) и H{Y/X) < H(Y). Поэтому, в общем случае, всегда имеет
место
(4.17)
H{X,Y)<H{Y) + H(X).
Пример: Связанные источники.
Сейчас самое время подробно разобрать числовой пример, на-
глядно поясняющий приведенные выше определения и формулы. Для
этой цели была подобрана задача, методика решения которой может
непосредственно использоваться на практике.
Пусть мы имеем выборку 100000 пар совместных событий (xi,yi)
дискретных источников X и У и алфавит каждого источника со-
держит четыре события. Пусть пара (xi,yi) встретилась 10000 раз.
Г40 Глава 4- Энтропия связанных источников

Тогда оценка вероятности пары (xi,2/i) равна 10000/10000 = 0,1.
Оценки остальных пар событий также получены подсчетами их от-
носительной частоты и сведены в таблицу 4.1. Будем считаем, что
полученные оценки близки к вероятностям пар событий и в даль-
нейшем будем говорить уже о вероятностях. Вероятности событий
Xi, yi получены суммированием строк и столбцов. Контрольная сум-
ма Y2i=ixi = X/i=i 2г = 1 приведена в правом нижнем углу.
/
Теперь, когда нам известны все вероятности, необходимые для
подсчета энтропии, определим:

1. Энтропии источников X и У;

2. Совместную энтропию источников;

3. Обе условные энтропии;

Для контроля мы также вычислим:

4. Условные вероятности P(yg/xi);

5. Определим условную энтропию H(Y/X).
Замечание. Для простоты проведем расчеты с точностью до 4
знаков после запятой.
Решение.
1.
н(х) _ А _
бит ^—*

i=i


= -2[0,15 • log2(0,15) + 0,35 • log2(0,35)] = 1,9261, (4.18)

_4 >( № ) = 1,8813;
j=i

2 4 4

?˜р- = Е Е -p(Xi> УЗ)=3-4464; (4-19)
i=i j=\

3. Без длинных вычислений из (4.16) получаем

= H(X,Y) - H(Y) = 3,4464 - 1,8813 = 1,5651 бит,
H(X/Y)

H(Y/X) = H{X,Y) - H{X) = 3,4464 - 1,19261 = 1,5203 бит;

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

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

ОГЛАВЛЕНИЕ

Следующая >>