Kullback–Leibler divergence

In mathematical statistics, the Kullback–Leibler (KL) divergence (also called relative entropy and I-divergence^[1]), denoted ${\displaystyle D_{\text{KL}}(P\parallel Q)}$, is a type of statistical distance: a measure of how one probability distribution P is different from a second, reference probability distribution Q.^[2][3] A simple interpretation of the KL divergence of P from Q is the expected excess surprise from using Q as a model instead of P when the actual distribution is P. While it is a measure of how different two distributions are, and in some sense is thus a "distance", it is not actually a metric, which is the most familiar and formal type of distance. In particular, it is not symmetric in the two distributions (in contrast to variation of information), and does not satisfy the triangle inequality. Instead, in terms of information geometry, it is a type of divergence,^[4] a generalization of squared distance, and for certain classes of distributions (notably an exponential family), it satisfies a generalized Pythagorean theorem (which applies to squared distances).^[5]

A relative entropy of 0 indicates that the two distributions in question are identical. Relative entropy is a nonnegative function of two distributions or measures. It has diverse applications, both theoretical, such as characterizing the relative (Shannon) entropy in information systems, randomness in continuous time-series, and information gain when comparing statistical models of inference; and practical, such as applied statistics, fluid mechanics, neuroscience and bioinformatics.

Introduction and context

Consider two probability distributions P and Q. Usually, P represents the data, the observations, or a measured probability distribution. Distribution Q represents instead a theory, a model, a description or an approximation of P. The Kullback–Leibler divergence ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  is then interpreted as the average difference of the number of bits required for encoding samples of P using a code optimized for Q rather than one optimized for P. Note that the roles of P and Q can be reversed in some situations where that is easier to compute, such as with the expectation–maximization algorithm (EM) and evidence lower bound (ELBO) computations.

Etymology

The relative entropy was introduced by Solomon Kullback and Richard Leibler in Kullback & Leibler (1951) as "the mean information for discrimination between ${\displaystyle H_{1}}$  and ${\displaystyle H_{2}}$  per observation from ${\displaystyle \mu _{1}}$ ",^[6] where one is comparing two probability measures ${\displaystyle \mu _{1},\mu _{2}}$ , and ${\displaystyle H_{1},H_{2}}$  are the hypotheses that one is selecting from measure ${\displaystyle \mu _{1},\mu _{2}}$  (respectively). They denoted this by ${\displaystyle I(1:2)}$ , and defined the "'divergence' between ${\displaystyle \mu _{1}}$  and ${\displaystyle \mu _{2}}$ " as the symmetrized quantity ${\displaystyle J(1,2)=I(1:2)+I(2:1)}$ , which had already been defined and used by Harold Jeffreys in 1948.^[7] In Kullback (1959), the symmetrized form is again referred to as the "divergence", and the relative entropies in each direction are referred to as a "directed divergences" between two distributions;^[8] Kullback preferred the term discrimination information.^[9] The term "divergence" is in contrast to a distance (metric), since the symmetrized divergence does not satisfy the triangle inequality.^[10] Numerous references to earlier uses of the symmetrized divergence and to other statistical distances are given in Kullback (1959, pp. 6–7, §1.3 Divergence). The asymmetric "directed divergence" has come to be known as the Kullback–Leibler divergence, while the symmetrized "divergence" is now referred to as the Jeffreys divergence.

Definition

For discrete probability distributions P and Q defined on the same sample space, ${\displaystyle \ {\mathcal {X}}\ ,}$  the relative entropy from Q to P is defined^[11] to be

${\displaystyle D_{\text{KL}}(P\parallel Q)=\sum _{x\in {\mathcal {X}}}P(x)\ \log \left({\frac {\ P(x)\ }{Q(x)}}\right)\ ,}$ 

which is equivalent to

${\displaystyle D_{\text{KL}}(P\parallel Q)=-\sum _{x\in {\mathcal {X}}}P(x)\ \log \left({\frac {\ Q(x)\ }{P(x)}}\right)~.}$ 

In other words, it is the expectation of the logarithmic difference between the probabilities P and Q, where the expectation is taken using the probabilities P.

Relative entropy is only defined in this way if, for all x, ${\displaystyle \ Q(x)=0\ }$  implies ${\displaystyle \ P(x)=0\ }$  (absolute continuity). Otherwise, it is often defined as ${\displaystyle +\infty }$ ,^[1] but the value ${\displaystyle \ +\infty \ }$  is possible even if ${\displaystyle \ Q(x)\neq 0\ }$  everywhere,^[12][13] provided that ${\displaystyle \ {\mathcal {X}}\ }$  is infinite in extent. Analogous comments apply to the continuous and general measure cases defined below.

Whenever ${\displaystyle \ P(x)\ }$  is zero the contribution of the corresponding term is interpreted as zero because

${\displaystyle \lim _{x\to 0^{+}}x\log(x)=0~.}$ 

For distributions P and Q of a continuous random variable, relative entropy is defined to be the integral^[14]

${\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{-\infty }^{\infty }p(x)\ \log \left({\frac {p(x)}{q(x)}}\right)\ \mathrm {d} \ \!x\ ,}$ 

where p and q denote the probability densities of P and Q.

More generally, if P and Q are probability measures on a measurable space ${\displaystyle \ {\mathcal {X}}\ ,}$  and P is absolutely continuous with respect to Q, then the relative entropy from Q to P is defined as

${\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}\ \log \left({\frac {P(\mathrm {d} \ \!x)}{Q(\mathrm {d} \ \!x)}}\right)\ P(\mathrm {d} \ \!x)\ ,}$ 

where ${\displaystyle \ {\frac {\ P(\mathrm {d} \ \!x)\ }{Q(\mathrm {d} \ \!x)\ }}}$  is the Radon–Nikodym derivative of P with respect to Q, i.e. the unique Q almost everywhere defined function r on ${\displaystyle \ {\mathcal {X}}\ }$  such that ${\displaystyle \ P(\mathrm {d} \ \!x)=r(x)Q(\mathrm {d} \ \!x)\ }$  which exists because P is absolutely continuous with respect to Q. Also we assume the expression on the right-hand side exists. Equivalently (by the chain rule), this can be written as

${\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}{\frac {P(\mathrm {d} \ \!x)}{Q(\mathrm {d} \ \!x)}}\ \log \left({\frac {P(\mathrm {d} \ \!x)}{Q(\mathrm {d} \ \!x)}}\right)\ Q(\mathrm {d} \ \!x)\ ,}$ 

which is the entropy of P relative to Q. Continuing in this case, if ${\displaystyle \mu }$  is any measure on ${\displaystyle {\mathcal {X}}}$  for which densities p and q with ${\displaystyle \ P(\mathrm {d} \ \!x)=p(x)\mu (\mathrm {d} \ \!x)\ }$  and ${\displaystyle \ Q(\mathrm {d} \ \!x)=q(x)\mu (\mathrm {d} \ \!x)\ }$  exist (meaning that P and Q are both absolutely continuous with respect to ${\displaystyle \ \mu \ }$ ), then the relative entropy from Q to P is given as

${\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}p(x)\ \log \left({\frac {\ p(x)\ }{q(x)}}\right)\ \mu (\mathrm {d} \ \!x)~.}$ 

Note that such a measure ${\displaystyle \mu }$  for which densities can be defined always exists, since one can take ${\displaystyle \ \mu ={\frac {1}{2}}\left(P+Q\right)\ }$  although in practice it will usually be one that in the context like counting measure for discrete distributions, or Lebesgue measure or a convenient variant thereof like Gaussian measure or the uniform measure on the sphere, Haar measure on a Lie group etc. for continuous distributions. The logarithms in these formulae are usually taken to base 2 if information is measured in units of bits, or to base e if information is measured in nats. Most formulas involving relative entropy hold regardless of the base of the logarithm.

Various conventions exist for referring to ${\displaystyle \ D_{\text{KL}}(P\parallel Q)\ }$  in words. Often it is referred to as the divergence between P and Q, but this fails to convey the fundamental asymmetry in the relation. Sometimes, as in this article, it may be described as the divergence of P from Q or as the divergence from Q to P. This reflects the asymmetry in Bayesian inference, which starts from a prior Q and updates to the posterior P. Another common way to refer to ${\displaystyle \ D_{\text{KL}}(P\parallel Q)\ }$  is as the relative entropy of P with respect to Q or the information gain from P over Q.

Basic example

Kullback^[3] gives the following example (Table 2.1, Example 2.1). Let P and Q be the distributions shown in the table and figure. P is the distribution on the left side of the figure, a binomial distribution with ${\displaystyle N=2}$  and ${\displaystyle p=0.4}$ . Q is the distribution on the right side of the figure, a discrete uniform distribution with the three possible outcomes ${\displaystyle x=}$  0, 1, 2 (i.e. ${\displaystyle {\mathcal {X}}=\{0,1,2\}}$ ), each with probability ${\displaystyle p=1/3}$ .

 

Two distributions to illustrate relative entropy

x	0	1	2
Distribution ${\displaystyle P(x)}$	${\displaystyle {\frac {9}{25}}}$	${\displaystyle {\frac {12}{25}}}$	${\displaystyle {\frac {4}{25}}}$
Distribution ${\displaystyle Q(x)}$	${\displaystyle {\frac {1}{3}}}$	${\displaystyle {\frac {1}{3}}}$	${\displaystyle {\frac {1}{3}}}$

Relative entropies ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  and ${\displaystyle D_{\text{KL}}(Q\parallel P)}$  are calculated as follows. This example uses the natural log with base e, designated ln to get results in nats (see units of information):

${\displaystyle {\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\sum _{x\in {\mathcal {X}}}P(x)\ln \left({\frac {P(x)}{Q(x)}}\right)\\&={\frac {9}{25}}\ln \left({\frac {9/25}{1/3}}\right)+{\frac {12}{25}}\ln \left({\frac {12/25}{1/3}}\right)+{\frac {4}{25}}\ln \left({\frac {4/25}{1/3}}\right)\\&={\frac {1}{25}}\left(32\ln(2)+55\ln(3)-50\ln(5)\right)\approx 0.0852996,\end{aligned}}}$ 

${\displaystyle {\begin{aligned}D_{\text{KL}}(Q\parallel P)&=\sum _{x\in {\mathcal {X}}}Q(x)\ln \left({\frac {Q(x)}{P(x)}}\right)\\&={\frac {1}{3}}\ln \left({\frac {1/3}{9/25}}\right)+{\frac {1}{3}}\ln \left({\frac {1/3}{12/25}}\right)+{\frac {1}{3}}\ln \left({\frac {1/3}{4/25}}\right)\\&={\frac {1}{3}}\left(-4\ln(2)-6\ln(3)+6\ln(5)\right)\approx 0.097455.\end{aligned}}}$ 

Interpretations

Statistics

In the field of statistics, the Neyman–Pearson lemma states that the most powerful way to distinguish between the two distributions P and Q based on an observation Y (drawn from one of them) is through the log of the ratio of their likelihoods: ${\displaystyle \log P(Y)-\log Q(Y)}$ . The KL divergence is the expected value of this statistic if Y is actually drawn from P. Kullback motivated the statistic as an expected log likelihood ratio.^[15]

Coding

In the context of coding theory, ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  can be constructed by 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.

Inference

In the context of machine learning, ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  is often called the information gain achieved if P would be used instead of Q which is currently used. By analogy with information theory, it is called the relative entropy of P with respect to Q.

Expressed in the language of Bayesian inference, ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  is a measure of the information gained by revising one's beliefs from the prior probability distribution Q to the posterior probability distribution P. In other words, it is the amount of information lost when Q is used to approximate P.^[16]

Information geometry

In applications, P typically represents the "true" distribution of data, observations, or a precisely calculated theoretical distribution, while Q typically represents a theory, model, description, or approximation of P. In order to find a distribution Q that is closest to P, we can minimize the KL divergence and compute an information projection.

While it is a statistical distance, it is not a metric, the most familiar type of distance, but instead it is a divergence.^[4] While metrics are symmetric and generalize linear distance, satisfying the triangle inequality, divergences are asymmetric and generalize squared distance, in some cases satisfying a generalized Pythagorean theorem. In general ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  does not equal ${\displaystyle D_{\text{KL}}(Q\parallel P)}$ , and the asymmetry is an important part of the geometry.^[4] The infinitesimal form of relative entropy, specifically its Hessian, gives a metric tensor that equals the Fisher information metric; see § Fisher information metric. Relative entropy satisfies a generalized Pythagorean theorem for exponential families (geometrically interpreted as dually flat manifolds), and this allows one to minimize relative entropy by geometric means, for example by information projection and in maximum likelihood estimation.^[5]

The relative entropy is the Bregman divergence generated by the negative entropy, but it is also of the form of an f-divergence. For probabilities over a finite alphabet, it is unique in being a member of both of these classes of statistical divergences.

Finance (game theory)

Consider a growth-optimizing investor in a fair game with mutually exclusive outcomes (e.g. a “horse race” in which the official odds add up to one). The rate of return expected by such an investor is equal to the relative entropy between the investor's believed probabilities and the official odds.^[17] This is a special case of a much more general connection between financial returns and divergence measures.^[18]

Financial risks are connected to ${\displaystyle D_{\text{KL}}}$  via information geometry.^[19] Investors' views, the prevailing market view, and risky scenarios form triangles on the relevant manifold of probability distributions. The shape of the triangles determines key financial risks (both qualitatively and quantitatively). For instance, obtuse triangles in which investors' views and risk scenarios appear on “opposite sides” relative to the market describe negative risks, acute triangles describe positive exposure, and the right-angled situation in the middle corresponds to zero risk.

Motivation

 

Illustration of the relative entropy for two normal distributions. The typical asymmetry is clearly visible.

In information theory, the Kraft–McMillan theorem establishes that any directly decodable coding scheme for coding a message to identify one value ${\displaystyle x_{i}}$  out of a set of possibilities X can be seen as representing an implicit probability distribution ${\displaystyle q(x_{i})=2^{-\ell _{i}}}$  over X, where ${\displaystyle \ell _{i}}$  is the length of the code for ${\displaystyle x_{i}}$  in bits. Therefore, relative entropy can be interpreted as the expected extra message-length per datum that must be communicated if a code that is optimal for a given (wrong) distribution Q is used, compared to using a code based on the true distribution P: it is the excess entropy.

${\displaystyle {\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\sum _{x\in {\mathcal {X}}}p(x)\log {\frac {1}{q(x)}}-\sum _{x\in {\mathcal {X}}}p(x)\log {\frac {1}{p(x)}}\\[5pt]&=\mathrm {H} (P,Q)-\mathrm {H} (P)\end{aligned}}}$ 

where ${\displaystyle \mathrm {H} (P,Q)}$  is the cross entropy of P and Q, and ${\displaystyle \mathrm {H} (P)}$  is the entropy of P (which is the same as the cross-entropy of P with itself).

The relative entropy ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  can be thought of geometrically as a statistical distance, a measure of how far the distribution Q is from the distribution P. Geometrically it is a divergence: an asymmetric, generalized form of squared distance. The cross-entropy ${\displaystyle H(P,Q)}$  is itself such a measurement (formally a loss function), but it cannot be thought of as a distance, since ${\displaystyle H(P,P)=:H(P)}$  is not zero. This can be fixed by subtracting ${\displaystyle H(P)}$  to make ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  agree more closely with our notion of distance, as the excess loss. The resulting function is asymmetric, and while this can be symmetrized (see § Symmetrised divergence), the asymmetric form is more useful. See § Interpretations for more on the geometric interpretation.

Relative entropy relates to "rate function" in the theory of large deviations.^[20][21]

Arthur Hobson proved that relative entropy is the only measure of difference between probability distributions that satisfies some desired properties, which are the canonical extension to those appearing in a commonly used characterization of entropy.^[22] Consequently, mutual information is the only measure of mutual dependence that obeys certain related conditions, since it can be defined in terms of Kullback–Leibler divergence.

Properties

• Relative entropy is always non-negative,
  $${\displaystyle D_{\text{KL}}(P\parallel Q)\geq 0,}$$

   
  a result known as Gibbs' inequality, with ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  equals zero if and only if ${\displaystyle P=Q}$  as measures.

In particular, if ${\displaystyle P(dx)=p(x)\mu (dx)}$  and ${\displaystyle Q(dx)=q(x)\mu (dx)}$ , then ${\displaystyle p(x)=q(x)}$  ${\displaystyle \mu }$ -almost everywhere. The entropy ${\displaystyle \mathrm {H} (P)}$  thus sets a minimum value for the cross-entropy ${\displaystyle \mathrm {H} (P,Q)}$ , the expected number of bits required when using a code based on Q rather than P; and the Kullback–Leibler divergence therefore represents the expected number of extra bits that must be transmitted to identify a value x drawn from X, if a code is used corresponding to the probability distribution Q, rather than the "true" distribution P.

• No upper-bound exists for the general case. However, it is shown that if P and Q are two discrete probability distributions built by distributing the same discrete quantity, then the maximum value of ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  can be calculated.^[23]
• Relative entropy remains well-defined for continuous distributions, and furthermore is invariant under parameter transformations. For example, if a transformation is made from variable x to variable ${\displaystyle y(x)}$ , then, since ${\displaystyle P(dx)=p(x)\,dx={\tilde {p}}(y)\,dy={\tilde {p}}(y(x))|{\tfrac {dy}{dx}}(x)|\,dx}$  and ${\displaystyle Q(dx)=q(x)\,dx={\tilde {q}}(y)\,dy={\tilde {q}}(y)|{\tfrac {dy}{dx}}(x)|dx}$  where ${\displaystyle |{\tfrac {dy}{dx}}(x)|}$  is the absolute value of the derivative or more generally of the Jacobian, the relative entropy may be rewritten:
  $${\displaystyle {\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\int _{x_{a}}^{x_{b}}p(x)\log \left({\frac {p(x)}{q(x)}}\right)\,dx\\[6pt]&=\int _{x_{a}}^{x_{b}}{\tilde {p}}(y(x))|{\frac {dy}{dx}}(x)|\log \left({\frac {{\tilde {p}}(y(x))\,|{\frac {dy}{dx}}(x)|}{{\tilde {q}}(y(x))\,|{\frac {dy}{dx}}(x)|}}\right)\,dx\\&=\int _{y_{a}}^{y_{b}}{\tilde {p}}(y)\log \left({\frac {{\tilde {p}}(y)}{{\tilde {q}}(y)}}\right)\,dy\end{aligned}}}$$

   
  where ${\displaystyle y_{a}=y(x_{a})}$  and ${\displaystyle y_{b}=y(x_{b})}$ . Although it was assumed that the transformation was continuous, this need not be the case. This also shows that the relative entropy produces a dimensionally consistent quantity, since if x is a dimensioned variable, ${\displaystyle p(x)}$  and ${\displaystyle q(x)}$  are also dimensioned, since e.g. ${\displaystyle P(dx)=p(x)\,dx}$  is dimensionless. The argument of the logarithmic term is and remains dimensionless, as it must. It can therefore be seen as in some ways a more fundamental quantity than some other properties in information theory^[24] (such as self-information or Shannon entropy), which can become undefined or negative for non-discrete probabilities.
• Relative entropy is additive for independent distributions in much the same way as Shannon entropy. If ${\displaystyle P_{1},P_{2}}$  are independent distributions, and ${\displaystyle P(dx,dy)=P_{1}(dx)P_{2}(dy)}$ , and likewise ${\displaystyle Q(dx,dy)=Q_{1}(dx)Q_{2}(dy)}$  for independent distributions ${\displaystyle Q_{1},Q_{2}}$  then
  $${\displaystyle D_{\text{KL}}(P\parallel Q)=D_{\text{KL}}(P_{1}\parallel Q_{1})+D_{\text{KL}}(P_{2}\parallel Q_{2}).}$$

   
• Relative entropy ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  is convex in the pair of probability measures ${\displaystyle (P,Q)}$ , i.e. if ${\displaystyle (P_{1},Q_{1})}$  and ${\displaystyle (P_{2},Q_{2})}$  are two pairs of probability measures then
  $${\displaystyle D_{\text{KL}}(\lambda P_{1}+(1-\lambda )P_{2}\parallel \lambda Q_{1}+(1-\lambda )Q_{2})\leq \lambda D_{\text{KL}}(P_{1}\parallel Q_{1})+(1-\lambda )D_{\text{KL}}(P_{2}\parallel Q_{2}){\text{ for }}0\leq \lambda \leq 1.}$$

   
• The Taylor expansion is ${\displaystyle D_{\text{KL}}(P\parallel Q)={\frac {1}{2}}\sum _{x}{\frac {(P(x)-Q(x))^{2}}{P(x)}}-{\frac {1}{3}}\sum _{x}{\frac {(P(x)-Q(x))^{3}}{P(x)^{2}}}+\cdots }$ .

Duality formula for variational inference

The following result, due to Donsker and Varadhan,^[25] is known as Donsker and Varadhan's variational formula.

Theorem [Duality Formula for Variational Inference] — Let ${\displaystyle \Theta }$  be a set endowed with an appropriate ${\displaystyle \sigma }$ -field ${\displaystyle {\mathcal {F}}}$ , and two probability measures P and Q, which formulate two probability spaces ${\displaystyle (\Theta ,{\mathcal {F}},P)}$  and ${\displaystyle (\Theta ,{\mathcal {F}},Q)}$ , with ${\displaystyle Q\ll P}$ . (${\displaystyle Q\ll P}$  indicates that Q is absolutely continuous with respect to P.) Let h be a real-valued integrable random variable on ${\displaystyle (\Theta ,{\mathcal {F}},P)}$ . Then the following equality holds

${\displaystyle \log E_{P}[\exp h]={\text{sup}}_{Q\ll P}\{E_{Q}[h]-D_{\text{KL}}(Q\parallel P)\}.}$ 

Further, the supremum on the right-hand side is attained if and only if it holds

${\displaystyle {\frac {Q(d\theta )}{P(d\theta )}}={\frac {\exp h(\theta )}{E_{P}[\exp h]}},}$ 

almost surely with respect to probability measure P, where ${\displaystyle {\frac {Q(d\theta )}{P(d\theta )}}}$  denotes the Radon-Nikodym derivative of Q with respect to P .

Proof

For a short proof assuming integrability of ${\displaystyle \exp(h)}$  with respect to P, let ${\displaystyle Q^{*}}$  have P-density ${\displaystyle {\frac {\exp h(\theta )}{E_{P}[\exp h]}}}$ , i.e. ${\displaystyle Q^{*}(d\theta )={\frac {\exp h(\theta )}{E_{P}[\exp h]}}P(d\theta )}$  Then

${\displaystyle D_{\text{KL}}(Q\parallel Q^{*})-D_{\text{KL}}(Q\parallel P)=-E_{Q}[h]+\log E_{P}[\exp h].}$ 

Therefore,

${\displaystyle E_{Q}[h]-D_{\text{KL}}(Q\parallel P)=\log E_{P}[\exp h]-D_{\text{KL}}(Q\parallel Q^{*})\leq \log E_{P}[\exp h],}$ 

where the last inequality follows from ${\displaystyle D_{\text{KL}}(Q\parallel Q^{*})\geq 0}$ , for which equality occurs if and only if ${\displaystyle Q=Q^{*}}$ . The conclusion follows.

For alternative proof using measure theory, see.^[26]

Examples

Multivariate normal distributions

Suppose that we have two multivariate normal distributions, with means ${\displaystyle \mu _{0},\mu _{1}}$  and with (non-singular) covariance matrices ${\displaystyle \Sigma _{0},\Sigma _{1}.}$  If the two distributions have the same dimension, k, then the relative entropy between the distributions is as follows:^[27]

${\displaystyle D_{\text{KL}}\left({\mathcal {N}}_{0}\parallel {\mathcal {N}}_{1}\right)={\frac {1}{2}}\left(\operatorname {tr} \left(\Sigma _{1}^{-1}\Sigma _{0}\right)-k+\left(\mu _{1}-\mu _{0}\right)^{\mathsf {T}}\Sigma _{1}^{-1}\left(\mu _{1}-\mu _{0}\right)+\ln \left({\frac {\det \Sigma _{1}}{\det \Sigma _{0}}}\right)\right).}$ 

The logarithm in the last term must be taken to base e since all terms apart from the last are base-e logarithms of expressions that are either factors of the density function or otherwise arise naturally. The equation therefore gives a result measured in nats. Dividing the entire expression above by ${\displaystyle \ln(2)}$  yields the divergence in bits.

In a numerical implementation, it is helpful to express the result in terms of the Cholesky decompositions ${\displaystyle L_{0},L_{1}}$  such that ${\displaystyle \Sigma _{0}=L_{0}L_{0}^{T}}$  and ${\displaystyle \Sigma _{1}=L_{1}L_{1}^{T}}$ . Then with M and y solutions to the triangular linear systems ${\displaystyle L_{1}M=L_{0}}$ , and ${\displaystyle L_{1}y=\mu _{1}-\mu _{0}}$ ,

${\displaystyle D_{\text{KL}}\left({\mathcal {N}}_{0}\parallel {\mathcal {N}}_{1}\right)={\frac {1}{2}}\left(\sum _{i,j=1}^{k}(M_{ij})^{2}-k+|y|^{2}+2\sum _{i=1}^{k}\ln {\frac {(L_{1})_{ii}}{(L_{0})_{ii}}}\right).}$ 

A special case, and a common quantity in variational inference, is the relative entropy between a diagonal multivariate normal, and a standard normal distribution (with zero mean and unit variance):

${\displaystyle D_{\text{KL}}\left({\mathcal {N}}\left(\left(\mu _{1},\ldots ,\mu _{k}\right)^{\mathsf {T}},\operatorname {diag} \left(\sigma _{1}^{2},\ldots ,\sigma _{k}^{2}\right)\right)\parallel {\mathcal {N}}\left(\mathbf {0} ,\mathbf {I} \right)\right)={1 \over 2}\sum _{i=1}^{k}\left(\sigma _{i}^{2}+\mu _{i}^{2}-1-\ln \left(\sigma _{i}^{2}\right)\right).}$ 

For two univariate normal distributions p and q the above simplifies to^[28]

${\displaystyle D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log {\frac {\sigma _{1}}{\sigma _{0}}}+{\frac {\sigma _{0}^{2}+(\mu _{0}-\mu _{1})^{2}}{2\sigma _{1}^{2}}}-{\frac {1}{2}}}$ 

In the case of co-centered normal distributions with ${\displaystyle k=\sigma _{1}/\sigma _{0}}$ , this simplifies^[29] to:

${\displaystyle D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log _{2}k+(k^{-2}-1)/2/\ln(2)\mathrm {bits} }$ 

Uniform distributions

Consider two uniform distributions, with the support of ${\displaystyle p=[A,B]}$  enclosed within ${\displaystyle q=[C,D]}$  (${\displaystyle C\leq A<B\leq D}$ ). Then the information gain is:

${\displaystyle D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log {\frac {D-C}{B-A}}}$ 

Intuitively,^[29] the information gain to a k times narrower uniform distribution contains ${\displaystyle \log _{2}k}$  bits. This connects with the use of bits in computing, where ${\displaystyle \log _{2}k}$  bits would be needed to identify one element of a k long stream.

Relation to metrics

While relative entropy is a statistical distance, it is not a metric on the space of probability distributions, but instead it is a divergence.^[4] While metrics are symmetric and generalize linear distance, satisfying the triangle inequality, divergences are asymmetric in general and generalize squared distance, in some cases satisfying a generalized Pythagorean theorem. In general ${\displaystyle D_{\text{KL}}(P\parallel Q)}$  does not equal ${\displaystyle D_{\text{KL}}(Q\parallel P)}$ , and while this can be symmetrized (see § Symmetrised divergence), the asymmetry is an important part of the geometry.^[4]

It generates a topology on the space of probability distributions. More concretely, if ${\displaystyle \{P_{1},P_{2},\ldots \}}$  is a sequence of distributions such that

${\displaystyle \lim _{n\to \infty }D_{\text{KL}}(P_{n}\parallel Q)=0}$ ,

then it is said that

${\displaystyle P_{n}{\xrightarrow {D}}Q}$ .

Pinsker's inequality entails that

${\displaystyle P_{n}\xrightarrow {D} P\Rightarrow P_{n}\xrightarrow {TV} P}$ ,

where the latter stands for the usual convergence in total variation.

Fisher information metric

Relative entropy is directly related to the Fisher information metric. This can be made explicit as follows. Assume that the probability distributions P and Q are both parameterized by some (possibly multi-dimensional) parameter ${\displaystyle \theta }$ . Consider then two close by values of ${\displaystyle P=P(\theta )}$  and ${\displaystyle Q=P(\theta _{0})}$  so that the parameter ${\displaystyle \theta }$  differs by only a small amount from the parameter value ${\displaystyle \theta _{0}}$ . Specifically, up to first order one has (using the Einstein summation convention)

${\displaystyle P(\theta )=P(\theta _{0})+\Delta \theta _{j}\,P_{j}(\theta _{0})+\cdots }$ 

with ${\displaystyle \Delta \theta _{j}=(\theta -\theta _{0})_{j}}$  a small change of ${\displaystyle \theta }$  in the j direction, and ${\displaystyle P_{j}\left(\theta _{0}\right)={\frac {\partial P}{\partial \theta _{j}}}(\theta _{0})}$  the corresponding rate of change in the probability distribution. Since relative entropy has an absolute minimum 0 for ${\displaystyle P=Q}$ , i.e. ${\displaystyle \theta =\theta _{0}}$ , it changes only to second order in the small parameters ${\displaystyle \Delta \theta _{j}}$ . More formally, as for any minimum, the first derivatives of the divergence vanish

${\displaystyle \left.{\frac {\partial }{\partial \theta _{j}}}\right|_{\theta =\theta _{0}}D_{\text{KL}}(P(\theta )\parallel P(\theta _{0}))=0,}$ 

and by the Taylor expansion one has up to second order

${\displaystyle D_{\text{KL}}(P(\theta )\parallel P(\theta _{0}))={\frac {1}{2}}\,\Delta \theta _{j}\,\Delta \theta _{k}\,g_{jk}(\theta _{0})+\cdots }$ 

where the Hessian matrix of the divergence

${\displaystyle g_{jk}(\theta _{0})=\left.{\frac {\partial ^{2}}{\partial \theta _{j}\,\partial \theta _{k}}}\right|_{\theta =\theta _{0}}D_{\text{KL}}(P(\theta )\parallel P(\theta _{0}))}$ 

must be positive semidefinite. Letting ${\displaystyle \theta _{0}}$  vary (and dropping the subindex 0) the Hessian ${\displaystyle g_{jk}(\theta )}$  defines a (possibly degenerate) Riemannian metric on the θ parameter space, called the Fisher information metric.

Fisher information metric theorem

When ${\displaystyle p_{(x,\rho )}}$  satisfies the following regularity conditions:

${\displaystyle {\frac {\partial \log(p)}{\partial \rho }},{\frac {\partial ^{2}\log(p)}{\partial \rho ^{2}}},{\frac {\partial ^{3}\log(p)}{\partial \rho ^{3}}}}$  exist,

${\displaystyle {\begin{aligned}\left|{\frac {\partial p}{\partial \rho }}\right|&<F(x):\int _{x=0}^{\infty }F(x)\,dx<\infty ,\\\left|{\frac {\partial ^{2}p}{\partial \rho ^{2}}}\right|&<G(x):\int _{x=0}^{\infty }G(x)\,dx<\infty \\\left|{\frac {\partial ^{3}\log(p)}{\partial \rho ^{3}}}\right|&<H(x):\int _{x=0}^{\infty }p(x,0)H(x)\,dx<\xi <\infty \end{aligned}}}$ 

where ξ is independent of ρ

${\displaystyle \left.\int _{x=0}^{\infty }{\frac {\partial p(x,\rho )}{\partial \rho }}\right|_{\rho =0}\,dx=\left.\int _{x=0}^{\infty }{\frac {\partial ^{2}p(x,\rho )}{\partial \rho ^{2}}}\right|_{\rho =0}\,dx=0}$ 

then:

${\displaystyle {\mathcal {D}}(p(x,0)\parallel p(x,\rho ))={\frac {c\rho ^{2}}{2}}+{\mathcal {O}}\left(\rho ^{3}\right){\text{ as }}\rho \to 0.}$ 

Variation of information

Another information-theoretic metric is variation of information, which is roughly a symmetrization of conditional entropy. It is a metric on the set of partitions of a discrete probability space.

Relation to other quantities of information theory

Many of the other quantities of information theory can be interpreted as applications of relative entropy to specific cases.

Self-information

Main article: Information content

The self-information, also known as the information content of a signal, random variable, or event is defined as the negative logarithm of the probability of the given outcome occurring.

When applied to a discrete random variable, the self-information can be represented as^{[citation needed]}

${\displaystyle \operatorname {\operatorname {I} } (m)=D_{\text{KL}}\left(\delta _{\text{im}}\parallel \{p_{i}\}\right),}$ 

is the relative entropy of the probability distribution ${\displaystyle P(i)}$  from a Kronecker delta representing certainty that ${\displaystyle i=m}$  — i.e. the number of extra bits that must be transmitted to identify i if only the probability distribution ${\displaystyle P(i)}$  is available to the receiver, not the fact that ${\displaystyle i=m}$ .

Mutual information

The mutual information,

${\displaystyle {\begin{aligned}\operatorname {I} (X;Y)&=D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))\\[5pt]&=\operatorname {E} _{X}\{D_{\text{KL}}(P(Y\mid X)\parallel P(Y))\}\\[5pt]&=\operatorname {E} _{Y}\{D_{\text{KL}}(P(X\mid Y)\parallel P(X))\}\end{aligned}}}$ 

is the relative entropy of the joint probability distribution ${\displaystyle P(X,Y)}$  from the product ${\displaystyle P(X)P(Y)}$  of the two marginal probability distributions — i.e. the expected number of extra bits that must be transmitted to identify X and Y if they are coded using only their marginal distributions instead of the joint distribution. Equivalently, if the joint probability ${\displaystyle P(X,Y)}$  is known, it is the expected number of extra bits that must on average be sent to identify Y if the value of X is not already known to the receiver.

Shannon entropy

The Shannon entropy,

${\displaystyle {\begin{aligned}\mathrm {H} (X)&=\operatorname {E} \left[\operatorname {I} _{X}(x)\right]\\&=\log(N)-D_{\text{KL}}\left(p_{X}(x)\parallel P_{U}(X)\right)\end{aligned}}}$ 

is the number of bits which would have to be transmitted to identify X from N equally likely possibilities, less the relative entropy of the uniform distribution on the random variates of X, ${\displaystyle P_{U}(X)}$ , from the true distribution ${\displaystyle P(X)}$  — i.e. less the expected number of bits saved, which would have had to be sent if the value of X were coded according to the uniform distribution ${\displaystyle P_{U}(X)}$  rather than the true distribution ${\displaystyle P(X)}$ . This definition of Shannon entropy forms the basis of E.T. Jaynes's alternative generalization to continuous distributions, the limiting density of discrete points (as opposed to the usual differential entropy), which defines the continuous entropy as

${\displaystyle \lim _{N\rightarrow \infty }H_{N}(X)=\log(N)-\int p(x)\log {\frac {p(x)}{m(x)}}\,dx,}$ 

which is equivalent to:

${\displaystyle \log(N)-D_{\text{KL}}(p(x)||m(x))}$ 

Conditional entropy

The conditional entropy^[30],

${\displaystyle {\begin{aligned}\mathrm {H} (X\mid Y)&=\log(N)-D_{\text{KL}}(P(X,Y)\parallel P_{U}(X)P(Y))\\[5pt]&=\log(N)-D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))-D_{\text{KL}}(P(X)\parallel P_{U}(X))\\[5pt]&=\mathrm {H} (X)-\operatorname {I} (X;Y)\\[5pt]&=\log(N)-\operatorname {E} _{Y}\left[D_{\text{KL}}\left(P\left(X\mid Y\right)\parallel P_{U}(X)\right)\right]\end{aligned}}}$ 

is the number of bits which would have to be transmitted to identify X from N equally likely possibilities, less the relative entropy of the product distribution ${\displaystyle P_{U}(X)P(Y)}$  from the true joint distribution ${\displaystyle P(X,Y)}$  — i.e. less the expected number of bits saved which would have had to be sent if the value of X were coded according to the uniform distribution ${\displaystyle P_{U}(X)}$  rather than the conditional distribution ${\displaystyle P(X|Y)}$  of X given Y.

Cross entropy

When we have a set of possible events, coming from the distribution p, we can encode them (with a lossless data compression) using entropy encoding. This compresses the data by replacing each fixed-length input symbol with a corresponding unique, variable-length, prefix-free code (e.g.: the events (A, B, C) with probabilities p = (1/2, 1/4, 1/4) can be encoded as the bits (0, 10, 11)). If we know the distribution p in advance, we can devise an encoding that would be optimal (e.g.: using Huffman coding). Meaning the messages we encode will have the shortest length on average (assuming the encoded events are sampled from p), which will be equal to Shannon's Entropy of p (denoted as ${\displaystyle \mathrm {H} (p)}$ ). However, if we use a different probability distribution (q) when creating the entropy encoding scheme, then a larger number of bits will be used (on average) to identify an event from a set of possibilities. This new (larger) number is measured by the cross entropy between p and q.

The cross entropy between two probability distributions (p and q) measures the average number of bits needed to identify an event from a set of possibilities, if a coding scheme is used based on a given probability distribution q, rather than the "true" distribution p. The cross entropy for two distributions p and q over the same probability space is thus defined as follows.

${\displaystyle \mathrm {H} (p,q)=\operatorname {E} _{p}[-\log(q)]=\mathrm {H} (p)+D_{\text{KL}}(p\parallel q).}$ 

For explicit derivation of this, see the Motivation section above.

Under this scenario, relative entropies (kl-divergence) can be interpreted as the extra number of bits, on average, that are needed (beyond ${\displaystyle \mathrm {H} (p)}$ ) for encoding the events because of using q for constructing the encoding scheme instead of p.

Bayesian updating

In Bayesian statistics, relative entropy can be used as a measure of the information gain in moving from a prior distribution to a posterior distribution: ${\displaystyle p(x)\to p(x\mid I)}$ . If some new fact ${\displaystyle Y=y}$  is discovered, it can be used to update the posterior distribution for X from ${\displaystyle p(x\mid I)}$  to a new posterior distribution ${\displaystyle p(x\mid y,I)}$  using Bayes' theorem:

${\displaystyle p(x\mid y,I)={\frac {p(y\mid x,I)p(x\mid I)}{p(y\mid I)}}}$ 

This distribution has a new entropy:

${\displaystyle \mathrm {H} {\big (}p(x\mid y,I){\big )}=-\sum _{x}p(x\mid y,I)\log p(x\mid y,I),}$ 

which may be less than or greater than the original entropy ${\displaystyle \mathrm {H} (p(x\mid I))}$ . However, from the standpoint of the new probability distribution one can estimate that to have used the original code based on ${\displaystyle p(x\mid I)}$  instead of a new code based on ${\displaystyle p(x\mid y,I)}$  would have added an expected number of bits:

${\displaystyle D_{\text{KL}}{\big (}p(x\mid y,I)\parallel p(x\mid I){\big )}=\sum _{x}p(x\mid y,I)\log \left({\frac {p(x\mid y,I)}{p(x\mid I)}}\right)}$ 

to the message length. This therefore represents the amount of useful information, or information gain, about X, that has been learned by discovering ${\displaystyle Y=y}$ .

If a further piece of data, ${\displaystyle Y_{2}=y_{2}}$ , subsequently comes in, the probability distribution for x can be updated further, to give a new best guess ${\displaystyle p(x\mid y_{1},y_{2},I)}$ . If one reinvestigates the information gain for using ${\displaystyle p(x\mid y_{1},I)}$  rather than ${\displaystyle p(x\mid I)}$ , it turns out that it may be either greater or less than previously estimated:

${\displaystyle \sum _{x}p(x\mid y_{1},y_{2},I)\log \left({\frac {p(x\mid y_{1},y_{2},I)}{p(x\mid I)}}\right)}$  may be ≤ or > than ${\displaystyle \displaystyle \sum _{x}p(x\mid y_{1},I)\log \left({\frac {p(x\mid y_{1},I)}{p(x\mid I)}}\right)}$ 

and so the combined information gain does not obey the triangle inequality:

${\displaystyle D_{\text{KL}}{\big (}p(x\mid y_{1},y_{2},I)\parallel p(x\mid I){\big )}}$  may be <, = or > than ${\displaystyle D_{\text{KL}}{\big (}p(x\mid y_{1},y_{2},I)\parallel p(x\mid y_{1},I){\big )}+D_{\text{KL}}{\big (}p(x\mid y_{1},I)\parallel p(x\mid I){\big )}}$ 

All one can say is that on average, averaging using ${\displaystyle p(y_{2}\mid y_{1},x,I)}$ , the two sides will average out.

Bayesian experimental design

A common goal in Bayesian experimental design is to maximise the expected relative entropy between the prior and the posterior.^[31] When posteriors are approximated to be Gaussian distributions, a design maximising the expected relative entropy is called Bayes d-optimal.

Discrimination information

Relative entropy ${\textstyle D_{\text{KL}}{\bigl (}p(x\mid H_{1})\parallel p(x\mid H_{0}){\bigr )}}$  can also be interpreted as the expected discrimination information for ${\displaystyle H_{1}}$  over ${\displaystyle H_{0}}$ : the mean information per sample for discriminating in favor of a hypothesis ${\displaystyle H_{1}}$  against a hypothesis ${\displaystyle H_{0}}$ , when hypothesis ${\displaystyle H_{1}}$  is true.^[32] Another name for this quantity, given to it by I. J. Good, is the expected weight of evidence for ${\displaystyle H_{1}}$  over ${\displaystyle H_{0}}$  to be expected from each sample.

The expected weight of evidence for ${\displaystyle H_{1}}$  over ${\displaystyle H_{0}}$  is not the same as the information gain expected per sample about the probability distribution ${\displaystyle p(H)}$  of the hypotheses,

${\displaystyle D_{\text{KL}}(p(x\mid H_{1})\parallel p(x\mid H_{0}))\neq IG=D_{\text{KL}}(p(H\mid x)\parallel p(H\mid I)).}$ 

Either of the two quantities can be used as a utility function in Bayesian experimental design, to choose an optimal next question to investigate: but they will in general lead to rather different experimental strategies.

On the entropy scale of information gain there is very little difference between near certainty and absolute certainty—coding according to a near certainty requires hardly any more bits than coding according to an absolute certainty. On the other hand, on the logit scale implied by weight of evidence, the difference between the two is enormous – infinite perhaps; this might reflect the difference between being almost sure (on a probabilistic level) that, say, the Riemann hypothesis is correct, compared to being certain that it is correct because one has a mathematical proof. These two different scales of loss function for uncertainty are both useful, according to how well each reflects the particular circumstances of the problem in question.

Principle of minimum discrimination information

The idea of relative entropy as discrimination information led Kullback to propose the Principle of Minimum Discrimination Information (MDI): given new facts, a new distribution f should be chosen which is as hard to discriminate from the original distribution ${\displaystyle f_{0}}$  as possible; so that the new data produces as small an information gain ${\displaystyle D_{\text{KL}}(f\parallel f_{0})}$  as possible.

For example, if one had a prior distribution ${\displaystyle p(x,a)}$  over x and a, and subsequently learnt the true distribution of a was ${\displaystyle u(a)}$ , then the relative entropy between the new joint distribution for x and a, ${\displaystyle q(x\mid a)u(a)}$ , and the earlier prior distribution would be:

${\displaystyle D_{\text{KL}}(q(x\mid a)u(a)\parallel p(x,a))=\operatorname {E} _{u(a)}\left\{D_{\text{KL}}(q(x\mid a)\parallel p(x\mid a))\right\}+D_{\text{KL}}(u(a)\parallel p(a)),}$ 

i.e. the sum of the relative entropy of ${\displaystyle p(a)}$  the prior distribution for a from the updated distribution ${\displaystyle u(a)}$ , plus the expected value (using the probability distribution ${\displaystyle u(a)}$ ) of the relative entropy of the prior conditional distribution ${\displaystyle p(x\mid a)}$  from the new conditional distribution ${\displaystyle q(x\mid a)}$ . (Note that often the later expected value is called the conditional relative entropy (or conditional Kullback–Leibler divergence) and denoted by ${\displaystyle D_{\text{KL}}(q(x\mid a)\parallel p(x\mid a))}$ ^[3][30]) This is minimized if ${\displaystyle q(x\mid a)=p(x\mid a)}$  over the whole support of ${\displaystyle u(a)}$ ; and we note that this result incorporates Bayes' theorem, if the new distribution ${\displaystyle u(a)}$  is in fact a δ function representing certainty that a has one particular value.

MDI can be seen as an extension of Laplace's Principle of Insufficient Reason, and the Principle of Maximum Entropy of E.T. Jaynes. In particular, it is the natural extension of the principle of maximum entropy from discrete to continuous distributions, for which Shannon entropy ceases to be so useful (see differential entropy), but the relative entropy continues to be just as relevant.

In the engineering literature, MDI is sometimes called the Principle of Minimum Cross-Entropy (MCE) or Minxent for short. Minimising relative entropy from m to p with respect to m is equivalent to minimizing the cross-entropy of p and m, since

${\displaystyle \mathrm {H} (p,m)=\mathrm {H} (p)+D_{\text{KL}}(p\parallel m),}$ 

which is appropriate if one is trying to choose an adequate approximation to p. However, this is just as often not the task one is trying to achieve. Instead, just as often it is m that is some fixed prior reference measure, and p that one is attempting to optimise by minimising ${\displaystyle D_{\text{KL}}(p\parallel m)}$  subject to some constraint. This has led to some ambiguity in the literature, with some authors attempting to resolve the inconsistency by redefining cross-entropy to be ${\displaystyle D_{\text{KL}}(p\parallel m)}$ , rather than ${\displaystyle \mathrm {H} (p,m)}$  ^{[citation needed]}.

Relationship to available work

 

Pressure versus volume plot of available work from a mole of argon gas relative

January 01, 1970