Is it Possible to Calculate Information Distances like the KL and Jensen-Shannon Divergences on EDFs and CDFs?

Question

With the data I'm currently analyzing, it is easier to derive the EDFs than the PDFs; furthermore, I'm much more comfortable using CDF-EDF goodness-of-fit tests like the Kolmgorov-Smirnov and Anderson-Darling, which I already have code for. I would also like to calculate a multitude of information and probabilistic distances (also metrics and divergences; I'm not using the technical terminology here) as a matter of routine for EDA purposes, including those in Cha Sung-Hyuk's incredibly useful taxonomy of distance measures1, as well as some from the Dezas' classic Dictionary of Distances2.

Many of these measures, however, are applied to PDFs, whereas it would be more convenient for me to apply them to CDFs and EDFs. In most cases, I would not be using them to test the fit to the CDF of some arbitrary reference distribution, but as a measure of difference between the known EDFs of two columns. Is it valid to substitute EDFs and CDFs in measures like the Kullback-Leibler and Jensen-Shannon Divergences and if so, does it change their properties in any appreciable way? If not, why so and are there any comparable analogs that we can substitute to measure the same quantities, like relative entropy? I have a passing familiarity with some of these probabilistic and information distances, particularly the KL and Jensen-Shannon, but still have much to learn about them, so this may be a dumb question with an obvious answer; I suspect I may be trying to apply a solution designed for apples to a problem involving oranges, so to speak, but cannot pin it down. Note that this CV question Fitting parametric CDF to ecdf is related since it asks the tangential question on whether there is "some sort of empirical version of Kullback Leibler Divergence," but that side point is never answered.

1 Sung-Hyuk, Cha, 2007, "Comprehensive Survey on Distance/Similarity Measures between Probability Density Functions," pp. 300-307 in International Journal of Mathematical Models and Methods in Applied Sciences, Vol. 1, No. 4. Widely available on the Internet last I knew, including here.

2 Deza, Elena and Deza, Michel Marie, 2006, Dictionary of Distances. Elsevier: Amsterdam.

Answer 1

The answer to this seems almost self-evident, after direct experience with plugging the EDFs and CDFs into measures like the Kullback-Leibler and Jensen-Shannon Divergences, instead of the PDFs they were designed for. I asked this question as a precaution prior to writing blog posts on coding these measures in T-SQL, at Information Measurement with SQL Server, Part 4.1: The Kullback-Leibler Divergence and Information Measurement with SQL Server, Part 4.2: The Jensen–Shannon Divergence and Its Relatives; after extensive experimentation, it's clear that the resounding answer is No.

It is of course possible to feed EDFs, CDFs or any other figures we choose in to these stochastic distances - nothing prevents us from abusing any function by plugging in any inappropriate data we want - but this raises several important problems, all of which would be compounded if we tried to communicate our research to others:

• The distance figures returned when using EDFs and CDFs are completely different from those received when PDFs are plugged in.

• There is also no equivalence in terms of the properties of the distances. For example, the Kullback-Leibler Divergence (KL) ordinarily requires the property of absolute continuity, in that the distances are only valid when a PDF has a positive count for both sides, whenever one distribution has a non-zero count for a particular value. Since EDFs and CDFs occur on semi-continuous scales from 0-1 this no longer applies. This particular property is problematic, since the condition is often hard to satisfy, but other properties are affected as well. The terms "divergence," "distance" and "metric" actually have technical meanings in the realm of distance measures, depending on whether or not they exhibit properties like symmetry and/or subadditivity. If substituting EDFs and CDFs results in the KL gaining symmetry (so that it can be calculated commensurately in both directions) then it is technically no longer a "divergence." The name would have to be changed as a result. Many of the other measures discussed by Hyuk, Deza's Dictionary of Distances (as referenced in the question) and others are also crafted by researchers with the aim of inducing particular properties, such as convexity and concavity, among many others. The aim is to create a toolbelt for data miners and others, so we can substitute distances to meet the needs of specific datasets and questions about them, much as a photographer may insert a fish-eye lens for particular shots. By plugging in EDFs and CDFs we may alter these properties in unforeseen ways, which would at a minimum require in-depth research to verify their presence or absence prior to publishing any research that makes us of them

• After reading scores of journal articles published on stochastic distances, I have yet to an encounter any reference to the substitution of EDFs and CDFs in the KL and its relatives. This does not stop of us from using these measures in this way, but does raise an issue of interpretability if we were to publish any findings using such figures. Other researchers will automatically expect us to use the KL and other stochastic measures designed for PDFs in a particular way; if we communicate our research through such means as publication, we will have to go to some lengths to explain why we used the KL in such an unexpected manner. This is especially true given the lack of correspondence in properties and final distance figures.

• We already have better measures at hand that are specifically designed with EDF-CDF comparisons in mind, like the Kolmogorov Distance that arises in the calculation of the K/S Test. Ordinary Euclidean Distance can also be used, as well as the distances that go into determining the Cramér–von Mises Criterion, a relative of the K/S Test.

The interpretability issue demands that we justify the usefulness of awkwardly plugging EDFs and CDFs into PDF distances like the KL, which means we'd probably have to do extensive research into the properties etc. that arise and justify their desirability. We'd also have to demonstrate that those properties make it a better choice for EDF-CDF comparisons than the Kolmogorov Distance, among others. The real clincher is that even if we found some exotic use case for this kind of substitution, the properties of the resulting distance measures may mean that terms like "divergence" no longer apply, in which case a name change would be practically mandatory. This is doubly true when we factor in the disparity in final distance figures that would result from the substitution. We cannot rule out some novel use, but can safely conclude that it would be misleading to retain the original distance names and would require rather lengthy justifications to avoid misinterpretation. In essence, they would cease to be the Kullback-Leibler and Jensen-Shannon Divergences if we made this kind of substitution, even if we retained the original mathematical formulas. I ran into these difficulties head-on while trying to code them to work in this manner, contrary to their intended uses, and could not justify using them in this way. Apparently no one else can justify them either, because such uses cases are practically non-existent in the literature.