Шеннонівська Ентропія: Сувора Межа на Скільки Можна Стиснути Дані

Основне питання, яке вирішує ентропія

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

H(X)  =  - sum over all symbols x of  p(x) * log2( p(x) )

// measured in bits per symbol
// by convention, p(x) * log2(p(x)) is taken to be 0 when p(x) = 0

Чому логарифм і чому основа 2

Шеннон хотів кількісті з трьома конкретними властивостями: вона повинна бути безперервною щодо ймовірностей, вона повинна бути максимальною, коли всі результати однаково ймовірні (максимальна невизначеність), і — критично — вона повинна бути додатною для незалежних подій, тобто інформативність двох незалежних символів разом дорівнює сумі їхніх індивідуальних інформативностей. Лише логарифм задовольняє додатності для незалежних ймовірностей (оскільки log(p*q) = log(p) + log(q)), що визначає функціональну форму майже унікально; основа логарифма тоді просто встановлює одиницю — основа 2 дає біти, основа e дає натси, основа 10 дає хартлі.

Однорідна справедлива монета, розрахована вручну

Справедлива монета має p(очок) = p(хвоста) = 0.5, отже:

H = -(0.5 * log2(0.5) + 0.5 * log2(0.5)) = -(0.5 * (-1) + 0.5 * (-1)) = -(-0.5 - 0.5) = 1 біт

Ухилена монета, p(очок) = 0.9, p(хвоста) = 0.1: H = -(0.9 * log2(0.9) + 0.1 * log2(0.1)) = -(0.9 * (-0.152) + 0.1 * (-3.322)) = -(-0.137 - 0.332) ≈ 0.469 біт

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

H = -(0.5 * log2(0.5) + 0.5 * log2(0.5))
  = -(0.5 * (-1) + 0.5 * (-1))
  = -(-0.5 - 0.5)
  = 1 bit

A biased coin, p(heads) = 0.9, p(tails) = 0.1:
H = -(0.9 * log2(0.9) + 0.1 * log2(0.1))
  = -(0.9 * (-0.152) + 0.1 * (-3.322))
  = -(-0.137 - 0.332)
  ≈ 0.469 bits

Двадцять питань, і чому ентропія – це не просто порада, а твердий підлогу.

Класична гра ‘20 запитань’ — лише задавати питання ‘так’ або ‘ні’, щоб визначити невідомий об’єкт із відомого набору — насправді є бінарним пошуком за невизначеності, і вона робить ентропію конкретною: оптимальна стратегія на кожному кроці розділяє залишок ймовірнісного масиву якомога ближче до 50/50, оскільки питання, яке ізолює майже певне вислідування, витрачає більшу частину свого інформаційного потенціалу. Для розподілу з ентропією H, теоретильно мінімальна очікувана кількість питань ‘так’ або ‘ні’, щоб ідентифікувати результат, становить H, якщо ймовірності є точними степенями 1/2, і це доведено, що неможливо зробити краще за H в середньому для будь-якого розподілу — це фактичний зміст теореми Шеннона про кодування джерела, і жодна винахідливість у формулюванні питань не може цього перемогти.

Кодування джерела: ентропія – це обіцянка справжнього коду, який майже може доставити

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

Кодування Хаффмана → оптимальний ПРЕФІКСНИЙ код для відомих, фіксованих ймовірностей; середня довжина знаходиться в межах 1 біта від H, часто набагато ближче; точно збігається з H, коли кожна ймовірність є степенем 1/2 Арифметичне кодування → кодує весь повідомлення як одне дробове число; не обмежується цілими бітами на символ, тому воно сходиться до H навіть тоді, коли Хаффмана не може досягти об’ єктивно близького ентропія H = 0.469 біт/символ (90/10 ухилений монети, розрахована вище) → будь-який без втратний стисник для цього джерела математично гарантовано потребує в середньому щонайменше 0.469 біт на символ — без винятків Це пояснює, чому ентропію називають теоретичним рівнем стиснення підлоги: gzip, zstd, JPEG's ентропійна стадія та всі загальні цілі кодери в кінцевій стадії приблизно ентропійний кодер проти деякої оціненої моделі ймовірностей даних. Краща модель ймовірностей (враховуючи контекст, кореляції між символами тощо) знижує ефективну ентропію та відповідно досяжний стислий розмір — але жодна модель, хоч як добре, не дозволяє вам перевершити ентропію справжнього базового розподілу.

Huffman coding    → optimal PREFIX-FREE code for known, fixed probabilities;
                     average length is within 1 bit of H, often much closer;
                     exactly matches H when every probability is a power of 1/2

Arithmetic coding → encodes the whole message as one fractional number;
                     not restricted to whole-bit-per-symbol codewords, so it
                     converges to H even when Huffman cannot get arbitrarily close

entropy H = 0.469 bits/symbol (90/10 biased coin, worked out above)
→ any lossless compressor on that source is mathematically guaranteed
  to need at least 0.469 bits per symbol on average — no exceptions

Поза одним символом: спільна, умовна та перехресна ентропія

Реальні джерела рідко є незалежними символ за символом — англійський текст має сильні кореляції між послідовними літерами, наприклад — і ентропія чітко узагальнюється для обробки цього, а спільна ентропія H(X,Y) вимірює невизначеність пари змінних разом; умовна ентропія H(Y|X) вимірює, наскільки залишається невизначеності в Y після того, як X вже відомо, і завжди ≤ H(Y) — знання чогось ніколи не збільшує вашу невизначеність щодо чогось іншого, в середньому. Перехресна ентропія, H(p,q) = -Σ p(x)log2(q(x)), вимірює середню довжину коду, коли ви кодуєте дані з істинного розподілу p за допомогою коду, оптимізованого для іншого, можливо неправильного, оціненого розподілу q — і це точно функція втрат, мінімізована при навчанні класифікатора, оскільки нижча перехресна ентропія означає, що передбачені моделлю ймовірності моделі ближчі до справжньої розподіл міток.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Shannon Entropy і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.