6
$\begingroup$

The KL Divergence is quite easy to compute in closed form for simple distributions -such as Gaussians- but has some not-very-nice properties. For example, it is not symmetrical (thus it is not a metric) and it does not respect the triangular inequality.

What is the reason it is used so often in ML? Aren't there other statistical distances that can be used instead?

$\endgroup$
4
  • $\begingroup$ This is an interesting question. Is it because the KL divergence can be approximately computed more cheaply than the other statistical distances? The KL divergence can be approximated with Monte Carlo rollouts, even if you don't have a closed-form solution (because it's defined as an integral). I am not familiar with the details of the other statistical distances, such as the Wasserstein metric, but I guess they may not be so cheap even to approximately compute (at least, that's one of the reasons that I can think of now why the KL divergence is more used than other measures). $\endgroup$
    – nbro
    Dec 15 '20 at 17:38
  • 2
    $\begingroup$ The KL divergence has also an information-theoretic interpretation, but I don't think this is the main reason why it's used so often. However, that interpretation may make the KL divergence possibly more intuitive to understand. Moreover, the KL divergence formula is quite simple. I don't really know how the other measures are defined (apart from the TVD), but maybe that (the simplicity) is also one reason. As you point out, the KL divergence has also some apparent disadvantages, so your question is more than valid. $\endgroup$
    – nbro
    Dec 15 '20 at 17:39
  • $\begingroup$ Anyway, I don't feel like providing an answer now, because I am not familiar with the details of other measures/metrics/distances, but maybe later I will investigate this issue, if I have some time. $\endgroup$
    – nbro
    Dec 15 '20 at 17:41
  • $\begingroup$ Many reasons like KL divergence will often arise when you use an entropic regularizer (which has strong convexity and hence some great theoretical use). It also appears in the theoretical lower bound in most MAB problems. I don't know how much you are aware of these stuff, but it has very rigorous maths behind it. Along with Pinsker's inequality it has some great theoretical use. $\endgroup$
    – user9947
    Dec 21 '20 at 18:37
2
$\begingroup$

This question is very general in the sense that the reason may differ depending on the area of ML you are considering. Below are two different areas of ML where the KL-divergence is a natural consequence:

  • Classification: maximizing the log-likelihood (or minimizing the negative log-likelihood) is equivalent to minimizing KL divergence as typical used in DL-based classification where one-hot targets are commonly used as reference (see https://stats.stackexchange.com/a/357974). Furthermore, if you have a one-hot vector $e_y$ with $1$ at index $y$, minimizing cross-entropy $\min_{\hat{p}}H(e_y, \hat{p}) = - \sum_y e_y \log \hat{p}_y = - \log \hat{p}$ boils down to maximizing the log-likelihood. In summary, maximizing the log-likelihood is arguably a natural objective, and KL-divergence (with 0 log 0 defined as 0) comes up because of its equivalence to log-likelihood under typical settings, rather than explicitly being motivated as the objective.
  • Multi-armed bandits (a sub-area of reinforcement learning): Upper confidence bound (UCB) is an algorithm derived from standard concentration inequalities. If we consider MABs with Bernoulli rewards, we can apply Chernoff's bound and optimize over the free parameter to obtain an upper bound expressed in terms of KL divergence as stated below (see https://page.mi.fu-berlin.de/mulzer/notes/misc/chernoff.pdf for some different proofs).

Let $X_1, \dots, X_n$ be i.i.d. Bernoulli RVs with parameter $p$. $$P(\sum_i X_i \geq (p+t)n) \leq \inf_\lambda M_X (\lambda) e^{-\lambda t} = \exp(-n D_{KL}(p+t||p)).$$

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – nbro
    Dec 22 '20 at 11:31
1
$\begingroup$

In ML we always deal with unknown probability distributions from which the data comes. The most common way to calculate the distance between real and model distribution is $KL$ divergence.

Why Kullback–Leibler divergence?

Although there are other loss functions (e.g. MSE, MAE), $KL$ divergence is natural when we are dealing with probability distributions. It is a fundamental equation in information theory that quantifies, in bits, how close two probability distributions are. It is also called relative entropy and, as the name suggests, it is closely related to entropy, which in turn is a central concept in information theory. Let's recall the definition of entropy for a discrete case:

$$ H = -\sum_{i=1}^{N} p(x_i) \cdot \text{log }p(x_i) $$

As you observed, entropy on its own is just a measure of a single probability distribution. If we slightly modify this formula by adding a second distribution, we get $KL$ divergence:

$$ D_{KL}(p||q) = \sum_{i=1}^{N} p(x_i)\cdot (\text{log }p(x_i) - \text{log }q(x_i)) $$

where $p$ is a data distribution and $q$ is model distribution.

As we can see, $KL$ divergence is the most natural way to compare 2 distributions. Moreover, it's pretty easy to calculate. This article provides more intuition on this:

Essentially, what we're looking at with the KL divergence is the expectation of the log difference between the probability of data in the original distribution with the approximating distribution. Again, if we think in terms of $log_2$ we can interpret this as "how many bits of information we expect to lose".

Cross entropy

Cross-entropy is commonly used in machine learning as a loss function where we have softmax (or sigmoid) output layer, since it represents a predictive distribution over classes. The one-hot output represents a model distribution $q$, while true labels represent a target distribution $p$. Our goal is to push $q$ to $p$ as close as possible. We could take a mean squared error over all values, or we could sum the absolute differences, but the one measure which is motivated by information theory is cross-entropy. It gives the average number of bits needed to encode samples distributed as $p$, using $q$ as the encoding distribution.

Cross-entropy based on entropy and generally calculates the difference between two probability distributions and closely related to $KL$ divergence. The difference is that it calculates the the total entropy between the distributions, while $KL$ divergence represents relative entropy. Corss-entropy can be defined as follows:

$$ H(p, q) = H(p) + D_{KL}(p \parallel q) $$

The first term in this equation is the entropy of the true probability distribution $p$ that is omitted during optimization, since the entropy of $p$ is constant. Hence, minimizing cross-entropy is the same as optimizing $KL$ divergence.

Log likelihood

It can be also shown that maximizing the (log) likelihood is equivalent to minimizing the cross entropy.

Limitations

As you mentioned, $KL$ divergence is not symmetrical. But in most cases this is not critical, since we want to estimate the model distribution by pushing it towards real one, but not vice versa. There is also a symmetrized version called Jensen–Shannon divergence: $$ D_{JS}(p||q)=\frac{1}{2}D_{KL}(p||m)+\frac{1}{2}D_{KL}(q||m) $$ where $m=\frac{1}{2}(p+q)$.

The main disadvantage of $KL$ is that both the unknown distribution and the model distribution must have support. Otherwise the $D_{KL}(p||q)$ becomes $+\infty$ and $D_{JS}(p||q)$ becomes $log2$

Second, it should be noted that $KL$ is not a metric, since it violates triangle inequality. That is, in some cases it won't tell us if we are going the right direction when estimating our model distribution. Here is an example taken from this answer. Given two discrete distributions $p$ and $q$, we calculate $KL$ divergence and Wasserstein metric:

enter image description here

As you can see, $KL$ divergence remained the same, while the Wasserstein metric decreased.

But as mentioned in comments, Wasserstein metric is highly intractable in a continuous space. We still can use it by applying the Kantorovich-Rubinstein duality used in Wasserstein GAN. You can also find more on this topic in this article.

The 2 drawbacks of $KL$ can be mitigated by adding noise. More on it in this paper

$\endgroup$
5
  • $\begingroup$ You say "The most common way to calculate the distance between real and model distribution is KL divergence", but you're not explaining why. The OP was already aware of the KL divergence can be used for and its disadvantages, so not sure why you're listing them here again. Apart from saying that the Wasserstein metric can be intractable, you're not really answering the question. Note that the question was not "What are the disadvantages of the KL divergence?". $\endgroup$
    – nbro
    Dec 19 '20 at 18:02
  • $\begingroup$ Thanks for your feedback. I spent more time and added more information. $\endgroup$ Dec 19 '20 at 21:13
  • 1
    $\begingroup$ I kind of agree with @nbro. This post is very informative and great intro to "What is KL?", but doesn't answer why KL is so popular in ML (additionally, OP already knows that KL is). This post says "KL is used to measure difference in 2 probability distributions, and is the most natural way to do so", but there are many other ways to measure the difference of 2 distributions and some are more natural/intuitive than KL (examples: wasserstein distance, cosine similarity, mean squared residuals, etc). This post doesn't explain to readers why KL is used over all the other metrics. $\endgroup$ Dec 19 '20 at 23:20
  • $\begingroup$ I tried to show the connection between entropy, KL and cross-entropy. Entropy is the central concept in information theory, and KL, in turn, is the basics of ML. $\endgroup$ Dec 20 '20 at 0:05
  • $\begingroup$ The measures you named is not natural for comparing 2 probability distributions (except Wasserstein, but it has its own drawbacks). MSE/MSR is natural for regression problems, cosine is natural for vectors $\endgroup$ Dec 20 '20 at 0:45

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.