# How to evaluate the KL divergence between two distributions that may require sampling?

The KL divergence between two distributions is: $$$$\int \mathbf{p}(x;\theta_{1}) \; log \frac{\mathbf{p}(x;\theta_{1})}{\mathbf{p}(x;\theta_{2})} \nu(dx) \\$$$$

If the expression $$\mathbf{p}(x;\theta)$$ is specified by its canonical parameters, we can simply calculate the KL divergence using the expressions of $$\mathbf{p}$$. However in the case of (conditional: deleted) distributions (where random vector $$\mathbf{x}$$ appears: added) $$\mathbf{p}(y|x;\theta_{1})$$, how would one find the KL divergence? Would it require sampling many $$x$$'s to estimate this value?

As a concrete example, in the case of Logistic regression we have for some random initialized $$\theta_0$$: $$$$\mathbf{p}(y = 1|x;\theta_0) = \frac{1}{1+e^{-\theta_0^{\intercal}x}} \quad\quad \mathbf{p}(y = 0|x;\theta_0) = \frac{e^{-\theta_0^{\intercal}x}}{1+e^{-\theta_0^{\intercal}x}}.$$$$

and another one with $$\theta_1$$: $$$$\mathbf{p}(y = 1|x;\theta_1) = \frac{1}{1+e^{-\theta_1^{\intercal}x}} \quad\quad \mathbf{p}(y = 0|x;\theta_1) = \frac{e^{-\theta_1^{\intercal}x}}{1+e^{-\theta_1^{\intercal}x}}.$$$$

Now we want to compute the improvement of model $$\theta_1$$ over $$\theta_0$$, using KL divergence:

\begin{align*} D(P(y|x;\theta_0)|P(y|x;\theta_1)) &= \frac{1}{1+exp(-\theta_0^{\intercal}x)} \cdot ln \biggl( \frac{1+exp(-\theta_{1}^{\intercal}x)}{1+exp(-\theta_0^{\intercal}x)} \biggr) \\ &+\; \frac{exp(-\theta_0^{\intercal}x)}{1+exp(-\theta_0^{\intercal}x)} \cdot ln \biggl( \frac{1+exp(-\theta_0^{\intercal}x)}{exp(-\theta_0^{\intercal}x)} \cdot \frac{exp(-\theta_{1}^{\intercal}x)}{1+exp(-\theta_{1}^{\intercal}x)} \biggr).\\ \end{align*}

How would one evaluate $$exp(-\theta_0^{\intercal} x)$$? Would you sample the values of x if possible? Now suppose you have many examples of $$x$$ available, ie in a training set, would it be "fair" to sample from the training set to evaluate $$D$$?

## edit

Removed the "conditional distribution", and replaced it with expressions where random vector $$\mathbf{x}$$ makes an appearance in the definition. There is a comparable question here https://math.stackexchange.com/questions/3016421/confused-by-kullback-leibler-on-conditional-probability-distributions. But in that case the accepted answer compute the expected value of the KL divergence wrt the distribution $$P(x)$$. But in my case I do not have this distribution $$P(x)$$, only a dataset $$\{(x_1,y_1),..,(x_n,y_n)\}$$. I can evaluate the quantitity $$D(P(y|x;\theta_0)|P(y|x;\theta_1))$$ for every $$(x_i,y_i)$$ in the dataset, but how would you compute the expecatation: $$$$E_{x \sim P(x)}[ D(P(y|x;\theta_0)|P(y|x;\theta_1)) ]$$$$ without this $$P(x)$$?. The naive method is to assume $$P(x)$$ is a uniform distribution, at which point the expectation is just the average... but it seems like a better solutions is available somewhere. The closest I can find is this: https://www.tsc.uc3m.es/~fernando/bare_conf3.pdf, which builds a CMF from the data itself.

The distribution being conditional or not does not change the notion of KL divergence.

Indeed, given $$p(x) \sim N(\mu_1, \sigma_1^2)$$ and $$q(x) \sim N(\mu_2, \sigma_2^2)$$, the KL can be estimated in closed form.

However, the KL between $$p(y|x) \sim N(\mu_1, \sigma_1^2)$$ and $$q(y|x) \sim N(\mu_2, \sigma_2^2)$$ shares the same closed form with the previous one

The only thing you have to know is what family of distribution does the conditional probability falls in

And in your example, $$x$$ is the conditioning, thus you are saying that "you know a point estimate $$\theta$$ and a point estimate $$x$$", which means that that term can be estimated in closed form as it's a product of two point estimates, aka numbers/vectors

the solution of you (last) formulation is straightforward, as $$P(y|x,\theta) ~ Bernoulli$$, and the kl of discrete distribution is trivial

The only thing you have to do is to compute the KL sample wise, and then average the KL over all the samples

What you will get is a unbiased monte carlo estimate of your overall KL

• @xiaolingxiao conditioning on X means that you already know X, so you would just proceed to use it as if it's a constant, and not a random variable... on the who would you estimate a KL of two non parametric distributions, you need to resort to approximations, and since KL is just an integral, if it's low dimensions you can use quadrature procedures, but if it's somewhat high dimension, something like monte carlo estimate (there are more advanced procedures, however at that point it highly depends on your specific problem) Commented Apr 30 at 14:12
• @xiaolingxiao it's still a bit unclear, because of the "some training" is not well defined. Initially $\theta_0$ is a point estimate (a specific vector say), and after training, it's also still a specific vector, just a different one. At no point in this whole procedure, $\theta$ represents a distribution, thus estimating the KL divergence, it's impossible (it's infinite for two point estimate/lambda distributions) Commented Apr 30 at 15:38
• @xiaolingxiao sorry but I have to say it... do you realize how your change in notation completely changes the problem? Commented Apr 30 at 17:23
• @xiaolingxiao answered on the answer, but please consider that wants to be the last answer, as it's probably the 3rd completely different formulation you are posting, and it's 100% against the community rules Commented Apr 30 at 17:26
• @xiaolingxiao it's an unbiased estimate for the distribution you have in your hand, that's it. you have a coin that gives you 80% times head and is bised? the MC estimate will tell you that the coin gives head 80% of the times (aka an unbiased estimate) Commented Apr 30 at 18:18