Все формулы РФ

Информатика / Кодирование информации

Дивергенция Кульбака—Лейблера для дискретных распределений

Дивергенция Кульбака—Лейблера для дискретных распределений даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Опубликовано: Обновлено:

Кодирование информацииСтраницы с задачами и решениямиЕсть историческая справкаДиагностика условий

Формула

$$D_{KL}(P\|Q)=\sum_i p_i\log_2\frac{p_i}{q_i}$$
Схема KL для P=(0,5;0,5)
KL для P=(0,5;0,5)KL для P=(0,5;0,5)Q=(q;1−q)0.0500.2750.3250.50.650.7250.9750.951.3qD_KL, бит

Минимум при Q=P; отдельное слагаемое может быть отрицательным, сумма неотрицательна.

Обозначения

$x$
аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$
целые индексы узла, шага либо компоненты, безразмерные
$ε / err$
допуск или оценка вычислительной ошибки, если она используется, единицы результата

Условия применения

P и Q должны быть распределениями с одинаковой поддержкой индексов и суммой вероятностей 1; при p_i>0 значение q_i=0 делает дивергенцию бесконечной. Нулевые p_i дают нулевой вклад по соглашению 0 log(0/q)=0, а основание 2 задаёт единицы бит.

Ограничения

Результат нельзя переносить на похожую по словам, но другую модель. Оценка ошибки может быть локальной, а сходимость — зависеть от гладкости, обусловленности или начальных данных. Округление, вырождение матрицы и нарушения ограничений меняют смысл вычисления. Число после знака равенства не заменяет проверку: следует показать, какая именно формула применена, в каких единицах получен ответ и почему условия выполнены. Для информационных величин особенно важно не смешивать биты и натуральные единицы.

Подробное объяснение

D_KL(P||Q) усредняет логарифм отношения вероятностей по истинному распределению P. Если модель Q недооценивает событие, которое P считает вероятным, вклад становится положительным и может быть большим.

Направление в записи существенно: веса p_i и логарифм p_i/q_i нельзя переставлять без изменения результата. Поэтому D_KL(P||Q) обычно не равно D_KL(Q||P).

Условие q_i>0 там, где p_i>0, не техническая мелочь. Нулевая вероятность в модели для возможного события делает логарифмическую потерю бесконечной.

Неотрицательность следует из неравенства Гиббса. Равенство нулю достигается тогда и только тогда, когда распределения совпадают на своём носителе, но это не делает дивергенцию расстоянием.

Первый вклад равен 0,5log₂(0,5/0,75)=0,5log₂(2/3)≈−0,292481, второй — 0,5log₂2=0,5. Их сумма 0,207519 положительна, хотя один вклад отрицателен. Это важная проверка: неотрицательна вся сумма, а не каждое слагаемое.

Как пользоваться формулой

  1. Выпишите D_{KL}(P\|Q)=\sum_i p_i\log_2\frac{p_i}{q_i} и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
  2. Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
  3. Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
  4. Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
  5. Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

Историческая справка

Соломон Кульбак и Ричард Лейблер опубликовали в 1951 году статью о информации и достаточности, закрепившую это выражение в статистике. Формула выросла на почве информационной теории после работы Клода Шеннона 1948 года и быстро получила смысл ожидаемой логарифмической потери при замене P моделью Q. В машинном обучении и статистике дивергенция используется для сравнения распределений, однако остаётся направленной: смена P и Q обычно меняет число. Современное обозначение D_KL подчёркивает именно расхождение, а не геометрическое расстояние.

Kullback и Leibler опубликовали статью «On Information and Sufficiency» в Annals of Mathematical Statistics в 1951 году. В ней расхождение связано со сравнением статистических моделей и достаточностью, а позднее термин широко вошёл в теорию информации и машинное обучение.

Историческая линия формулы

Дивергенция названа по статье Соломона Кульбака и Ричарда Лейблера 1951 года. Это не метрика: симметрия и неравенство треугольника для неё не требуются, поэтому слово «расстояние» допустимо только как нестрогая интуиция. Источник в карточке указан для различения исторического имени, публикации и современной вычислительной формы; эти уровни не следует смешивать.

Пример

Для P=(0,5;0,5), Q=(0,75;0,25): D=0,5log₂(2/3)+0,5log₂2≈−0,292481+0,5=0,207519 бита. Значение неотрицательно. Первый вклад равен 0,5log₂(0,5/0,75)=0,5log₂(2/3)≈−0,292481, второй — 0,5log₂2=0,5. Их сумма 0,207519 положительна, хотя один вклад отрицателен. Это важная проверка: неотрицательна вся сумма, а не каждое слагаемое. D_KL(P||Q) усредняет логарифм отношения вероятностей по истинному распределению P. Если модель Q недооценивает событие, которое P считает вероятным, вклад становится положительным и может быть большим.

Частая ошибка

Нельзя менять P и Q местами без пересчёта. Нельзя подставлять q_i=0 при p_i>0: результат бесконечен. Не следует ожидать симметрии или неравенства треугольника. И нельзя забывать, что логарифм по основанию два даёт биты, а естественный — наты. В разборе «Дивергенция Кульбака—Лейблера для дискретных распределений» проверяют именно обозначения и условия данной записи.

Практика

Задачи с решением

Совпадающие распределения

Условие. Проверьте D_KL(P||Q) при P=Q=(0,4;0,6).

Решение. В каждом ненулевом слагаемом p_i/q_i=1 и log₂1=0.

Ответ. D_KL=0.

Дивергенция для P=(1;0)

Условие. Вычислите D_KL((1;0)||(0,5;0,5)).

Решение. Единственный ненулевой вклад: 1·log₂(1/0,5)=log₂2=1.

Ответ. D_KL=1 бит.

Дополнительные источники

  • https://doi.org/10.1214/aoms/1177729694
  • https://onlinelibrary.wiley.com/doi/pdf/10.1002/j.1538-7305.1948.tb01338.x

Связанные формулы

Информатика

Взаимная информация двух дискретных величин

$I(X;Y)=\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}$

Взаимная информация двух дискретных величин даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Информатика

Ёмкость двоичного симметричного канала

$C=1-H_2(p),\quad H_2(p)=-p\log_2p-(1-p)\log_2(1-p)$

Ёмкость двоичного симметричного канала даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Информатика

Перекрёстная энтропия дискретного распределения

$H(P,Q)=-\sum_i p_i\log_2q_i$

Перекрёстная энтропия дискретного распределения даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.