Kullback-Leibler-Divergenz für zwei Proben

10

Ich habe versucht, eine numerische Schätzung der Kullback-Leibler-Divergenz für zwei Stichproben zu implementieren. Um die Implementierung zu debuggen, ziehen Sie die Stichproben aus zwei Normalverteilungen und N ( 1 , 2 ) .N(0,1)N(1,2)

Für eine einfache Schätzung habe ich zwei Histogramme erstellt und versucht, das Integral numerisch zu approximieren. Ich habe mich nicht mehr mit den Teilen des Histogramms befasst, bei denen die Fächer eines der Histogramme Null sind, sodass ich entweder durch Null oder den Logarithmus von Null dividiere. Wie gehe ich mit diesem Problem um?

Eine verwandte Frage kam mir in den Sinn: Wie kann man die KL-Divergenz zwischen zwei verschiedenen Gleichverteilungen genau berechnen? Muss ich das Integral auf die Vereinigung der Unterstützung beider Distributionen beschränken?

Jimbob
quelle
Nun, die Unterstützung der Normalverteilung ist die Menge der reellen Zahlen. In der reinen Mathematik gibt es kein Problem, aber für Ihre numerische Annäherung müssen Sie sicherstellen, dass Ihre Stichprobengröße im Verhältnis zu der Region, über die Sie integrieren möchten, groß genug ist. Sie werden nicht in der Lage sein, über (-inf, + inf) zu integrieren, wie Sie es in reiner Mathematik können ... Möchten Sie etwas Vernünftiges? Wenn Sie mehr als 3 Standardabweichungen vom Mittelwert entfernt sind, wird es ziemlich dünn ...
Matthew Gunn
1
In Bezug auf Ihre zweite Frage ist die KL-Divergenz zwischen zwei verschiedenen Gleichverteilungen undefiniert ( ist undefiniert). In ähnlicher Weise ist die KL-Divergenz für zwei empirische Verteilungen undefiniert, es sei denn, jede Probe hat mindestens eine Beobachtung mit dem gleichen Wert wie jede Beobachtung in der anderen Probe. log(0)
Jbowman
@jbowman Kleine Notiz. Obwohl Sie Recht haben, dass undefiniert ist (oder - ), ist es in der Informationstheorie üblich, log ( 0 ) 0 als 0 zu behandeln . log(0)log(0)00
Luca Citi
Eine ähnliche Frage: mathoverflow.net/questions/119752/…
kjetil b halvorsen

Antworten:

9

Die Kullback-Leibler-Divergenz ist definiert als Um dies aus empirischen Daten zu berechnen (abzuschätzen), benötigen wir möglicherweise einige Schätzungen der Dichtefunktionen p ( x ) , q (

KL(P||Q)=p(x)logp(x)q(x)dx
. Ein natürlicher Ausgangspunkt könnte also eine Dichteschätzung sein (und danach nur noch eine numerische Integration). Wie gut oder stabil eine solche Methode wäre, weiß ich nicht.p(x),q(x)

Aber zuerst Ihre zweite Frage, dann komme ich zur ersten zurück. Nehmen wir an, und q sind einheitliche Dichten für [ 0 , 1 ] bzw. [ 0 , 10 ] . Dann ist KL ( p | | q ) = log 10, während KL ( q | | p ) schwieriger zu definieren ist, aber der einzig vernünftige Wert ist , soweit ich sehen kann, da es die Integration von logpq[0,1][0,10]KL(p||q)=log10KL(q||p). Diese Ergebnisse sind aus der Interpretation, die ich inIntuition über die Kullback-Leibler (KL) -Divergenzgebe, vernünftiglog(1/0)was wir wählen können, um als log zu interpretierenlog

Zurück zur Hauptfrage. Es wird sehr nichtparametrisch abgefragt, und es werden keine Annahmen über die Dichten gemacht. Wahrscheinlich sind einige Annahmen erforderlich. Unter der Annahme, dass die beiden Dichten als konkurrierende Modelle für dasselbe Phänomen vorgeschlagen werden, können wir wahrscheinlich annehmen, dass sie dasselbe dominierende Maß haben: Die KL-Divergenz zwischen einer kontinuierlichen und einer diskreten Wahrscheinlichkeitsverteilung wäre beispielsweise immer unendlich. Ein Artikel, der sich mit dieser Frage befasst, lautet wie folgt: https://pdfs.semanticscholar.org/1fbd/31b690e078ce938f73f14462fceadc2748bf.pdf Sie schlagen eine Methode vor, für die keine vorläufige Dichteschätzung erforderlich ist, und analysieren ihre Eigenschaften.

(Es gibt viele andere Papiere). Ich werde zurückkommen und einige Details aus diesem Papier veröffentlichen, die Ideen.

 EDIT               

Einige Ideen aus diesem Artikel, in denen es um die Abschätzung der KL-Divergenz mit iid-Proben aus absolut kontinuierlichen Verteilungen geht. Ich zeige ihren Vorschlag für eindimensionale Verteilungen, aber sie geben auch eine Lösung für Vektoren (unter Verwendung der Schätzung der Dichte des nächsten Nachbarn). Für Beweise lesen Sie das Papier!

Sie schlagen vor, eine Version der empirischen Verteilungsfunktion zu verwenden, die jedoch linear zwischen Stichprobenpunkten interpoliert wird, um eine kontinuierliche Version zu erhalten. Sie definieren

Pe(x)=1ni=1nU(xxi)
UU(0)=0.5Pcc
D^(PQ)=1ni=1nlog(δPc(xi)δQc(xi))
δPc=Pc(xi)Pc(xiϵ)ϵ eine Zahl ist, die kleiner als der kleinste Abstand der Proben ist.

R-Code für die Version der empirischen Verteilungsfunktion, die wir benötigen, ist

my.ecdf  <-  function(x)   {
    x   <-   sort(x)
    x.u <-   unique(x)
    n  <-  length(x) 
    x.rle  <-  rle(x)$lengths
    y  <-  (cumsum(x.rle)-0.5) / n
    FUN  <-  approxfun(x.u, y, method="linear", yleft=0, yright=1,
                           rule=2)
    FUN
}          

Beachten Sie, dass rleder Fall mit Duplikaten bearbeitet wirdx .

Dann ist die Schätzung der KL-Divergenz gegeben durch

KL_est  <-  function(x, y)   {
    dx  <-  diff(sort(unique(x)))
    dy  <-  diff(sort(unique(y)))
    ex  <-  min(dx) ; ey  <-  min(dy)
    e   <-  min(ex, ey)/2
    n   <-  length(x)    
    P  <-   my.ecdf(x) ; Q  <-  my.ecdf(y)
    KL  <-  sum( log( (P(x)-P(x-e))/(Q(x)-Q(x-e)))) / n
    KL              
}

Dann zeige ich eine kleine Simulation:

KL  <-  replicate(1000, {x  <-  rnorm(100)
                         y <- rt(100, df=5)
                         KL_est(x, y)})
hist(KL, prob=TRUE)

Dies ergibt das folgende Histogramm, das (eine Schätzung) der Stichprobenverteilung dieses Schätzers zeigt:

Stichprobenverteilung des KL-Schätzers

Zum Vergleich berechnen wir die KL-Divergenz in diesem Beispiel durch numerische Integration:

LR  <-  function(x) dnorm(x,log=TRUE)-dt(x,5,log=TRUE)
100*integrate(function(x) dnorm(x)*LR(x),lower=-Inf,upper=Inf)$value
[1] 3.337668

hmm ... der Unterschied ist groß genug, dass es hier viel zu untersuchen gibt!

kjetil b halvorsen
quelle
5

Ich habe die Antwort von kjetil-b-halvorsen ein wenig erweitert und es tut mir leid, dass ich nicht kommentiert habe. Ich habe nicht den Ruf:

  1. Ich habe das Gefühl, dass die analytische Berechnung sein sollte (ohne Multiplikation mit 100):

LR <- function(x) dnorm(x,log=TRUE)-dt(x,5,log=TRUE) integrate(function(x) dnorm(x)*LR(x),lower=-Inf,upper=Inf)$value

  1. D^(P||Q)D^(P||Q)1D(P||Q)

Sobald diese beiden Korrekturen vorgenommen wurden, erscheinen die Ergebnisse realistischer.

ColibriIO
quelle
Danke, ich werde das prüfen und meine Antwort aktualisieren.
kjetil b halvorsen