Інформаційна ентропія

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

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

Історія

У 1946 американський вчений-статистик Джон Тьюкі запропонував назву БІТ (BIT - абревіатура від BInary digiT), одне з головних понять XX століття. Тьюки обрав біт для позначення одного двійкового розряду, здатного приймати значення 0 або 1. Шеннон використав біт як одиницю виміру інформації. Мірою кількості інформації Шеннон запропонував вважати функцію, названу ним ентропією.

Нехай повідомлення - осмислене українською мовою. Шеннон зауважив, що при передачі різних букв ми передаємо різну кількість інформації. Якщо ми передаємо букви, що часто зустрічаються, то інформації менше; при передачі рідкісних букв - більше. Це видно при кодуванні букв алфавіту азбукою Морзе. Найчастіші літери передаються коротко, а для рідкісних використовують більш довгі ланцюжки. Так, буква «Е» кодується однією точкою «.», а рідкісна «Ш» - чотирма тире «----» (це найдовша послідовність на букву в азбуці Морзе).

Кількість інформації на букву пов'язано з частотою вживань цієї букви у всіх повідомленнях, які формуються на мові. Чим більше рідкісну букву ми передаємо, тим більше в ній інформації.

Ентропія - міра непередбачуваності. Це поняття Шеннон взяв із статистичної термодинаміки. Нехай імовірність i-того символу алфавіту, що складається з n символів (міра частоти, з якою зустрічається символ у всіх повідомленнях мови), дорівнює p_i.

Шеннон пише: «Величина H грає центральну роль в теорії інформації як міра кількості інформації, можливості вибору і невизначеності». Кількість інформації, що передається в повідомленні, тісно пов'язане з мірою невизначеності, або непередбачуваності переданих символів.

Визначення

Ентропія $H_r(S)$ (за основою $r$) джерела інформації $S$ обчислюється за формулою:

$H_r(S) = \sum_{i=1}^q p_i \log_r \left(\frac{1}{p_i}\right),$

де $p_i$ — ймовірність отримання символу $s_i$, $q$ — кількість символів в алфавіті.

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

$H_2(2) = \frac{1}{2} \log_2 2 + \frac{1}{2} \log_2 2 = 1$.

Тобто інформаційна ентропія такої комірки дорівнює 1.

Властивості

• Ентропія завжди невід'ємна
• Ентропія максимальна, якщо значення x_i випадкової величини X рівноймовірні
• Максимальне значення ентропії H_max(X)=log_aN

Див. також

• Теорія кодування