KL-дивергенция

Определение и что оно значит

$$\htmlData{k=kl}{\text{KL}(p \,\|\, q)} = \sum_x p(x)\log_2 \htmlData{k=ratio}{\frac{p(x)}{q(x)}} = \mathbb{E}_{p}\!\left[\log_2 \frac{p(X)}{q(X)}\right]$$

Три прочтения одного числа, и каждое пригодится:

• лишние биты. Сколько в среднем вы переплачиваете, кодируя данные из $p$ кодом, построенным под $q$. Это разложение $H(p,q) - H(p)$ из прошлого урока;
• ожидание логарифма отношения правдоподобий. Тот же объект $\frac{dP}{dQ}$, что в уроке 180 блока 3;
• насколько данные различают гипотезы. Если $\text{KL}$ велика, одного наблюдения почти хватает, чтобы отличить $p$ от $q$; если мала — потребуется много.

Почему $\text{KL} \ge 0$

Вывод короткий, и стоит его проделать — он объясняет, откуда неотрицательность берётся. Неравенство Йенсена для выпуклой $\varphi$ говорит $\mathbb{E}[\varphi(X)] \ge \varphi(\mathbb{E}[X])$. Возьмём $\varphi = -\log$, она выпукла:

$\text{KL}(p\|q) = \mathbb{E}_p\!\left[-\log\frac{q}{p}\right] \ \ge \ -\log \mathbb{E}_p\!\left[\frac{q}{p}\right] = -\log \sum_x p(x)\frac{q(x)}{p(x)} = -\log 1 = 0$

Равенство в неравенстве Йенсена достигается только когда аргумент постоянен почти наверное, то есть $q/p = \text{const}$; вместе с нормировкой это даёт $q = p$. Отсюда и «равенство тогда и только тогда».

Это же неравенство даёт всё остальное в блоке:

утверждение	как получается
$H(p, q) \ge H(p)$	$= H(p) + \text{KL} \ge H(p)$
$H(p) \le \log_2 n$	из $\text{KL}(p \| \text{uniform}) \ge 0$
$I(X;Y) \ge 0$	это $\text{KL}$ совместного от произведения
$\text{ELBO} \le \log p(x)$	зазор равен $\text{KL} \ge 0$

То есть одно неравенство Йенсена держит весь блок. Если запоминать здесь одну вещь, то эту.

Не расстояние

Слово «дивергенция» вместо «расстояния» выбрано не из скромности. KL нарушает два из трёх свойств метрики:

• не симметрична: $\text{KL}(p\|q) \ne \text{KL}(q\|p)$;
• не удовлетворяет неравенству треугольника;
• неотрицательность и «нуль только при совпадении» — выполняются.

Подвигайте ползунки и сравните две KL в виджете. Они почти всегда различаются, а при обнулении веса одна уходит в бесконечность, тогда как другая остаётся конечной.

распределение p

a

0.6

b

0.3

c

0.1

распределение q

a

0.333

b

0.333

c

0.333

сделать q равномерной подогнать q под p

H(p)

1.2955 бит

H(p, q)

1.585 бит

KL(p‖q)

0.2895 бит

KL(q‖p)

0.347 бит

H(q)

1.585 бит

Если хочется настоящей метрики, она есть: дивергенция Йенсена–Шеннона

$\text{JS}(p, q) = \tfrac12 \text{KL}(p \| m) + \tfrac12 \text{KL}(q \| m), \qquad m = \tfrac{p+q}{2}$

симметрична, ограничена одним битом, а её корень — настоящая метрика. Усреднённое $m$ покрывает носители обоих, поэтому JS никогда не бесконечна — свойство, за которое её и взяли в оригинальный GAN.

Что делать с бесконечностью

Обнуление в $q$ там, где $p$ положительна, — не редкий вырожденный случай, а повседневная проблема. Три стандартных ответа:

• сглаживание: подмешать $\varepsilon$ равномерного, $q' = (1-\varepsilon)q + \varepsilon u$;
• параметризация без нулей: softmax, гауссиана с носителем на всей прямой;
• другая дивергенция: JS, полное вариационное расстояние или Вассерштейн, которые конечны при непересекающихся носителях.

Последний пункт — исторически важный. Ранние GAN’ы оптимизировали JS, и при непересекающихся носителях генератора и данных её градиент обращался в нуль: дивергенция равна своему максимуму, но не подсказывает, куда двигаться. Вассерштейновское расстояние это исправило, потому что оно учитывает, насколько далеко носители друг от друга, а не только то, что они не пересекаются.

Где встречается

Стоит увидеть, что это одна величина в разных костюмах:

место	что за KL
кросс-энтропийный лосс	$\text{KL}(\hat p_{\text{данные}} \| p_{\text{модель}})$ плюс константа
L2-регуляризация	$\text{KL}$ posterior до prior, если смотреть байесовски
VAE	$\text{KL}(q(z\|x) \| p(z))$ — второй член ELBO
дистилляция	$\text{KL}$ от ученика до учителя
PPO	$\text{KL}$-ограничение на шаг политики
RLHF	$\text{KL}$-штраф к исходной модели
взаимная информация	$\text{KL}$ совместного от произведения маргинальных

Семь строк, одна формула. И в каждом случае выбор направления — какое распределение стоит слева — определяет поведение метода, а не только знак. Об этом следующий урок.