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. QPQ

=-ΣP(Xi)ln(Q(Xi))+ΣP(Xi)ln(P(Xi))

DKeu(P||Q)=Eu=1Nem(PEuQEu)PEu
=-P(XEu)eun(Q(XEu))+P(XEu)eun(P(XEu))

Se , podemos calcular facilmente que P ( X i ) l n ( Q ( X i ) ) = 0 P ( X i ) l n ( P ( X i ) ) = 0

P(XEu)=0 0
P(XEu)eun(Q(XEu))=0 0
P(XEu)eun(P(XEu))=0 0

Mas se e como calcularQ ( X i ) = 0 P ( X i ) l n ( Q ( X i ) )

P(XEu)0 0
Q(XEu)=0 0
P(XEu)eun(Q(XEu))
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ímboloP(XEu)!=0 0P(XEu)0 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(XEu)=0 0XEuQ
@ Matthew Obrigado, corrigido. Eu segui meu hábito de codificação acidentalmente.
smwikipedia 16/05
Q(XEu)=0 0XEuPQ

Respostas:

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

QEu=0 0EuQEuQEuQP

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