Kullback-Leibler Divergence

posted-in:

KL-divergence frequently appears in many fields such as statistics and information theory. It is defined as the expected value of logarithmic transformation of likelihood ratio. Note that:

1. expected value: weighted integration with probability density.
2. logarithmic transformation: conversion multiplication to linear combination that is suitable for convex optimization and function analysis.
3. likelihood ratio: a measure of likelihood comparison

1. What is KL-divergence?

1.1 Definition

For any probability distributions $P$ and $Q$, KL-divergence (Kullback-Leibler divergence)1 is defined as follows, using their probability density function $p(x)$ and $q(x)$. %

1.2 Basic properties

KL-divergence has the following properties.

• non-negative）It has a non-negative range. %

• completeness）When it equals to $0$, $P$ and $Q$ are equivalent. %

• assymmetry）It is not symmetric about $P$ and $Q$. %

• absolute continuity）Unless it diverges, $Q$ is absolutely continuous with respect to $P$. %

​ For example, calculating KL-divergence2 between two Gaussian distributions gives the following results: It can be seen that the more the shapes between two distributions do not match, the more KL-divergence increases.

1.3 Is KL-divergence a metrics?

​ KL-divergence is so important measurement when considering probability and information that it is called by various names depending on the field and context.

“KL-divergence” “KL-metrics” “KL-information” “Information divergence” “Information gain” “Relative entropy”

Since KL-divergence is always non-negative, it might be interpreted as the metrics in the space where the probability distributions $P$ and $Q$ exist. However, KL-divergence is not strictly a metric because it only satisfies “non-negativity” and “completeness” among the following axioms of metrics.

Axioms of metrics $d(~)$:

1. non-negativity $d(x, ~ y) \geq 0$

2. completeness $d(x, ~ y) = 0 ~~ \Leftrightarrow ~~ x = y$

3. symmetry $d(x, ~ y) = d(y, ~ x)$

4. The triangle inequality $d(x, ~ y) + d(y, ~ z) \geq d(x, ~ z)$

Note that $d()$ is called the distance function or simply distance

For example, Euclidean distance, squared distance, Mahalanobis distance, and Hamming distance satisfy these conditions, and can be clearly considered as metrics. On the other hand, KL-divergence is a divergence, not metrics. In mathematics, “divergence” is an extended concept of “metrics” that satisfies only non-negativity and completeness among axioms of metrics. By introducing “divergence”, you can reduce the constraints of axioms of metrics and have a high level of abstraction.

The word “divergence” is generally interpreted as the process or state of diverging; for example, in physics it appears as a vector operator div. There is no Japanese words that corresponds to the meaning of divergence, but it seems that “相違度”, “分離度”, “逸脱度”, “乖離度” etc. might be used.

As an example, let’s measure the KL-divergence between two Gaussian distributions $N (0, 1)$ (blue) and $N (1, 2)$ (red). In the figure, the left shows KL-divergence from red one as seen from blue one, and the right shows KL-divergence from blue one as seen from red one. Their value are surely different.

Note that given two Gaussian distribution $p_1,p_2$ as %

the following holds. %

.

img src=”images/comparison_of_dkl_norm.png” width=”600”

Incidentally, in addition to the KL-divergence, the following is known as a measure of the proximity (or closeness) between two probability distributions.

The metrics to measure closeness between $q(x)$ and $p(x)$

• ${\chi}^2(q ; p) := \sum_{i=1}^{k} \frac{ { \{ p_i - q_i \} }^{2} }{p_i}$ (${\chi}^2$ statistics)
• $L_1(q ; p) := \int \vert q(x) - p(x) \vert ~ dx$ ($L_1$-norm)
• $L_2(q ; p) := \int { \{ q(x) - p(x) \} }^{2} ~ dx$ ($L_2$-norm)
• $I_K(q ; p) := \int { \\{ \sqrt{ q(x) } - \sqrt{ p(x) } \\} }^{2} ~ dx$ (Herringer distance)
• $\mathbb{D}(q ; p) := \int f \left( {\large \frac{q(x)}{p(x)} } \right) q(x) ~ dx$ ($f$-divergence)
• $I_{\lambda}(q ; p) := \int \left\{ { \left( {\large \frac{q(x)}{p(x)} } \right) }^{\lambda} - 1 \right\} q(x) ~ dx$ (Generalized information)
• ${D}_{KL}(q ; p) := \int \log \left( {\large \frac{q(x)}{p(x)} } \right) q(x) ~ dx$ (KL-divergence)
• $JSD(q \mid\mid p) := \frac{1}{2} {D}_{KL}(q \mid\mid \frac{q+p}{2}) + \frac{1}{2} {D}_{KL}(p \mid\mid \frac{q+p}{2})$ (JS-divergence)

2. Relatinoship to other measurements

2.1 KL-divergence vs Mutual information

In information theory, entropy $H(X)$, join entropy $H(X,Y)$, conditional entropy $H(X \vert Y)$, mutual information $MI(X,Y)$ are defined as follows by using probability density $Pr()$3. %

For any two random variable $X$ and $Y$, mutual information $MI(X, Y)$ specifies the mutual (symmetric) dependence between them.

Here, the following relationship holds between KL-divergence and mutual information. %

So that, mutual information $MI (X, Y)$ is interpreted as the degree of difference (average degree of deviation) between the joint distribution $Pr (x, y)$ when the $X$ and $Y$ are not independent and the joint distribution $Pr (x) Pr (y)$ when $X$ and $Y$ are independent.

（cf.）Formula transformation of mutual information: %

2.2 KL-divergence vs Log likelihood ratio

​ In the field of Bayes inference and statistical modeling, you often face the problem of estimating the true distribution $q(x)$ by $p_{\hat{\theta}}(x)$ (that is the combination of stochastic model $p_{\theta}(x)$ and estimated parameter $\hat{\theta}$ ) . Therefore, KL-divergence is used when you want to measure the difference between two distributions, or when you want to incorporate the estimation error into the loss function or risk function in order to solve the optimization problem for the parameter $\theta$ .

​ Also, KL-divergence is related to the log likelihood ratio so much that it has a deep connection to the model selection method 4 such as likelihood ratio test, Bayes factor, and AIC (Akaike’s information criterion).

• 　KL-divergence of estimated distribution $p_{\theta}(x)$ for the true distribution $q(x)$ : $D_{KL}(q \mid\mid p_{\theta})$ is considerd as the expected value of the log likelihood ratio $q(x)/p_{\theta}(x)$ for tue true distribution $q(x)$. % ~
%

​ When using KL-divergence as the evaluation/loss value in model selection/comparison, it is equivalent that minimizing KL-divergence: $D_{KL}( q \mid\mid p )$ and maximizing the log likelihood: $\log p(x)$ as follows. %

• For any parametric stochastic model $f(x \vert \theta)$ (such as a linear regression model) which represents the estimated distribution as ~ \\ \begin{align} p_{\theta}(x) = f(x|\theta) \end{align} ~ \\ , if a certain loss function $L(\theta)$ is given, the optimal parameter $\theta^*$ exists as it satisfy the following. % Then, for any estimated parameter $\hat{\theta}$ ,the estimated loss of the model $f(x \vert \hat{\theta})$ is represented by KL-divergence. (Note that $\ell( \cdot \vert x)$ means the log likelihood function.) % %

2.3 KL-divergence vs Fisher information

Given a certain stochastic model $f(\cdot \vert \theta)$, Fisher information $I(\theta)$ for the parameter $\theta$ is defined as follows. (Note that $\ell( \cdot \vert x)$ means the log likelihood function.) % Also, between KL-divergence and Fisher information, the following holds. %

(cf.) The following equation holds by using Taylor expansion of $\ell( \cdot \vert x)$.
%

This formula indicates that in parameter space $\Theta$, for all point $\theta \in \Theta$ ant its neighborring point $\theta + h$, their KL-divergence：$D_{KL} ( f(x \vert \theta) \mid\mid f(x \vert \theta+h) )$ is directly proportional to Fisher information $I(\theta)$. After all, Fisher information $I(\theta)$ measures the local information that the stochastic model $f(\cdot \vert \theta)$ has at the point $\theta$.

3. References

1. Also, f-divergence is defined as its generalized class.

2. I used scipy.stats.entropy().

3. Although thermodynamic entropy is originated in Boltzmann, the historical background of Shannon information is mentioned below link. There seems to be a reference flow: Hartley → Nyquist → Shannon. http://www.ieice.org/jpn/books/kaishikiji/200112/200112-9.html

4. Article on gneralized information criterion(GIC): https://www.ism.ac.jp/editsec/toukei/pdf/47-2-375.pdf