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$ двух независимых событий равна сумме неопределённоcтей каждого события: $$ 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, то энтропия стремиться к нулю. Например, для трёх вероятностей (c $\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$. Eсли $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}. $$
