Інформаці́йна ентропі́я () — це усереднена швидкість, із якою продукує інформацію стохастичне джерело даних.

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

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

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

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

Введення

Основною ідеєю теорії інформації є те, що чим більше хтось знає про предмет, то менше нової інформації про нього вони здатні отримати. Якщо подія є дуже ймовірною, то коли вона трапляється, в цьому немає нічого неочікуваного, і відтак вона привносить мало нової інформації. І навпаки, якщо подія була малоймовірною, то її трапляння є набагато інформативнішим. Таким чином, інформаційний вміст є висхідною функцією оберненої ймовірності події (1/p, де p є ймовірністю події). Тепер, якщо може трапитися більше подій, ентропія вимірює усереднений інформаційний вміст, який ви можете очікувати отримати, якщо дійсно трапляється одна з цих подій. З цього випливає, що викидання грального кубика має більше ентропії, ніж підкидання монети, оскільки кожен з результатів грального кубика має меншу ймовірність, ніж кожен з результатів монети.

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

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

Англомовний текст, якщо розглядати його як стрічку символів, має досить низький рівень ентропії, тобто, він є доволі передбачуваним. Навіть якщо ми не знаємо точно, що буде далі, ми можемо бути доволі впевненими, що, наприклад, «e» там буде набагато поширенішою за «z», що поєднання «qu» зустрічатиметься набагато частіше за будь-які інші поєднання, які містять «q», і що поєднання «th» буде набагато поширенішим за «z», «q» або «qu». Після перших кількох літер часто можна вгадати решту слова. Англійський текст має між 0.6 та 1.3 біта ентропії на символ повідомлення.Schneier, B: Applied Cryptography, Second edition, John Wiley and Sons.

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

Для наочності уявіть, що ми хочемо передати послідовність, до складу якої входять 4 символи, «А», «Б», «В» і «Г». Таким чином, повідомленням для передавання може бути «АБАГГВАБ». Теорія інформації пропонує спосіб обчислення найменшої можливої кількості інформації, яка передасть це. Якщо всі 4 літери є рівноймовірними (25 %), ми не можемо зробити нічого кращого (над двійковим каналом), аніж кодувати кожну літеру 2 бітами (у двійковому вигляді): «А» може бути кодовано як «00», «Б» — як «01», «В» — як «10», а «Г» — як «11». Тепер припустімо, що «А» трапляється з імовірністю 70 %, «Б» — 26 %, а «В» та «Г» — по 2 % кожна. Ми могли би призначити коди змінної довжини, так, що отримання «1» казало би нам дивитися ще один біт, якщо тільки ми не отримали вже перед цим 2 послідовні біти одиниць. В цьому випадку «А» було би кодовано як «0» (один біт), «Б» — як «10», а «В» і «Г» як «110» і «111». Легко побачити, що протягом 70 % часу потрібно надсилати лише один біт, 26 % часу — два біти, і лише протягом 4 % від часу — 3 біти. Тоді в середньому необхідно менше за 2 біти, оскільки ентропія є нижчою (через високу поширеність «А» з наступною за нею «Б» — разом 96 % символів). Обчислення суми зважених за ймовірностями логарифмічних імовірностей вимірює та схоплює цей ефект.

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

Означення

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

Тут є оператором математичного сподівання (), а є кількістю інформації . і сама є випадковою величиною.

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

де є основою логарифма, який застосовується. Звичними значеннями є 2, число Ейлера е, та 10, а відповідними одиницями ентропії є біти для , нати для , та бани для .Schneider, T.D, Information theory primer with an appendix on logarithms, National Cancer Institute, 14 April 2007.

У випадку для деякого значення відповідного доданку приймають рівним , що відповідає границі

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

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

Приклад

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

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

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

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

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

Обґрунтування