Теорія інформації: ентропія Шеннона, взаємна інформація, теорема каналу

1. Ентропія Шеннона

У 1948 р. Клод Шеннон запитав: «Скільки інформації несе повідомлення?» Відповідь — ентропія H(X), яка вимірює середню невизначеність випадкової величини X.

Ентропія дискретної випадкової величини: H(X) = −Σ_x p(x)·log₂ p(x) [біти] де p(x) = P(X = x), а 0·log₂(0) ≡ 0 Властивості: ① H(X) ≥ 0 (завжди невід'ємна) ② H(X) ≤ log₂|𝒳| (максимум = рівномірний розподіл) ③ H(X₁,…,Xₙ) ≤ H(X₁)+…+H(Xₙ) (субадитивність) ④ H(X|Y) ≤ H(X) (умова не може збільшити ентропію)

Приклад: монета

Чесна монета: p = 0.5, 1−p = 0.5 H = −0.5·log₂0.5 − 0.5·log₂0.5 = −0.5·(−1) − 0.5·(−1) = 1 біт Несправедлива монета: p = 0.9, 1−p = 0.1 H = −0.9·log₂0.9 − 0.1·log₂0.1 = −0.9·(−0.152) − 0.1·(−3.322) ≈ 0.137 + 0.332 = 0.469 біт Висновок: більша переваженість → менша ентропія

Ланцюгове правило

H(X, Y) = H(X) + H(Y | X) H(X₁,…,Xₙ) = Σ H(Xᵢ | X₁,…,X_{i-1})

2. Взаємна інформація і дивергенція KL

Взаємна інформація I(X;Y) вимірює кількість інформації про X, що міститься в Y (і навпаки).

Взаємна інформація: I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) = H(X) + H(Y) − H(X,Y) = Σ_{x,y} p(x,y)·log₂ [p(x,y)/(p(x)p(y))] I(X;Y) ≥ 0, і рівне нулю тоді і тільки тоді, коли X⊥Y

Дивергенція Кульбака-Лейблера

D_KL(P || Q) = Σ_x P(x)·log₂[P(x)/Q(x)] Властивості: • D_KL(P||Q) ≥ 0 (нерівність Гіббса) • D_KL(P||Q) = 0 ⟺ P = Q • НЕ симетрична: D_KL(P||Q) ≠ D_KL(Q||P) • Зв'язок: I(X;Y) = D_KL(p(x,y) || p(x)p(y))

Застосування в ML

D_KL(P||Q) — основа функції втрат крос-ентропії. Якщо P = справжній розподіл, Q = модель, то мінімізація крос-ентропії H(P,Q) = H(P) + D_KL(P||Q) еквівалентна мінімізації KL-дивергенції.

3. Коди Хаффмана

Оптимальний алгоритм префіксного кодування з мінімальною середньою довжиною кодового слова. Запропонований Девідом Хаффманом у 1952 р.

Алгоритм: жадібна побудова дерева

Ставимо кожен символ у список із його ймовірністю
Обираємо два вузли з найменшими ймовірностями
З'єднуємо їх у новий внутрішній вузол (сума ймовірностей)
Повторюємо до одного кореневого вузла
Ліва гілка = 0, права гілка = 1

Приклад: символи A,B,C,D,E з частотами Символ | P(x) | Код Хаффмана | Довжина A | 0.40 | 0 | 1 B | 0.20 | 10 | 2 C | 0.20 | 110 | 3 ← * D | 0.10 | 1110 | 4 E | 0.10 | 1111 | 4 Середня довжина L = 0.4·1+0.2·2+0.2·3+0.1·4+0.1·4 = 2.2 біти Ентропія H = 2.122 біти [код майже оптимальний!] Теорема Шеннона: H(X) ≤ L < H(X)+1

4. Стиснення без втрат: LZ77 та LZ78

Алгоритми Лемпеля-Зіва (1977, 1978) — основа ZIP, gzip, PNG, GIF. Не потребують попереднього знання розподілу символів — є адаптивними.

LZ77 («ковзне вікно»): Кодує посилання на попередні появи рядка: < відстань, довжина, наступний символ > Приклад: "ABCABCABCABC" A B C (0,3,A) B C... → замість 12 символів: 3 символи + два посилання LZ78 / LZW (GIF, ZIP): Динамічний словник {число → рядок} Будує словник по мірі читання

Теореми асимптотичної оптимальності

Для будь-якого стаціонарного ергодичного джерела коефіцієнт стиснення LZ-алгоритмів наближається до ентропійної межі H(X) при n→∞ (теорема Зіва, 1978).

5. Пропускна здатність каналу

Скільки інформації можна надійно передати каналом зв'язку? Теорема кодування каналу Шеннона (1948) дає точну відповідь.

Пропускна здатність дискретного каналу: C = max_{p(x)} I(X;Y) [біти/символ] Теорема кодування каналу (другий теорем Шеннона): • Якщо R < C → існує код зі швидкістю R і похибкою → 0 • Якщо R > C → будь-який код матиме стійку похибку Канал із додаванням гаусового шуму (AWGN): C = B · log₂(1 + SNR) [біти/с] де B = смуга пропускання [Гц] SNR = сигнал/шум = P_signal/P_noise

Числові приклади

Wi-Fi 2.4 ГГц: B=20 МГц, SNR=30 дБ=1000 C = 20·10⁶ · log₂(1+1000) ≈ 20·10⁶ · 9.97 ≈ 200 Мбіт/с Telephone (ADSL): B=1.1 МГц, SNR=40 дБ=10000 C = 1.1·10⁶ · log₂(10001) ≈ 1.1·10⁶ · 13.3 ≈ 14.6 Мбіт/с Космічний зв'язок: B=100 МГц, SNR=−10 дБ=0.1 C = 100·10⁶ · log₂(1.1) ≈ 100·10⁶ · 0.137 ≈ 13.7 Мбіт/с

6. Ентропія неперервних розподілів

Диференціальна ентропія узагальнює поняття ентропії на неперервні випадкові величини.

Диференціальна ентропія: h(X) = −∫ f(x)·ln f(x) dx Приклади: N(μ, σ²): h = ½·ln(2πeσ²) [нормальний] Uniform[a,b]: h = ln(b−a) [рівномірний] Exp(λ): h = 1 − ln(λ) [показниковий] Теорема максимальної ентропії: • При заданому E[X]=μ і Var(X)=σ² → максимальна h = N(μ,σ²) • Ось чому нормальний розподіл настільки «природній»!

7. Застосування в ML і безпеці

Крос-ентропійні втрати в нейромережах: L = −Σ yᵢ log(ŷᵢ)
Вирішальні дерева: критерій інформаційного виграшу IG = H(parent) − Σ H(child)
Варіаційний автокодер (VAE): D_KL(q(z|x)||p(z)) — частина ELBO
Ентропія паролів: H = log₂(|алфавіт|^довжина) — пароль з 12 символів ≈ 79 біт
Квантова теорія інформації: ентропія фон Неймана S(ρ) = −Tr(ρ·log ρ)

Про цю статтю

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

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

Навіщо читати цю статтю

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

Часті запитання (FAQ)

Що таке Теорія інформації і чому це важливо знати?

Теорія інформації — ключова тема в комп'ютерних наук. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.

Які ключові формули та методи використовуються в теорія інформації?

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

Де в реальному житті застосовується теорія інформації?

Сфери застосування теорія інформації надзвичайно широкі: програмуванні (бекенд, алгоритми), штучному інтелекті, кібербезпеці та обробці великих даних. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.

Як розрахувати теорія інформації онлайн?

На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Теорія інформації'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.

Яка різниця між теорія інформації та суміжними темами?

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