Раздел «Образование».FIVTLecturesTerm4Lecture08:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Следующая лекция
Предыдущая лекция

Лекция 8. Теория информации. Взаимная информация двух случайных величин. Понятие информационного канала.

Зависимые случайные величины

Взаимная информация двух случайных величин E и V равна сумме энтропий H(E) + H(V) минус этропия случайной величины E x V:

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

Этой картинке можно придать точный смысл. Но пока мы ограничимся интуитивным восприятием. Плошадь кружочков равна H(E) и H(V). Общая площадь объединённых кружочков равна H(E x V). Взаимная информация — это площадь пересечение двух кружочков. В сумме H(E) + H(V) площадь пересечения посчитана дважды. Поэтому H(E) + H(V) - H(E x V) даёт площадь пересечения.

Пусть случайная величина E принимает значения i из множества {1,2, ..., n} с вероятностями P(E,i), а случайная величина V принимает значения j из множества {1,2,..,m} c вероятностями P(V,i). Если случайные величины независимы, то случайная величина E x V (случайная величина, чьи значения есть пара (i,j) - результаты измерения случаных величин E и V) имеет следующие вероятности:

Задача 1. Покажите, что

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

оказажется > 0. Чем выше эта величина, тем больше будет вероятность верного прогноза температуры по давлению и наоборот.

Задача 2. Покажите, что взаимная информация ограничена сверху H(V) и H(E), то есть

Доказательство может быть основано на простом факте:

То есть, когда мы "включаем детализацию" и вместо множества значений {холодно, нормально, горячо} начинаем различать детали — {очень холодно, средне холодно, слегка холодно, нормально, слегка горячо, ..}, энтропия распределения может только увеличиться.

Информационный канал. Пропускная способность

Информационный канал — это две зависимые случайные величины E и V, она из которых (V) называется входом, а другая (E) — выходом. Информационный канал задается матрицей условных вероятностей

В качестве примера, можно привести канал, который проводит биты и имеет помехи — с вероятностью p он инвертирует 0 и с вероятностью q он инвертирует 1.

  P = | 1-p    q    |
      |             |
      | p      1-q  |

Обратите внимание, что информационный канал не задаёт распределения самих случайных величин E и V. Он лишь определяет их связь — условные вероятности значений на выходе при известном значении на входе.

Задача 3. Найдите взаимную вероятность случайных величин E и V с указанной выше матрицей условных вероятностей P для следующих случаев:

Задача 4. Найдите максимум взаимной информации двух случайных величин, связанных матрицей P Укажите значения P(V,0) и P(V, 1) на которых достигается максимум.

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

Канал с одинаковыми вероятностями инвертирования 0 и 1 задается матрицей A(p):

  A(p) = | 1-p    q    |
         |             |
         | p      1-q  |

Задача 5. Найдите аналитическую функцию значения пропускной способности канала A(p). Нарисуйте график.
Ответ: C(p) = 1 - H(p)
capacity.png

Какова пропускная способность абсолютного лгуна (человека, который всегда врет)?

Две другие формулы взаимной информации

Формулу

после несложных манипуляций с суммами можно преобразовать в такие формулы:

Отметим, что обе формулы имеют симметричные варианты (E и V Меняются местами).

Геометрическая иллюстрация значения пропускной способности битового канала

H_capacity.png

Задачи на вычисление взаимной информации

Было произведено несколько измерений пары случайных величин (x,y). Множество всех измерений отображено на рисунке. Оцените взаимную информацию x и y (A,B,C,D — четыре разные задачи).