ML: Трохи про ентропію
Вступ
Ентропія — важлива міра, що характеризує розподіл ймовірностей, має широке застосування в машинному навчанні. Перед цим документом варто переглянути вступ до теорії ймовірностей.
Міра невизначеності
Розглянемо дискретні випадкові величини. Корисно мати міру невизначеності їхніх значень. Однією з мір, що характеризують таку невизначеність, є "типове" відхилення від середнього значення: $\sigma=\sqrt{D}$, де $D =\langle (X-X_{ср})^2 \rangle$ — дисперсія. Така невизначеність випадкової величини $X$ залежить як від розподілу ймовірностей $\{p_1,...,p_n\}$, так і від її можливих значень: $\{x_1,...,x_n\}$. Це ускладнює порівняння ступенів невизначеності двох величин суттєво різної природи. Тому в ряді випадків зручно мати міру невизначеності, яка залежить лише від розподілу ймовірностей випадкової величини.
Нехай для простоти є дві події $X$ і $Y$, що мають ймовірності $P_X$ і $P_Y$. Чим вища ймовірність події, тим менша її невизначеність (вона швидше за все відбудеться). Тому постулюємо, що міра невизначеності, як функція ймовірності, монотонно спадає: $L(P_X) \lt L(P_Y)$, якщо $P_X \gt P_Y$, а для достовірної події вона дорівнює нулю: $L(1)=0$.
Постулюємо також, що невизначеність спільної ймовірності $P(X,Y)=P_X\cdot P_Y$ двох незалежних подій дорівнює сумі невизначеностей кожної події: $$ L\bigr(P_X\cdot P_Y\bigr) = L\bigr(P_X\bigr)+L\bigr(P_Y\bigr) $$ Ці вимоги з точністю до додатного множника фіксують функцію: $L(x)=-\log x$.Ентропія розподілу ймовірностей $p_i$, за визначенням, є середнім значенням $L(p_i)$.
Ентропія
Нехай $P=\{p_1,...,p_n\}$ — набір $n$ ненульових ймовірностей. Це можуть бути ймовірності появи символів у тексті або ймовірності несумісних класів у моделі класифікації: $$ p_\alpha > 0,~~~~~~~~~~~\sum^n_{\alpha=1} p_\alpha = 1. $$ Ентропія $H$ є мірою рівномірності ймовірностей (чим більша $H$, тим ближчі $p_\alpha$ одна до одної): $$ H(P) = - \sum^n_{\alpha=1} p_\alpha\,\log p_\alpha. $$
Як логарифм зазвичай обирають натуральний логарифм $\ln$ або логарифм за основою два: $\log_2$. Ентропія завжди додатна. Якщо всі ймовірності рівні: $p_\alpha=1/n$, то ентропія досягає свого максимального значення $H_\max = \log n$. Якщо одна ймовірність прямує до 1, а решта до 0, то ентропія прямує до нуля. Наприклад, для трьох ймовірностей (з $\log=\ln$ і $\log_2$):
ln log2
H(0.33, 0.33, 0.33) = 1.10 | 1.58 |
H(0.25, 0.25, 0.50) = 1.04 | 1.50 | n: 2 3 10 100
H(0.10, 0.20, 0.70) = 0.80 | 1.16 | ln n: 0.69 1.10 2.30 4.61 <- H_max ln
H(0.10, 0.10, 0.80) = 0.64 | 0.92 | log2 n: 1.00 1.58 3.32 6.64 <- H_max log2
H(0.01, 0.01, 0.98) = 0.11 | 0.16 |
Нагадаємо, що $\ln p = \log_2 p \cdot \ln 2$. Тому ентропія
з натуральним логарифмом завжди дорівнює $0.69$ від ентропії з двійковим логарифмом.
Ентропія також характеризує ступінь "непередбачуваності" несумісних подій, ймовірності яких дорівнюють $p_\alpha$. Якщо $n$ невелике і всі ймовірності малі, крім однієї, то майже завжди відбувається відповідна їй подія. Ця ситуація цілком передбачувана (ентропія мала). При рівномірному ж розподілі ймовірностей може відбутися "що завгодно" (ентропія максимальна).
☝ Доведення основної властивості ентропії проводиться за допомогою пошуку екстремуму зі зв'язками (метод множників Лагранжа). Умову нормування (сума $p_\alpha$ дорівнює 1) множимо на параметр $\lambda$ і додаємо до ентропії. Потім шукаємо екстремум за $p_1,...,p_n,\lambda$: $$ H = -\sum p_\alpha\,\ln p_\alpha + \lambda\,\bigr(\sum p_\alpha- 1\bigr), ~~~~~~~\frac{\partial H}{\partial p_\alpha} = -\ln p_\alpha - 1 +\lambda = 0~~~~~=>~~~~~p_\alpha=\mathrm{const}. $$ Похідна за $\lambda$ дає умову нормування, з якої випливає, що $p_\alpha=1/n$.
Код Гаффмана
Нехай є рядок символів, ймовірності яких дорівнюють оберненим степеням двійки. Закодуємо кожен символ двійковим числом так, щоб довжина коду була тим більшою, чим менша ймовірність символу. Тоді ентропія за логарифмом з основою $2$ дорівнює середній довжині у бітах (на символ) коду рядка символів.
Наприклад, нехай ймовірності символів $\{a,b,c,d,e\}$ дорівнюють $\{1/2,~1/4,~1/8,~1/16,~1/16\}$. Побудуємо бінарне дерево, листками якого є символи. Спускаючись вниз від кореня (рівноймовірно обираючи ліву або праву гілки), ми будемо потрапляти в ці символи із заданими ймовірностями (див. рисунок). Тоді оптимальний код символу буде кодом шляху до нього по дереву ($0$ — на ліву гілку, $1$ — на праву):
Якщо $p_b = 1/2^b$, то $b = -\log_2 p_b$ дорівнює числу біт (кроків від кореня до листка). Відповідно, середня довжина на символ $b\,p_b$ дорівнює ентропії тексту.
Такий код є префіксним кодом Гаффмана і не потребує розділового символу (бінарна послідовність однозначно декодується). Коли ймовірності не є оберненими степенями двійки, також можна побудувати бінарне дерево, дотримуючись такого алгоритму.
Спочатку зі списку символів обирають два символи з найменшими ймовірностями і об'єднують їх у бінарну гілку
(вище це були б d,e).
Потім ці символи зі списку видаляють, а замість них у список поміщають корінь їхньої гілки (як фіктивний символ) з їхньою
сумарною ймовірністю.
Процедура повторюється, поки у списку не залишиться єдиний вузол (корінь бінарного дерева).
Середня довжина коду Гаффмана на символ більша або дорівнює ентропії $H$ розподілу ймовірностей символів і менша, ніж $H_{\max}=\log_2 n$. Довжина коду кожного символу зазвичай (але не завжди) дорівнює цілій частині $-\log_2 p_\alpha$.
Крос-ентропія
Розглянемо два набори ймовірностей $P=\{p_1,...,p_n\}$ і $Q=\{q_1,...,q_n\}$. Ступінь різності цих розподілів характеризує крос-ентропія: $$ H(P,Q) = -\sum^n_{\alpha=1} p_\alpha\,\ln q_\alpha. $$
Вона досягає мінімуму, коли розподіли збігаються $p_\alpha=q_\alpha$ (це доводиться так само, як і для ентропії). На Python крос-ентропію легко обчислити за допомогою бібліотеки numpy:
import numpy as np p = np.array([0.1, 0.2, 0.7]) q = np.array([0.7, 0.1, 0.2]) H = - p @ np.log(q)Наведемо приклади крос-ентропії:
Q H(P,Q)
[0.33, 0.33, 0.33] 1.10
[0.25, 0.25, 0.50] 0.90
P = [0.10, 0.20, 0.70] [0.10, 0.20, 0.70] 0.80
[0.10, 0.10, 0.80] 0.85
[0.70, 0.10, 0.20] 1.62
Зауважимо, що для будь-яких $P,Q$ справедлива нерівність $H(P) \le H(P,Q)$.
Крос-ентропія безпосередньо пов'язана з відстанню Кульбака — Лейблера:
$$
D_{KL}(P,Q) = \sum^n_{\alpha=1} p_\alpha \ln \frac{p_\alpha}{q_\alpha} = H(P,Q)-H(P).
$$
Ця відстань завжди невід'ємна і дорівнює нулю, коли розподіли ймовірностей $P$ і $Q$ збігаються.
На відміну від звичайних метрик, ця відстань несиметрична: $D_{KL}(P,Q)\neq D_{KL}(Q,P)$.
Умовна ентропія
Нехай є словник $\mathcal{V}=\{w^{(1)},...,w^{(\text{V})}\}$, що складається з $\text{V}=|\mathcal{V}|$ слів (або символів). Послідовність $\mathcal{T}= w_1\,w_2....\,w_N$, де $w_i\in \mathcal{V}$ утворює текст довжиною $N=\mathrm{len}(\mathcal{T})$. .
Нехай для кожного слова відомі $\text{V}$ ймовірностей $P(w_i)$ і $\text{V}^2$ умовних ймовірностей $P(w_i\to w_j)$. Тоді можна визначити умовну ентропію: $$ H_1 = - \sum_i P\bigr(w^{(i)}\bigr)~~\sum_j P\bigr(w^{(i)}\to w^{(j)}\bigr)\,\log P\bigr(w^{(i)}\to w^{(j)}\bigr). $$ Аналогічно, за допомогою $P(w^{(i)},w^{(j)})$ і $P(w^{(i)},w^{(j)} \to w^{(k)})$, можна визначити умовну ентропію другого порядку $H_2$ і т.д.Перплексія
Ймовірнісна мовна модель для даного слова $w$, за його контекстом $\{\mathcal{T} - w\}$ (текст $\mathcal{T}$ без слова $w$) або за попередніми до $w$ словами передбачає ймовірність цього слова: $P(w|\mathcal{T} - w)$. Однією з метрик якості різних моделей є перплексія. Чим менша перплексія, тим краща модель.
Перплексією (perplexity) тексту $\mathcal{T}$ довжиною $N=\mathrm{len}(\mathcal{T})$ називають: $$ \mathcal{P} = \exp\Bigr( -\frac{1}{N}\,\sum^{N}_{i=1} \ln P(w_i|\mathcal{T}-w_i) \Bigr). $$
Якщо ймовірності $P(w_i|\mathcal{T}-w_i)$ оцінюються за попередньою до слова $w_i$ історією
$P(w_i|w_1...w_{i-1})$
то, за ланцюговим правилом маємо (сума логарифмів дорівнює логарифму добутку):
$\mathcal{P}=\exp(-\ln P(w_1...w_n)/N)$, або:
$$
\mathcal{P} = P(w_1,...,w_N)^{-1/N} \equiv \sqrt[N]{\frac{1}{P(w_1,...,w_N)}}.
$$
Чим вища спільна ймовірність послідовності слів, тим менша перплексія.
Важливо пам'ятати, що мовна модель повинна повертати "чесну", нормовану на одиницю
ймовірність слова $P(w_i|\mathcal{T}-w_i)$.
Тобто сума таких ймовірностей за всіма словами словника
повинна дорівнювати одиниці. Якщо це не так, то перплексія може виявитися невиправдано заниженою
(наприклад, коли для будь-якого слова словника модель повертає 1).
Найпростіша мовна модель, незалежно від контексту, передбачає безумовну ймовірність слова: $P(w|\mathcal{T} - w) = P(w)$. У цьому випадку в сумі буде $N^{(i)} = P(w^{(i)})\cdot N$ разів зустрічатися слово $w^{(i)}$ і перплексія дорівнює експоненті від ентропії ймовірностей слів словника: $$ \mathcal{P}_{1} = \exp\Bigr( -\sum^{n}_{\alpha=1} P\bigr(w^{(\alpha)}\bigr)\,\ln P\bigr(w^{(\alpha)}\bigr) \Bigr) ~=~ e^{H(P)}, $$ де $\mathcal{V}=\{w^{(1)},...,w^{(n)}\}$ — словник з $n$ слів. Коли в моделі всі ймовірності рівні $P(w)=1/n$, перплексія дорівнює потужності словника (кількості різних слів): $\mathcal{P}_0 = n$. Мінімальне значення перплексії дорівнює 1. Перплексія, на відміну від ентропії, не залежить від основи логарифма (можна замінити $\ln\mapsto \log_2$ і $e\mapsto 2$).
Перплексію іноді інтерпретують як ступінь розгалуження тексту (branching factor) (скільки можливо гілок для чергового слова, зважених на ймовірності цих гілок).
Ентропія словника залежить від його розміру. Нижче наведено значення ентропії (натуральний логарифм), ймовірності якої обчислені на одному і тому ж англійському тексті при різних розмірах словника n (слова, що не потрапили до словника, замінюються на токен UNK):
n: 100 1000 5000 10000 36500 H: 2.913 4.811 5.841 6.080 6.247 P = exp H: 18 123 344 437 516Тому вказівка перплексії мовної моделі, взагалі кажучи, необхідно супроводжувати розміром словника, яким оперує модель.
Зазвичай мовну модель будують на одній множині документів, а перплексію вимірюють на іншій. Щоб не було тематичного або стильового перекосу, кожен документ розбивається на тренувальну і тестову частини (hold-out perplexity). Якщо як помилку моделі використовують крос-ентропію CE у розрахунку на слово, то перплексія дорівнює $\mathcal{P}=\exp\text{CE}$.
Існує 1B Word Benchmark data set довжиною близько 829'250'940 англійських слів зі словником 793'471 слів (в архіві 11 GB). На цьому датасеті часто порівнюють різні мовні моделі (див. тут і тут). Так 5-грамні моделі з інтерполяцією дають значення $\mathcal{P}=67$ (1.76B параметрів), LSTM + CNN INPUTS (див. цей документ) $\mathcal{P}=30$ (1.04B параметрів), а ансамбль моделей досягає значення $\mathcal{P}=23.7$ (2016).
Диференціальна ентропія
Для неперервних випадкових величин ентропія їхньої щільності ймовірності $p(x)$ визначається аналогічним чином: $$ H[X] = -\int\limits_X p(x)\,\ln p(x)\,dx = - \langle \ln p(x) \rangle $$ і називається диференціальною ентропією. Розглянемо як приклад нормальний (гаусів) розподіл із середнім $\mu$ і дисперсією $D$: $$ p(x) = \frac{1}{\sqrt{2\pi D}}\, e^{-\frac{(x-\mu)^2}{2D}}. $$ Диференціальна ентропія цього розподілу дорівнює: $$ H[X] ~=~ \ln\sqrt{2\pi D} + \frac{\langle(x-\mu)^2\rangle}{2D} ~=~ \frac{1}{2}\ln (2\pi\,D\,e). $$ Звернемо увагу, що на відміну від ентропії для дискретних випадкових чисел, диференціальна ентропія може бути від'ємною (вище при $D \lt 1/2\pi e$). Пов'язано це з тим, що значення щільності ймовірності (на відміну від ймовірностей) можуть бути більшими за одиницю.
Можна показати, що нормальний розподіл має найбільшу диференціальну ентропію серед усіх розподілів з такою ж дисперсією (доводиться це за допомогою лагранжевого методу з двома зв'язками — на нормування розподілу і рівність його дисперсії $D$). Тому для будь-якої випадкової величини $$ \langle(x-x_{ср})^2\rangle \ge \frac{e^{2H(X)}}{2\pi e}. $$
