Eine Anpassung der Kullback-Leibler-Distanz?

28

Schau dir dieses Bild an: Bildbeschreibung hier eingeben

Wenn wir eine Stichprobe aus der Rotdichte ziehen, werden einige Werte voraussichtlich unter 0,25 liegen, während es unmöglich ist, eine solche Stichprobe aus der Blauverteilung zu erzeugen. Infolgedessen ist der Kullback-Leibler-Abstand von der roten zur blauen Dichte unendlich. Die beiden Kurven sind jedoch in gewissem "natürlichen Sinne" nicht so verschieden.

Hier ist meine Frage: Gibt es eine Anpassung des Kullback-Leibler-Abstandes, die einen endlichen Abstand zwischen diesen beiden Kurven erlauben würde?

Ocram
quelle
1
In welchem ​​"natürlichen Sinne" sind diese Kurven "nicht so verschieden"? Wie hängt diese intuitive Nähe mit einer statistischen Eigenschaft zusammen? (Ich kann mir mehrere Antworten
überlegen,
1
Nun ... sie sind ziemlich nahe beieinander in dem Sinne, dass beide über positive Werte definiert sind; sie nehmen beide zu und dann ab; beide haben eigentlich die gleiche Erwartung; und der Kullback-Leibler-Abstand ist "klein", wenn wir uns auf einen Teil der x-Achse beschränken ... Um diese intuitiven Begriffe mit einer statistischen Eigenschaft zu verknüpfen, würde ich eine strenge Definition für diese Merkmale benötigen ...
ocram

Antworten:

18

Sie können sich Kapitel 3 von Devroye, Gyorfi und Lugosi, Eine probabilistische Theorie der Mustererkennung , Springer, 1996, ansehen. Siehe insbesondere den Abschnitt über Divergenzen.f

Abweichungen können als eine Verallgemeinerung von Kullback-Leibler angesehen werden (oder alternativ kann KL als ein Spezialfall einer f- Abweichung angesehen werden).ff

Die allgemeine Form ist

Df(p,q)=q(x)f(p(x)q(x))λ(dx),

wobei ein Maß ist, das die mit p und q verbundenen Maße dominiert, und f ( ) eine konvexe Funktion ist, die f ( 1 ) = 0 erfüllt . (Wenn p ( x ) und q ( x ) sind Dichten in Bezug auf Lebesguemaß, ersetzen nur die Schreibweise d x für λ ( d x ) und du bist gut zu gehen.)λpqf()f(1)=0p(x)q(x)dxλ(dx)

Wir erholen KL, indem wir . Wir können die Hellinger-Differenz über f ( x ) = ( 1 - √ erhaltenf(x)=xlogxund wir erhalten dieGesamtvariationoderL1Entfernung, indem wirf(x)= 1 nehmenf(x)=(1x)2L1. Letzteres gibtf(x)=12|x1|

DTV(p,q)=12|p(x)q(x)|dx

Beachten Sie, dass dies mindestens eine endliche Antwort gibt.

In einem weiteren kleinen Buch mit dem Titel Density Estimation: The ViewL1 spricht sich Devroye (unter anderem) stark für die Verwendung dieser letzteren Distanz aus. Dieses letztere Buch ist wahrscheinlich etwas schwieriger zu bekommen als das erste und, wie der Titel andeutet, etwas spezialisierter.


Nachtrag : Durch diese Frage wurde mir bewusst, dass es den Anschein hat, dass das von @Didier vorgeschlagene Maß (bis zu einer Konstanten) als Jensen-Shannon-Divergenz bekannt ist. Wenn Sie dem Link zu der Antwort in dieser Frage folgen, werden Sie feststellen, dass es sich bei der Quadratwurzel dieser Größe tatsächlich um eine Metrik handelt, die in der Literatur zuvor als Spezialfall für eine Abweichung erkannt wurde . Ich fand es interessant, dass wir das Rad (ziemlich schnell) durch die Diskussion dieser Frage kollektiv "neu erfunden" haben. Die Interpretation, die ich in dem Kommentar unter @ Didiers Antwort dazu gegeben habe, wurde auch zuvor erkannt. Alles in allem irgendwie ordentlich.f

Kardinal
quelle
1
Sehr schön! Ich werde versuchen, "Eine probabilistische Theorie der Mustererkennung" zu finden und ihr Kapitel 3 zu verstehen!
Ocram
1
Gute Antwort, beachte, dass am häufigsten auf eine andere Weise definiert wird, die es zur Hälfte des L 1 -Abstands macht. DTVL1
Robin Girard
1
@robin, danke für deinen Kommentar. Ja, das merke ich. Ich habe nur versucht, eine chaotische Nebenkonstante in der Ausstellung zu vermeiden. Aber genau genommen haben Sie recht. Ich habe es entsprechend aktualisiert.
Kardinal
3
Ihr Nachtrag ist die nützlichste Information, die ich bisher über stats.SE erhalten habe. Herzlichen Dank dafür. Ich reproduziere hier einfach die Referenz, die Sie angegeben haben: research-repository.st-andrews.ac.uk/bitstream/10023/1591/1/… Endres und Schindelin, Eine neue Metrik für Wahrscheinlichkeitsverteilungen, IEEE Trans. auf Info. Deine. vol. 49, nein. 3, Jul. 2003, S. 1858-1860.
Habe
1
@Didier, well, it was more a happy accident than anything else. No one was responding to the other question, so I decided to try to figure out what the Jensen-Shannon Divergence was in the first place. Once I found the definition, it seemed reasonable to connect the two questions via my addendum. I'm glad you found it useful. Regards.
cardinal
19

κ(P|Q)PQPQAQ(A)=0P(A)0κ(PQ)κ(QP). Recall that

κ(PQ)=Plog(PQ).
A way out of both these drawbacks, still based on KL divergence, is to introduce the midpoint
R=12(P+Q).
Thus R is a probability measure, and P and Q are always absolutely continuous with respect to R. Hence one can consider a "distance" between P and Q, still based on KL divergence but using R, defined as
η(P,Q)=κ(PR)+κ(QR).
Then η(P,Q) is nonnegative and finite for every P and Q, η is symmetric in the sense that η(P,Q)=η(Q,P) for every P and Q, and η(P,Q)=0 iff P=Q.

An equivalent formulation is

η(P,Q)=2log(2)+(Plog(P)+Qlog(Q)(P+Q)log(P+Q)).

Addendum 1 The introduction of the midpoint of P and Q is not arbitrary in the sense that

η(P,Q)=min[κ(P)+κ(Q)],
where the minimum is over the set of probability measures.

Addendum 2 @cardinal remarks that η is also an f-divergence, for the convex function

f(x)=xlog(x)(1+x)log(1+x)+(1+x)log(2).
Did
quelle
2
@Marco, @Didier Piau, it might be noted that @Didier's suggestion is another special case of an f-divergence where f(x)=xlogx(1+x)log(1+x2).
cardinal
1
@Marco, @Didier Piau, an alternative formulation which has some evocative nature is η(P,Q)=PlogP+QlogQ2RlogR=2H(R)(H(P)+H(Q)) and so η(P,Q)=2(H(μ(P,Q))μ(H(P),H(Q)) where μ(x,y)=x+y2. In other words, 12η(P,Q) is "difference between the entropy of the average measure and the average entropy of the measures".
cardinal
3
Isn't this just the Jensen-Shannon divergence?
Memming
"where the minimum is over the set of probability measures." I like this characterization of the Jensen–Shannon divergence. Is there a proof of it somewhere?
user76284
10

The Kolmogorov distance between two distributions P and Q is the sup norm of their CDFs. (This is the largest vertical discrepancy between the two graphs of the CDFs.) It is used in distributional testing where P is an hypothesized distribution and Q is the empirical distribution function of a dataset.

It is hard to characterize this as an "adaptation" of the KL distance, but it does meet the other requirements of being "natural" and finite.

Incidentally, because the KL divergence is not a true "distance," we don't have to worry about preserving all the axiomatic properties of a distance. We can maintain the non-negativity property while making the values finite by applying any monotonic transformation R+[0,C] for some finite value C. The inverse tangent will do fine, for instance.

whuber
quelle
1
Thank you for your suggestion about the Kolmogorov distance. Can you make your comment about the monotonic transformation a little bit more explicit? Thx
ocram
1
@Marco I don't understand how one could be any more explicit. Do you mean restating what I wrote in terms of a formula such as arctan(KL(P,Q)) or f(KL(P,Q)) for f:R+[0,C] with xy implies f(x)f(y) for all x,y0?
whuber
1
Yes, that's what I meant :-) I was not sure on what to apply the transformation. Now, it is clear, thx
ocram
1
@Marco: I am lost. Do you settle for the Kolmogorov distance (which is always finite but has nothing in common with KL divergence)? Or for a bounded monotone transform of KL divergence (such as arctan)? In the example of your post (and in any other not absolutely continuous example), the latter produces the supremum of the transform (π/2 if you settle for arctan). In effect, this abandons any idea of estimating a distance between such probability measures more precisely than saying they are far far away (whether you encode this by π/2 or by + is irrelevant).
Did
@Didier Yes, the transformed KL divergence (when symmetrized, as you describe) might not satisfy the triangle inequality and therefore would not be a distance, but it would still define a topology (which would likely be metrizable). You would thereby give up little or nothing. I remain agnostic about the merits of doing any of this: it seems to me this is just a way of papering over the difficulties associated with infinite values of the KL divergence in the first place.
whuber
2

Yes there does, Bernardo and Reuda defined something called the "intrinsic discrepancy" which for all purposes is a "symmetrised" version of the KL-divergence. Taking the KL divergence from P to Q to be κ(PQ) The intrinsic discrepancy is given by:

δ(P,Q)min[κ(PQ),κ(QP)]

Searching intrinsic discrepancy (or bayesian reference criterion) will give you some articles on this measure.

In your case, you would just take the KL-divergence which is finite.

Another alternative measure to KL is Hellinger distance

EDIT: clarification, some comments raised suggested that the intrinsic discrepancy will not be finite when one density 0 when the other is not. This is not true if the operation of evaluating the zero density is carried out as a limit Q0 or P0 . The limit is well defined, and it is equal to 0 for one of the KL divergences, while the other one will diverge. To see this note:

δ(P,Q)min[Plog(PQ),Qlog(QP)]

Taking limit as P0 over a region of the integral, the second integral diverges, and the first integral converges to 0 over this region (assuming the conditions are such that one can interchange limits and integration). This is because limz0zlog(z)=0. Because of the symmetry in P and Q the result also holds for Q.

probabilityislogic
quelle
1
Even the "intrinsic discrepancy" will be infinite when P is zero with positive probability for Q and vice versa, even if P and Q are otherwise identical.
whuber
1
Yes... I am afraid that the intrinsic discrepancy does not fulfil the requirement. But thank you for the suggestion. Any other suggestion would be appreciated.
ocram
1
It does fulfil the requirement, if you restrict the support of the blue density to be where it has strictly positive support, just as you have for the red one (>0)
probabilityislogic
3
@probabilityislogic: I do not unerstand your last remarks. First, let us give their proper names to the notions involved and say that P is absolutely continuous with respect to Q (denoted PQ) if, for every measurable A, Q(A)=0 implies P(A)=0. Now, notwithstanding your somewhat mysterious (to me) limit considerations, your δ(P,Q) is finite iff PQ or QP. .../...
Did
2
.../... A way out of the conundrum you seem to be dug into might be to introduce the mid-point measure P+Q. Since PP+Q and QP+Q, the quantity η(P,Q):=κ(P|P+Q)+κ(Q|P+Q) is always finite. Furthermore η(P,Q)=0 iff P=Q and η is symmetric. Hence η(P,Q) indeed measures a kind of "distance" between P and Q.
Did