Лекции / ЛЕКЦИЯ 2.doc Взаимная информация

ЛЕКЦИЯ 2

ВЗАИМНАЯ ИНФОРМАЦИЯ.

ЦЕЛЬ ЛЕКЦИИ: На основе понятия условной энтропии дать определение взаимной информации, рассмотреть свойства и представить вывод формулы для вычисления среднего количества взаимной информации.

Измеряй все, доступное измерению, и делай недоступное измерению доступным. Галилео Галилей

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

[1]

или H(x,y) = H(x) + H_x (y)

Условная энтропия удовлетворяет следующим условиям.:

0 ≤H_x(y) ≤ H(y),

H_x(y) = 0, когда по реализации ансамбля X можно точно установить реализацию ансамбля Y;

H_x(y) = H(y), когда ансамбли Х и У независимы и знание реализации X не прибавляет информации об Y;

H(y) > H_x(y) – общий случай, когда знание реализации X снижает первоначальную неопределенность Y.

Взаимная информация.

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

Введем обозначение взаимной информации I(x,y). В соответствии со свойством 5 энтропии, можем записать соотношение

I(x,y)=H(x) – H(x,y), [2]

которое будет определять меру взаимной информации для любых пар (x,y) ансамблей Х и У.

В выражении [2] Н(х) – априорная энтропия, Н(x,y) – остаточная энтропия после получения сведений об ансамбле Х. Тогда I(x,y) будет характеризовать полную информацию, содержащуюся в ансамбле У об ансамбле Х.

Проиллюстрируем графически энтропию системы и информацию

Рис. 1 Графическое отображение взаимной информации.

Верхние раздельные овалы - при отсутствии связи между ансамблями переменных Х и У;

Нижние совмещенные овалы - при наличии статистической связи между ансамблями Х и У.

Рассмотрим ансамбли Х и У, характеризующие систему. Энтропию ансамбля Х изобразим овалом с площадью Н(Х): чем больше энтропия, тем больше площадь. Энтропия ансамбля У - второй овал с площадью Н(У). Если ансамбли статистически независимы, т.е. связь между ними отсутствует, овалы не пересекаются. Полная энтропия системы равна сумме энтропий, т. е. сумме площадей.

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

Н(Х,У) = Н(Х) + Н(У) - I(Х,Y)       [3]

Чем больше взаимная информация, тем теснее связь, тем меньше энтропия Н(Х,У).

Из свойства 5 энтропии следует

H(X,Y) = H(X) + H_X(Y)

H(X,Y) = H(Y) + H_Y(X) [4]

а также

H(X) + H_X(Y) = H(Y) + H_Y(X)

H(X) –H_X(Y) = H(Y) – H_Y(X) [5]

Сравнив [5] и [2], отметим, что выражение [5] характеризует взаимное равенство информации об ансамбле Х, если известен ансамбль У, и обратно, знание об ансамбле У, если известен ансамбль Х.

I(X,Y) – называется средней взаимной информацией, содержащейся в ансамблях Х и У.

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

1. I(X,Y) = I(Y,X). Взаимная информация симметрична.

2. I(X,Y) ≥ 0. Взаимная информация всегда положительна.

3. I(X,Y) = 0 тогда и только тогда, когда ансамбли Х и У независимы.

4. I(X,Y) = H(X) – H_X(Y) = H(Y) – H_Y(X) = H(X) + H(Y) – H(X,Y), т. е. в случае наступления совместного события H(X) + H(Y) = H(X,Y) взаимная информация отсутствует.

5. I(X,Y) ≤ min{H(X),H(Y)}. Взаимная информация не может быть больше информации о каждом ансамбле в отдельности.

6. I(X,Y) ≤ min {log‌‌ ‌‌|X|, log|Y|}. Логарифмическая мера каждого из ансамблей в отдельности больше или равна взаимной информации.

7. Взаимная информация I(X,Y) имеет максимум (является выпуклой функцией распределения вероятностей).

В общем случае свойство 4 определяет взаимную информацию через энтропию объединенной системы H(X,Y) и энтропию отдельных ее частей H(X) и H(Y) рис.1.

I(X,Y) = H(X) + H(Y) – H(X,Y) [6]

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

H(X)=M[-log P(X)], H(Y)=M[-log P(Y)], H(X,Y)=M[-log P(X,Y)] [7]

Тогда выражение [6] примет вид

I(X,Y) =M[ - logP(X) – logP(Y) + log(X,Y)].

Преобразовав, получим

[8]

Выражение [8] преобразуем с использованием свойства математического

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

У= [у=φ(х)]

представляет собой набор множества значений случайных величин. Для вычисления математического ожидания величины у необязательно знать распределение вероятностей p_y(y) для у. Если распределение p_x(x) по ансамблю Х известно, то

Тогда, если p(x_i) вероятность реализации любого из m элементов ансамбля Х, а p(y_j) вероятность реализации любого из n элементов ансамбля У, то выражение количества взаимной информации будет иметь вид

[9]

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

Марковская модель источника.

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

Случайный процесс х_1, x_2, … со значениями x_i , алфавита Х, (i = 1, 2, …) задан, если для любых n указан способ вычисления совместных распределений вероятностей p(x₁ ,…x _n). Проще всего задать случайный процесс, предположив, что его значения в различные моменты времени независимы и одинаково распределены.

где p(x_i) – вероятность появления x_i в момент i. Для описания такого процесса достаточно указать вероятности p(x) для всех x (всего IХI – 1 вероятностей). Для описания более сложных моделей процессов следует опираться на свойство стационарности, позволяющее упростить математические выкладки. Процесс называется стационарным, если для любых n и t имеет место равенство

p(x₁, …, x _n) = p( x _{1+ t} x _{n+ t}),

причем x_i = x_{1+ t}, i = 1, …n. Случайный процесс стационарен, если вероятность любой последовательности не изменится при ее сдвиге во времени. Числовые характеристики, в частности математическое ожидание, стационарных процессов не зависят от времени. Рассматривая стационарные процессы, мы можем вычислять независящие от времени информационные характеристики случайных процессов. Пример стационарного процесса – процесс, значения которого независимы и одинаково распределены.

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

К. Шеннон так определяет дискретный источник сообщений: “ Можно считать, что дискретный источник создает сообщение символ за символом. Он будет выбирать последовательные символы с некоторыми вероятностями, зависящими, вообще говоря, как от предыдущих выборов, так и от конкретного рассматриваемого символа. Физическая система или математическая модель системы, которая создает такую последовательность символов, определяемую некоторой заданной совокупностью вероятностей, называется вероятностным процессом. Поэтому можно считать, что дискретный источник представляется некоторым вероятностным процессом. Обратно, любой вероятностный процесс, который создает дискретную последовательность символов, выбираемых из некоторого конечного множества, может рассматриваться как дискретный источник”.

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

Примерами дискретного источника могут служить:

1. Печатные тексты на различных языках.

2. Непрерывные источники сообщений, которые превращены в дискретные с помощью некоторого процесса квантования (квантованная речь, телевизионный сигнал.

3. Математические случаи, когда просто определяется абстрактно некоторый вероятностный процесс, который порождает последовательность символов.

Подобные источники создают представляют собой вероятностные процессы, известные как дискретные Марковские процессы. В общем случае результат может быть описан следующим образом. Существует конечное число возможных “состояний” системы : S₁,S₂,. . . ,S_n. Кроме того, имеется совокупность переходных вероятностей pi(j), т. е. вероятностей того, что система, находящаяся в cостоянии S_i , перейдет затем в состояние S_j. Чтобы использовать этот Марковский процесс в качестве источника сообщений, нужно только предположить, что при каждом переходе из одного состояния в другое создается одна буква. Состояния будут соответствовать “остатку влияния” предшествовавших букв. В графическом примере “состоянием” является узловая точка схемы, а переходные вероятности и создаваемые при этом буквы указаны около соответствующих линий.

Такой источник из четырех букв A, B, C, В , имеющих, соответственно, переходные вероятности 0,1; 0,4; 0,3; 0,2, возвращаясь в узловую точку после

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

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

Простейшей моделью источника, порождающего зависимые сообщения, является Марковский источник. Случайный процесс называют цепью Маркова связности s, если для любых n и для любых x = (x₁, …, x_n) алфавита X справедливы соотношения

p(x) = p(x_{1 , …,}x _s )p(x _{s+ 1}/ x ₁, … , x _s)p(x_s+2/x₂, …,x_s+1)…p(x_n/x_n-s,…,x _n-1).

Марковским процессом связности s называется такой процесс, для которого при n > s p(x_n ,…, x_n-1) = p(x_n /x _n-s ,…, x_n-1), т. е. условная вероятность текущего значения при известных s предшествующих не зависит от всех других предшествующих значений.

Описание Марковского процесса задается начальным распределением вероятностей на последовательностях из первых s значений и условными вероятностями p(x_n /x_n-s ,…,x_n-1) для всевозможных последовательностей. Если указанные условные вероятности не изменяются при сдвиге последовательностей во времени, Марковская цепь называется однородной. Однородная Марковская цепь связности s = 1 называется простой цепью Маркова. Для ее описания достаточно указать распределение вероятностей p(x₁) величины х, принадлежащей множеству Х и условные вероятности

π_ij = P(x_t = j / x_t-1 = i), i,j = 0,1,…,M-1,

называемые переходными вероятностями цепи Маркова.

Переходные вероятности удобно записывать в виде квадратной матрицы размерности МхМ

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

Если p_t - стохастический вектор, компоненты которого – вероятности состояний цепи Маркова в момент времени t, т.е. p_t=[p_t(0),…,p_t(M-1)], где p_t(i) есть вероятность состояния i в момент времени t (I = 0,1,…,M-1), то из формулы полной вероятности следует

или в матричной форме

p_t+1 = p_tΠ. [ 10 ]

Для произвольного числа шагов n получим

,

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

p = pΠ. [ 2 ]

Предположим, р₁ = р. Тогда, воспользовавшись выражением [1], получим р₂ = р и, наконец, p _t = p при всех t. Таким образом, Марковская цепь стационарна, если в качестве начального распределения выбрано решение уравнения [ 2 ].

Стохастический вектор р, удовлетворяющий уравнению [ 2 ], называется стационарным распределением для цепи Маркова, задаваемой матрицей переходных вероятностей Π. Финальным распределением вероятностей называют вектор

[ 3 ]

Величина p_∞ не зависит от начального распределения и от времени, т. е. является стационарным распределением. Цепи, определяемые выражением [ 3 ], называют эргодическими. Если все элементы матрицы Π положительны и не равны нулю, соответствующая Марковская цепь эргодична. Чтобы сформулировать необходимое и достаточное условие эргодичности, введем несколько определений.

Состояние цепи i достижимо из состояния j, если для некоторого n вероятность перехода из состояния j в состояние i за n шагов положительна. Множество состояний называется замкнутым, если никакое состояние вне С не может быть достигнуто из состояния, входящего в С.

Цепь называется неприводимой, если в ней нет никаких замкнутых множеств кроме множества всех состояний. Цепь Маркова неприводима тогда и только тогда, когда состояния достижимы друг из друга. Состояние i называется периодическим, если существует такое t > 1, что вероятность перехода из i в i за n шагов равна нулю при всех n не кратных t. Цепь, не содержащая периодических состояний, называется непериодической. Непериодическая неприводимая цепь Маркова эргодична.

ЛИТЕРАТУРА.

1. Шеннон К. Работы по теории информации и кибернетике. М.: изд. “ИЛ”, 1963 г., стр. 249 – 259.

8