Answers.Body: <p>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 <span class="math-container">$KL$</span> divergence.</p>
  <h3>Why Kullback–Leibler divergence?</h3>
  <p>Although there are other loss functions (e.g. MSE, MAE), <span class="math-container">$KL$</span> 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:</p>
  <p><span class="math-container">$$
  H = -\sum_{i=1}^{N} p(x_i) \cdot \text{log }p(x_i)
  $$</span></p>
  <p>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 <span class="math-container">$KL$</span> divergence:</p>
  <p><span class="math-container">$$
  D_{KL}(p||q) = \sum_{i=1}^{N} p(x_i)\cdot (\text{log }p(x_i) - \text{log }q(x_i))
  $$</span></p>
  <p>where <span class="math-container">$p$</span> is a data distribution and <span class="math-container">$q$</span> is model distribution.</p>
  <p>As we can see, <span class="math-container">$KL$</span> divergence is the most natural way to compare 2 distributions. Moreover, it's pretty easy to calculate. This <a href="https://www.countbayesie.com/blog/2017/5/9/kullback-leibler-divergence-explained" rel="nofollow noreferrer">article</a> provides more intuition on this:</p>
  <blockquote>
  <p>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 <span class="math-container">$log_2$</span> we can interpret this as &quot;how many
  bits of information we expect to lose&quot;.</p>
  </blockquote>
  <h3>Cross entropy</h3>
  <p>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 <span class="math-container">$q$</span>, while true labels represent a target distribution <span class="math-container">$p$</span>. Our goal is to push <span class="math-container">$q$</span> to <span class="math-container">$p$</span> 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 <span class="math-container">$p$</span>, using <span class="math-container">$q$</span> as the encoding distribution.</p>
  <p>Cross-entropy based on entropy and generally calculates the difference between two probability distributions and closely related to <span class="math-container">$KL$</span> divergence. The difference is that it calculates the the total entropy between the distributions, while <span class="math-container">$KL$</span> divergence represents relative entropy. Corss-entropy can be defined as follows:</p>
  <p><span class="math-container">$$
  H(p, q) = H(p) + D_{KL}(p \parallel q)
  $$</span></p>
  <p>The first term in this equation is the entropy of the true probability distribution <span class="math-container">$p$</span> that is omitted during optimization, since the entropy of <span class="math-container">$p$</span> is constant. Hence, minimizing cross-entropy is the same as optimizing <span class="math-container">$KL$</span> divergence.</p>
  <h3>Log likelihood</h3>
  <p>It can be also <a href="https://en.wikipedia.org/wiki/Cross_entropy#Relation_to_log-likelihood" rel="nofollow noreferrer">shown</a> that maximizing the (log) likelihood is equivalent to minimizing the cross entropy.</p>
  <h3>Limitations</h3>
  <p>As you mentioned, <span class="math-container">$KL$</span> 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 <a href="https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence" rel="nofollow noreferrer">Jensen–Shannon divergence</a>:
  <span class="math-container">$$
  D_{JS}(p||q)=\frac{1}{2}D_{KL}(p||m)+\frac{1}{2}D_{KL}(q||m)
  $$</span>
  where <span class="math-container">$m=\frac{1}{2}(p+q)$</span>.</p>
  <p>The main disadvantage of <span class="math-container">$KL$</span> is that both the unknown distribution and the model distribution must have support. Otherwise the <span class="math-container">$D_{KL}(p||q)$</span> becomes <span class="math-container">$+\infty$</span> and <span class="math-container">$D_{JS}(p||q)$</span> becomes <span class="math-container">$log2$</span></p>
  <p>Second, it should be noted that <span class="math-container">$KL$</span> 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 <a href="https://stats.stackexchange.com/a/351153/137038">this answer</a>. Given two discrete distributions <span class="math-container">$p$</span> and <span class="math-container">$q$</span>, we calculate <span class="math-container">$KL$</span> divergence and Wasserstein metric:</p>
  <p><a href="https://i.sstatic.net/aN5Ld.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aN5Ld.png" alt="enter image description here" /></a></p>
  <p>As you can see, <span class="math-container">$KL$</span> divergence remained the same, while the Wasserstein metric decreased.</p>
  <p>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 <a href="https://arxiv.org/pdf/1701.07875.pdf" rel="nofollow noreferrer">Wasserstein GAN</a>. You can also find more on this topic in this <a href="https://jonathan-hui.medium.com/gan-wasserstein-gan-wgan-gp-6a1a2aa1b490" rel="nofollow noreferrer">article</a>.</p>
  <p>The 2 drawbacks of <span class="math-container">$KL$</span> can be mitigated by adding noise. More on it in this <a href="https://openaccess.thecvf.com/content_CVPR_2019/papers/Jenni_On_Stabilizing_Generative_Adversarial_Training_With_Noise_CVPR_2019_paper.pdf" rel="nofollow noreferrer">paper</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T18:02:01.113Z
Answers.Text: 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?".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T21:13:11.260Z
Answers.Text: Thanks for your feedback. I spent more time and added more information.
Answers.UserDisplayName: Aray Karjauv
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T23:20:05.687Z
Answers.Text: 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.
Answers.UserDisplayName: user3667125
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-20T00:05:55.263Z
Answers.Text: 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.
Answers.UserDisplayName: Aray Karjauv
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-20T00:45:45.727Z
Answers.Text: 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
Answers.UserDisplayName: Aray Karjauv
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T14:11:02.443Z
Answers.LastActivityDate: 2020-12-22T15:40:27.503Z
Answers.LastEditDate: 2020-12-22T15:40:27.503Z
Answers.UserDisplayName: Aray Karjauv
Answers.Body: <p>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:</p>
  <ul>
  <li>Classification: maximizing the log-likelihood (or minimizing the negative log-likelihood) is equivalent to minimizing KL divergence as typical used in DL-based classification <strong>where one-hot targets are commonly used as reference</strong> (see <a href="https://stats.stackexchange.com/a/357974">https://stats.stackexchange.com/a/357974</a>). Furthermore, if you have a one-hot vector <span class="math-container">$e_y$</span> with <span class="math-container">$1$</span> at index <span class="math-container">$y$</span>, minimizing cross-entropy <span class="math-container">$\min_{\hat{p}}H(e_y, \hat{p}) = - \sum_y e_y \log \hat{p}_y = - \log \hat{p}$</span> 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.</li>
  <li>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 <a href="https://page.mi.fu-berlin.de/mulzer/notes/misc/chernoff.pdf" rel="nofollow noreferrer">https://page.mi.fu-berlin.de/mulzer/notes/misc/chernoff.pdf</a> for some different proofs).</li>
  </ul>
  <p>Let <span class="math-container">$X_1, \dots, X_n$</span> be i.i.d. Bernoulli RVs with parameter <span class="math-container">$p$</span>.
  <span class="math-container">$$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)).$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T11:31:10.873Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/117559/discussion-on-answer-by-rhdxor-why-is-kl-divergence-used-so-often-in-machine-lea).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T09:52:35.003Z
Answers.LastActivityDate: 2020-12-20T12:15:21.267Z
Answers.LastEditDate: 2020-12-20T12:15:21.267Z
Answers.UserDisplayName: rhdxor
Body: <p>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.</p>
  <p>What is the reason it is used so often in ML? Aren't there other statistical distances that can be used instead?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T17:38:15.983Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T17:39:16.130Z
Comments.Text: [The KL divergence has also an information-theoretic interpretation](https://ai.stackexchange.com/a/20574/2444), 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T17:41:20.940Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <probability-distribution><kl-divergence><wasserstein-metric><total-variational-distance>
Title: Why is KL divergence used so often in Machine Learning?
UserDisplayName: Federico Taschin
ThreadText: # Why is KL divergence used so often in Machine Learning?
  
  (Asked by: username_0 on 2020-12-15)
  
  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?
  
  **Tags:** probability-distribution, kl-divergence, wasserstein-metric, total-variational-distance
  
  > **Comments:**
  > **username_1**: 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).  
  > **username_1**: [The KL divergence has also an information-theoretic interpretation](https://ai.stackexchange.com/a/20574/2444), 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.  
  > **username_1**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-12-19. Score: 4
  
  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](https://www.countbayesie.com/blog/2017/5/9/kullback-leibler-divergence-explained) 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](https://en.wikipedia.org/wiki/Cross_entropy#Relation_to_log-likelihood) 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](https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_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](https://stats.stackexchange.com/a/351153/137038). Given two discrete distributions $p$ and $q$, we calculate $KL$ divergence and Wasserstein metric:
  
  [![enter image description here](https://i.sstatic.net/aN5Ld.png)](https://i.sstatic.net/aN5Ld.png)
  
  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](https://arxiv.org/pdf/1701.07875.pdf). You can also find more on this topic in this [article](https://jonathan-hui.medium.com/gan-wasserstein-gan-wgan-gp-6a1a2aa1b490).
  
  The 2 drawbacks of $KL$ can be mitigated by adding noise. More on it in this [paper](https://openaccess.thecvf.com/content_CVPR_2019/papers/Jenni_On_Stabilizing_Generative_Adversarial_Training_With_Noise_CVPR_2019_paper.pdf)
  
  > **Comments:**
  > **username_1**: 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?".  
  > **username_2**: Thanks for your feedback. I spent more time and added more information.  
  > **username_3**: I kind of agree with @username_1. 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.  
  > **username_2**: 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.  
  > **username_2**: 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  
  
  ---
  
  ### Answer by username_4 on 2020-12-19. Score: 2
  
  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)).$$
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/117559/discussion-on-answer-by-username_4-why-is-kl-divergence-used-so-often-in-machine-lea).  
  
  ---
  
  