Энтропия, кросс-энтропия и KL-дивергенция

Предыдущая заметка закончилась конкретной задачей: подогнать обучаемое распределение $Q$ к целевому распределению $P$. Для этого нужно число, которое измеряет, насколько $Q$ далеко от $P$. Стандартный первый выбор — расхождение Кульбака–Лейблера (Kullback–Leibler divergence):

$$D_{\mathrm{KL}}(P \,\|\, Q) = \sum_{x \in \mathcal X} P(x)\,\log\frac{P(x)}{Q(x)} .$$

Что означает эта формула? В этой заметке мы строим её с нуля: неожиданность → энтропия → кросс-энтропия → KL. Попутно станет ясно, почему кросс-энтропия служит функцией потерь классификаторов и языковых моделей. Промежуточные величины — энтропия и кросс-энтропия:

$$\begin{gathered} H(P) = -\sum_{x\in\mathcal X} P(x)\log P(x), \\ H(P, Q) = -\sum_{x\in\mathcal X} P(x)\log Q(x). \end{gathered}$$

Обозначения. $P$ — реальное распределение (данных, целевое), $Q$ — предполагаемое распределение (модели). $H(P)$ — энтропия $X \sim P$, которую иногда записывают и как $H(X)$. Для непрерывных распределений строчные $p$ и $q$ обозначают плотности, а суммы становятся интегралами; что меняется для плотностей, сказано в конце раздела о KL. $\log_2$ даёт биты, $\ln$ — наты (nats); просто $\log$ означает любое из двух, если всюду используется одно основание.

Неожиданность#

Построение ниже следует интуитивному пути, которым идёт объяснение энтропии в StatQuest Джоша Стармера (Starmer, 2021); строгое изложение — в Cover and Thomas (2006), глава 2.

Возьмём два поля, на каждом по десять значков. На поле A 5 ноликов и 5 крестиков, на поле B — 9 ноликов и 1 крестик. Вытянем один значок наугад. На каком поле вытянуть X неожиданнее?

Рисунок

На каком поле вытянуть X неожиданнее?

Будем неформально понимать неожиданность (surprise) как ощущение, что чего-то не должно было случиться. Вероятности вытянуть каждый значок равны

$$\begin{gathered} \text{A:}\quad P(\text{O}) = \tfrac12,\;\; P(\text{X}) = \tfrac12, \\ \text{B:}\quad P(\text{O}) = \tfrac{9}{10},\;\; P(\text{X}) = \tfrac{1}{10}. \end{gathered}$$

Крестик явно неожиданнее на поле B, значит, неожиданность должна расти, когда вероятность падает.

Первая попытка: $1/p$. Чтобы сравнить $\tfrac12$ и $\tfrac1{10}$, перевернём дроби: $1/P(\text{X})$ равно $2$ на поле A и $10$ на поле B. Такая мера правильно упорядочивает поля, а как функция $p$ она убывает.

Проблема. Возьмём нечестную монету, которая всегда падает орлом (H, heads): HHHHHHHHHH. Два её исхода дают

$$\begin{aligned} P(H) = 1 &: \quad \frac{1}{P(H)} = \frac11 = 1, \\[4pt] P(T) = 0 &: \quad \frac{1}{P(T)} = \frac10 . \end{aligned}$$

Орёл вообще не должен нас удивлять, поэтому первое значение должно быть равно $0$. Второе даже не является числом.

Исправление: возьмём логарифм.

$$\begin{aligned} \log\frac{1}{P(H)} &= \log 1 = 0, \\ \log\frac{1}{P(T)} &= \log 1 - \log 0 \quad\text{не определено}. \end{aligned}$$

Эта неопределённость нам не мешает: исход с вероятностью $0$ никогда не происходит, так что его неожиданность никогда не понадобится. Так мы получаем определение неожиданности, которую также называют собственной информацией (self-information):

$$s(x) = \log\frac{1}{P(x)} = -\log P(x).$$

Она равна $0$ при $P(x) = 1$ и неограниченно растёт при $P(x) \to 0$.

Рисунок

У достоверного исхода неожиданность должна быть нулевой

Несимметричная монета#

Пусть $P(H) = 0.9$ и $P(T) = 0.1$, где T (tails) — решка. Тогда

$$\log_2\frac{1}{0.9} \approx 0.152, \qquad \log_2\frac{1}{0.1} \approx 3.322 .$$

Решка выпадает гораздо реже орла, поэтому её неожиданность гораздо больше.

	Орёл	Решка
Вероятность $P(x)$	$0.9$	$0.1$
Неожиданность $\log_2 \frac{1}{P(x)}$	$0.152$	$3.322$

Неожиданность аддитивна#

Теперь подбросим монету три раза и увидим H H T. Броски независимы, поэтому вероятность последовательности равна $0.9 \times 0.9 \times 0.1$, и

$$\begin{aligned} s(\text{HHT}) &= \log_2\frac{1}{0.9\cdot 0.9\cdot 0.1} \\ &= -\log_2 0.9 - \log_2 0.9 - \log_2 0.1 \\ &\approx 0.152 + 0.152 + 3.322 \\ &= 3.626 \text{ бита}. \end{aligned}$$

Полная неожиданность последовательности равна сумме неожиданностей отдельных бросков. Именно это даёт логарифм: он превращает произведение вероятностей в сумму. Никакая другая непрерывная функция этого не делает. Пусть $s(pq) = s(p) + s(q)$ для всех $p, q \in (0, 1]$, и положим $g(t) = s(e^{-t})$ при $t \ge 0$. Тогда $g(t + u) = g(t) + g(u)$, а единственные непрерывные решения этого уравнения линейны, $g(t) = ct$. Следовательно, $s(p) = c\log\frac1p$. Требование, чтобы редкие исходы были неожиданными, даёт $c > 0$, а выбор $c$ — это выбор основания. Поэтому логарифмы появляются во всех информационных мерах; соответствующий результат о единственности для самой энтропии доказал Шеннон (Shannon, 1948, теорема 2).

Рисунок

Вероятности перемножаются, неожиданности складываются

Энтропия: ожидаемая неожиданность#

Теперь оценим полную неожиданность после 100 бросков. Мы ожидаем около $90$ орлов и $10$ решек:

$$\begin{aligned} &\underbrace{(0.9\cdot 100)}_{\text{число H}}\cdot \underbrace{0.152}_{\text{неожиданность H}} \\ &\quad +\; (0.1\cdot 100)\cdot 3.322 \;\approx\; 46.9 \text{ бита}. \end{aligned}$$

Разделив на 100, получаем неожиданность на один бросок:

$$0.9 \cdot 0.152 + 0.1 \cdot 3.322 \approx 0.469 \text{ бита}.$$

Это неожиданность, которую мы ожидаем в среднем при каждом броске монеты. Каждая вероятность умножается на свою неожиданность, а это в точности математическое ожидание: если $S = s(X)$ — неожиданность случайного исхода $X \sim P$, то $\mathbb E[S] = \sum_x P(x)\,s(x)$. Ожидаемая неожиданность — это энтропия:

$$\begin{aligned} H(P) &= \sum_x P(x)\log\frac{1}{P(x)} \\ &= -\sum_x P(x)\log P(x), \end{aligned}$$

величина, которую ввёл Клод Шеннон в 1948 году (Shannon, 1948).

Исходы с $P(x) = 0$ никогда не происходят, поэтому их слагаемые исключаются из суммы. Иначе говоря, мы пользуемся соглашением $0 \cdot \log\frac10 = 0$, которое совпадает с пределом $p\log\frac1p$ при $p \to 0$ (Cover and Thomas, 2006, §2.1). Поэтому у нечестной монеты, которая всегда падает орлом, энтропия равна $1 \cdot \log 1 = 0$: в ней нет никакой неожиданности.

Снова о полях#

$$\begin{aligned} H_A &= \tfrac12\log_2 2 + \tfrac12\log_2 2 = 1 \text{ бит}, \\ H_B &= \tfrac{9}{10}\log_2\frac{10}{9} + \tfrac{1}{10}\log_2 10 \approx 0.469 \text{ бита}. \end{aligned}$$

У поля B в точности то же распределение, что у несимметричной монеты, поэтому и энтропия у него та же. Сбалансированное поле менее предсказуемо: большая энтропия означает большую неопределённость. Для двух исходов энтропия ни одного распределения не превышает 1 бита, и достигает этого значения только равномерное; это следует из неравенства Гиббса в следующем разделе.

Кросс-энтропия: неожиданность при неверном представлении#

Возьмём монету, которую наша модель считает честной, ${Q = (0.5,\,0.5)},$ а в реальности она нечестная, ${P = (0.99,\,0.01)}.$ Мы видим десять орлов подряд:

	Вероятность 10 орлов	Неожиданность (наты)
Модель $Q$	$0.5^{10} \approx 0.001$	$\ln 0.5^{-10} \approx 6.93$
Реальность $P$	$0.99^{10} \approx 0.90$	$\ln 0.99^{-10} \approx 0.10$

Рисунок

Десять орлов: неожиданно для модели, обычно в реальности

Исход был обычным. Наша неожиданность вызвана тем, что мы верим в ошибочную модель.

Кросс-энтропия (cross-entropy) $H(P, Q)$ — это средняя неожиданность, когда реальное распределение равно $P$, а мы верим в $Q$:

$$H(P, Q) = \sum_{x\in\mathcal X} \underbrace{P(x)}_{\substack{\text{как часто } x \\ \text{встречается}}}\; \underbrace{\log\frac{1}{Q(x)}}_{\substack{\text{насколько нас} \\ \text{это удивляет}}}$$

Рисунок

Как читать формулу кросс-энтропии

Модель верна. Если $Q = P$, кросс-энтропия сводится к энтропии: $H(P, P) = H(P)$.

Всегда (неравенство Гиббса, Gibbs’ inequality):

$$H(P, Q) \;\ge\; H(P),$$

причём равенство достигается только при $Q = P$ (Cover and Thomas, 2006, теорема 2.6.3). Вера в неверное распределение может только увеличить среднюю неожиданность. Доказательство займёт одну строку, когда у разности $H(P, Q) - H(P)$ появится имя; оно приведено в следующем разделе.

Одно следствие закрывает вопрос, оставшийся открытым в примере с полями. Пусть $Q$ равномерно на $|\mathcal X|$ исходах. Тогда $\log\frac{1}{Q(x)} = \log|\mathcal X|$ для каждого $x$, так что $H(P, Q) = \log|\mathcal X|$, и неравенство Гиббса даёт $H(P) \le \log|\mathcal X|$, причём равенство достигается только для равномерного $P$ (Cover and Thomas, 2006, теорема 2.6.4). Для двух исходов эта граница равна $\log_2 2 = 1$ биту.

Асимметрия. В общем случае $H(P, Q) \ne H(Q, P)$. Оставим $P$ нечестной монетой, а $Q$ — честной, и возьмём один бросок и натуральные логарифмы. Первый аргумент — всегда то распределение, которое порождает исходы. Сначала при вере в честную монету и нечестной реальности, затем при вере в нечестную монету и честной реальности:

$$\begin{aligned} H(P, Q) &= 0.99\ln 2 + 0.01\ln 2 \\ &= \ln 2 \approx 0.69, \\ H(Q, P) &= 0.5\ln\frac{1}{0.99} + 0.5\ln\frac{1}{0.01} \\ &\approx 2.31 . \end{aligned}$$

В каждой сумме веса — фактические вероятности, а под логарифмами стоят предполагаемые. Вера в то, что честная монета нечестная, наказывается гораздо сильнее: решка тогда выпадает в половине случаев, и модель, считающая монету нечестной, сильно удивляется каждой из них.

Расхождение Кульбака–Лейблера#

Кросс-энтропия смешивает два источника неожиданности: неожиданность, которую реальное распределение даёт в любом случае, и дополнительную неожиданность, вызванную неверной моделью. Чтобы выделить вторую, вычтем энтропию реального распределения:

$$\begin{aligned} H(P, Q) - H(P) &= \sum_x P(x)\log\frac{1}{Q(x)} \\ &\quad - \sum_x P(x)\log\frac{1}{P(x)} \\ &= \sum_{x\in\mathcal X} P(x)\log\frac{P(x)}{Q(x)} \\ &= D_{\mathrm{KL}}(P \,\|\, Q). \end{aligned}$$

KL-дивергенция (Kullback and Leibler, 1951) — это дополнительная неожиданность от того, что моделью служит $Q$, а не $P$. Вычитание требует, чтобы оба слагаемых были конечны; сумма справа — общее определение. Её слагаемые подчиняются тем же соглашениям, что и раньше. Слагаемое с $P(x) = 0$ даёт $0$. Слагаемое с $P(x) > 0$, но $Q(x) = 0$ равно $P(x)\log\frac{P(x)}{0} = +\infty$, и тогда $D_{\mathrm{KL}}(P\,\|\,Q)$ тоже бесконечна. Поэтому KL конечна, только если $Q$ даёт положительную вероятность каждому исходу, которому её даёт $P$, то есть если $P$ абсолютно непрерывно относительно $Q$ (Cover and Thomas, 2006, §2.3). Следующая заметка показывает, что это условие означает при обучении.

Итак, KL неотрицательна и равна нулю только при $Q = P$. Она не симметрична и не удовлетворяет неравенству треугольника (Cover and Thomas, 2006, §2.3; пример приведён ниже), поэтому это дивергенция, а не расстояние. Для двух монет, в натах и с четырьмя знаками после точки, чтобы части сходились,

$$\begin{aligned} D_{\mathrm{KL}}(P\,\|\,Q) &\approx 0.6931 - 0.0560 = 0.6371, \\ D_{\mathrm{KL}}(Q\,\|\,P) &\approx 2.3076 - 0.6931 = 1.6145 . \end{aligned}$$

Рисунок

Кросс-энтропия = энтропия + KL-дивергенция

Два поля из начала заметки дают каждому значку положительную вероятность, поэтому KL-дивергенция между ними конечна в обоих направлениях, а её значение зависит от направления:

$$\begin{aligned} D_{\mathrm{KL}}(A\,\|\,B) &= \tfrac12\log_2\frac{1/2}{9/10} + \tfrac12\log_2\frac{1/2}{1/10} \\ &\approx 0.737 \text{ бита},\\ D_{\mathrm{KL}}(B\,\|\,A) &= \tfrac{9}{10}\log_2\frac{9/10}{1/2} + \tfrac{1}{10}\log_2\frac{1/10}{1/2} \\ &\approx 0.531 \text{ бита}. \end{aligned}$$

Проверим: $H(B, A) = H_B + D_{\mathrm{KL}}(B\,\|\,A) = 0.469 + 0.531 = 1$ бит. Если измерять неожиданность по равномерному полю A, каждый вытянутый значок обходится ровно в один бит, каким бы ни было настоящее поле.

Рисунок

Сравнение двух полей с помощью KL

Те же распределения показывают, что KL нарушает неравенство треугольника. Отождествим O с орлом, а X с решкой и сравним поле A с нечестной монетой $P = (0.99, 0.01)$ — один раз напрямую и один раз через поле B. Напрямую $D_{\mathrm{KL}}(A\,\|\,P) \approx 2.329$ бита. Через поле B получаем $D_{\mathrm{KL}}(A\,\|\,B) + D_{\mathrm{KL}}(B\,\|\,P) \approx 0.737 + 0.208 = 0.945$ бита, то есть меньше.

Почему мы минимизируем именно кросс-энтропию#

Для истинного распределения данных $P$ и модели $Q_\theta$:

$$\underbrace{D_{\mathrm{KL}}(P \,\|\, Q_\theta)}_{\text{минимизируем по } \theta} = \underbrace{H(P, Q_\theta)}_{\text{минимизируем по } \theta} - \underbrace{H(P)}_{\substack{\text{константа: энтропия} \\ \text{данных}}}$$

• Изменение параметров модели не может изменить энтропию данных, поэтому $H(P)$ при оптимизации — константа.
• Её значение нам тоже не нужно. Для многомерных данных, например изображений, оценить $H(P)$ по сэмплам — само по себе трудная задача.
• Поэтому минимизация KL по $\theta$ и минимизация кросс-энтропии имеют одно и то же решение, а кросс-энтропия — та часть, которую можно оценить по сэмплам. Именно поэтому классификаторы и языковые модели обучают с кросс-энтропийной функцией потерь. Там то же рассуждение применяется к условному распределению метки (или следующего токена) при заданном входе. Целевое распределение $P(\cdot \mid x)$ тогда — истинное условное распределение метки, которого мы напрямую не видим. Каждый обучающий пример даёт одну наблюдённую метку, one-hot-вектор, и средний отрицательный логарифм правдоподобия наблюдённых меток — выборочная оценка условной кросс-энтропии $\mathbb E_x\, H\big(P(\cdot \mid x), Q(\cdot \mid x)\big)$. Мягкие целевые значения, например сглаживание меток (label smoothing) или вероятности модели-учителя, заменяют one-hot-вектор другой оценкой $P(\cdot \mid x)$.

По сэмплам $x_1, \dots, x_N$ из $P$ кросс-энтропия оценивается средним отрицательным логарифмом правдоподобия:

$$\begin{aligned} H(P, Q_\theta) &= \mathbb E_{x\sim P}\big[-\log Q_\theta(x)\big] \\ &\approx -\frac1N\sum_{i=1}^N \log Q_\theta(x_i). \end{aligned}$$

Его минимизация — это метод максимального правдоподобия (maximum-likelihood estimation). Для дискретных исходов средний отрицательный логарифм правдоподобия в точности равен кросс-энтропии $H(\hat P, Q_\theta)$ между эмпирическим распределением $\hat P$ сэмплов (вероятность $1/N$ в каждой точке $x_i$) и моделью, так что максимальное правдоподобие минимизирует $D_{\mathrm{KL}}(\hat P\,\|\,Q_\theta)$ (Goodfellow, Bengio and Courville, 2016, §5.5). С ростом $N$ среднее по закону больших чисел сходится к $H(P, Q_\theta)$, а она отличается от $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$ только на константу $H(P)$. Поэтому «минимизировать $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$», «минимизировать $H(P, Q_\theta)$» и «максимизировать правдоподобие» — три названия одной и той же цели обучения: точно — для эмпирического распределения, а в пределе большого числа сэмплов — для самого $P$.

Следующие семейства генеративных моделей различаются в основном тем, как они справляются с тем, что $\log Q_\theta(x)$ трудно вычислить: VAE оценивают его снизу, нормализующие потоки (normalizing flows) вычисляют точно, GAN вообще обходятся без него, а диффузионные модели снова оценивают его снизу, но с фиксированным процессом зашумления вместо обучаемого энкодера.

Дивергенция Йенсена–Шеннона#

Дивергенция Йенсена–Шеннона (Jensen–Shannon divergence; Lin, 1991) строится из того же элемента, но она симметрична и ограничена. Она сравнивает оба распределения с их смесью $M = \tfrac12(P + Q)$:

$$\begin{aligned} D_{\mathrm{JS}}(P \,\|\, Q) &= \tfrac12 D_{\mathrm{KL}}(P \,\|\, M) \\ &\quad + \tfrac12 D_{\mathrm{KL}}(Q \,\|\, M). \end{aligned}$$

Поскольку $M(x) > 0$ везде, где $P(x) > 0$ или $Q(x) > 0$, оба слагаемых всегда конечны. Оба неотрицательны, поэтому $D_{\mathrm{JS}} \ge 0$, причём равенство достигается только при $P = M = Q$. Для верхней границы заметим, что $P(x) \le P(x) + Q(x) = 2M(x)$. Значит, в каждом слагаемом $D_{\mathrm{KL}}(P\,\|\,M)$ выполнено $\log\frac{P(x)}{M(x)} \le \log 2$, так что $D_{\mathrm{KL}}(P\,\|\,M) \le \log 2$, причём равенство достигается, только если $P(x) = 2M(x)$, то есть $Q(x) = 0$, везде, где $P(x) > 0$. То же верно для второго слагаемого. Следовательно,

$$0 \;\le\; D_{\mathrm{JS}}(P \,\|\, Q) \;\le\; \ln 2 \text{ ната} = 1 \text{ бит},$$

и максимум достигается ровно тогда, когда $P$ и $Q$ не перекрываются. Для двух монет $D_{\mathrm{JS}} \approx 0.193$ ната ($0.279$ бита).

JS понадобится дважды. В следующей заметке это одна из функций потерь, которые сравниваются на целевом распределении с двумя модами. В заметке о GAN оказывается, что исходная целевая функция GAN при оптимальном дискриминаторе равна $2\,D_{\mathrm{JS}}(P\,\|\,Q) - 2\ln 2$, где $P$ — распределение данных, а $Q$ — распределение генератора (Goodfellow et al., 2014). Насыщение JS на уровне $\ln 2$ для неперекрывающихся распределений, в свою очередь, объясняет, почему обучение GAN может застревать (Arjovsky and Bottou, 2017).

Дальше#

Теперь у нас есть число, которое говорит, насколько модель $Q$ далека от данных $P$, и мы знаем, что минимизация $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$ — это максимальное правдоподобие. Следующая заметка применяет это к гауссовской модели из предыдущей заметки. Она обучает гауссиану $Q$, минимизируя выборочную оценку KL, выясняет, какие допущения стоят за формулой: общий носитель (common support) и направление, — и сравнивает, что делают прямая KL, обратная KL (forward / reverse KL) и JS, когда одна гауссиана должна описать две моды. Раздел Ноутбук в ней описывает код, в котором KL и JS оцениваются по сэмплам.

Литература#

• C. E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423 and 27(4), 623–656, 1948. Теорема 2: единственность формулы энтропии.
• S. Kullback, R. A. Leibler. On Information and Sufficiency. Annals of Mathematical Statistics, 22(1), 1951.
• J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1), 1991.
• T. M. Cover, J. A. Thomas. Elements of Information Theory, 2nd ed. Wiley, 2006. §2.1 (энтропия, соглашение $0\log 0 = 0$), §2.3 (относительная энтропия), теоремы 2.6.3 (информационное неравенство) и 2.6.4 (максимум энтропии); §8.1 и §8.5–8.6 (дифференциальная энтропия и относительная энтропия для плотностей).
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. §3.13 (теория информации) и §5.5 (максимальное правдоподобие и кросс-энтропия).
• I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio. Generative adversarial nets. NeurIPS, 2014.
• M. Arjovsky, L. Bottou. Towards principled methods for training generative adversarial networks. ICLR, 2017.
• J. Starmer. Entropy (for data science) Clearly Explained!!! StatQuest, YouTube, 2021. Путь к энтропии через неожиданность, которым мы шли выше.