13
$\begingroup$

I am going to use KL divergence in my python code and I got this tutorial.

On that tutorial, to implement KL divergence is quite simple.

kl = (model * np.log(model/actual)).sum()

As I understand, the probability distribution of model and actual should be <= 1.

My question is, what's the maximum bound/maximum possible value of k?. I need to know the maximum possible value of kl distance as for the maximum bound in my code.

$\endgroup$
15
$\begingroup$

Or even with the same support, when one distribution has a much fatter tail than the other. Take $$KL(P\vert\vert Q) = \int p(x)\log\left(\frac{p(x)}{q(x)}\right) \,\text{d}x$$ when $$p(x)=\overbrace{\frac{1}{\pi}\,\frac{1}{1+x^2}}^\text{Cauchy density}\qquad q(x)=\overbrace{\frac{1}{\sqrt{2\pi}}\,\exp\{-x^2/2\}}^\text{Normal density}$$ then $$KL(P\vert\vert Q) = \int \frac{1}{\pi}\,\frac{1}{1+x^2} \log p(x) \,\text{d}x + \int \frac{1}{\pi}\,\frac{1}{1+x^2} [\log(2\pi)/2+x^2/2]\,\text{d}x$$ and $$\int \frac{1}{\pi}\,\frac{1}{1+x^2} x^2/2\,\text{d}x=+\infty$$ There exist other distances that remain bounded such as

  • the $L¹$ distance, equivalent to the total variation distance,
  • the Wasserstein distances
  • the Hellinger distance
$\endgroup$
  • 1
    $\begingroup$ Very good remark @Xi'an $\endgroup$ – Carlos Campos Jun 18 '18 at 21:07
  • $\begingroup$ Thanks @Xi'an is that mean, even the sum of all bins for both distributions are = 1, kl divergence has no a maximum bound? do you have any other options distance function for two probability distribution that has defined maximum bound/ static bound? $\endgroup$ – user46543 Jun 19 '18 at 1:10
  • $\begingroup$ Is P absolutely continuous with respect to Q in this case? $\endgroup$ – Sangwoong Yoon Apr 5 at 12:58
  • $\begingroup$ In which "case"? The KL is not defined as such for distributions that are not absolutely continuous wrt one another I believe. $\endgroup$ – Xi'an Apr 5 at 13:00
12
$\begingroup$

For distributions which do not have the same support, KL divergence is not bounded. Look at the definition:

$$KL(P\vert\vert Q) = \int_{-\infty}^{\infty} p(x)\ln\left(\frac{p(x)}{q(x)}\right) dx$$

if P and Q have not the same support, there exists some point $x'$ where $p(x') \neq 0$ and $q(x') = 0$, making KL go to infinity. This is also applicable for discrete distributions, which is your case.

Edit: Maybe a better choice to measure divergence between probability distributions would be the so called Wasserstein distance which is a metric and has better properties than KL divergence. It has become quite popular due to its applications in deep-learning (see WGAN networks)

$\endgroup$
  • $\begingroup$ Thanks @carlos-campos my distribution both the actual and model have the same condition which is the sum of all bins = 1. Is that means my Kl divergence still does not has a maximum bound? I will look at wassertein distance $\endgroup$ – user46543 Jun 19 '18 at 0:58
  • $\begingroup$ does Wasserstein or Earth mover distance has an explicit maximum bound? because I need it. $\endgroup$ – user46543 Jun 19 '18 at 1:47
  • $\begingroup$ @user46543 Wasserstein distance can be as high as $\infty$ $\endgroup$ – Mark L. Stone Jun 19 '18 at 11:31
  • $\begingroup$ Hi @MarkL.Stone so there is no distance function for calculating the distance between two probability distributions which has the static maximum bound? e.g while two probability distributions have sum of 1 and the maximum bound of the distance will be 1. Am I correct? $\endgroup$ – user46543 Jun 19 '18 at 11:54
3
$\begingroup$

To add to the excellent answers by Carlos and Xi'an, it is also interesting to note that a sufficient condition for the KL divergence to be finite is for both random variables to have the same compact support, and for the reference density to be bounded. This result also establishes an implicit bound for the maximum of the KL divergence (see theorem and proof below).


Theorem: If the densities $p$ and $q$ have the same compact support $\mathscr{X}$ and the density $p$ is bounded on that support (i.e., is has a finite upper bound) then $KL(P||Q) < \infty$.

Proof: Since $q$ has compact support $\mathscr{X}$ this means that there is some positive infimum value:

$$\underline{q} \equiv \inf_{x \in \mathscr{X}} q(x) > 0.$$

Similarly, since $p$ has compact support $\mathscr{X}$ this means that there is some positive supremum value:

$$\bar{p} \equiv \sup_{x \in \mathscr{X}} p(x) > 0.$$

Moreover, since these are both densities on the same support, and the latter is bounded, we have $0 < \underline{q} \leqslant \bar{p} < \infty$. This means that:

$$\sup_{x \in \mathscr{X}} \ln \Bigg( \frac{p(x)}{q(x)} \Bigg) \leqslant \ln ( \bar{p}) - \ln(\underline{q}).$$

Now, letting $\underline{L} \equiv \ln ( \bar{p}) - \ln(\underline{q})$ be the latter upper bound, we clearly have $0 \leqslant \underline{L} < \infty$ so that:

$$\begin{equation} \begin{aligned} KL(P||Q) &= \int \limits_{\mathscr{X}} \ln \Bigg( \frac{p(x)}{q(x)} \Bigg) p(x) dx \\[6pt] &\leqslant \sup_{x \in \mathscr{X}} \ln \Bigg( \frac{p(x)}{q(x)} \Bigg) \int \limits_{\mathscr{X}} p(x) dx \\[6pt] &\leqslant (\ln ( \bar{p}) - \ln(\underline{q})) \int \limits_{\mathscr{X}} p(x) dx \\[6pt] &= \underline{L} < \infty. \\[6pt] \end{aligned} \end{equation}$$

This establishes the required upper bound, which proves the theorem. $\blacksquare$

$\endgroup$
  • $\begingroup$ The result is correct but the constraint heavy: a Beta ${\cal B}(\alpha,\beta)$ density does not enjoy a compact support when $\max(\alpha,\beta)>1$. $\endgroup$ – Xi'an Jun 19 '18 at 6:28
  • $\begingroup$ That's true: it is only a sufficient condition after all. Weaker sufficient conditions are welcome! $\endgroup$ – Reinstate Monica Jun 19 '18 at 6:32

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.