Интуиция о расхождении Кульбака-Лейблера (КЛ)

48

Я узнал об интуиции, лежащей в основе дивергенции KL, о том, насколько функция распределения моделей отличается от теоретического / истинного распределения данных. Источник Читаю продолжает говорить о том , что интуитивное понимание «расстояний» между этими двумя распределениями является полезным, но не следует воспринимать буквально , потому что для двух распределений и , то KL дивергенция не является симметричной в и .PQPQ

Я не уверен, как понять последнее утверждение, или это где интуиция «расстояния» ломается?

Я был бы признателен за простой, но проницательный пример.

ОЦП
источник
3
Я думаю, что вы должны сделать шаг назад и понять, что у вас обычно есть асимметрия в статистике между истинным распределением населения и выборкой (или истинной и моделью) и т. Д., И это то, что отражает дивергенция KL ... В общей теории вероятности нет Это различие обычно и симметричная метрика имеет больше смысла
seanv507
1
Какой «источник» вы читали?
августа

Ответы:

34

(Метрическое) расстояние должно быть симметричным, т.е. . Но, по определению, нет.DD(P,Q)=D(Q,P)KL

Пример: , , .Ω={A,B}P(A)=0.2,P(B)=0.8Q(A)=Q(B)=0.5

У нас есть:

KL(P,Q)=P(A)logP(A)Q(A)+P(B)logP(B)Q(B)0.19

а также

KL(Q,P)=Q(A)logQ(A)P(A)+Q(B)logQ(B)P(B)0.22

таким образом, и, следовательно, не является (метрическим) расстоянием.K LKL(P,Q)KL(Q,P)KL

микрофон
источник
51

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

Расходимость Кульбака-Лейблера: Если у Вас есть две гипотезы о том, какие распределения генерирования данных , и , то является отношение правдоподобия для тестирования против . Мы видим, что расхождение Кульбака-Лейблера, приведенное выше, является ожидаемым значением логарифмического отношения правдоподобия согласно альтернативной гипотезе. Таким образом, является мерой сложности этой тестовой задачи, когда является нулевой гипотезой. Так что асимметрия

KL(P||Q)=p(x)logp(x)q(x)dx
XPQp(x)q(x)H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P) просто отражает асимметрию между нулевой и альтернативной гипотезой.

Давайте посмотрим на это в конкретном примере. Пусть будет -распределением, а - стандартным нормальным распределением (в численном примере ниже ). Интеграл, определяющий расхождение, выглядит сложным, поэтому давайте просто используем численное интегрирование в R:PtνQν=1

> lLR_1  <-  function(x) {dt(x, 1, log=TRUE)-dnorm(x, log=TRUE)}  
> integrate(function(x) dt(x, 1)*lLR_1(x), lower=-Inf, upper=Inf)
Error in integrate(function(x) dt(x, 1) * lLR_1(x), lower = -Inf, upper = Inf) : 
  the integral is probably divergent

> lLR_2  <-  function(x) {-dt(x, 1, log=TRUE)+dnorm(x, log=TRUE)}  
> integrate(function(x) dnorm(x)*lLR_2(x), lower=-Inf, upper=Inf)
0.2592445 with absolute error < 1e-07

В первом случае интеграл, по-видимому, численно расходится, что указывает на то, что расхождение очень велико или бесконечно, во втором случае оно мало, суммируя: Первый случай подтверждается аналитическим символическим интегрированием в ответ @ Xi'an здесь: Каково максимальное значение дивергенции Кульбака-Лейблера (KL) .

KL(P||Q)KL(Q||P)0.26

Что это говорит нам в практическом плане? Если нулевая модель является стандартным нормальным распределением, но данные генерируются из распределения, тогда довольно легко отклонить нулевое! Данные из распределения не похожи на обычные распределенные данные. В другом случае роли поменялись. Ноль - но данные нормальные. Но обычные распределенные данные могут выглядеть как данные , поэтому эта проблема намного сложнее! Здесь мы имеем размер выборки , и все данные, которые могут поступить из нормального распределения, также могут быть получены из ! Смена ролей, нет, разница происходит в основном от ролей выбросов.t1t1t1t1n=1t1

При альтернативном распределении существует довольно большая вероятность получения выборки, которая имеет очень малую вероятность при нулевой (нормальной) модели, что дает огромную расходимость. Но когда альтернативное распределение нормальное, практически все данные, которые мы можем получить, будут иметь умеренную вероятность (на самом деле, плотность ...) при нулевой модели , поэтому расхождение мало.t1t1

Это связано с моим ответом: почему мы должны использовать t ошибок вместо обычных ошибок?

Къетил б Халворсен
источник
22

Прежде всего, нарушение условия симметрии является наименьшей проблемой с расходимостью Кульбака-Лейблера. также нарушает неравенство треугольника. Вы можете просто ввести симметричную версию как , но это все еще не метрика, потому что и и нарушает неравенство треугольника. Чтобы доказать это, просто возьмите три смещенные монеты A, B и C, которые производят намного меньше голов, чем хвостов, например, монеты с вероятностью головы: A = 0,1, B = 0,2 и C = 0,3. В обоих случаях, регулярная дивергенция KL D или ее симметричная версия SKL, убедитесь, что они не заполняют неравенство треугольника D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)S K L ( A , B ) + S K L
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
Просто используйте следующие формулы: S
D(P||Q)=ipilog(piqi)
SKL(P,Q)=i(piqi)log(piqi)

D(A||B)=0.1log(0.10.2)+0.9log(0.90.8)0.0159
D(B||C)0.0112
D(A||C)0.0505
0.0159+0.01120.0505
SKL(A,B)0.0352
SKL(B,C)0.0234
SKL(A,C)0.1173
0.0352+0.02340.1173

Я ввел этот пример в цель. Давайте представим, что вы подбрасываете несколько монет, например, 100 раз. Пока эти монеты беспристрастны, вы просто закодируете результаты броска с последовательностью 0-1 бит (1-головка, 0-хвост). В такой ситуации, когда вероятность головы равна вероятности хвоста и равна 0,5, это достаточно эффективное кодирование. Теперь у нас есть несколько предвзятых монет, поэтому мы бы предпочли кодировать более вероятные результаты с более коротким кодом, например, объединять группы голов и хвостов и представлять последовательности из k голов с более длинным кодом, чем последовательность из k хвостов (они более вероятны). И здесь происходит расхождение Кульбака-Лейблера . Если P представляет истинное распределение результатов, а Q является только приближением P, тоD(P||Q)D(P||Q) обозначает штраф, который вы платите, когда кодируете результаты, которые на самом деле приходят из P-дистрибьютора, с кодировкой, предназначенной для Q (штраф в смысле дополнительных битов, которые вам нужно использовать).

Если вам просто нужна метрика, используйте расстояние Bhattacharyya (конечно, модифицированная версия )1[xp(x)q(x)]

Адам Пзедничек
источник
7
Если кто-то заинтересован в том, чтобы на самом деле иметь метрику с более тесной связью с дивергенцией KL, они могли бы рассмотреть квадратный корень дивергенции Дженсена-Шеннона вместо Бхаттачарьи.
кардинал
5

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

Почему? Дивергенция KL - это не то расстояние, которое вы обычно используете, например, норма . Действительно, оно положительно и равно нулю тогда и только тогда, когда два распределения равны (как в аксиомах для определения расстояния). Но, как уже упоминалось, это не симметрично. Есть способы обойти это, но имеет смысл не быть симметричным.L2

Действительно, дивергенция KL определяет расстояние между модельным распределением (которое вы на самом деле знаете) и теоретическим , так что имеет смысл обрабатывать по-разному («теоретическое» расстояние от до предполагая, что модель ) и («эмпирическое» расстояние до предполагающее данные ), поскольку они означают совершенно разные меры.QPKL(P,Q)PQPKL(Q,P)PQQ

meduz
источник
5

Учебник «Элементы теории информации» дает нам пример:

Например, если бы мы знали истинное распределение p случайной величины, мы могли бы построить код со средней длиной описания H (p). Если бы вместо этого мы использовали код для распределения q, нам понадобилось бы в среднем H (p) + D (p || q) битов для описания случайной величины.

Перефразируя приведенное выше утверждение, мы можем сказать, что если мы изменим распределение информации (с q на p), нам потребуется в среднем D (p || q) дополнительных битов для кодирования нового распределения.

Иллюстрация

Позвольте мне проиллюстрировать это, используя одно его применение в обработке естественного языка.

Считаю , что большая группа людей, помеченный B, являются посредниками , и каждый из них назначается задачей выбрать существительное от turkey, animalи bookи передач его на C. Существует имя парня , который может послать каждый из них по электронной почте , чтобы дать им некоторые намеки. Если никто из группы не получил электронное письмо, они могут поднять брови и некоторое время сомневаться в том, что нужно С. И вероятность каждого выбранного варианта составляет 1/3. Единственное в своем роде распределение (если нет, это может касаться их собственных предпочтений, и мы просто игнорируем такие случаи).

Но если им дают глагол, например baste, 3/4 из них могут выбрать turkeyи 3/16 выбрать animalи 1/16 выбрать book. Тогда сколько информации в битах в среднем получил каждый из медиаторов, узнав глагол? Это:

D(p(nouns|baste)||p(nouns))=x{turkey,animal,book}p(x|baste)log2p(x|baste)p(x)=34log23413+316log231613+116log211613=0.5709  bits

Но что, если дан глагол read? Мы можем представить, что все они будут выбирать bookбез колебаний, тогда среднее значение получения информации для каждого посредника от глагола readбудет:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Мы видим, что глагол readможет дать посредникам больше информации. И это то, что может измерить относительная энтропия.

Давайте продолжим нашу историю. Если C подозревает, что существительное может быть неправильным, потому что A сказал ему, что он мог ошибиться, отправив неправильный глагол посредникам. Тогда сколько информации в битах может дать такая плохая новость C?

1) если глаголом, данным A, было baste:

D(p(nouns)||p(nouns|baste))=x{turkey,animal,book}p(x)log2p(x)p(x|baste)=13log21334+13log213316+13log213116=0.69172  bits

2) а что если глагол был read?

D(p(nouns)||p(nouns|baste))=x{book,,}p(x)log2p(x)p(x|baste)=13log2131+13log2130+13log2130=  bits

Поскольку C никогда не знает, какими будут два других существительных, и любое слово в словаре будет возможно.

Мы видим, что дивергенция KL асимметрична.

Я надеюсь, что я прав, и если нет, пожалуйста, прокомментируйте и помогите исправить меня. Заранее спасибо.

Лернер Чжан
источник