Calcular a divergência de Kullback-Leibler na prática?

15

Estou usando o KL Divergence como uma medida de dissimilaridade entre 2 e . $p.m.f.$ $P$ $Q$

D_{K eu} (P | | Q) = \sum_{Eu = 1}^{N} em (\frac{P_{Eu}}{Q_{Eu}}) P_{Eu}

$D_{KL}(P||Q) = \sum_{i=1}^N \ln \left( \frac{P_i}{Q_i} \right) P_i$

= - \sum P (X_{Eu}) eu n (Q (X_{Eu})) + \sum P (X_{Eu}) eu n (P (X_{Eu}))

$=-\sum P(X_i)ln\left(Q(X_i)\right) + \sum P(X_i)ln\left(P(X_i)\right)$

Se , podemos calcular facilmente que

P (X_{Eu}) = 0 0

$P(X_i)=0$

P (X_{Eu}) eu n (Q (X_{Eu})) = 0 0

$P(X_i)ln\left(Q(X_i)\right)=0$

P (X_{Eu}) eu n (P (X_{Eu})) = 0 0

$P(X_i)ln\left(P(X_i)\right)=0$

Mas se e como calcular

P (X_{Eu}) \neq 0 0

$P(X_i)\ne0$

Q (X_{Eu}) = 0 0

$Q(X_i)=0$

P (X_{Eu}) eu n (Q (X_{Eu}))

$P(X_i)ln\left(Q(X_i)\right)$

distributions distance kullback-leibler smwikipedia
fonte

Para salvar todos os outros algum tempo olhando para o que você quis dizer que você pode querer mudar Para com o "\ ne" símbolo

P (X_{i})! = 0

$P(X_i)!=0$

P (X_{i}) \neq 0

$P(X_i) \ne 0$

Além disso, você quer dizer que para todos os ? Nesse caso, a divergência de KL não é definida, pois não é uma função de probabilidade (elas devem somar 1 sobre o suporte).

Q (X_{i}) = 0

$Q(X_i) = 0$

X_{i}

$X_i$

Q

$Q$

@ Matthew Obrigado, corrigido. Eu segui meu hábito de codificação acidentalmente.

smwikipedia 16/05

Q (X_{i}) = 0

$Q(X_i)=0$

X_{i}

$X_i$

P

$P$

Q

$Q$

15

Você não pode e você não. Imagine que você tem uma variável aleatória de distribuição de probabilidade Q. Mas seu amigo Bob acha que o resultado vem da distribuição de probabilidade P. Ele construiu uma codificação ideal, que minimiza o número de bits esperados que ele precisará usar para informar as resultado. Mas, como ele construiu a codificação de P e não de Q, seus códigos serão mais longos do que o necessário. A divergência KL mede quanto tempo os códigos serão.

Agora vamos dizer que ele tem uma moeda e ele quer lhe contar a sequência de resultados que ele obtém. Como cabeça e cauda são igualmente prováveis, ele fornece os dois códigos de 1 bit. 0 para cabeça, 1 para cauda. Se ele conseguir cauda, cauda, cauda, ele pode enviar 1 1 0 1. Agora, se sua moeda cair no limite, ele não poderá contar! Nenhum código que ele envia para você funcionaria. Neste ponto, a divergência de KL quebra.

Como a divergência de KL se decompõe, você terá que usar outra medida ou outra distribuição de probabilidade. O que você deve fazer realmente depende do que você deseja. Por que você está comparando distribuições de probabilidade? De onde vêm suas distribuições de probabilidade, são estimadas a partir de dados?

Você diz que suas distribuições de probabilidade vêm de documentos de linguagem natural de alguma forma e deseja comparar pares de categorias.

Primeiro, eu recomendaria uma medida de relação simétrica. Para esta aplicação, parece que A é tão semelhante a B quanto B é semelhante a A.

Você já tentou a medida de similaridade de cosseno? É bastante comum na PNL.

Se você deseja manter a KL, uma coisa que você pode fazer é estimar uma função de probabilidade de ambos os documentos e depois ver quantos bits extras você precisaria, em média, para qualquer documento. Ou seja (P || (P + Q) / 2 + Q || (P + Q) / 2) / 2

user1417648
fonte

Ótima explicação, mas um pouco confusa: a maneira como você descreve o primeiro parágrafo, não é KL (Q || P)?

Jurgen

8

Na prática, também me deparei com essa questão. Nesse caso, descobri que substituir o valor 0 por um número muito pequeno pode causar problemas. Dependendo do valor que você usar, você introduzirá um "viés" no valor de KL. Se você estiver usando o valor KL para teste de hipótese ou algum outro uso que envolva um limite, esse pequeno valor poderá influenciar seus resultados. Descobri que a maneira mais eficaz de lidar com isso é considerar apenas o cálculo do KL em um espaço consistente de hipótese X_i, onde AMBOS P e Q são diferentes de zero. Essencialmente, isso limita o domínio da KL a um domínio em que ambos são definidos e mantém você longe de problemas ao usar a KL para executar testes de hipótese.

concipiotech
fonte

Obrigado. É uma sugestão interessante. Basicamente, também está tentando basear P e Q no mesmo conjunto de resultados. Vou tentar isso.

smwikipedia

Se eu calcular KL sobre o subconjunto de dados em que P e Q são diferentes de zero, preciso re-normalizar P e Q nesse subconjunto? Ou apenas use o valor de probabilidade original? Eu acho que eu deveria. Caso contrário, P e Q ainda não estão na mesma base.

smwikipedia

Eu apenas tentei com sua sugestão. P distribui mais de 10 mil resultados e Q distribui mais de 10 mil também. Mas P e Q só têm resultados em 3K em comum. Se eu usar apenas os resultados comuns de 3K para estimar a diferença entre P e Q, não acho razoável. Porque estamos ignorando muitas coisas. E, por outro lado, o resultado dessa abordagem é bem diferente do que recebo adicionando um número pequeno (ou pseudo-contagem).

smwikipedia

Adicione um pouco de contexto, estou trabalhando em um experimento de PNL. Tenho várias categorias de documentos e quero dizer o quão próximo cada par de categorias está relacionado.

smwikipedia 20/05

5

$Q_i=0$ $i$ $Q_i$ $Q_i$ $Q$ $P$

A solução é nunca permitir probabilidades 0 ou 1 nas distribuições estimadas. Isso geralmente é alcançado por alguma forma de suavização, como Good-Turing, Dirichlet ou Laplace.

Daniel Mahler
fonte

Calcular a divergência de Kullback-Leibler na prática?

Respostas: