Fragen zur KL-Divergenz?

14

Ich vergleiche zwei Verteilungen mit der KL-Divergenz, die mir eine nicht standardisierte Zahl zurückgibt, die nach dem, was ich über diese Kennzahl gelesen habe, die Informationsmenge ist, die erforderlich ist, um eine Hypothese in die andere umzuwandeln. Ich habe zwei Fragen:

a) Gibt es eine Möglichkeit, eine KL-Divergenz so zu quantifizieren, dass sie aussagekräftiger interpretiert wird, z. B. wie eine Effektgröße oder ein R ^ 2? Jede Form von Standardisierung?

b) In R kann bei Verwendung von KLdiv (Flexmix-Paket) der 'esp'-Wert (Standard esp = 1e-4) festgelegt werden, der alle Punkte kleiner als esp auf einen Standard setzt, um numerische Stabilität zu gewährleisten. Ich habe mit verschiedenen esp-Werten gespielt und für meinen Datensatz erhalte ich eine zunehmend größere KL-Divergenz, je kleiner eine Zahl ist, die ich auswähle. Was ist los? Ich würde erwarten, dass die Ergebnisse umso zuverlässiger sind, je kleiner der esp ist, da sie mehr „reale Werte“ in die Statistik einfließen lassen. Nein? Ich muss das esp ändern, da es sonst die Statistik nicht berechnet sondern einfach als NA in der Ergebnistabelle auftaucht ...

Genug weiter
quelle

Antworten:

9

Angenommen, Sie erhalten n IID-Samples, die entweder von p oder von q generiert wurden. Sie möchten identifizieren, welche Verteilung sie generiert hat. Nehmen Sie als Nullhypothese an, dass sie von q erzeugt wurden. Geben Sie a die Wahrscheinlichkeit eines Fehlers vom Typ I an, wobei die Nullhypothese fälschlicherweise verworfen wird, und b die Wahrscheinlichkeit eines Fehlers vom Typ II.

Dann ist für großes n die Wahrscheinlichkeit eines Fehlers vom Typ I mindestens

exp(-nKL(p,q))

Mit anderen Worten, für ein "optimales" Entscheidungsverfahren fällt die Wahrscheinlichkeit des Typs I mit jedem Datenpunkt höchstens um einen Faktor exp (KL (p, q)). Der Fehler vom Typ II fällt höchstens um den Faktor .exp(KL(q,p))

Für beliebiges n sind a und b wie folgt verwandt

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

und

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

Wenn wir die obige Schranke als die untere Schranke von a in Form von b und KL ausdrücken und b auf 0 verringern, scheint sich das Ergebnis der "exp (-n KL (q, p))" - Schranke auch für kleines n zu nähern

Weitere Details auf Seite 10 hier und auf den Seiten 74-77 von Kullback des „Informationstheorie und Statistik“ (1978).

Als Randnotiz kann diese Interpretation verwendet werden, um die Fisher-Informationsmetrik zu motivieren , da für jedes Verteilungspaar p, q im Fisher-Abstand k (kleines k) die gleiche Anzahl von Beobachtungen erforderlich ist, um sie voneinander zu unterscheiden

Jaroslaw Bulatow
quelle
1
+1 Diese Interpretation gefällt mir! Können Sie "p unter e" klarstellen? warum nimmst du kleine e? Sie sagen, "die Wahrscheinlichkeit, den gegenteiligen Fehler zu machen, ist", es ist eine obere Schranke oder eine genaue Wahrscheinlichkeit? Wenn ich mich erinnere, ist diese Art von Ansatz auf Chernoff zurückzuführen. Haben Sie die Referenzen (ich finde, Ihre erste Referenz ist nicht klar :))?
Robin Girard
1
Warum nehme ich ein kleines e ... hmm ... das ist, was Balasubramanians Papier getan hat, aber jetzt, zurück zu Kullback, scheint es, dass seine Bindung für jedes e gilt, und er gibt auch gebunden für endliche n, lassen Sie mich die Antwort aktualisieren
Jaroslaw Bulatow
ok, wir brauchen kein kleines e (jetzt b, Typ II-Fehler genannt), damit es klein bleibt, aber b = 0 ist der Wert, für den das vereinfachte (exp (-n KL (p, q)) gebunden wird entspricht der komplizierteren Schranke oben. Seltsamerweise ist die untere Schranke für Typ I-Fehler bei 0 Typ II-Fehler <1, ​​ich frage mich, ob <1 Typ II-Fehlerrate tatsächlich erreichbar ist
Jaroslaw Bulatow
1
Tatsächlich ist die Referenz zu Covers "Elementen der Informationstheorie", Seite 309, 12.8 "Steins Lemma"
Jaroslaw Bulatow,
8

KL hat eine tiefe Bedeutung, wenn Sie eine Reihe von Zahnersatzteilen als Mannigfaltigkeit innerhalb des Fischertensors visualisieren. Sie gibt den geodätischen Abstand zwischen zwei "nahen" Verteilungen an. Formal:

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

Die folgenden Zeilen erläutern detailliert, was mit diesen mathematischen Formeln gemeint ist.

Definition der Fisher-Metrik.

Betrachten wir eine parametrisierten Familie von Wahrscheinlichkeitsverteilungen (gegeben durch Dichten in R n ), wobei x eine Zufallsvariable ist und Theta ist ein Parameter in R p . Sie können alle wissen, dass die Fischerinformationsmatrix F = ( F i j ) istD=(f(x,θ))RnxRpF=(Fij)

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

Mit dieser Notation ist eine Riemannsche Mannigfaltigkeit und F ( θ ) ist ein Riemannscher metrischer Tensor. (Das Interesse dieser Metrik wird durch den unteren Satz von Cramer Rao gegeben.)DF(θ)

Sie können sagen ... OK mathematische Abstraktion, aber wo ist KL?

Es ist keine mathematische Abstraktion, wenn , können Sie sich Ihre parametrisierte Dichte wirklich als Kurve vorstellen (anstelle einer Teilmenge eines Raums unendlicher Dimension) und F 11 ist mit der Krümmung dieser Kurve verbunden ... (siehe das Seminal) Artikel von Bradley Efron ( http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176343282 )p=1F11

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

ds2=Fijdθidθj

und es ist bekannt, dass es die doppelte Kullback-Leibler-Divergenz ist:

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
quelle
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
quelle
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
quelle