Лабораторна робота № 10

Тема роботи: Визначення умовної та безумовної ентропії.

Мета роботи: Навчитися обчислювати умовну та безумовну ентропію з використанням програм MathCad або Microsoft Excel.

Теоретичні відомості

Ентропія - це середньостатистична міра невизначеності відомостей спостерігача відносно стану спостережуваного об'єкта.

Кількість інформації деякого повідомлення визначається:

,

де - коефіцієнт, який узгоджує розмірності

БЕЗУМОВНА ЕНТРОПІЯ

Термін «безумовна ентропія» запозичений з математичної статистики за аналогією з безумовною ймовірністю, що стосу­ється статистичне незалежних подій, тут — повідомлень. Отже, безумовна ентропія — це кількість інформації, яка припадає на одне повідомлення джерела із статистично незалежними повідомленнями..

Якщо є дискретне джерело статистично незалежних повідомлень з ансамблем А = {а₁,а₂, ...,а_і, ...,a_k} та р = {р₁,р₂, ...,р_і ,..., p_k}, то кількість інформації (середня), що припадає на одне по­відомлення а_і є А й визначається формулою Шенона

(9.1)

є характеристикою цього джерела в цілому. Вона має фізичний зміст середньої за ансамблем невизначеності вибору джерелом повідомлення з А, причому байдуже, якого саме повідомлення, оскільки обчислення ентропії «поглинає» індекс і. Наприклад, джерело з k = 8 незалежними та рівно ймовірними повідомленнями має ентропію

біт/повідомлення.

Тут ураховано, що р_і = р= 1/8. Для нерівно ймовірних повідомлень у цьому разі Н(А)<3 біт/повідомлення.

Властивості ентропії при цьому зберігаються, тобто якщо р =1 або 0, то до ансамблю А не може входити більш як одне повідомлення. Таким чином,

або

(9.2)

де невизначеність 0 • , якщо її розкрити за правилом Лопіталя через граничний перехід, дає

Н₀(А) = 0. (9.3)

Якщо в алфавіті А буде більше, ніж одне повідомлення, то виключення a_k з А (р (a_k) = 0) лише спростить модель джерела - його ансамбль і не змінить результат обчислення ентропії Н (А) за (2.8).

Безумовна ентропія К рівноймовірних повідомлень завжди максимальна й визначається виразом

H(A) = log₂K, (9.4)

який називається формулою Хартлі, її легко дістати з формули Шеннона (9.1), поклавши р_і = 1/К для і= 1 ... К, хоча хронологічно першою була запропонована форму­ла (9.4).

Таким чином, основними властивостями безумовної ентро­пії дискретних повідомлень є такі:

• ентропія — величина дійсна, обмежена та невід'ємна;

• ентропія вірогідних повідомлень дорівнює нулю;

• ентропія максимальна, якщо повідомлення рівно ймовірні та статистично незалежні;

• ентропія джерела з двома альтернативними подіями може змінюватися від 0 до 1;

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

Умовна ентропія

Припустимо, що повідомлення а зустрічалося у довгому лан­цюзі з N=1000 повідомлень l₁ = 200 разів, повідомлення b у цьому самому ланцюзі — l₂ = 200 разів, а разом вони зустрілися лише l₃=50 разів. Скориставшись теоремою математичної статистики, можна встановити, що ймовірність появи повідомлення а в цьому ланцюзі р(а)=l₁/N=0,25, а повідомлення b – p(b)=l₂/N=0,2. Крім того, p(ab)=l₃/N=0,05. При цьому p(ab)=p(а) р (b) = 0,25 • 0,2 = 0,05, що є явною ознакою статистичної незалежності повідомлень а та b. Саме для таких повідомлень існує безумовна ентропія, про яку йшлося вище.

Коли б у цьому прикладі пара ab зустрілася l₃ = 30 разів, то виявилося б, що р (ab) = l₃/N = 0,03 < р (а) р (b). Це є ознакою порушення статистичної незалежності повідомлень а та b, яка відбиває той факт, що вони не «прагнуть» зустрічатися разом у послідовностях повідомлень, тобто поява одного з них дає підставу з більшою впевненістю не очікувати появи іншого, ніж це було б до появи першого повідомлення. Це означає, що ймовірність появи, скажімо, повідомлення b в послідовності відразу після появи повідомлення а трохи зменшується, і навпаки, хоча взагалі безумовна ймовірність р (а) чи р (b) по всій послідовності в цілому є сталою.

З іншого боку, при l₃ = 100 маємо p(ab) = l₃/N = 0,1 >p(a)p(b), що дає підставу підозрювати взаємне «тяжіння» а до b, і навпаки. Тут теж проглядається порушення статистичної незалежності, тобто відношення «байдужості» між повідомленнями а та b. Поява в послідовності одного з них, наприклад а, трохи збільшує ймовірність появи повідомлення b відразу за повідомленням а, і навпаки. Проте безумовні ймовірності p(а) та p(b) по послідовності в цілому теж є сталими.

Мірою порушення статистичної незалежності (стану «байдужості») між повідомленнями а та b є умовна ймовірність появи повідомлення а за умови, що вже з'явилося повідомлення b: p(a/b), або умовна ймовірність появи повідомлення b, коли вже з’явилося повідомлення а: р (b/a), причому взагалі p(a/b) p(b/a).

Теорія математичної статистики визначає умовну ймовірність через безумовні ймовірності р(а), р(b) та сумісну безумовну ймовірність р(ab) за законом множення ймовірностей:

р(ab)=p(a)p(b/a)=p(b)p(a/b). (9.5)

Звідси випливає, що

p (b/a) = p (ab) / p (a); p (a/b) = p (ab) / p (b). (9.6)

Зокрема, для статистично незалежних повідомлень а та b (див. вище) маємо

p (b/a) = 0,05 / 0,25 = 0,2 = р (b);

p (a/b) = 0,05 / 0,2 = 0,25 = р (а),

тобто умовні ймовірності появи повідомлень вироджуються в безумовні.

Тоді для l₃ = 30 знаходимо

p(b/а)= 0,03/0,25 = 0,12; р (a/b) = 0,03/0,2 = 0,15,

тобто встановлений факт появи повідомлення а зменшує безумовну ймовірність p (b) = 0,2 до умовної ймовірності р (b/a) = 0,12 появи повідомлення b за умови наявного вже повідомлення а. І навпаки, факт появи повідомлення b зменшує безумовну ймовірність p(а) = 0,25 до умовної ймовірності p(a/b)=0,15 появи повідомлення а за умови наявності повідомлення b. Як бачимо, ймовірність появи повідомлення b зменшується на 0,08, а повідомлення а — на 0,1 кожного разу, як інше з них з'явиться в послідовності.

Аналогічно стосовно наведеного вище прикладу з l₃ = 100

р (b/a) = 0,1/0,25 = 0,4; p(а/b) = 0,1/0,2 = 0,5,

що підкреслює згадане вище «тяжіння» а та b одне до одного через підсилення ймовірностей появи їх.

Ці локальні порушення ймовірностей при статистичній залеж­ності повідомлень не можуть бути непоміченими джерелом. І воно на них реагує відповідним зменшенням або збільшенням кількості інформації в кожному такому повідомленні. Звісно й ентропія такого джерела має змінюватися належним чином, причому називається вона умовною, визначається виразом (9.7), але з урахуванням умовних ймовірностей повідомлень.

(9.7)

Розрізняють два різновиди умовної ентропії: часткову та загальну. Першу знаходять так:

(9.8)

(9.9)

де A = {a₁, a₂, ...,a_і.,..., a_k}, В = {b₁, b₂,..., b_j ..., b_l} — алфавіти повідомлень; a_і— конкретне повідомлення, відносно якого визначається часткова умовна ентропія Н(В/а_і) алфавіту В за умови вибору попереднього повідомлення а_і; b_j — конкретне повідомлення, відносно якого обчислюється часткова умовна ентропія Н (A/b_j) алфавіту А за умови вибору попереднього повідомлення b_j, і — номер повідомлення з алфавіту A; j — но­мер повідомлення з алфавіту В; р (a/b), p (b/а) — умовні ймовірності.

Загальна умовна ентропія можна визначається так : якщо часткова умовна ентропія джерела А відносно конкретного повідомлення b_j дорівнює H (A/b_j), a розподіл ймовірностей Р_B джерела В задано ансамблем В iз Р_B = = {p (b₁), ....,p (b_j),...p (b_k)}, то цілком природно обчислити середнє по j значення H (A/b_j) за всіма j як статистичне усереднення методом зваженої суми, тобто

(9.10)

де H(А/В) — загальна умовна ентропія джерела А відносно джерела В. Це питома (середньо статична) кількість інформації, що припадає на будь-яке повідомлення джерела А, якщо відомо його статистичну взаємозалежність із джерелом В.

Аналогічно (9.10) загальна умовна ентропія джерела В відносно джерела А визначається виразом

(9.11)

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

Ентропію об’єднання двох джерел можна визначити за формулою :

Н(А,В) = Н(А) + Н (В/А) = Н(А,В) = Н(В) + Н (А/В) (9.12)