Лекція взаємна інформація

МЕТА ЛЕКЦІЇ: На основі поняття умовної ентропії дати визначення взаємної інформації, розглянути властивості і представити висновок формули для обчислення середньої кількості взаємної інформації.

Виміряй все, доступне вимірюванню, і роби недоступне виміру доступним. Галілео Галілей

У попередній лекції наведено визначення умовної ентропії як величини, яка б показала, яка в середньому невизначеність вибору значення деякої величини у. коли відомо значення х.

Умовна ентропія задовольняє таким умовам .:

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

Введемо позначення взаємної інформації I (x, y). Відповідно до властивістю 5 ентропії, можемо записати співвідношення

Проілюструємо графічно ентропію системи та інформацію

Мал. 1 Графічне відображення взаємної інформації.

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

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

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

Якщо ж між ансамблями виникає статистичний зв'язок (кореляція), то овали на схемі перетинаються. Виникла взаємна інформація I (Х, У) і є кількісна міра цього перетину. Ентропія зменшується на величину цієї інформації:

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

З властивості 5 ентропії слід

Порівнявши [5] і [2], відзначимо, що вираз [5] характеризує взаємне рівність інформації про ансамбль Х. якщо відомий ансамбль У. і назад, знання про ансамбль У, якщо відомий ансамбль Х.

Властивості взаємної інформації.

I (X, Y) ≤ min. Взаємна інформація не може бути більше інформації про кожен ансамблі окремо.

I (X, Y) ≤ min. Логарифмічна міра кожного з ансамблів окремо більше або дорівнює взаємної інформації.

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

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

Тоді вираз [6] набуде вигляду

Вираз [8] перетворимо з використанням властивості математичного

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

являє собою набір безлічі значень випадкових величин. Для обчислення математичного очікування величини у необов'язково знати розподіл ймовірностей py (y) для у. Якщо розподіл px (x) по ансамблю Х відомо, то

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

Марковська модель джерела.

Розглянемо випадкові послідовності з довільного числа подій. Якщо елементи випадкової послідовності - речові числа, то такі послідовності називаються випадковими процесами. Номер елемента в послідовності трактується як момент часу, в який з'явився дане значення. У загальному випадку безліч значень часу може бути безперервним або дискретним, безліч значень випадкової послідовності може бути також безперервним або дискретним

де p (xi) - імовірність появи xi в момент i. Для опису такого процесу досить вказати ймовірності p (x) для всіх x (всього IХI- 1 ймовірностей). Для опису більш складних моделей процесів слід спиратися на властивість стаціонарності, що дозволяє спростити математичні викладки. Процес називається стаціонарним, якщо для будь-яких n і t має місце рівність

причому xi = x1 + t, i = 1, ... n. Випадковий процес стационарен, якщо ймовірність будь-якій послідовності не зміниться при її зсуві в часі. Числові характеристики, зокрема математичне очікування, стаціонарних процесів не залежать від часу. Розглядаючи стаціонарні процеси, ми можемо обчислювати незалежні від часу інформаційні характеристики випадкових процесів. Приклад стаціонарного процесу - процес, значення якого незалежні і однаково розподілені.

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

К. Шеннон так визначає дискретне джерело повідомлень: "Можна вважати, що дискретний джерело створює повідомлення символ за символом. Він буде вибирати послідовні символи з деякими можливостями, залежними, взагалі кажучи, як від попередніх виборів, так і від конкретного розглянутого символу. Фізична система або математична модель системи, яка створює таку послідовність символів, яка визначається деякою заданою сукупністю ймовірностей, називається імовірнісним процесом. Тому можна вважати, що дискретний джерело представляється деяким імовірнісним процесом. Назад, будь імовірнісний процес, який створює дискретну послідовність символів, які обирають з деякого кінцевого безлічі, може розглядатися як дискретний джерело ".

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

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

Друковані тексти на різних мовах.

Безперервні джерела повідомлень, які перетворені в дискретні за допомогою деякого процесу квантування (квантованими мова, телевізійний сигнал.

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

Подібні джерела створюють являють собою ймовірні процеси, відомі як дискретні Марковские процеси. У загальному випадку результат може бути описаний таким чином. Існує кінцеве число можливих "станів" системи: S1, S2.Sn. Крім того, є сукупність перехідних ймовірностей pi (j), т. Е. Ймовірностей того, що система, яка перебуває в cостояние Si. перейде потім в стан Sj. Щоб використовувати цей Марковський процес в якості джерела повідомлень, потрібно тільки припустити, що при кожному переході з одного стану в інший створюється одна буква. Стану будуть відповідати "залишку впливу" передували букв. У графічному прикладі "станом" є вузлова точка схеми, а перехідні ймовірності та створювані при цьому літери вказані близько відповідних ліній.

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

створення чергової літери, може формувати як кінцеві, так і нескінченну послідовності.

На дискретний джерело можна поширити такі характеристики випадкового сигналу, як ергодичність і стаціонарність. Вважаючи джерело ергодичним, можна "... ототожнювати середні значення уздовж деякої послідовності із середнім значенням по ансамблю можливих послідовностей (причому ймовірність розбіжності дорівнює нулю)". Наприклад, відносна частота букви А в приватній нескінченної послідовності буде з ймовірністю одиниця дорівнювати її відносної частоті по ансамблю послідовностей.

Найпростішою моделлю джерела, що породжує залежні повідомлення, є Марковський джерело. Випадковий процес називають ланцюгом Марковасвязностіs, якщо для будь-яких n і для будь-яких x = (x1, ..., xn) алфавіту X справедливі співвідношення

Опис Марківського процесу задається початковим розподілом ймовірностей на послідовностях з перших s значень і умовними ймовірностями p (xn / xn-s, ..., xn-1) для всіляких послідовностей. Якщо зазначені умовні ймовірності не змінюються при зсуві послідовностей в часі, Марковська ланцюг називається однорідною. Однорідна Марковська ланцюг зв'язності s = 1 називається простий ланцюгом Маркова. Для її опису досить вказати розподіл ймовірностей p (x1) величини х, що належить безлічі Х і умовні ймовірності

звані перехідними ймовірностями ланцюга Маркова.

Перехідні ймовірності зручно записувати у вигляді квадратної матриці розмірності мхм

званої матрицею перехідних ймовірностей. Ця матриця - стохастична (неотрицательная, сума елементів кожного рядка дорівнює 1).

або в матричної формі

Для довільного числа кроків n отримаємо

,

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

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

Величина p∞ не залежить від початкового розподілу і від часу, т. Е. Є стаціонарним розподілом. Ланцюги, що визначаються виразом [3], називають ергодичними. Якщо всі елементи матриці Π позитивні і не дорівнюють нулю, відповідна Марковська ланцюг ергодичності. Щоб сформулювати необхідна і достатня умова ергодичності, введемо кілька визначень.

Стан ланцюга iдостіжімо зі стану j, якщо для деякого n ймовірність переходу зі стану j в стан i за n кроків позитивна. Безліч станів називається замкнутим. якщо ніяке стан поза С не може бути досягнуто зі стану, що входить в С.

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

1. Шеннон К. Роботи по теорії інформації і кібернетики. М. изд. "ІЛ", 1963 р. Стор 249 - 259.