Intuition sur la divergence de Kullback-Leibler (KL)

48

J'ai appris sur l'intuition qui se cache derrière la divergence KL, en quoi une fonction de distribution de modèle diffère de la distribution théorique / vraie des données. La source que je lis poursuit en disant que la compréhension intuitive de la « distance » entre ces deux distributions est utile, mais ne devrait pas être pris à la lettre parce que pour deux distributions et , le KL est Divergence pas symétrique en et .PQPQ

Je ne sais pas trop comment comprendre la dernière affirmation, ou s'agit-il de l'intuition de la "distance"?

J'apprécierais un exemple simple, mais perspicace.

cgo
la source
3
Je pense que vous devez prendre du recul et comprendre que vous avez généralement une asymétrie statistique entre la répartition réelle de la population et l’échantillon (ou vrai et modèle), etc., et c’est ce que reflète la divergence KL ... Dans la théorie de la probabilité générale, il n’existe Cette distinction
n’est pas
1
Quelle "source" lisiez-vous?
Nbro

Réponses:

34

Une distance (métrique) doit être symétrique, c'est-à-dire . Mais, par définition, ne l’est pas.DD(P,Q)=D(Q,P)KL

Exemple: , , .Ω={A,B}P(A)=0.2,P(B)=0.8Q(A)=Q(B)=0.5

On a:

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

et

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

donc et donc n'est pas une distance (métrique).KL(P,Q)KL(Q,P)KL

micro
la source
51

En ajoutant aux autres excellentes réponses, une réponse avec un autre point de vue qui peut peut-être ajouter un peu plus d'intuition, ce qui a été demandé.

La divergence de Kullback-Leibler est Si vous avez deux hypothèse sur laquelle la distribution génère les données , et , puis est le rapport de vraisemblance pour tester contre . Nous voyons que la divergence de Kullback-Leibler ci-dessus est alors la valeur attendue du ratio de loglikistence sous l'hypothèse alternative. Donc, est une mesure de la difficulté de ce problème de test, lorsque est l'hypothèse nulle. Donc l'asymétrie

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) reflète simplement l'asymétrie entre les hypothèses nulle et alternative.

Voyons cela dans un exemple particulier. Soit la distribution distribution et la distribution normale standard (dans l’exemple numérique ci-dessous ). L'intégrale définissant la divergence semble compliquée, utilisons simplement l'intégration numérique dans 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

Dans le premier cas, l'intégrale semble diverger numériquement, indiquant que la divergence est très grande ou infinie, dans le second cas, elle est petite, résumant ainsi: Le premier cas est vérifié par intégration symbolique analytique en réponse de @ Xi'an ici: Quelle est la valeur maximale de la divergence de Kullback-Leibler (KL) .

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

Qu'est-ce que cela nous dit concrètement? Si le modèle null est une distribution normale standard mais que les données sont générées à partir d'une distribution , il est assez facile de rejeter la valeur null! Les données d'une distribution ne ressemblent pas à des données distribuées normales. Dans l'autre cas, les rôles sont inversés. Le null est le mais les données sont normales. Mais les données distribuées normales peuvent ressembler à données, ce problème est donc beaucoup plus difficile! Nous avons ici la taille d'échantillon , et toutes les données pouvant provenir d'une distribution normale pourraient également provenir d'un ! En changeant de rôle, non, la différence provient principalement des rôles de personnes éloignées.t1t1t1t1n=1t1

Dans la distribution alternative il existe une probabilité relativement grande d'obtenir un échantillon qui a une très faible probabilité selon le modèle nul (normal), ce qui donne une divergence énorme. Mais lorsque la distribution alternative est normale, pratiquement toutes les données que nous pouvons obtenir auront une probabilité modérée (en réalité, la densité ...) sous le modèle nul , de sorte que la divergence est faible.t1t1

Ceci est lié à ma réponse ici: Pourquoi devrions-nous utiliser des erreurs t à la place des erreurs normales?

kjetil b halvorsen
la source
22

Tout d’abord, la violation de la condition de symétrie est le plus petit problème de la divergence de Kullback-Leibler. viole également l'inégalité des triangles. Vous pouvez simplement introduire la version symétrique sous la forme , mais ce n'est toujours pas métrique, car et viole l'inégalité des triangles. Prouver que nous prenons simplement trois pièces biaisées A, B et C qui produisent beaucoup moins de têtes que de queues, par exemple des pièces avec une probabilité de têtes de: A = 0,1, B = 0,2 et C = 0,3. Dans les deux cas, la divergence D régulière KL ou sa version symétrique SKL, vérifiez qu’elles ne remplissent pas l’inégalité du triangle D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
Utilisez simplement ces formules:
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

J'ai introduit cet exemple dans le but. Imaginons que vous jetiez des pièces, par exemple 100 fois. Tant que ces pièces sont non biaisées, vous encoderiez simplement les résultats du lancer avec une séquence de 0-1 bits (1 tête, 0 queue). Dans une telle situation, lorsque la probabilité de la tête est la même que la probabilité de la queue et égale à 0,5, le codage est très efficace. Maintenant, nous avons quelques pièces biaisées, nous préférerions donc coder des résultats plus probables avec un code plus court, par exemple fusionner des groupes de têtes et de queues et représenter des séquences de k têtes avec un code plus long que la séquence de k queues (elles sont plus probables). Et ici, la divergence de Kullback-Leibler . Si P représente la vraie distribution des résultats et que Q n’est qu’une approximation de P, alorsD(P||Q)D(P||Q) indique la pénalité que vous payez lorsque vous codez des résultats qui proviennent en réalité de P distrib avec un codage destiné à Q (pénalité au sens des bits supplémentaires que vous devez utiliser).

Si vous avez simplement besoin d'une métrique, utilisez la distance de Bhattacharyya (bien sûr, la version modifiée )1[xp(x)q(x)]

Adam Przedniczek
la source
7
Si l’on veut vraiment avoir une métrique plus proche de la divergence de KL, on pourrait considérer la racine carrée de la divergence de Jensen-Shannon à la place de Bhattacharyya.
cardinal
5

Je suis tenté de donner ici une réponse purement intuitive à votre question. En reformulant ce que vous dites, la divergence KL est un moyen de mesurer la distance entre deux distributions, comme vous le feriez pour calculer la distance entre deux ensembles de données dans un espace de Hilbert, mais vous devez faire preuve de prudence.

Pourquoi? La divergence KL n'est pas une distance comme celle que vous pouvez utiliser habituellement, telle que par exemple la norme . En effet, il est positif et égal à zéro si et seulement si les deux distributions sont égales (comme dans les axiomes pour définir une distance). Mais comme mentionné, ce n'est pas symétrique. Il y a moyen de contourner cela, mais il est logique que ce ne soit pas symétrique.L2

En effet, la divergence KL définit la distance entre une distribution de modèle (que vous connaissez réellement) et une distribution théorique telle qu’il soit logique de traiter différemment (la distance "théorique" de à supposant que modèle ) et (la distance "empirique" de à supposant que les données ) signifient des mesures très différentes.QPKL(P,Q)PQPKL(Q,P)PQQ

meduz
la source
5

Le manuel Elements of Information Theory nous donne un exemple:

Par exemple, si nous connaissions la vraie distribution p de la variable aléatoire, nous pourrions construire un code avec une longueur de description moyenne H (p). Si, au contraire, nous utilisions le code pour une distribution q, nous aurions besoin de H (p) + D (p || q) bits en moyenne pour décrire la variable aléatoire.

Pour paraphraser la déclaration ci-dessus, nous pouvons dire que si nous changeons la distribution de l'information (de q à p), nous avons besoin de D (p || q) en moyenne, bits supplémentaires pour coder la nouvelle distribution.

Une illustration

Permettez-moi d'illustrer cela en utilisant une application de celui-ci dans le traitement du langage naturel.

Considérez qu'un grand groupe de personnes, étiquetée B, sont des médiateurs et chacun d'eux se voit attribuer une tâche de choisir un nom de turkey, animalet booket le transmettre à C. Il y a un nom de type A qui peut envoyer chacun d'eux un courriel à donner leur quelques allusions. Si personne dans le groupe n'a reçu l'e-mail, ils peuvent lever les sourcils et hésiter pendant un moment en considérant les besoins de C. Et la probabilité que chaque option soit choisie est de 1/3. Distribution fondamentalement uniforme (sinon, cela peut être lié à leurs propres préférences et nous ignorons simplement de tels cas).

Mais si on leur donne un verbe, par exemple baste, 3/4 d'entre eux peuvent choisir turkeyet 3/16 choisir animalet 1/16 choisir book. Alors combien d’informations en bits chacun des médiateurs en moyenne a obtenu une fois qu’ils connaissent le verbe? Il est:

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

Mais que faire si le verbe donné est read? On peut imaginer que tous choisiraient booksans hésiter, alors le gain d'information moyen pour chaque médiateur du verbe readest:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Nous pouvons voir que le verbe readpeut donner plus d’informations aux médiateurs. Et c'est ce que l'entropie relative peut mesurer.

Continuons notre histoire. Si C soupçonne que le nom peut être faux parce que A lui a dit qu'il aurait pu se tromper en envoyant le mauvais verbe aux médiateurs. Alors combien d’informations en bits une telle mauvaise nouvelle peut-elle donner à C?

1) si le verbe donné par A était 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) mais si le verbe était read?

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

Puisque C ne sait jamais ce que seraient les deux autres noms et que n'importe quel mot du vocabulaire serait possible.

Nous pouvons voir que la divergence KL est asymétrique.

J'espère que j'ai raison, et si ce n'est pas le cas, commentez et aidez-moi à me corriger. Merci d'avance.

Lerner Zhang
la source