Des questions sur la divergence KL?

14

Je compare deux distributions avec une divergence KL qui me renvoie un nombre non standardisé qui, selon ce que j'ai lu sur cette mesure, est la quantité d'informations nécessaires pour transformer une hypothèse en l'autre. J'ai deux questions:

a) Existe-t-il un moyen de quantifier une divergence KL afin qu'elle ait une interprétation plus significative, par exemple comme une taille d'effet ou un R ^ 2? Toute forme de normalisation?

b) Dans R, lorsque vous utilisez KLdiv (package flexmix), vous pouvez définir la valeur 'esp' (standard esp = 1e-4) qui définit tous les points plus petits que esp sur une certaine norme afin de fournir une stabilité numérique. J'ai joué avec différentes valeurs esp et, pour mon ensemble de données, j'obtiens une divergence KL de plus en plus grande, plus un nombre est petit. Que se passe-t-il? Je m'attends à ce que plus l'esp est petite, plus les résultats devraient être fiables car ils laissent plus de «valeurs réelles» faire partie de la statistique. Non? Je dois changer l'esp car sinon il ne calcule pas la statistique mais apparaît simplement comme NA dans le tableau des résultats ...

Ampleforth
la source

Réponses:

10

Supposons que l'on vous donne n échantillons IID générés par p ou par q. Vous souhaitez identifier la distribution qui les a générés. Prenez comme hypothèse nulle qu'elles ont été générées par q. Soit a une probabilité d'erreur de type I, rejetant par erreur l'hypothèse nulle, et b une probabilité d'erreur de type II.

Alors pour un grand n, la probabilité d'erreur de type I est au moins

exp(nKL(p,q))

En d'autres termes, pour une procédure de décision "optimale", la probabilité de type I diminue au maximum d'un facteur exp (KL (p, q)) à chaque point de donnée. L'erreur de type II diminue au maximum du facteur .exp(KL(q,p))

Pour n arbitraire, a et b sont liés comme suit

blogb1a+(1b)log1banKL(p,q)

et

aloga1b+(1a)log1abnKL(q,p)

Si nous exprimons la borne ci-dessus en tant que borne inférieure sur a en termes de b et KL et diminuons b à 0, le résultat semble approcher la borne "exp (-n KL (q, p))" même pour les petits n

Plus de détails à la page 10 ici , et aux pages 74-77 de "Theory Information and Statistics" de Kullback (1978).

En remarque, cette interprétation peut être utilisée pour motiver la métrique de Fisher Information, car pour toute paire de distributions p, q à la distance de Fisher k l'une de l'autre (petite k), vous avez besoin du même nombre d'observations pour les distinguer

Yaroslav Bulatov
la source
1
+1 J'aime cette interprétation! pourriez-vous clarifier "p en dessous de e"? pourquoi prenez-vous un petit e? vous dites que "la probabilité de faire l'erreur inverse est" est-ce une probabilité supérieure ou exacte? Si je me souviens bien, ce type d'approche est dû à Chernoff, avez-vous les références (je trouve que votre première référence ne clarifie pas le point :))?
robin girard
1
Pourquoi est-ce que je prends un petit e ... hmm ... c'est ce que le papier de Balasubramanian a fait, mais maintenant, pour en revenir à Kullback, il semble que sa limite soit valable pour tout e, et il donne également une limite pour n fini, permettez-moi de mettre à jour la réponse
Yaroslav Bulatov
ok, nous n'avons pas besoin que le petit e (maintenant appelé b, erreur de type II) soit petit pour que la borne soit maintenue, mais b = 0 est la valeur pour laquelle la borne simplifiée (exp (-n KL (p, q))) correspond à la limite la plus compliquée ci-dessus. Curieusement, la limite inférieure pour l'erreur de type I étant donnée 0 l'erreur de type II est <1, je me demande si <1 le taux d'erreur de type II est réellement réalisable
Yaroslav Bulatov
1
En fait, une référence beaucoup plus facile à comprendre pour cela est "Elements of Information Theory", page 309, 12.8 "Stein's Lemma"
Yaroslav Bulatov
8

KL a une signification profonde lorsque vous visualisez un ensemble de dentités comme un collecteur dans le tenseur métrique de Fisher , il donne la distance géodésique entre deux distributions "proches". Officiellement:

ds2=2KL(p(x,θ),p(x,θ+dθ))

Les lignes suivantes sont ici pour expliquer en détail ce que l'on entend par ces formules mathématiques las.

Définition de la métrique de Fisher.

Considérons une famille paramétrée de distributions de probabilité (donnée par les densités dans R n ), où x est une variable aléatoire et thêta est un paramètre dans R p . Vous savez tous que la matrice d’information du pêcheur F = ( F i j ) estD=(f(x,θ))RnxRpF=(Fij)

Fij=E[d(logf(x,θ))/dθid(logf(x,θ))/dθj]

Avec cette notation, est une variété riemannienne et F ( θ ) est un tenseur métrique riemannien. (L'intérêt de cette métrique est donné par le théorème de la borne inférieure du cramer Rao)DF(θ)

Vous pouvez dire ... OK abstraction mathématique mais où est KL?

p=1F11

ds2p(x,θ)p(x,θ+dθ)

ds2=Fijdθidθj

and it is known to be twice the Kullback Leibler Divergence:

ds2=2KL(p(x,θ),p(x,θ+dθ))

If you want to learn more about that I suggest reading the paper from Amari http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176345779 (I think there is also a book from Amari about riemannian geometry in statistic but I don't remember the name)

robin girard
la source
Please add $ around your LaTeX. It should now be rendered ok. See meta.math.stackexchange.com/questions/2/…
Rob Hyndman
1
Since I am not a mathematician nor a statistician, I would like to restate what you were saying to make sure I did not mis-understand. So, you are saying that taking ds^2 (twice the KL) would have a similar meaning as R^2 (in a regression model) for a general distribution. And that this could actually be used to quantify distances geometrically? Does ds^2 have a name so I can do more reading about this. Is there a paper that directly describes this metric and shows applications and examples?
Ampleforth
I think you are far from understanding the point, and I am not sure you should try to go further now. If you are motivated, you can read the paper from Bradley Efron I mentionned or that paper from Amari projecteuclid.org/….
robin girard
1
This seems to be a characterization of directional derivative of KL rather than of KL itself, and it doesn't seem possible to get KL divergence out of it because unlike the derivative, KL-divergence doesn't depend on the geometry of the manifold
Yaroslav Bulatov
7

The KL(p,q) divergence between distributions p(.) and q(.) has an intuitive information theoretic interpretation which you may find useful.

Suppose we observe data x generated by some probability distribution p(.). A lower bound on the average codelength in bits required to state the data generated by p(.) is given by the entropy of p(.).

Now, since we don't know p(.) we choose another distribution, say, q(.) to encode (or describe, state) the data. The average codelength of data generated by p(.) and encoded using q(.) will necessarily be longer than if the true distribution p(.) was used for the coding. The KL divergence tells us about the inefficiencies of this alternative code. In other words, the KL divergence between p(.) and q(.) is the average number of extra bits required to encode data generated by p(.) using coding distribution q(.). The KL divergence is non-negative and equal to zero iff the actual data generating distribution is used to encode the data.

emakalic
la source
2

For part (b) of your question, you might be running into the problem that one of of your distributions has density in a region where the other does not.

D(PQ)=pilnpiqi

This diverges if there exists an i where pi>0 and qi=0. The numerical epsilon in the R implementation "saves you" from this problem; but it means that the resulting value is dependent on this parameter (technically qi=0 is no required, just that qi is less than the numerical epsilon).

Dave
la source