Can KL-Divergence ever be greater than 1?

Question

I've been working on building some test statistics based on the KL-Divergence,

\begin{equation} D_{KL}(p \| q) = \sum_i p(i) \log\left(\frac{p(i)}{q(i)}\right), \end{equation}

And I ended up with a value of $1.9$ for my distributions. Note that the distributions have support of $140$K levels, so I don't think plotting out the whole distributions would be reasonable here.

What I'm wondering is, is it possible to have a KL-Divergence of greater than 1? A lot of the interpretations I've seen of KL-Divergence are based on an upper bound of 1. If it can go greater than 1, what is the interpretation of KL-Divergence beyond 1?

Edit: I know it's a bad choice of reference, but the Wikipedia article on KL Divergence suggests that "a Kullback–Leibler divergence of 1 indicates that the two distributions behave in such a different manner that the expectation given the first distribution approaches zero." I had thought it was implied that this meant the KL-Divergence was bounded above by 1, but it's apparent that this is a mistake in the article.

Answer 1

The Kullback-Leibler divergence is unbounded. Indeed, since there is no lower bound on the $q(i)$'s, there is no upper bound on the $p(i)/q(i)$'s. For instance, the Kullback-Leibler divergence between a Normal $N(\mu_1,\sigma^2)$ and a Normal $N(\mu_2,\sigma^2)$ with equal variance is $$\frac{1}{2\sigma^{2}}(\mu_1-\mu_2)^2$$which is clearly unbounded.

Wikipedia [which has been known to be wrong!] indeed states

"...a Kullback–Leibler divergence of 1 indicates that the two distributions behave in such a different manner that the expectation given the first distribution approaches zero."

which makes no sense (expectation of which function? why 1 and not 2?)

A more satisfactory explanation from the same Wikipedia page is that the Kullback–Leibler divergence

"...can be construed as measuring the expected number of extra bits required to code samples from P using a code optimized for Q rather than the code optimized for P."

Answer 2

I think the answers here are great but I wanted to add more context regarding the interpretation of KL that helped me personally; The KL divergence can literally be written as the difference between the negative entropy of p (plogp) and the cross entropy between p and q (-plog(q)) by expanding the log term in the KL divergence, KL(p||q). Note that the entropy itself is strictly positive, so in the expanded version of the KL, plogp - plogq, the first term is always negative (by definition because it's just the negative of a strictly positive value) and the second term is always positive. Moreover, it's intuitive that the cross entropy is always larger in magnitude than the entropy, e.g. imagine I want to send a message using a finite set of words that I've chosen intentionally (regular entropy) but someone comes along and steals my word bank and swaps with a different one. One can imagine that if I still want to send the same message but I have to use a different set of words, the coherence of the message will likely be attenuated unless my new set of words happen to be the same as the old set. Thus, the KL is always positive. More rigorously, this can be shown via Jensen's inequality. Additionally, this particular issue has come up in my lab quite a bit (pun intended), that is, the interpretation of the KL. In my view, the exact value of the KL is not that useful because it's not actually a true metric. The KL is mostly useful as a loss function to maximize the likelihood of a variational posterior with respect to some prior distribution assembled from data. In this use case, the KL is perfect! All we need to do is minimize it and we know that we can't go below zero, so there's not much ambiguity in the progress of training. For a more interpretable metric, look for things that are true metrics or are at least normalized / bounded on both sides. Examples include the Jenson-Shannon divergence, the variation of information / normalized mutual information and normalized entropies (??). Yes, if you are computing entropy from a distribution generated via histograms, you can always normalize the entropy w.r.t it's largest possible value (uniform distribution).