Calculer la divergence Kullback-Leibler en pratique?

15

J'utilise KL Divergence comme mesure de dissimilarité entre 2 et . $p.m.f.$ $P$ $Q$

D_{K L} (P | | Q) = \sum_{i = 1}^{N} \ln (\frac{P_{i}}{Q_{i}}) P_{i}

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

= - \sum P (X_{i}) l n (Q (X_{i})) + \sum P (X_{i}) l n (P (X_{i}))

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

Si alors nous pouvons facilement calculer que

P (X_{i}) = 0

$P(X_i)=0$

P (X_{i}) l n (Q (X_{i})) = 0

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

P (X_{i}) l n (P (X_{i})) = 0

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

Mais si

P (X_{i}) \neq 0

$P(X_i)\ne0$

Q (X_{i}) = 0

$Q(X_i)=0$

P (X_{i}) l n (Q (X_{i}))

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

distributions distance kullback-leibler smwikipedia
la source

Pour enregistrer tout le monde un peu de temps à regarder ce que vous vouliez dire que vous pouvez changer

P (X_{i})! = 0

$P(X_i)!=0$

P (X_{i}) \neq 0

$P(X_i) \ne 0$

De plus, voulez-vous dire que

Q (X_{i}) = 0

$Q(X_i) = 0$

X_{i}

$X_i$

Q

$Q$

@Matthew Merci, corrigé. J'ai suivi mon habitude de codage accidentellement.

smwikipedia

@Matthew

Q (X_{i}) = 0

$Q(X_i)=0$

X_{i}

$X_i$

P

$P$

Q

$Q$

15

Vous ne pouvez pas et vous ne le faites pas. Imaginez que vous ayez une variable aléatoire de distribution de probabilité Q. Mais votre ami Bob pense que le résultat vient de la distribution de probabilité P. Il a construit un encodage optimal, qui minimise le nombre de bits attendus qu'il devra utiliser pour vous dire le résultat. Mais, puisqu'il a construit l'encodage à partir de P et non à partir de Q, ses codes seront plus longs que nécessaire. La divergence KL mesure la durée des codes.

Disons maintenant qu'il a une pièce et qu'il veut vous dire la séquence des résultats qu'il obtient. Parce que la tête et la queue sont également probables, il leur donne les deux codes 1 bit. 0 pour la tête, 1 pour la queue. S'il obtient queue queue tête queue, il peut envoyer 1 1 0 1. Maintenant, si sa pièce tombe sur le bord, il ne peut pas vous le dire! Aucun code qu'il vous enverrait ne fonctionnerait. À ce stade, la divergence KL tombe en panne.

Étant donné que la divergence KL tombe en panne, vous devrez soit utiliser une autre mesure ou d'autres distributions de probabilité. Ce que vous devez faire dépend vraiment de ce que vous voulez. Pourquoi comparez-vous les distributions de probabilité? D'où viennent vos distributions de probabilité, sont-elles estimées à partir des données?

Vous dites que vos distributions de probabilités proviennent d'une manière ou d'une autre de documents en langage naturel et que vous souhaitez comparer des paires de catégories.

Tout d'abord, je recommanderais une mesure de parenté symétrique. Pour cette application, il semble que A soit aussi similaire à B que B est similaire à A.

Avez-vous essayé la mesure de similitude cosinus? C'est assez courant en PNL.

Si vous voulez vous en tenir à KL, une chose que vous pourriez faire est d'estimer une fonction de probabilité à partir des deux documents, puis de voir combien de bits supplémentaires vous auriez besoin en moyenne pour l'un ou l'autre document. Soit (P || (P + Q) / 2 + Q || (P + Q) / 2) / 2

user1417648
la source

Grande explication mais un peu déroutante: la façon dont vous décrivez le premier paragraphe, n'est-ce pas KL (Q || P)?

Jurgen

8

Dans la pratique, j'ai également rencontré ce problème. Dans ce cas, j'ai constaté que le fait de remplacer la valeur de 0 par un très petit nombre peut provoquer des problèmes. En fonction de la valeur que vous utilisez, vous introduirez un "biais" dans la valeur KL. Si vous utilisez la valeur KL pour le test d'hypothèse ou toute autre utilisation impliquant un seuil, cette petite valeur peut biaiser vos résultats. J'ai trouvé que la façon la plus efficace de traiter cela est de ne considérer que le calcul du KL sur un espace d'hypothèse cohérent X_i où les DEUX P et Q sont non nuls. Essentiellement, cela limite le domaine du KL à un domaine où les deux sont définis et vous évite les ennuis lors de l'utilisation du KL pour effectuer des tests d'hypothèse.

concipiotech
la source

Merci. C'est une suggestion intéressante. Fondamentalement, il essaie également de fonder P et Q sur le même ensemble de résultats. Je vais essayer ça.

smwikipedia

Si je calcule KL sur le sous-ensemble de données où P et Q sont non nuls, dois-je re-normaliser P et Q sur ce sous-ensemble? Ou utilisez-vous simplement la valeur de probabilité d'origine? Je pense que je devrais. Sinon, P et Q ne sont toujours pas sur la même base.

smwikipedia

Je viens d'essayer avec votre suggestion. P distribue plus de 10 000 résultats et Q distribue également plus de 10 000 résultats. Mais P et Q n'ont en commun que 3K résultats. Si j'utilise uniquement les résultats 3K communs pour estimer la différence entre P et Q, je ne pense pas que ce soit raisonnable. Parce que nous ignorons beaucoup de choses. Et btw, le résultat avec cette approche est assez différent de ce que j'obtiens en ajoutant un petit nombre (ou pseudo-compte).

smwikipedia

Ajoutez un peu de contexte, je travaille sur une expérience PNL. J'ai plusieurs catégories de documents et je veux dire à quel point chaque paire de catégories est liée les unes aux autres.

smwikipedia

5

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

La solution est de ne jamais autoriser 0 ou 1 probabilités dans les distributions estimées. Ceci est généralement réalisé par une certaine forme de lissage comme le lissage de Good-Turing, le lissage de Dirichlet ou le lissage de Laplace.

Daniel Mahler
la source

Calculer la divergence Kullback-Leibler en pratique?

Réponses: