2
$\begingroup$

I have two data samples of a value and I want to compute some distance which would represent the difference in their distribution. I read about Kullback-Leibler distance which could be used for comparing two distributions.

Would it be the right way if I compute the density of both samples and pass it as input to compute KL distance?

$\endgroup$
2
$\begingroup$

The Kullback-Leibler divergence is not a distance: it is not even symmetric, and you could (and most likely will) get completely different results by orders of magnitudes depending on what is your reference measure.

The proper way of answering your question is to use the Wasserstein distance, in particular Wasserstein-2. This is a proper distance defined in the settings of theory of optimal transport.

I will first detail the theoretical idea, then present one practical solution (not the only one) that can be easily implemented.

The basic idea is the following, given two measures $\mu$, $\nu$, you can quantify how 'close' they are by measuring how much kinetic energy it would take you to deform one to the other.

In other words, if you had to move the mass from $\mu$ to $\nu$ by hand, and the cost of transport of one unit of mass is proportional to the distance squared, you are trying to minimize the total cost of transport.

Call $\pi(x,y)$ the amount of mass moved from $x$ to $y$. Then your objective function is

$$ \min_{\pi \geq 0} \iint |x-y|^2 \pi(x,y) dx dy $$ subject to the constraints $$ \int \pi(x,y) dx = \nu(y) \quad \text{(all the mass at y comes from somewhere)} $$ $$ \int \pi(x,y) dy = \mu(x) \quad \text{(all the mass at x goes somewhere)} $$ How do we solve this in practice? Well this is merely a linear programming programming problem in infinite dimensions.

For instance, if you had iid data samples, $(x_i)_{i=1,..,n}$ and $(y_j)_{j=1,..,m}$, you are seeking an assignment $\pi_{ij}$ that minimizes the transport cost. One way is to solve the finite dimension linear program $$ \min_{\pi_{ij} \geq 0} \sum_{i,j} |x_i-y_j|^2 \pi_{ij} $$ subject to $$ \sum_i \pi_{ij} = \frac{1}{m} $$ $$ \sum_j \pi_{ij} = \frac{1}{n} $$ More references on computational optimal transport: https://arxiv.org/pdf/1803.00567.pdf

$\endgroup$
  • $\begingroup$ ... Nice link ... $\endgroup$ – Mark L. Stone May 10 '18 at 14:52
0
$\begingroup$

Yes, KL divergence would be appropriate in this case. It's a good way to quantify differences between two probability distributions.

$\endgroup$

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

  • $\begingroup$ Hey thanks for your response, but to compute kl divergence can i use density function to get the density from set of points and then pass that as distribution to kl divergence $\endgroup$ – blehblehbleh May 19 '17 at 7:41
  • $\begingroup$ I'm posting as a comment since there are so many answers to these questions in various locations on this site. Firstly, as Skeftical notes, KL is not a distance. I believe that Halvorsen has a really nice post on that topic on this site. You should look it up, but the shortest story is that KL is not symmetric, so it doesn't measure the 'distance' between two distrbutions. Because one typically has to 're-use' the data in situations like this, using KL probably will give a biased answer to a question of this sort. In fact the Aikake Information Criteria is specifically based on that idea. $\endgroup$ – aginensky Dec 30 '17 at 15:57
  • $\begingroup$ There are issues with the power of the test etc. but you should look at Kolmogorov-Smirnov test as a way of deciding if two samples are drawn from the same distribution. It is implemented in R and Python. $\endgroup$ – aginensky Dec 30 '17 at 15:59
  • $\begingroup$ There are symmetrical alternatives to KL Divergence which makes them proper metrics. See this thread here: math.stackexchange.com/questions/1028224/… $\endgroup$ – Pankaj Daga Mar 10 '18 at 21:17
  • $\begingroup$ Although KL divergence is not symmetric, can we use it to measure the "relative" distance between 3 distributions? Say, we have distribution A, B, and X. We want to determine whether A or B is closer to the distribution of X. Then we can take X as the ground truth distribution and the other two as approximations, and then compare KL(X||A) and KL(X||B). Will this be reasonable? $\endgroup$ – Tyler 十三将士归玉门 Nov 20 '18 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.