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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
2 шеннони ентропії: ентропія інформації є логарифмом за основою 2 з числа можливих результатів; за двох монет існує чотири можливі результати, й ентропія становить два біти.

В теорії інформації системи моделюються передавачем, каналом та приймачем. Передавач продукує повідомлення, які надсилаються каналом. Канал якимось чином змінює ці повідомлення. Приймач намагається визначити, яке повідомлення було надіслано. В цьому контексті ентропі́я (точніше, ентропі́я Ше́ннона, англ. entropy, Shannon entropy) — це математичне сподівання (усереднене значення) інформації, яка міститься в кожному повідомленні. «Повідомлення» може бути модельовано будь-яким потоком інформації.

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

Логарифм розподілу ймовірності є корисним як міра ентропії, оскільки для незалежних джерел він є адитивним. Наприклад, ентропія підкидання монети складає 1 шеннон, тоді як ентропія m підкидань складає m шеннонів. Зазвичай вам потрібно log2(n) бітів для представлення величини, яка може набувати одного з n значень, якщо n є ступенем числа 2. Якщо ці значення є однаково ймовірними, то ентропія (в шеннонах) дорівнює числу бітів. Рівність між кількістю бітів і шеннонів дотримується лише тоді, коли всі результати є однаково ймовірними. Якщо одна з цих подій є ймовірнішою за інші, то спостереження цієї події є менш інформативним. І навпаки, рідкісніші події надають більше інформації при їхньому спостереженні. Оскільки спостереження менш імовірних подій трапляється рідше, в підсумку виходить, що ентропія (при розгляді її як усередненої інформації), отримувана від нерівномірно розподілених даних, є меншою за log2(n). Якщо вихід є незмінним, то ентропія дорівнює нулеві. Коли розподіл імовірності джерела є відомим, ентропія Шеннона точно кількісно виражає ці міркування. Зміст спостережуваних подій (зміст повідомлень) у визначенні ентропії не має значення. Ентропія враховує лише ймовірність спостереження певної події, тому інформація, яку вона включає, є інформацією про розподіл ймовірності, що лежить в основі, а не про зміст самих подій.

Взагалі, ентропія позначає безлад або невизначеність. Ентропію Шеннона було введено Клодом Шенноном у його праці 1948 року «Математична теорія зв'язку[en]».[1] Ентропія Шеннона забезпечує абсолютну межу найкращої можливої усередненої довжини кодування без втрат, або стиснення джерела інформації. Ентропію Шеннона узагальнює ентропія Реньї[en].

Зміст

Введення[ред.ред. код]

Ентропія — це міра непередбачуваності кількості інформації (англ. unpredictability of information content). Для отримання неформального, інтуїтивного розуміння зв'язку між цими трьома термінами, розгляньмо приклад опитування з якогось політичного питання. Як правило, такі опитування відбуваються тому, що результати такого опитування не є заздалегідь відомими. Іншими словами, результати опитування є відносно непередбачуваними, і фактичне здійснення опитування та з'ясовування результатів дає деяку нову інформацію; це просто різні способи сказати, що ентропія результатів опитування є високою. Тепер розгляньмо випадок, коли таке ж опитування проводиться вдруге незабаром після першого опитування. Оскільки результати першого опитування вже є відомими, підсумки другого опитування можна передбачити добре, і ці результати не повинні містити багато нової інформації; в цьому випадку ентропія результатів другого опитування є низькою по відношенню до першої.

Тепер розгляньмо приклад з підкиданням монети. Коли монета є справедливою[en], тобто коли ймовірність випадання аверсу така ж, як і ймовірність випадання реверсу, то ентропія підкидання монети є настільки високою, наскільки це можливо. Причиною цього є те, що немає жодного способу передбачити результат підкидання монети заздалегідь — найкраще, що ми можемо зробити, це передбачити, що монета випаде аверсом догори, і наш прогноз буде правильним з імовірністю 1/2. Таке підкидання монети має один біт ентропії, оскільки є два можливі результати, які трапляються з однаковою ймовірністю, і з'ясування фактичного результату містить один біт інформації. На противагу до цього, підкидання монети, яка має два аверси й жодного реверсу, має нульову ентропію, оскільки монета завжди випадатиме аверсом, і результат може бути передбачено цілком. Аналогічно, один двійковий біт має шеннонів або біт ентропії, оскільки він може мати одне з двох значень (1 та 0). Подібно до цього, один тріт містить (близько 1.58496) біт інформації, оскільки він може мати одне з трьох значень.

Текст англійською мовою має досить низький рівень ентропії. Іншими словами, він є доволі передбачуваним. Навіть якщо ми не знаємо точно, що буде далі, ми можемо бути доволі впевненими, що, наприклад, там буде набагато більше e, ніж z, що поєднання «qu» зустрічатиметься набагато частіше за будь-які інші поєднання, які містять «q», і що поєднання «th» буде набагато поширенішим за «z», «q» або «qu». Після перших кількох літер часто можна вгадати решту слова. Англійський текст має між 0.6 та 1.3 біт ентропії для кожного символу повідомлення.[2][3]

Якщо схема стиснення є вільною від втрат, — тобто, завжди можна відтворити повне первинне повідомлення шляхом розтискання, — то стиснене повідомлення має такий самий обсяг інформації, як і первинне, але переданий меншою кількістю символів. Тобто, воно має більше інформації, або вищу ентропію, на один символ. Це означає, що стиснене повідомлення має меншу надмірність. Грубо кажучи, теорема Шеннона про джерело шифрування[en] стверджує, що схема стиснення без втрат в середньому не може стиснути повідомлення так, щоби воно мало більше одного біту інформації на біт повідомлення, але що будь-яке значення менше одного біту інформації на біт повідомлення може бути досягнуто шляхом застосування відповідної схеми кодування. Ентропія повідомлення на біт, помножена на довжину цього повідомлення, є мірою того, наскільки багато інформації в цілому містить повідомлення.

Теорема Шеннона також означає, що жодна схема стиснення без втрат не може скорочувати всі повідомлення. Якщо якісь повідомлення виходять коротшими, хоча б одне повинне вийти довшим в силу принципу Діріхле. В практичному застосуванні це зазвичай не є проблемою, оскільки нас, як правило, цікавить стиснення лише певних типів повідомлень, наприклад, документів англійською мовою на противагу до тексту тарабарщиною, або цифрових фотографій, а не шуму, і не важливо, якщо алгоритм стиснення робить робить довшими малоймовірні або нецікаві послідовності. Проте, проблема все ще може виникнути навіть при повсякденному використанні при застосуванні алгоритму стиснення до вже стиснених даних: наприклад, створення zip-файлу музики, зображень або відео, які вже перебувають у стисненому форматі, такому як FLAC, МР3, WebM, MP4, PNG або JPEG, як правило, дає в результаті zip-файл, який є трохи більшим за первинні файли.

Визначення[ред.ред. код]

Назвавши її на честь Η-теореми Больцмана[en], Шеннон визначив ентропію Η (грецька літера ета) дискретної випадкової величини X з можливими значеннями {x1, …, xn} та функцією маси ймовірності P(X) як

Тут Е є оператором математичного сподівання (англ. expectation), а I є кількості інформації X.[4][5] I(X) і сама є випадковою величиною.

Ентропію може бути записано в явному вигляді як

де b є основою[en] логарифму, який застосовується. Звичними значеннями b є 2, число Ейлера е, та 10, а одиницею ентропії є шеннон для b = 2, нат для b = e, та гартлі для b = 10.[6] Коли b = 2, одиниці вимірювання ентропії також часто називають бітами.

У випадку p(xi) = 0 для деякого i значення відповідного доданку 0 logb(0) приймається рівним 0, що відповідає границі

Коли розподіл є неперервним, а не дискретним, сума замінюється інтегралом:

де P(x) являє собою функцію густини розподілу

Можна також визначити умовну ентропію двох подій X та Y, які набувають значень xi та yj відповідно, як

де p(xi, yj) є ймовірністю того, що X = xi та Y = yj. Цю величину слід розуміти як ступінь довільності випадкової величини X при заданій події Y.

Приклад[ред.ред. код]

Ентропія Η(X) (тобто очікувана неочікуваність) підкидання монети, вимірювана в шеннонах, представлена графічно відносно справедливості монети Pr(X = 1), де X = 1 є випадінням аверса.

Зауважте, що максимум графіка залежить від розподілу. Тут ентропія складає щонайбільше 1 шеннон, і для повідомлення результатів підкидання справедливої монети (2 можливі значення) потрібно в середньому не більше 1 біту. Результат справедливого грального кубика (6 можливих значень) потребуватиме в середньому log26 бітів.

Детальніші відомості з цієї теми Ви можете знайти в статті Функція двійкової ентропії[en].

Детальніші відомості з цієї теми Ви можете знайти в статті Процес Бернуллі[en].

Розгляньмо підкидання монети з відомими, але не обов'язково справедливими, ймовірностями випадання аверсу чи реверсу; цей процес відомий як процес Бернуллі[en].

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

Проте, якщо ми знаємо, що монета не є справедливою, а випадає аверсом чи реверсом з імовірностями p та q, де pq, то тоді невизначеності є менше. Кожного разу, як її підкидають, випадання однієї зі сторін є ймовірнішим, ніж випадання іншої. Зниження невизначеності отримує кількісну оцінку в вигляді меншої ентропії: в середньому кожне підкидання монети подає менше ніж один повний біт інформації.

Крайнім випадком є двоаверсова монета, яка ніколи не випадає реверсом, або двореверсова монета монета, яка ніколи не дає в результаті аверс. Тут немає ніякої невизначеності. Ентропія дорівнює нулеві: кожне підкидання монети не подає жодної нової інформації, оскільки результати кожного підкидання монети завжди визначені. В цьому зв'язку ентропію може бути нормалізовано шляхом ділення її на довжину інформації. Це співвідношення називається метричною ентропією[en], воно є мірою хаотичності інформації.

Обґрунтування[ред.ред. код]

Щоби зрозуміти сенс pi log(1/pi), по-перше, спробуймо визначити функцію інформації, I, з точки зору події i з імовірністю pi. Скільки інформації отримується завдяки спостереженню події i? Розв'язок Шеннона випливає з фундаментальних властивостей інформації:[7]

  1. I(p) ≥ 0 – інформація є невід'ємною величиною
  2. I(1) = 0 – події, які відбуваються завжди, не несуть інформації
  3. I(p1 p2) = I(p1) + I(p2) – інформація від незалежних подій є адитивною

Остання властивість є ключовою. Вона стверджує, що спільна ймовірність несе стільки ж інформації, скільки й дві окремі події по одній. Зокрема, якщо перша подія може видавати один з n однаково ймовірних результатів, а інша має один із m однаково ймовірних результатів, то існує mn можливих результатів спільної події. Це означає, що якщо для кодування першого значення потрібно log2(n) біт, а для кодування другого — log2(m), то для кодування обох потрібно log2(mn) = log2(m) + log2(n). Шеннон виявив, що правильним вибором функції для кількісної оцінки інформації, яка зберігала би цю адитивність, є логарифмічна, тобто

Основою логарифму може бути будь-яке фіксоване дійсне число, більше за 1. Різні одиниці інформації (біти для log2, тріти для log3, нати для натурального логарифму ln і так далі) є лише сталі кратні одна одній. (На противагу, якби основа логарифму була меншою за 1, то ентропія була би від'ємною.) Наприклад, у випадку підкидання справедливої монети, аверс дає log2(2) = 1 біт інформації, який становить приблизно 0.693 нат, або 0.631 тріт. В силу адитивності, n підкидань дають n біт інформації, що становить приблизно 0.693n нат, або 0.631n тріт.

Тепер припустімо, що ми маємо розподіл, в якому подія i може траплятися з імовірністю pi. Припустімо, що ми взяли проби N разів, і результат i було побачено, відповідно, ni = N pi разів. Загальною кількістю інформації, яку ми отримали, є

.

Отже, усередненою кількістю інформації, яку ми отримуємо з кожною подією, є

Аспекти[ред.ред. код]

Відношення до термодинамічної ентропії[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Ентропія в термодинаміці та теорії інформації[en].

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

У статистичній термодинаміці найзагальнішою формулою для термодинамічної ентропії S термодинамічної системи є ентропія Ґіббза[en],

де kB є сталою Больцмана, а pi є ймовірністю мікростану. Ентропію Ґіббза було визначено Віллардом Ґіббзом 1878 року після ранішої праці Больцмана (1872 року).[8]

Ентропія Ґіббза переноситься майже беззмінною до світу квантової фізики, даючи ентропію фон Неймана[en], введену Джоном фон Нейманом 1927 року,

де ρ є матрицею густини квантової механічної системи, а Tr є слідом.

На побутовому практичному рівні зв'язок між інформаційною та термодинамічною ентропією очевидним не є. Фізики та хіміки схильні більше цікавитися змінами ентропії при спонтанному розвитку системи від її первісних умов, у відповідності з другим законом термодинаміки, ніж незмінним розподілом імовірності. І, як вказує малість сталої Больцмана kB, зміни в S / kB навіть для невеликих кількостей речовин у хімічних та фізичних процесах являють собою обсяги ентропії, які є надзвичайно великими порівняно з чим завгодно в стисненні даних та обробці сигналів. Крім того, в класичній термодинаміці ентропія визначається в термінах макроскопічних вимірювань, і не робить жодних посилань на будь-який розподіл імовірності, що є головним у визначенні ентропії інформаційної.

Зв'язок між термодинамікою і тим, що зараз відомо як теорія інформації, було вперше зроблено Людвігом Больцманом, і виражено його знаменитим рівнянням[en]:

де S є термодинамічною ентропією окремого макростану (визначену термодинамічними параметрами, такими як температура, об'єм, енергія тощо), W є числом мікростанів (різних комбінацій частинок у різних енергетичних станах), які можуть дати даний макростан, а kB є сталою Больцмана. Передбачається, що кожен мікростан є однаково правдоподібним, так що ймовірністю заданого мікростану є pi = 1/W. При підставленні цих імовірностей до наведеного вище виразу для ентропії Ґіббза (або, рівнозначно, ентропії Шеннона, помноженої на kB) в результаті виходить рівняння Больцмана. В термінах теорії інформації інформаційна ентропія системи є кількістю інформації, якої «бракує» для визначення мікростану при відомому макростані.

На думку Джейнса[en] (1957 року), термодинамічну ентропію, як пояснюється статистичною механікою, слід розглядати як застосування інформаційної теорії Шеннона: термодинамічна ентропія інтерпретується як така, що є пропорційною до кількості додаткової інформації Шеннона, необхідної для визначення детального мікроскопічного стану системи, яка залишається не повідомленою описом виключно в термінах макроскопічних величин класичної термодинаміки, з коефіцієнтом пропорційності, який є просто сталою Больцмана. Наприклад, додавання теплоти до системи підвищує її термодинамічну ентропію, оскільки це збільшує число можливих мікроскопічних станів системи, які узгоджуються з вимірюваними значеннями його макроскопічних величин, роблячи таким чином будь-який повний опис стану довшим. (Див. статтю термодинаміка максимальної ентропії[en]). Демон Максвелла може (гіпотетично) знижувати термодинамічну ентропію системи з використанням інформації про стан окремих молекул, але, як показали Ландауер[en] (з 1961 року) з колегами, щоби діяти, цей демон мусить сам підвищувати термодинамічну ентропію в цьому процесі, принаймні на кількість інформації Шеннона, яку він пропонує спочатку отримати й зберегти; і, таким чином, загальна термодинамічна ентропія не знижується (що розв'язує парадокс). Принцип Ландауера встановлює нижню межу кількості тепла, яке комп'ютер повинен генерувати для обробки заданого обсягу інформації, хоча сучасні комп'ютери є набагато менш ефективними.

Ентропія як кількість інфромації[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Теорема Шеннона про джерело шифрування[en].

Ентропія визначається в контексті ймовірнісної моделі. Незалежні підкидання справедливої монети мають ентропію по 1 біту на підкидання. Джерело, яке завжди породжує довгий рядок «Б», має ентропію 0, оскільки наступним символом завжди буде «Б».

Ентропійна швидкість джерела даних означає усереднене число бітів на символ, потрібне для його кодування. Експерименти Шеннона з передбаченням людьми показують швидкість інформації на символ англійською мовою між 0.6 і 1.3 біта;[9] Алгоритм стиснення PPM[en] може досягати рівня стиснення в 1.5 біти на символ англомовного тексту.

Зверніть увагу на наступні моменти з попереднього прикладу:

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

Шеннонівське визначення ентропії, при застосуванні до джерела інформації, може визначати мінімальну пропускну здатність каналу, необхідну для надійного передавання джерела у вигляді закодованих двійкових цифр (див. застереження нижче курсивом). Цю формулу може бути виведено шляхом обчислення математичного сподівання кількості інформації, яка міститься в одній цифрі з джерела інформації. Див. також теорему Шеннона — Гартлі.

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

Ентропія як міра різноманітності[ред.ред. код]

Ентропія є одним з декількох способів вимірювання різноманітності. Зокрема, ентропія Шеннона є логарифмом 1D, індексу істинної різноманітності[en] з параметром, який дорівнює 1.

Стиснення даних[ред.ред. код]

Докладніше: Стиснення даних

Ентропія ефективно обмежує продуктивність найсильнішого можливого стиснення без втрат, яке може бути реалізовано теоретично з допомогою типового набору[en], або практично із застосуванням кодування Хаффмана, Лемпеля — Зіва, або арифметичного кодування. Продуктивність наявних алгоритмів стиснення даних часто застосовують як грубу оцінку ентропії блоку даних.[10][11] Див. також колмогорівську складність. На практиці для захисту від помилок алгоритми стиснення навмисно включають деяку розумну надмірність у вигляді контрольних сум.

Світовий технологічний потенціал для зберігання та передавання інформації[ред.ред. код]

Дослідження 2011 року в журналі «Science» оцінює світовий технологічний потенціал для зберігання та передавання оптимально стисненої інформації, нормалізований за найефективнішими алгоритмами стиснення, доступними в 2007 році, оцінюючи таким чином ентропію технологічно доступних джерел.[12]

Всі числа — в ентропійно стиснених ексабайтах
Тип інформації 1986 2007
Зберігання 2.6 295
Широкомовлення 432 1900
Телекомунікації 0.281 65

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

Обмеження ентропії як кількості інформації[ред.ред. код]

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

(Для конкретної послідовності повідомлень або символів, породженої заданим стохастичним процесом, також може бути визначено «швидкість власної інформації»: у випадку стаціонарного процесу вона завжди дорівнюватиме швидкості ентропії.) Для порівняння різних джерел інформації, або встановлення зв'язку між ними, використовуються й інші кількості інформації[en].

Важливо не плутати наведені вище поняття. Яке з них мається на увазі, часто може бути зрозумілим лише з контексту. Наприклад, коли хтось говорить, що «ентропія» англійської мови становить близько 1 біта на символ, вони насправді моделюють англійську мову як стохастичний процес, і говорять про швидкість її ентропії. Шеннон і сам використовував цей термін таким чином.[3]

Хоча ентропія і використовується часто як характеристика кількості інформації джерела даних, ця кількість інформації не є абсолютною: вона вирішальною мірою залежить від імовірнісної моделі. Джерело, яке завжди породжує один і той же символ, має ентропійну швидкість[en] 0, але визначення того, що є символом, залежить від абетки. Розгляньмо джерело, яке видає рядок АБАБАБАБАБ..., в якому за А завжди слідує Б, і навпаки. Якщо ймовірнісна модель розглядає окремі літери як незалежні, то ентропійна швидкість послідовності складає 1 біт на символ. Але якщо послідовність розглядається як "АБ АБ АБ АБ АБ ..." з дволітерними блоками як символами, то ентропійна швидкість складає 0 біт на символ.

Проте, якщо ми використовуємо дуже великі блоки, то оцінка посимвольної ентропійної швидкості може стати штучно заниженою. Це відбувається тому, що насправді розподіл ймовірності послідовності не є пізнаваним точно; це лише оцінка. Наприклад, припустімо, що розглядаються тексти всіх будь-коли опублікованих книг як послідовність, у якій кожен символ є текстом цілої книги. Якщо існує N опублікованих книг, і кожну книгу опубліковано лише одного разу, то оцінкою ймовірності кожної книги є 1/N, а ентропією (в бітах) є −log2(1/N) = log2(N). Як практичний код, це відповідає призначенню кожній книзі унікального ідентифікатора і використання його замість тексту книги будь-коли, коли потрібно послатися на цю книгу. Це надзвичайно корисно для розмов про книги, але не дуже корисно для характеризування кількості інформації окремих книг або мови в цілому: неможливо відтворити книгу з її ідентифікатора, не знаючи розподілу ймовірності, тобто повного тексту всіх книг. Ключова ідея полягає в тому, що повинна братися до уваги складність імовірнісної моделі. Колмогорівська складність являє собою теоретичне узагальнення цієї ідеї, яке дозволяє розглядати кількість інформації послідовності незалежно від конкретної ймовірнісної моделі; воно розглядає найкоротшу програму для універсального комп'ютера, яка виводить цю послідовність. Такою програмою є код, який досягає ентропійної швидкості послідовності для заданої моделі, плюс кодовий словник (тобто, ймовірнісна модель), але вона не може бути найкоротшою.

Наприклад, послідовністю Фібоначчі є 1, 1, 2, 3, 5, 8, 13, .... При розгляді цієї послідовності як повідомлення, а кожного числа як символу, існує майже стільки ж символів, скільки є символів у повідомленні, даючи ентропію близько log2(n). Таким чином, перші 128 символів послідовності Фібоначчі мають ентропію приблизно 7 біт/символ. Проте цю послідовність може бути виражено за допомогою формули [F(n) = F(n−1) + F(n−2) для n = 3, 4, 5, …, F(1) =1, F(2) = 1], і ця формула має значно нижчу ентропію, і застосовується до послідовності Фібоначчі будь-якої довжини.

Дані як марковський процес[ред.ред. код]

Звичний спосіб визначення ентропії для тексту ґрунтується на марковській моделі тексту. Для джерела нульового порядку (кожен символ вибирається незалежно від останніх символів) двійковою ентропією є

де pi є ймовірністю i. Для марковського джерела[en] першого порядку (такого, в якому ймовірність вибору символу залежить лише від безпосередньо попереднього символу) ентропійною швидкістю[en] є

[Джерело?]

де i є станом (деякими попередніми символами), а є ймовірністю j за заданого в якості попереднього символу i.

Для марковського джерела другого порядку ентропійною швидкістю є

b-арна ентропія[ред.ред. код]

В загальному випадку b-арна ентропія джерела = (S, P) з первинною абеткою[en] S = {a1, …, an} і дискретним розподілом ймовірності P = {p1, …, pn}, де pi є імовірністю ai (скажімо, pi = p(ai)), визначається як

Зауваження: b у «b-арній ентропії» є числом різних символів ідеальної абетки, яка використовується як стандартне мірило для вимірювання первинних абеток. В теорії інформації для абетки для кодування інформації є необхідними і достатніми два символи. Тому стандартним є брати b = 2 («двійкова ентропія»). Таким чином, ентропія первинної абетки, з її заданим емпіричним розподілом імовірності, — це число, яке дорівнює числу (можливо дробовому) символів «ідеальної абетки», з оптимальним розподілом імовірності, необхідних для кодування кожного символу первинної абетки. Також зверніть увагу, що «оптимальний розподіл імовірності» тут означає рівномірний розподіл: первинна абетка з n символів має найвищу можливу ентропію (для абетки з n символів), коли розподіл імовірності абетки є рівномірним. Цією оптимальною ентропією виявляється logb(n).

Ефективність[ред.ред. код]

Первинна абетка з нерівномірним розподілом матиме меншу ентропію, ніж якби ці символи мали рівномірний розподіл (тобто, були «оптимальною абеткою»). Цю дефективність ентропії може бути виражено відношенням, яке називається ефективністю:[ця цитата потребує посилання]

[прояснити]

Ефективність є корисною для кількісної оцінки ефективності використання каналу зв'язку. Це формулювання також називають нормалізованою ентропією, оскільки ентропія ділиться на максимальну ентропію .

Характеризування[ред.ред. код]

Ентропія Шеннона характеризується[en] невеликим числом критеріїв, перерахованих нижче. Будь-яке визначення ентропії, яке задовольняє ці припущення, має вигляд

де K є сталою, яка відповідає виборові одиниць вимірювання.

Далі pi = Pr(X = xi), а Ηn(p1, …, pn) = Η(X).

Неперервність[ред.ред. код]

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

Симетричність[ред.ред. код]

При перевпорядкуванні виходів xi ця міра повинна залишатися незмінною.

тощо

Максимум[ред.ред. код]

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

Для рівноймовірних подій ентропія повинна зростати зі збільшенням числа виходів.

Адитивність[ред.ред. код]

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

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

При заданому ансамблі n рівномірно розподілених елементів, які поділяються на k блоків (підсистем) з b1, …, bk елементами в кожному, ентропія всього ансамблю повинна дорівнювати сумі ентропії системи блоків і окремих ентропій блоків, кожна з яких є зваженою на ймовірність знаходження в цьому відповідному блоці.

Для додатних цілих чисел bi, де b1 + … + bk = n,

При виборі k = n, b1 = … = bn = 1 це означає, що ентропія певного виходу дорівнює нулеві: Η1(1) = 0. Це означає, що ефективність первинної абетки з n символами може бути визначено просто як таку, що дорівнює її n-арній ентропії. Див. також надмірність інформації.

Додаткові властивості[ред.ред. код]

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

  • Додавання або усунення подій з нульовою ймовірністю не впливає на ентропію:
.
.
Ця максимальна ентропія logb(n) ефективно досягається первинною абеткою, яка має рівномірний розподіл ймовірності: невизначеність є максимальною, коли всі можливі події є однаково ймовірними.
  • Ентропія, або обсяг інформації, розкритої шляхом визначення (X,Y) (тобто визначення X та Y одночасно) дорівнює інформації, розкритої шляхом проведення двох послідовних експериментів: спершу виявлення значення Y, а потім виявлення значення X, за умови, що ви знаєте значення Y. Це може бути записано як
  • Якщо Y = f(X), де f є детермінованою, то Η(f(X)|X) = 0. Застосування попередньої формули до Η(X, f(X)) дає
отже, Η(f(X)) ≤ Η(X), таким чином, ентропія величини може тільки зменшуватися, коли остання проходить через детерміновану функцію.
  • Якщо X та Y в є двома незалежними експериментами, то знання значення Y не впливає на наше знання про значення X (оскільки ці двоє не впливають одне на одне в силу незалежності):
  • Ентропія двох одночасних подій є не більшою за суму ентропій кожної з окремих подій, і дорівнює їй, якщо ці дві події є незалежними. Точніше, якщо X та Y є двома випадковими величинами на одному й тому ж імовірнісному просторі, а (X, Y) позначає їхній декартів добуток, то

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

Розширення дискретної ентропії до неперервного випадку[ред.ред. код]

Диференційна ентропія[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Диференційна ентропія[en].

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

Цю формулу зазвичай називають непере́рвною ентропі́єю (англ. continuous entropy), або диференційною ентропією[en]. Попередником неперервної ентропії h[f] є вираз функційної Η в Η-теоремі Больцмана[en].

Хоча аналогія між обома функціями й наводить на роздуми, мусить бути поставлено наступне питання: чи є диференційна ентропія обґрунтованим розширенням дискретної ентропії Шеннона? Диференційній ентропії бракує ряду властивостей, якими володіє дискретна ентропія Шеннона, — вона навіть може бути від'ємною, — і відтак було запропоновано поправки, зокрема, взяття границі щільності дискретних точок[en].

Щоби відповісти на це питання, ми мусимо встановити зв'язок між цими двома функціями:

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

Щоби зробити це, почнімо з неперервної функції f, дискретизованої засіками розміру . Згідно теореми про середнє значення, в кожному засіку існує таке значення xi, що

і відтак інтеграл функції f може бути наближено (в рімановому сенсі) за допомогою

де ця границя і «розмір засіку прямує до нуля» є рівноцінними.

Позначмо

і, розкриваючи цього логарифма, ми маємо

При Δ → 0 ми маємо

Але зауважте, що log(Δ) → −∞ при Δ → 0, отже, нам потрібне особливе визначення диференціалу або неперервної ентропії:

що, як було сказано раніше, називають диференці́йною ентропі́єю (англ. differential entropy). Це означає, що диференційна ентропія не є границею ентропії Шеннона при n → ∞. Вона радше відрізняється від границі ентропії Шеннона нескінченним зсувом (див. також статтю про інформаційну розмірність[en]).

Взяття границі щільності дискретних точок[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Взяття границі щільності дискретних точок[en].

В результаті виходить, що, на відміну від ентропії Шеннона, диференційна ентропія не є в цілому доброю мірою невизначеності або інформації. Наприклад, диференційна ентропія може бути від'ємною; крім того, вона не є інваріантною відносно неперервних перетворень координат. Цю проблему може бути проілюстровано зміною одиниць вимірювання, коли x є розмірною величиною. f(x) тоді матиме одиниці 1/x. Аргумент логарифму мусить бути безрозмірним, інакше він був би неправильним, так що така диференційна ентропія, як наведено вище, була би неправильною. Якщо є деяким «стандартним» значенням x (тобто, «розміром засіку»), і відтак має такі ж одиниці вимірювання, то видозмінену диференційну ентропію може бути записано в належному вигляді як

і результат буде однаковим при будь-якому виборі одиниць вимірювання для x. Насправді границя дискретної ентропії при N → 0 включала би також і член log(N), який в загальному випадку був би нескінченним. Це є очікуваним, неперервні величини при дискретизації зазвичай матимуть нескінченну ентропію. Взяття границі щільності дискретних точок[en] в дійсності є мірою того, наскільки розподіл є простішим для опису за розподіл, який є рівномірним над своєю схемою квантування.

Відносна ентропія[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Узагальнена відносна ентропія[en].

Іншою корисною мірою ентропії, яка однаково добре працює в дискретному та неперервному випадках, є відно́сна ентропі́я (англ. relative entropy) розподілу. Вона визначається як відстань Кульбака — Лейблера від розподілу до еталонної міри m наступним чином. Припустімо, що розподіл імовірності p є абсолютно неперервним відносно міри m, тобто має вигляд p(dx) = f(x)m(dx) для деякої невід'ємної m-інтегрованої функції f з m-інтегралом 1, тоді відносну ентропію може бути визначено як

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

Застосування в комбінаториці[ред.ред. код]

Ентропія стала корисною величиною в комбінаториці.

Нерівність Люміса — Уїтні[ред.ред. код]

Простим прикладом цього є альтернативне доведення нерівності Люміса — Уїтні[en]: для будь-якої підмножини AZd ми маємо

де Pi є ортогональною проекцією в i-й координаті:

Це доведеня випливає як простий наслідок нерівності Ширера[en]: якщо X1, …, Xd є випадковими величинами, а S1, …, Sn є підмножинами {1, …, d}, такими, що кожне ціле число між 1 і d лежить точно в r з цих підмножин, то

де є декартовим добутком випадкових величин Xj з індексами j в Si (тому розмірність цього вектора дорівнює розмірові Si).

Ми зробимо нарис, як з цього випливає Люміс — Уїтні: справді, нехай X є рівномірно розподіленою випадковою величиною зі значеннями в A, і такою, що кожна точка з A трапляється з однаковою ймовірністю. Тоді (згідно додаткових властивостей ентропії, згадуваних вище) Η(X) = log|A|, де |A| позначає потужність A. Нехай Si = {1, 2, …, i−1, i+1, …, d}. Діапазон міститься в Pi(A) і, отже, . Тепер застосуймо це, щоби обмежити праву частину нерівності Ширера, і піднести до ступеня протилежні частини нерівності, яку ви отримали в результаті.

Наближення до біноміального коефіцієнту[ред.ред. код]

Для цілих чисел 0 < k < n покладімо q = k/n. Тоді

де

[13]

Ось нарис доведення. Зауважте, що є одним із членів виразу

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

оскільки в підсумовуванні є n + 1 членів. Переставлення дає нижню межу.

Гарною інтерпретацією цього є те, що числом двійкових стрічок довжини n з рівно k одиниць є приблизно .[14]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Shannon, Claude E. (July–October 1948). Математична теорія зв'язку[en]. Bell System Technical Journal 27 (3). с. 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x.  (PDF) (англ.)
  2. Schneier, B: Applied Cryptography, Second edition, page 234. John Wiley and Sons. (англ.)
  3. а б Shannon, C. E. (January 1951). Prediction and Entropy of Printed English. Bell System Technical Journal[en] 30 (1). с. 50–64. doi:10.1002/j.1538-7305.1951.tb01366.x. Процитовано 30 March 2014.  (англ.)
  4. Borda, Monica (2011). Fundamentals in Information Theory and Coding. Springer. с. 11. ISBN 978-3-642-20346-6.  (англ.)
  5. Han, Te Sun & Kobayashi, Kingo (2002). Mathematics of Information and Coding. American Mathematical Society. с. 19–20. ISBN 978-0-8218-4256-0.  (англ.)
  6. Schneider, T.D, Information theory primer with an appendix on logarithms, National Cancer Institute, 14 April 2007. (англ.)
  7. Carter, Tom (March 2014). An introduction to information theory and entropy. Santa Fe. Процитовано Aug 2014.  (англ.)
  8. Compare: Boltzmann, Ludwig (1896, 1898). Vorlesungen über Gastheorie : 2 Volumes – Leipzig 1895/98 UB: O 5262-6. English version: Lectures on gas theory. Translated by Stephen G. Brush (1964) Berkeley: University of California Press; (1995) New York: Dover ISBN 0-486-68455-5 (англ.)
  9. Mark Nelson (24 August 2006). The Hutter Prize. Процитовано 2008-11-27.  (англ.)
  10. T. Schürmann and P. Grassberger, Entropy Estimation of Symbol Sequences, CHAOS,Vol. 6, No. 3 (1996) 414–427 (англ.)
  11. T. Schürmann, Bias Analysis in Entropy Estimation J. Phys. A: Math. Gen. 37 (2004) L295-L301. (англ.)
  12. а б "The World's Technological Capacity to Store, Communicate, and Compute Information", Martin Hilbert and Priscila López (2011), Science, 332(6025), 60–65; free access to the article through here: martinhilbert.net/WorldInfoCapacity.html (англ.)
  13. Aoki, New Approaches to Macroeconomic Modeling. page 43.
  14. Probability and Computing, M. Mitzenmacher and E. Upfal, Cambridge University Press (англ.)

Література[ред.ред. код]

Підручники з теорії інформації[ред.ред. код]

Посилання[ред.ред. код]