Дивергенция Кульбака-Лейблера для двух образцов

Я попытался реализовать численную оценку дивергенции Кульбака-Лейблера для двух выборок. Для отладки реализации возьмем образцы из двух нормальных распределений $\mathcal N (0,1)$ и $\mathcal N (1,2)$ .

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

В моей голове возник вопрос: как точно вычислить KL-дивергенцию между двумя различными равномерными распределениями? Нужно ли ограничивать интеграл объединением поддержки обоих дистрибутивов?

estimation intuition kullback-leibler numerics Jimbob
источник

Что ж, поддержка нормального распределения - это набор действительных чисел. В чистой математике проблем нет, но да, для вашего числового приближения вам нужно убедиться, что размер выборки достаточно велик по отношению к области, в которую вы хотите интегрироваться. Вы не сможете интегрировать поверх (-inf, + inf), как в чистой математике ... Хотите что-нибудь разумное? Если вы находитесь более чем на 3 стандартных отклонения от среднего значения, оно будет довольно тонким ...

Мэтью Ганн

Что касается вашего второго вопроса, KL-расхождение между двумя различными равномерными распределениями не определено (

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

\log (0)

$\log(0)$

Jbowman

@jbowman Небольшая заметка. Хотя вы правы в том, что

не определено (или

), в теории информации принято трактовать

как

\log (0)

$\log(0)$

- \infty

$-\infty$

\log (0) \cdot 0

$\log(0) \cdot 0$

0

$0$

Лука

Аналогичный вопрос: mathoverflow.net/questions/119752/…

kjetil b halvorsen

Ответы:

Расходимость Кульбака-Лейблера определяется как так что для вычисления (оценки) этого по эмпирическим данным нам понадобятся, может быть, некоторые оценки функций плотности . Таким образом, естественной отправной точкой может быть оценка плотности (а после этого просто численное интегрирование). Насколько хорошим или стабильным был бы такой метод, я не знаю.

KL (п | | Q) знак равно \int_{- \infty}^{\infty} п (Икс) журнал \frac{п (Икс)}{Q (Икс)} d Икс

$\DeclareMathOperator{\KL}{KL} \KL(P || Q) = \int_{-\infty}^\infty p(x) \log \frac{p(x)}{q(x)} \; dx$

p (x), q (x)

$p(x), q(x)$

Но сначала ваш второй вопрос, потом я вернусь к первому. Допустим, и - однородные плотности на и соответственно. Тогда то время как определить сложнее, но единственное разумное значение, которое я могу дать, это , насколько я могу видеть, поскольку оно включает интегрирование $p$ $q$ $[0,1]$ $[0,10]$ $\KL(p || q)=\log 10$ $\KL(q || p)$ $\infty$ которую мы можем интерпретировать как . Эти результаты обоснованы из интерпретации, которую я даю в «Интуиции» о расхождении Кульбака-Лейблера (КЛ) $\log(1/0)$ $\log \infty$

Возвращаясь к основному вопросу. Это задается очень непараметрическим способом, и не делается никаких предположений о плотности. Вероятно, необходимы некоторые предположения. Но если предположить, что две плотности предложены в качестве конкурирующих моделей для одного и того же явления, мы, вероятно, можем предположить, что они имеют одну и ту же доминирующую меру: расхождение KL между непрерывным и дискретным распределением вероятности всегда будет, например, бесконечностью. Один документ, посвященный этому вопросу, следующий: https://pdfs.semanticscholar.org/1fbd/31b690e078ce938f73f14462fceadc2748bf.pdf Они предлагают метод, который не требует предварительной оценки плотности, и анализируют его свойства.

(Есть много других работ). Я вернусь и опубликую некоторые детали из этой газеты, идеи.

 EDIT

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

Они предлагают использовать версию эмпирической функции распределения, но линейно интерполировать между точками выборки, чтобы получить непрерывную версию. Они определяют где- шаговая функция Хевисайда, но определенная так, что. Тогда эта функция, интерполированная линейно (и вытянутая горизонтально за пределы диапазона), равна(для непрерывного). Затем они предлагают оценить дивергенцию Кульбака-Либлер от

п_{е} (Икс) знак равно \frac{1}{N} Σ_{я знак равно 1}^{N} U (Икс - {Икс}_{я})

$P_e(x) = \frac1{n}\sum_{i=1}^n U(x-x_i)$

U

$U$

U (0) = 0.5

$U(0)=0.5$

P_{c}

$P_c$

c

$c$

где

является числом, меньшим, чем наименьшее расстояние между выборками.

\hat{D} (п | | Q) знак равно \frac{1}{N} Σ_{я знак равно 1}^{N} журнал (\frac{δ п_{с} ({Икс}_{я})}{δ Q_{с} ({Икс}_{я})})

$\hat{D}(P \| Q) = \frac1{n}\sum_{i=1}^n \log\left(\frac{\delta P_c(x_i)}{\delta Q_c(x_i)}\right)$

δ P_{c} = P_{c} (x_{i}) - P_{c} (x_{i} - ϵ)

$\delta P_c = P_c(x_i)-P_c(x_i-\epsilon)$

ϵ

$\epsilon$

R-код для версии эмпирической функции распределения, которая нам нужна

my.ecdf  <-  function(x)   {
    x   <-   sort(x)
    x.u <-   unique(x)
    n  <-  length(x) 
    x.rle  <-  rle(x)$lengths
    y  <-  (cumsum(x.rle)-0.5) / n
    FUN  <-  approxfun(x.u, y, method="linear", yleft=0, yright=1,
                           rule=2)
    FUN
}

обратите внимание, что rleиспользуется, чтобы заботиться о случае с дубликатами в x.

Тогда оценка дивергенции KL дается

KL_est  <-  function(x, y)   {
    dx  <-  diff(sort(unique(x)))
    dy  <-  diff(sort(unique(y)))
    ex  <-  min(dx) ; ey  <-  min(dy)
    e   <-  min(ex, ey)/2
    n   <-  length(x)    
    P  <-   my.ecdf(x) ; Q  <-  my.ecdf(y)
    KL  <-  sum( log( (P(x)-P(x-e))/(Q(x)-Q(x-e)))) / n
    KL              
}

Затем я покажу небольшую симуляцию:

KL  <-  replicate(1000, {x  <-  rnorm(100)
                         y <- rt(100, df=5)
                         KL_est(x, y)})
hist(KL, prob=TRUE)

которая дает следующую гистограмму, показывающую (оценку) выборочного распределения этой оценки:

Для сравнения мы вычислим расхождение KL в этом примере путем численного интегрирования:

LR  <-  function(x) dnorm(x,log=TRUE)-dt(x,5,log=TRUE)
100*integrate(function(x) dnorm(x)*LR(x),lower=-Inf,upper=Inf)$value
[1] 3.337668

хм ... разница настолько велика, что здесь есть, что исследовать!

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

Если немного расширить ответ kjetil-b-halvorsen , и извините за отсутствие комментариев, у меня нет репутации:

У меня такое ощущение, что аналитические вычисления должны быть (без умножения на 100):

LR <- function(x) dnorm(x,log=TRUE)-dt(x,5,log=TRUE) integrate(function(x) dnorm(x)*LR(x),lower=-Inf,upper=Inf)$value

$\hat D(P||Q)$ $\hat D(P||Q)-1 \to D(P||Q)$

После внесения этих двух поправок результаты кажутся более реалистичными.

ColibriIO
источник

Спасибо, я посмотрю на это и обновлю свой ответ.

kjetil b halvorsen