# Calculating an estimate of KL Divergence using the samples drawn from distributions

Given two sets of samples drawn from two different distributions, is it computationally possible to get an estimate of KL-Divergence between the two distribution using these samples?

Here I am assuming the dimensionality of the two distributions is high (say d). To compute the estimate, we first need to discretize the entire space and then estimate probabilities based on the frequencies. Let us say, we discretize each dimension into p bins. Then the total number of grids in the space will be $$p^d$$. So we need to compute the probabilities of the two distributions for $$p^d$$ grids, which is exponential in time. Hence I assume we cannot compute an estimate of KL Divergence using the samples for any practical problem.

I wanted to check if this explanation is correct or if I am missing anything. Could someone assert if this rationale is correct?

• If you know the distributions, you can fit them then calculate the divergence at points of your choosing, In any case regularization is advisable. I found this presentation, which gives a more detailed treatment: Kullback-Leibler Divergence Estimation of Continuous Distributions.
– Emre
Mar 23 '18 at 0:59
• @Emre Right, but sometimes we don't know the distributions. Example: features extracted from a neural network. So in the case where we don't know the form of the distribution, we can't estimate KL-Divergence. Please correct me if I am wrong. Mar 23 '18 at 1:07
• In that case you want a nonparametric estimator; cf. e.g., Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions.
– Emre
Mar 23 '18 at 2:28
• @Emre I didn't know this. Thanks for the direction. I will check it. Mar 23 '18 at 2:35