Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

Інформаційна ентропія - міра невизначеності або непередбачуваності інформації, невизначеність появи будь-якого символу первинного алфавіту. При відсутності інформаційних втрат чисельно дорівнює кількості інформації на символ переданого повідомлення.

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

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

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


1. Формальні визначення

Інформаційна двійкова ентропія для незалежних випадкових подій x з n можливими станами (від 1 до n , p - Функція ймовірності) розраховується за формулою:

H (x) =- \ sum_ {i = 1} ^ np (i) \ log_2 p (i).

Ця величина також називається середньої ентропією повідомлення. Величина \ Log_2 \ frac {1} {p (i)} називається приватної ентропією, що характеризує тільки i -E стан.

Таким чином, ентропія події x є сумою з протилежним знаком усіх творів відносних частот появи події i , Помножених на їх же виконавчі логарифми [1]. Це визначення для дискретних випадкових подій можна розширити для функції розподілу ймовірностей.


1.1. Визначення по Шеннону

Шеннон припустив, що приріст інформації дорівнює втраченої невизначеності, і поставив вимоги до її виміру:

  1. міра повинна бути безперервною; тобто зміна значення величини ймовірності на малу величину повинно викликати мале результуюче зміна функції;
  2. у випадку, коли всі варіанти (букви в наведеному прикладі) рівноймовірно, збільшення кількості варіантів (букв) повинно завжди збільшувати значення функції;
  3. повинна бути можливість зробити вибір (у нашому прикладі літер) за два кроки, в яких значення функції кінцевого результату повинно бути сумою функцій проміжних результатів.

Тому функція ентропії H повинна відповідати умовам:

  1. H (p_1, \; \ ldots, \; p_n) визначена і неперервна для всіх p_1, \; \ ldots, \; p_n , Де p_i \ in [0, \; 1] для всіх i = 1, \; \ ldots, \; n і p_1 + \ ldots + p_n = 1 . (Неважко бачити, що ця функція залежить тільки від розподілу ймовірностей, але не від алфавіту.)
  2. Для цілих позитивних n , Має виконуватися наступне нерівність:
  3. Для цілих позитивних b i , Де b_1 + \ ldots + b_k = n , Має виконуватися рівність:
    H \ underbrace {\ left (\ frac {1} {n}, \; \ ldots, \; \ frac {1} {n} \ right)} _n =

Шеннон показав, що єдина функція, яка задовольняє цим вимогам, має вигляд:

-K \ sum_ {i = 1} ^ np (i) \ log_2 p (i),

де K - Константа (і насправді потрібна тільки для вибору одиниць виміру).

Шеннон визначив, що вимірювання ентропії ( H =- p_1 \ log_2 p_1-\ ldots-p_n \ log_2 p_n ), Що застосовується до джерела інформації, може визначити вимоги до мінімальної пропускної здатності каналу, необхідної для надійної передачі інформації у вигляді закодованих двійкових чисел. Для виведення формули Шеннона необхідно обчислити математичне сподівання "кількості інформації", що міститься в цифрі з джерела інформації. Міра ентропії Шеннона висловлює невпевненість реалізації випадкової змінної. Таким чином, ентропія є різницею між інформацією, що міститься у повідомленні, та тією частиною інформації, яка точно відома (або добре передбачувана) в повідомленні. Прикладом цього є надмірність мови - є явні статистичні закономірності в появі букв, пар послідовних літер, трійок і т. д. (див. ланцюга Маркова).

Визначення ентропії Шеннона пов'язане з поняттям термодинамічної ентропії. Больцман і Гіббс проробили велику роботу по статистичної термодинаміки, яка сприяла прийняттю слова "ентропія" в інформаційну теорію. Існує зв'язок між термодинамічною та інформаційної ентропією. Наприклад, демон Максвелла також протиставляє термодинамічну ентропію інформації, і отримання якої-небудь кількості інформації одно втраченої ентропії.


1.2. Визначення за допомогою власної інформації

Також можна визначити ентропію випадкової величини, ввівши попередньо поняття розподілу випадкової величини X , Що має кінцеве число значень: [2]

P_X (x_i) = p_i, \ quad p_i \ geqslant 0, \; i = 1, \; 2, \; \ ldots, \; n
\ Sum_ {i = 1} ^ n p_i = 1

і власною інформацією :

I (X) = - log P X (X).

Тоді ентропія визначається як:

H (X) = E (I (X)) =- \ sum_ {i = 1} ^ n p (i) \ log p (i).

Від підстави логарифма залежить одиниця виміру інформації та ентропії: біт, Тріт, нат або Хартлі.


2. Властивості

Ентропія є кількістю, визначеним у контексті ймовірнісної моделі для джерела даних. Наприклад, кидання монети має ентропію - 2 (0,5 log 2 0,5) = 1 біт на одне кидання (за умови його незалежності). У джерела, який генерує рядок, що складається лише з літер "А", ентропія дорівнює нулю: - \ Sum_ {i = 1} ^ \ infty \ log_2 1 = 0 . Так, наприклад, досвідченим шляхом можна встановити, що ентропія англійського тексту дорівнює 1,5 біт на символ, що звичайно буде змінюватись для різних текстів. Ступінь ентропії джерела даних означає середнє число бітів на елемент даних, необхідних для її зашифровки без втрати інформації, при оптимальному кодуванні.

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

2.1. Математичні властивості

  1. Позитивність: H (X) \ geqslant 0 .
  2. Обмеженість: H (X) =-E (\ log_2 p_i) = \ sum_ {i = 1} ^ n p_i \ log_2 \ frac {1} {p_i} = \ sum_ {i = 1} ^ n p_i f (g_i) \ leqslant f \ left (\ sum_ {i = 1} ^ n p_i g_i \ right) = \ log_2 n , Що випливає з нерівності Йєнсена для ввігнутої функції f (g i) = log 2 g i і g_i = \ frac {1} {p_i} . Якщо все n елементів з X рівноймовірно, H (X) = log 2 n .
  3. Якщо X, \; Y незалежні, то H (X \ cdot Y) = H (X) + H (Y) .
  4. Ентропія - опукла вгору функція розподілу ймовірностей елементів.
  5. Якщо X, \; Y мають однакове розподіл ймовірностей елементів, то H (X) = H (Y) .

2.2. Ефективність

Алфавіт може мати імовірнісний розподіл далеке від рівномірного. Якщо вихідний алфавіт містить n символів, тоді його можна порівняти з "оптимізованим алфавітом", ймовірнісний розподіл якого рівномірне. Співвідношення ентропії вихідного і оптимізованого алфавіту - це ефективність вихідного алфавіту, яка може бути виражена у відсотках. Ефективність вихідного алфавіту з n символами може бути також визначена як його n -Арная ентропія.

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


3. Варіації і узагальнення

3.1. B-арная ентропія

У загальному випадку b-арная ентропія (де b дорівнює 2, 3, ...) джерела \ Mathcal {S} = (S, \; P) з вихідним алфавітом S = \ {a_1, \; \ ldots, \; a_n \} і дискретним розподілом ймовірності P = \ {p_1, \; \ ldots, \; p_n \}, де p i є ймовірністю a i ( p i = p (a i) ), Визначається формулою:

H_b (\ mathcal {S}) =- \ sum_ {i = 1} ^ n p_i \ log_b p_i.

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

Якщо слідування символів алфавіту не незалежно (наприклад, під французькою мовою після букви "q" майже завжди слід "u", а після слова "передовик" в радянських газетах зазвичай слід було слово "виробництва" або "праці"), кількість інформації, яку несе послідовність таких символів (а, отже, і ентропія ), очевидно, менше. Для обліку таких фактів використовується умовна ентропія.

Умовної ентропією першого порядку (аналогічно для Марковської моделі першого порядку) називається ентропія для алфавіту, де відомі ймовірності появи однієї букви після іншої (тобто, ймовірно двобуквений сполучень):

H_1 (\ mathcal {S}) =- \ sum_i p_i \ sum_j p_i (j) \ log_2 p_i (j),

де i - Це стан, що залежить від попереднього символу, і p i (j) - Це ймовірність j за умови, що i був попереднім символом.

Наприклад, для російської мови без букви "е" H_0 = 5, \; H_1 = 4 {,} 358, \; H_2 = 3 {,} 52, \; H_3 = 3 {,} 01 [3].

Через приватну і загальну умовні ентропії повністю описуються інформаційні втрати при передачі даних в каналі з перешкодами. Для цього застосовуються так звані канальні матриці. Для опису втрат з боку джерела (тобто відомий посланий сигнал) розглядають умовну ймовірність p (b_j \ mid a_i) отримання приймачем символу b j за умови, що був відправлений символ a i . При цьому канальна матриця має такий вигляд:

b 1 b 2 ... b j ... b m
a 1 p (b_1 \ mid a_1)p (b_2 \ mid a_1) ... p (b_j \ mid a_1) ... p (b_m \ mid a_1)
a 2 p (b_1 \ mid a_2)p (b_2 \ mid a_2) ... p (b_j \ mid a_2) ... p (b_m \ mid a_2)
... ... ... ... ... ... ...
a i p (b_1 \ mid a_i)p (b_2 \ mid a_i) ... p (b_j \ mid a_i) ... p (b_m \ mid a_i)
... ... ... ... ... ... ...
a m p (b_1 \ mid a_m)p (b_2 \ mid a_m) ... p (b_j \ mid a_m) ... p (b_m \ mid a_m)

Очевидно, ймовірно, розташовані по діагоналі, описують ймовірність правильного прийому, а сума всіх елементів стовпця дає ймовірність появи відповідного символу на стороні приймача - p (b j) . Втрати, що припадають на переданий сигнал a i , Описуються через приватну умовну ентропію:

H (B \ mid a_i) =- \ sum_ {j = 1} ^ mp (b_j \ mid a_i) \ log_2 p (b_j \ mid a_i).

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

H (B \ mid A) = \ sum_i p (a_i) H (B \ mid a_i).

H (B \ mid A) означає ентропію з боку джерела, аналогічно розглядається H (A \ mid B) - Ентропія з боку приймача: замість p (b_j \ mid a_i) всюди вказується p (a_i \ mid b_j) (Підсумовуючи елементи рядка можна отримати p (a i) , А елементи діагоналі означають імовірність того, що був відправлений саме той символ, який отриманий, то є ймовірність правильної передачі).


3.3. Взаємна ентропія

Взаємна ентропія або ентропія об'єднання призначена для розрахунку ентропії взаємопов'язаних систем (ентропії спільного появи статистично залежних повідомлень) і позначається H (A B) , Де A характеризує передавач, а B - Приймач.

Взаємозв'язок переданих та отриманих сигналів описується імовірностями спільних подій p (a i b j) , І для повного опису характеристик каналу потрібно тільки одна матриця:

p (a 1 b 1) p (a 1 b 2) ... p (a 1 b j) ... p (a 1 b m)
p (a 2 b 1) p (a 2 b 2) ... p (a 2 b j) ... p (a 2 b m)
... ... ... ... ... ...
p (a i b 1) p (a i b 2) ... p (a i b j) ... p (a i b m)
... ... ... ... ... ...
p (a m b 1) p (a m b 2) ... p (a m b j) ... p (a m b m)

Для більш загального випадку, коли описується не канал, а в цілому взаємодіючі системи, матриця необов'язково повинна бути квадратною. Очевидно, сума всіх елементів стовпця з номером j дає p (b j) , Сума рядка з номером i є p (a i) , А сума всіх елементів матриці дорівнює 1. Спільна ймовірність p (a i b j) подій a i і b j обчислюється як добуток вихідної і умовної ймовірності:

p (a_ib_j) = p (a_i) p (b_j \ mid a_i) = p (b_j) p (a_i \ mid b_j).

Умовні ймовірності виробляються за формулою Байеса. Таким чином, є всі дані для обчислення ентропій джерела і приймача:

H (A) =- \ sum_i \ left (\ sum_j p (a_i b_j) \ log \ sum_j p (a_i b_j) \ right),
H (B) =- \ sum_j \ left (\ sum_i p (a_i b_j) \ log \ sum_i p (a_i b_j) \ right).

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

H (A B) = - Σ Σ p (a i b j) log p (a i b j).
i j

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

H (AB) = H (A) + H (B \ mid A) = H (B) + H (A \ mid B).

Взаємна ентропія має властивість інформаційної повноти - з неї можна отримати всі розглянуті величини.


4. Історія

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

Поняття ентропії, як міри випадковості, введено Шенноном в його статті "A Mathematical Theory of Communication", опублікованій у двох частинах у Bell System Technical Journal в 1948 році.


Примітки

  1. Це подання зручно для роботи з інформацією, представленою в двійковій формі; в загальному випадку підстава логарифма може бути іншим.
  2. Габідулін, Е. М., Пилипчук, Н. І. Лекції з теорії інформації - М .: МФТІ, 2007. - С. 16. - 214 с. - ISBN 5-7417-0197-3. .
  3. Лебедєв Д. С., Гармаш В. А. Про можливість збільшення швидкості передачі телеграфних повідомлень. - М.: Електрозв'язок, 1958. - № 1. - С. 68-69.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Ентропія
Термодинамічна ентропія
Інформаційна ера
Інформаційна війна
Інформаційна архітектура
Інформаційна система
Інформаційна безпека
Інформаційна економіка
Інформаційна модель
© Усі права захищені
написати до нас
Рейтинг@Mail.ru