Що таке інформація?
До Шеннона поняття "інформація" не мало математичного визначення. Інженери знали, що передавання повідомлення через зашумлену телефонну лінію ненадійне, але не мали точного способу виміряти, що саме передається і що саме втрачається. Фундаментальне прозріння Шеннона було радикальним: інформація стосується не смислу, семантики чи важливості. Вона стосується здивування — тієї міри, якою повідомлення зменшує невизначеність.
Формально, інформаційний вміст події з імовірністю p дорівнює I = −log₂(p) біт. Вибір основи 2 дає одиниці бітів (двійкових розрядів). Подія з імовірністю 1/2 (підкидання чесної монети) несе рівно 1 біт інформації. Подія з імовірністю 1/4 несе 2 біти. Подія з імовірністю 1/8 несе 3 біти. Достовірна подія (p = 1) несе 0 бітів — вона не повідомляє нічого нового. Це визначення — єдине, що узгоджується з трьома природними вимогами: інформація адитивна для незалежних подій, є неперервною функцією ймовірності і максимальна для рівномірних розподілів.
Ентропія Шеннона
Для джерела, яке породжує символи з алфавіту з імовірностями p₁, p₂, ..., pₙ, ентропія Шеннона дорівнює: H = −Σᵢ pᵢ log₂(pᵢ) біт на символ. Вона вимірює середній інформаційний вміст на символ — інакше кажучи, середню невизначеність перед спостереженням кожного символу.
Чесна монета має H = 1 біт. Монета, зміщена на орла з імовірністю 0,9, має H ≈ 0,469 біт — значно менше невизначеності, а отже, менше інформації на кожне підкидання. Англійський текст, із його високо передбачуваними частотами літер і граматичною структурою, має ентропію приблизно 1,0–1,5 біт на символ (Шеннон оцінив це за допомогою експериментів з людьми-випробуваними). Це означає, що англійський текст має величезну надлишковість — приблизно 75% символів можна передбачити з контексту.
Ентропія Шеннона формально ідентична термодинамічній ентропії у формулі Больцмана, де k замінено на основу логарифма. Це не збіг: обидві величини вимірюють кількість можливих станів (мікростанів у фізиці, повідомлень у теорії комунікації), сумісних із відомими макроскопічними обмеженнями. Глибокий зв'язок між теорією інформації та термодинамікою — досліджений Рольфом Ландауером, Чарльзом Беннетом та іншими — показує, що стирання інформації має мінімальну термодинамічну вартість kT ln(2) джоулів на біт. Цей "принцип Ландауера" пов'язує обчислення, інформацію та фізику на фундаментальному рівні.
Стиснення даних
Теорема Шеннона про кодування джерела (1948) встановлює фундаментальну межу стиснення даних без втрат: жоден алгоритм не може стиснути дані нижче H бітів на символ у середньому, де H — ентропія джерела. Вище H досяжне ідеальне стиснення без втрат (у принципі, для достатньо довгих повідомлень). Ця межа одночасно є і дном, нижче якого не може опуститися жоден алгоритм, і ціллю, до якої наближаються хороші алгоритми.
Кодування Хаффмана (1952) присвоює символам двійкові коди змінної довжини, даючи коротші коди частішим символам — так само, як азбука Морзе дає літері 'E' одну крапку (найпоширенішій літері англійської мови). Кодування Хаффмана оптимальне серед посимвольних кодів. Арифметичне кодування працює з цілими повідомленнями і може наблизитися до межі ентропії як завгодно близько. Алгоритми LZ77 і LZ78 (1977–78), використані у zip, gzip та PNG, експлуатують повторювані шаблони в даних, а не статистику символів, і формують основу більшості сучасних універсальних компресорів. Сучасні компресори, як-от Brotli (використовується у веббраузерах) і Zstandard, поєднують статистичне моделювання з ентропійним кодуванням, досягаючи стиснення в межах кількох відсотків від теоретичної межі.
Теорема про зашумлений канал
Найдивовижніший результат Шеннона — теорема про кодування для зашумленого каналу — зруйнувала те, що інженери вважали фундаментальним обмеженням. Інтуїція підказувала: будь-який реальний канал зв'язку додає шум, помилки спотворюють повідомлення, і єдиний спосіб зменшити помилки — передавати повільніше. Шеннон довів, що ця інтуїція хибна.
Для будь-якого каналу з пропускною здатністю C = B · log₂(1 + S/N) біт/секунду (де B — смуга пропускання в Гц, а S/N — відношення потужності сигналу до шуму) можливо передавати інформацію на будь-якій швидкості R < C з імовірністю помилки, яка прямує до нуля зі збільшенням довжини повідомлення — просто обравши правильний завадостійкий код. Передача на швидкостях вище C неможлива незалежно від коду. Пропускна здатність каналу C — це фундаментальна межа, встановлена теорією інформації.
Доведення Шеннона неконструктивне: він показав, що випадковий код спрацює з високою ймовірністю, але не вказав, який саме код використовувати. Пошук практичних кодів, що наближаються до межі Шеннона, займав інженерів наступні п'ять десятиліть.
Дослідіть алгоритми кодування, стиснення та передавання інформації у симуляції кодування Хаффмана — подивіться, як коди змінної довжини та кодування пов'язані з інформаційно-теоретичними принципами, які відкрив Шеннон.
Завадостійкі коди
Річард Хеммінг, працюючи в Bell Labs у 1950 році, розробив перші завадостійкі коди. Коди Хеммінга додають до повідомлення надлишкові перевірочні біти так, що будь-яку однобітову помилку можна не просто виявити, а й виправити. Код Хеммінга (7,4) передає 7 бітів на кожні 4 біти даних, дозволяючи виправити будь-яку однобітову помилку. Схема працює через вибір кодових слів, максимально віддалених одне від одного за "відстанню Хеммінга" (кількістю позицій бітів, у яких вони різняться).
Коди Ріда-Соломона (1960), які нині використовуються в кожному CD, DVD, QR-коді та у зв'язку з далеким космосом, розглядають дані як коефіцієнти многочлена й передають додаткові точки обчислення. Це дозволяє виправляти пакетні помилки — подряпина на CD може пошкодити багато послідовних бітів, і код Ріда-Соломона здатен відновити вихідні дані, доки вціліє достатньо точок обчислення. Турбокоди (1993) та коди з малою щільністю перевірок на парність (LDPC) можуть досягати швидкостей передачі в межах частки відсотка від межі Шеннона — досягнення, яке десятиліттями вважалося практично неможливим. Мережа далекого космічного зв'язку NASA використовує LDPC-коди для сигналів зондів «Вояджер», які нині перебувають на відстані понад 20 мільярдів кілометрів.
Теорія інформації в біології та машинному навчанні
ДНК можна аналізувати як інформаційний канал, у якому мутації відіграють роль шуму. Геном людини кодує приблизно 6,4 мільярда пар основ, що відповідає приблизно 1,5 гігабайтам сирої інформації — хоча ефективний інформаційний вміст нижчий через повторювані послідовності та надлишкові кодони (генетичний код використовує 64 кодони для 20 амінокислот і сигналів зупинки). Інформаційно-теоретичний аналіз геномних послідовностей допомагає виявляти функціональні ділянки: ділянки з низькою ентропією (високо консервативні послідовності) часто відповідають життєво важливим генам або регуляторним елементам.
У машинному навчанні ентропія Шеннона трапляється повсюдно. Функція втрат крос-ентропії — стандартна цільова функція для навчання класифікаційних мереж — це саме ентропія Шеннона між істинним розподілом міток і розподілом, передбаченим моделлю. Мінімізація крос-ентропії еквівалентна методу максимальної правдоподібності. Взаємна інформація I(X;Y) = H(X) − H(X|Y) вимірює, наскільки знання про змінну Y зменшує невизначеність щодо X; вона використовується для відбору ознак, навчання представлень і в методах інформаційного вузького горла (information bottleneck), які стискають представлення, зберігаючи лише інформацію, релевантну для завдання. Принцип мінімальної довжини опису (MDL), запропонований Йормою Ріссаненом, розглядає статистичне навчання як задачу стиснення: найкраща модель — та, що найбільше стискає дані, природним чином збалансовуючи якість підгонки та складність моделі.