3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Emre
    Commented Mar 23, 2018 at 0:59
  • $\begingroup$ @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. $\endgroup$
    – JVG
    Commented Mar 23, 2018 at 1:07
  • 1
    $\begingroup$ In that case you want a nonparametric estimator; cf. e.g., Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions. $\endgroup$
    – Emre
    Commented Mar 23, 2018 at 2:28
  • $\begingroup$ @Emre I didn't know this. Thanks for the direction. I will check it. $\endgroup$
    – JVG
    Commented Mar 23, 2018 at 2:35

2 Answers 2

Reset to default
2
$\begingroup$

Check this article. They use k-NN to interpolate the values of P(x) and Q(x), so that you can use the KL-divergence formula with 'approximated histograms'.

Improve this answer
$\endgroup$
0
$\begingroup$

There is no need to discretize the space since KL divergence can be calculated for continuous spaces.

Yes - you can calculate the difference between samples using KL divergence.

Based on differences between samples, estimating a possible difference in populations is the core of statistical inference. It is a very complex issue.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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