2. Ентропія по Шеннону.

Ідеї Хартлі розвинув і узагальнив американський вчений Клод Шенон в науковій праці „Математична теорія зв’язку”. Клод Шенон підійшов з ймовірних позицій вимірювання інформації, враховуючи ту обставину, що в переважній більшості випадків доводиться мати справу з такими системами, стани яких не є рівно ймовірними (рівно можливими).

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

Нехай запущено на ПК програму–генератор, яка на екрані монітора може демонструвати появу будь-якої букви із заданого алфавіту X (X₁, X₂, … X_m). Кожна буква появляється на екрані згідно із ймовірністю її появи p(x_i). Нехай на екрані послідовно появилась послідовність із n букв (n досить велике число, значно більше за m). Якщо нас зацікавить буква x_i, то вона на екрані з’явиться приблизно (n∙p(x_i) разів. Кожна поява на екрані букви x_i дає за формулою (1.4) кількість інформації, що дорівнює біт. Усього (за всі появи букви x_i) буде одержано (–n∙p(x_i)∙log₂(p(x_i)) бітів інформації.

Загальна кількість інформації, яку потрібно просумувати після демонстрації цієї послідовності із n букв, дорівнює:

(біт) (1.5)

Співвідношення (1.5) було одержано в 1948 р. К.Шеноном для визначення середньої кількості інформації у повідомленні, що складається із незалежних і нерівноймовірних елементів. Якщо всі стани системи є рівноймовірними, тобто

p(x₁)=p(x₂)=…=p(x_m)= ,

то I=

Отже, з (1.5), як окремий випадок, при n=1, одержується формула Хартлі (1.3). Саме формулу (1.5) вивів, виходячи з імовірнісних позицій, Клод Шенон.

Основними поняттями започаткованої Шеноном статистичної теорії інформації, яка викладена в роботі „Математична теорія зв’язку” є введене ним поняття інформаційної ентропії.

Ентропія в теорії інформації є мірою невизначеності, яка існує при одержанні повідомлень. Свою назву міра невизначеності одержала завдяки зовнішній схожості з термодинамічною ентропією. Пригадаймо з курсу фізики формулу , де k – коефіцієнт Больцмана (k=1,38∙10^-16 ерг/град), яка відома в термодинаміці як ентропія чи міра хаосу, безладдя в системі. Завдяки зовнішній схожості міри невизначеності і термодинамічної ентропії Джон фон Нейман (один з основоположників обчислювальної техніки) запропонував Шенону використати термін „ентропія” і в обчислювальній техніці. При цьому він жартома зауважив: „що таке ентропія не знає ніхто”.

Згідно з основним положенням статистичної теорії інформації, будь-яке повідомлення, що буде передаватися, є результатом випадкового вибору із множини можливих повідомлень даного типу. Оскільки вибір є випадковим, то існує невизначеність, яка знімається тільки після одержання повідомлення. Міра невизначеності для одержувача інформації залежить від того, наскільки великим є вибір із множини можливих повідомлень.

Ентропія, як оцінка невизначеності, відображає здатність матеріального джерела проявляти все нові і нові стани і таким чином генерувати інформацію. Інформація за Шеноном — це повідомлення, яке зменшує невизначеність системи (події), що існувала до одержання повідомлення.

Зміст ентропії полягає в тому, що її збільшення означає зменшення впорядкованості системи. Безладною система залишається тільки тоді, коли про неї дуже мало знаємо. Ентропія такої системи для нас велика. З набуттям нових знань про систему, з надходженням певної інформації, ентропія системи зменшується. Отже, надходження інформації сприяє зменшенню ентропії. Це зменшення пропорційне інформації, яка надходить. Таким чином, за міру інформації можна взяти певну кількість ентропії, яка відповідає цій інформації.

Нехай є система X з дискретною множиною можливих станів x₁, x₂, …, x_m, які утворюють повну групу подій з відповідними ймовірностями p(x₁), p(x₂), …, p(x_m). Тоді функцію

(1.6)

де логарифми беруться при довільній, але у всіх випадках одній і тій же основі a, Шенон назвав ентропією системи X.

При p(x_i)=0 завжди приймають, що і p(x_i)∙log p(x_i)=0. Цій функції притаманні властивості, які є необхідними для міри невизначеності систем.

1. Ентропія є дійсною і додатною функцією аргументів p(x_i), що змінюються в інтервалі від 0 до 1.

2. Ентропія H(X)=0 тоді, коли одне із значень p(x₁), p(x₂), …, p(x_m) дорівнює одиниці, а всі інші – нулю. Але це саме той випадок, коли результат випробовування може бути передбачений заздалегідь з певною достовірністю. Але в цьому випадку невизначеність системи відсутня, вона рівна нулю.

3. Функція H(X) набирає максимального значення log_am, коли стани системи рівноймовірні, тобто коли p(x₁)= p(x₂)=…= p(x_m)= .

4. Невизначеність складеної системи дорівнює сумі невизначеності її незалежних складових (властивість адитивності для незалежних систем X і Y). H(X,Y)=H(X)+H(Y).

5. Ентропія H(X) неперервно залежить від ймовірностей станів системи X, тобто при досить малій зміні ймовірностей x_i (i=1, 2,…, m) ентропія змінюється дуже мало.

6. Ентропія системи, яка має тільки два нерівноймовірні стани (m=2), може змінюватися від нуля до одиниці.

Шенон довів єдність існування ентропії (1.6) для системи X.

Як зазначено в самому означенні ентропії, основа логарифма в (1.6) відповідає одиниці вимірювання ентропії. Якщо a=2, то ентропія вимірюється в бітах, а якщо a=10 – в десяткових одиницях або дітах, якщо a=e – в натуральних одиниця або нітах.

Найбільш поширеними є двійкові одиниці вимірювання. Тому в наступному будемо розглядати ентропію (1.4) при основі логарифма a=2.

(1.7)

Із порівняння формул (1.5) та (1.7) випливає, що

I = n∙H(X) (1.8),

де I – кількість інформації у повідомленні із n елементів, а H(X) – ентропія на один елемент повідомлення.

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

Як тільки повідомлення одержано, невизначеність повністю знімається. Отже, після прийому повідомлення відбувається зменшення ентропії від H(X) до нуля, а з другого боку – одержання інформації від нуля до I (при n=1). Тому кількість інформації тут чисельно дорівнює апріорній ентропії системи.

Зазначимо, що Клод Шенон фактично не робив різниці між ентропією і кількістю інформації, а Норберт Вінер підкреслював, що кількість інформації – це деяка від’ємна ентропія.

Основними позитивними сторонами формул Шенона (1.5), (1.6) є їх абстрагування від семантичних і якісних, індивідуальних властивостей системи. На відміну від формул Хартлі формули Шенона враховують різноймовірність станів системи, структуру повідомлень (мають статистичний характер). Формули зручні для практичних обчислень.

Справжня цінність Шенонівського поняття ентропії полягає в тому, що виражена нею „ступінь невизначеності події„ (стану системи) виявляється в багатьох випадках саме тією характеристикою, яка відіграє важливу роль в різноманітних процесах, які зустрічаються в природі і техніці, або так чи інакше пов’язаних з передачею та зберіганням інформації.

За Шеноном кількість інформації у повідомленні визначається за формулою

I=H₀-H₁, (1.9)

де H₀ – ентропія системи до одержання повідомлення, а H₁ – ентропія системи після одержання повідомлення. Для випадку, коли стани системи рівнонеймовірні і незалежні, H₀ і H₁ вимірюються за формулою (1.3).

Приклад 1. На факультеті 512 студентів, серед них 64 – відмінників. Яку кількість інформації несе повідомлення „Перше місце на олімпіаді зайняв студент-відмінник”?

За формулою (1.2) одержимо

H₀=log₂512=log₂2⁹=9 (біт)

H₁=log₂64=log₂2⁶=6 (біт)

За формулою (1.9) одержимо

І=9-6=3 (біти)

Приклад 2. Клавіатура ПК має 103 клавіші. Яку кількість інформації несе повідомлення „Набрано текст із 12 великих латинських букв”?

Згідно з теоремою про кількість слів довжини n над алфавітом потужності n, маємо: [11, с.26]

H₀=log₂103¹²=12∙log₂103≈80,2 (біт)

H₁=log₂26¹²=12∙log₂26≈56,4 (біт)

За формулою (1.12) одержуємо

І=80,2-56,4=23,8 (біт)

Приклад 3. В двох урнах є по 40 кульок. В першій урні – 10 білих, 10 червоних і 20 жовтих. В другій урні – 15 білих, 20 червоних і 5 жовтих. Із кожної урни виймають по одній кульці. В якому із цих випробовувань більше невизначеності?

,

p(x₂)=0,25,

Обрахуємо H(X) та H(Y) за формулою (1.7).

H(X) = – (0,25log₂0,25+0,25log₂0,25+0,5log₂0,5)= = (0,34666+0,34666+0,34657)/0,6934=1,5

H(Y) = – (0,375log₂0,375+0,5log₂0,5+0,125log₂0,125)= = (0,98002+0,34657+0,34666)/0,694=1,4056

Отже, більше невизначеності у першому випробуванні.

Приклад 4. Дано частотний словник української мови

Таблиця 2

Буква	Частота	Буква	Частота	Буква	Частота
а, і	0,062	к	0,022	ф	0,0018
б, ь	0,014	л, м	0,026	х	0,009
в	0,035	т, н	0,053	ц, щ	0,008
г	0,065	о	0,090	ч	0,013
д	0,025	п	0,023	я	0,018
е, є	0,072	р	0,040	й	0,012
ж, ю, ч	0,010	с	0,045	ї	0,062
з, и	0,016	у	0,021	ґ	0,040

Яку кількість інформації містить слово „ХЛІБ”?

І = – 4(0,009log₂0,009+0,026log₂0,026+0,062log₂0,062+0,014log₂0,014)= = –4 (-0,5342) = 2,132.