Рассчитать расхождение Кульбака-Лейблера на практике?

15

Я использую KL Divergence как меру различия между 2 p.m.f. P и Q .

=-ΣР(Хя)лп(В(Хя))+ΣР(Хя)лп(Р(Хя))

DKL(P||Q)=i=1Nln(PiQi)Pi
=P(Xi)ln(Q(Xi))+P(Xi)ln(P(Xi))

Если то мы можем легко вычислить, что P ( X i ) l n ( Q ( X i ) ) = 0 P ( X i ) l n ( P ( X i ) ) = 0

P(Xi)=0
P(Xi)ln(Q(Xi))=0
P(Xi)ln(P(Xi))=0

P(Xi)0
Q(Xi)=0
P(Xi)ln(Q(Xi))
smwikipedia
источник
P(Xi)!=0P(Xi)0
Q(Xi)=0XiQ
@ Matthew Спасибо, исправлено. Я случайно последовал своей привычке кодирования.
smwikipedia
Q(Xi)=0XiPQ

Ответы:

15

Вы не можете и не можете. Представьте, что у вас есть случайная переменная распределения вероятности Q. Но ваш друг Боб считает, что результат исходит из распределения вероятности P. Он построил оптимальное кодирование, которое минимизирует количество ожидаемых битов, которые ему нужно будет использовать, чтобы сообщить вам исход. Но, поскольку он построил кодировку из P, а не из Q, его коды будут длиннее, чем необходимо. KL-дивергенция измеряет, насколько длиннее будут коды.

Теперь предположим, что у него есть монета, и он хочет рассказать вам последовательность результатов, которые он получает. Поскольку голова и хвост одинаково вероятны, он дает им оба 1-битных кода. 0 для головы, 1 для хвоста. Если у него хвост, хвост, голова, хвост, он может отправить 1 1 0 1. Теперь, если его монета приземлится на грани, он не сможет вам сказать! Никакой код, который он посылает тебе, не сработает. В этот момент KL-расхождение нарушается.

Поскольку KL-дивергенция нарушается, вам придется либо использовать другую меру, либо другое распределение вероятностей. Что вы должны сделать, зависит от того, что вы хотите. Почему вы сравниваете распределение вероятностей? Откуда берутся ваши вероятностные распределения, они оцениваются по данным?

Вы говорите, что ваши вероятностные распределения как-то получены из документов на естественном языке, и вы хотите сравнить пары категорий.

Во-первых, я бы рекомендовал симметричную меру родства. Для этого приложения звучит так, как будто A похож на B, а B похож на A.

Вы пробовали меру косинусного подобия? Это довольно распространено в НЛП.

Если вы хотите придерживаться KL, одну вещь, которую вы могли бы сделать, это оценить функцию вероятности по обоим документам, а затем посмотреть, сколько дополнительных бит вам понадобится в среднем для каждого документа. То есть (P || (P + Q) / 2 + Q || (P + Q) / 2) / 2

user1417648
источник
Отличное объяснение, но немного запутанное: как вы описываете первый абзац, разве это не KL (Q || P)?
Юрген
8

На практике я тоже столкнулся с этой проблемой. В этом случае я обнаружил, что замена значения 0 на очень небольшое число может вызвать проблемы. В зависимости от значения, которое вы используете, вы введете «смещение» в значение KL. Если вы используете значение KL для проверки гипотез или другого использования, которое включает пороговое значение, то это небольшое значение может повлиять на ваши результаты. Я обнаружил, что наиболее эффективный способ справиться с этим - это рассмотреть возможность вычисления KL только в согласованном пространстве гипотез X_i, где ОБА P и Q отличны от нуля. По сути, это ограничивает домен KL доменом, в котором определены оба, и избавляет вас от проблем при использовании KL для проверки гипотез.

concipiotech
источник
Благодарю. Это интересное предложение. По сути, он также пытается основать P и Q на одном и том же наборе результатов. Я попробую это.
smwikipedia
Если я вычислю KL по подмножеству данных, где P и Q отличны от нуля, нужно ли мне повторно нормализовать P и Q по этому подмножеству? Или просто использовать исходное значение вероятности? Я думаю, я должен. В противном случае P и Q все еще не находятся на одной базе.
smwikipedia
Я только что попробовал с твоим предложением. P распределяет более 10 000 результатов, а Q также распределяет более 10 000 результатов. Но P и Q имеют только 3K общих результатов. Если я использую только общие результаты 3K для оценки разницы между P и Q, я не думаю, что это разумно. Потому что мы игнорируем многие вещи. И, кстати, результат с этим подходом весьма отличается от того, что я получаю, добавляя небольшое число (или псевдосчет).
smwikipedia
Добавьте некоторый контекст, я работаю над экспериментом НЛП. У меня есть несколько категорий документов, и я хочу рассказать, насколько близко каждая пара категорий связана друг с другом.
smwikipedia
5

Qi=0iQiQiQP

Решение состоит в том, чтобы никогда не допускать 0 или 1 вероятностей в оценочных распределениях. Обычно это достигается с помощью некоторой формы сглаживания, такой как сглаживание по Тьюрингу, сглаживание Дирихле или сглаживание Лапласа.

Дэниел Малер
источник