Тео́рія інформ́ації () — це математичне дослідження кількісного вираження, зберігання та передавання інформації. Заснував цю галузь і забезпечив їй надійну основу Клод Шеннон у 1940-х роках, хоча ранній внесок до цьому напряму зробили в 1920-х роках праці Гаррі Найквіста та Ральфа Гартлі. Вона перебуває на перетині електронної інженерії, математики, статистики, інформатики, нейробіології, фізики та електротехніки.

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

До застосувань основних предметів теорії інформації належать кодування джерела/стиснення даних (наприклад, для файлів zip) та канальне кодування/виявляння та виправляння помилок (наприклад, для DSL). Її вплив був вирішальним для успіху місій «Вояджер» до глибокого космосу, винайдення компакт-диска, можливості мобільних телефонів і розвитку Інтернету й штучного інтелекту. Ця теорія також знайшла застосування й в інших сферах, як-от індуктивній статистиці, криптографії, нейробіології, сприйнятті, обробці сигналів, мовознавстві, еволюції та функціюванні молекулярних кодів (біоінформатиці), теплофізиці, молекулярній динаміці, чорних дірах, квантових обчисленнях, інформаційному пошуку, збиранні інформації, виявлянні плагіату, розпізнаванні образів, виявлянні аномалій, музичній аналітиці, створенні живопису, проєктуванні , вивченні космічного простору, вимірності простору, і навіть епістемології.

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

Теорія кодування займається пошуком конкретних методів, званих кодами (), для підвищення ефективності та зниження рівня помилок при передаванні даних зашумленими каналами, з наближенням до пропускної спроможності каналу. Ці коди можливо умовно поділити на методи стискання даних (кодування джерела) та виправляння помилок (кодування каналу). У випадку останнього знадобилося багато років, щоби знайти методи, можливість яких довів Шеннон.

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

Історичне підґрунтя

Знаковою подією, що заклала основу дисципліни теорії інформації та привернула до неї негайну світову увагу, стала публікація класичної статті Клода Е. Шеннона «Математична теорія зв'язку» в у липні та жовтні 1948 року. Історик оцінив цю статтю як найважливіше досягнення 1948 року, вище за транзистор, зазначивши, що ця праця була «навіть глибшою й фундаментальнішою» за транзистор. Шеннон став відомим як «батько теорії інформації». Він викладав деякі зі своїх початкових ідей щодо теорії інформації ще 1939 року в листі до Веннівера Буша.

До цієї статті обмежені інформаційно-теоретичні ідеї розробили в Bell Labs, при цьому всі вони неявно виходили з однакової ймовірності подій. У своїй статті 1924 року «Деякі чинники, які впливають на швидкість телеграфу» () Гаррі Найквіст помістив теоретичний розділ, де кількісно визначив «відомості» () та «швидкість лінії» (), з якою їх можливо передавати комунікаційною системою, встановивши співвідношення (що нагадує сталу Больцмана), де W — швидкість передачі відомостей, m — кількість різних рівнів напруги, з яких можна обирати на кожному часовому кроці, а K — стала. Стаття Ральфа Гартлі 1928 року «Передавання інформації» () використовує термін інформація () як вимірювану величину, що відображає здатність приймача розрізняти одну послідовність символів з будь-якими іншими, тим самим кількісно визначаючи інформацію як , де S — кількість можливих символів, а n — кількість символів у передаванні. Отже, одиницею інформації була десяткова цифра, яку згодом іноді називали гартлі на його честь як одиницю, шкалу або міру інформації. 1940 року Алан Тюрінг використав подібні ідеї як частину статистичного аналізу для розшифровки німецьких шифрів «Енігми» під час Другої світової війни.

Більшість математичного апарату теорії інформації для різноймовірнісних подій розробили для галузі термодинаміки Людвіг Больцман та Джозая Віллард Ґіббз. Зв'язки між інформаційною ентропією та термодинамічною ентропією, включно з важливими внесками 1960-х років, розглянуто в статті .

У революційній і новаторській статті Шеннона, роботу над якою було значною мірою завершено в Bell Labs до кінця 1944 року, Шеннон уперше представив якісну та кількісну модель зв'язку як статистичний процес, що лежить в основі теорії інформації, розпочавши з твердження:

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

Кількості інформації

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

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

Далі вираз вигляду , коли , вважають за згодою нульовим. Це виправдано тим, що для будь-якої основи логарифму.

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

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

Інтуїтивно, ентропія дискретної випадкової величини є мірою невизначеності (), пов'язаної зі значенням , коли відомий лише її розподіл.

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

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

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

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

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

Наприклад, якщо подає положення шахової фігури — це рядок, а це стовпець, то спільна ентропія рядка та стовпця фігури буде ентропією її положення.

Попри схожість позначень, спільну ентропію не слід плутати з ().

Умовна ентропія (неоднозначність) () або умовна невизначеність () величини за заданої випадкової величини (також звана неоднозначністю щодо , ) — це усереднена умовна ентропія за :

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

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

де (, конкретна взаємна інформація) — це поточкова взаємна інформація.

Основна властивість взаємної інформації полягає в тому, що

Тобто, знаючи Y, можливо заощадити в середньому бітів при кодуванні X порівняно з ситуацією, коли Y невідома.

Взаємна інформація симетрична:

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

Іншими словами, це міра того, наскільки в середньому зміниться розподіл імовірності X, якщо задано значення Y. Її часто переобчислюють як розходження добутку відособлених розподілів зі справжнім спільним розподілом: