# Kullback-Leibler distance for comparing two distribution from sample points

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?

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. The Kantorovich formulation of optimal transport is shown below.

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

• ... Nice link ... – Mark L. Stone May 10 '18 at 14:52
• Why does the answer only talk about Wasserstein-2, but not Wasserstein-1? Is one preferred here over the other for some reason? – develarist Oct 13 '20 at 21:23

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

• 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 – blehblehbleh May 19 '17 at 7:41
• 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. – meh Dec 30 '17 at 15:57
• 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. – meh Dec 30 '17 at 15:59
• There are symmetrical alternatives to KL Divergence which makes them proper metrics. See this thread here: math.stackexchange.com/questions/1028224/… – Pankaj Daga Mar 10 '18 at 21:17
• 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? – CyberPlayerOne Nov 20 '18 at 5:54