Дивергенція KL

Ідея: Ціна хибної моделі

Сесії йдуть за $P$: $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$. Модель постачальника $Q$ каже $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$, $\frac{1}{2}$.

• Код за $Q$ витрачає $2$, $3$, $3$, $1$ біти
• Найкращий код для $P$ у середньому дає $H(P)=\frac{7}{4}$
• Хибна модель коштує зайвих бітів

Приклад: Зайві біти на сесію

Скільки зайвих бітів на сесію ви платите, кодуючи за $Q$ сесії, що йдуть за $P$?

1. Перехресна ентропія: $\frac{1}{2}\times 2+\frac{1}{4}\times 3+\frac{1}{8}\times 4=\frac{9}{4}$
2. Зайве: $\frac{9}{4}-\frac{7}{4}=\frac{1}{2}$ біта

Формула: Дивергенція Кульбака-Лейблера

$D_{\mathrm{KL}}(P\parallel Q)=\sum p(x){\log }_2\left(\frac{p(x)}{q(x)}\right)$

Дорівнює H(P, Q) − H(P): зайві біти за кодування істини хибною моделлю.

Ідея: Ніколи не від’ємна

Окремі доданки бувають від’ємними, але сума ніколи: $D_{\mathrm{KL}}(P\parallel Q)\ge 0$.

• Нуль лише тоді, коли $P$ і $Q$ той самий закон
• Жоден код не кращий за побудований для істини

Швидка перевірка: Інший напрям

Тепер нехай істина це $Q$. Чому дорівнює $D_{\mathrm{KL}}(Q\parallel P)$ у бітах?

Ідея: Напрям має значення

$\frac{1}{2}$ в один бік, $\frac{5}{8}$ в інший: це не відстань. Ваги беруться з першого аргументу.

• $q(x)=0$ там, де $p(x)>0$: нескінченність
• Де $p(x)=0$, доданок зникає
• Тому моделі ризику лишають вагу кожному баченому стану

Ідея: Свідчення на одне спостереження

$D_{\mathrm{KL}}(P\parallel Q)$ це очікуване свідчення на користь $P$ проти $Q$ від одного спостереження, у бітах.

• $8$ сесій: $8\times \frac{1}{2}=4$ біти
• Відношення правдоподібностей близько $2^4=16$
• Мала дивергенція: довго чекати, щоб розрізнити моделі

Типова помилка: Аргументи в хибному порядку

$D_{\mathrm{KL}}(P\parallel Q)$ і $D_{\mathrm{KL}}(Q\parallel P)$ відповідають на різні запитання; одна може бути нескінченною, а інша ні.

Натомість Перший аргумент дає ваги й стоїть у чисельнику відношення.

Ідея: Як сказати це на співбесіді

Зайві біти на повідомлення за кодування істини хибною моделлю.

• Ніколи не від’ємна
• Не симетрична
• Нескінченна, коли модель дає нуль реальній події