In mathematical statistics, the Kullback–Leibler (KL) divergence (also called relative entropy and I-divergence), denoted D KL ( P ∥ Q ) {\displaystyle D_{\text{KL}}(P\parallel Q)} , is a type of statistical distance: a measure of how much an approximating probability distribution Q is different from a true probability distribution P. Mathematically, it is defined as
D KL ( P ∥ Q ) = ∑ x ∈ X P ( x ) log P ( x ) Q ( x ) . {\displaystyle D_{\text{KL}}(P\parallel Q)=\sum _{x\in {\mathcal {X}}}P(x)\,\log {\frac {P(x)}{Q(x)}}{\text{.}}}
A simple interpretation of the KL divergence of P from Q is the expected excess surprisal from using the approximation Q instead of P when the actual is P. While it is a measure of how different two distributions are and is thus a distance in some sense, 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, 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). KL divergence is always a non-negative real number, with value 0 if and only if the two distributions in question are identical. 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, bioinformatics, and machine learning.
Introduction and context Consider two probability distributions, a true P and an approximating Q. Often, P represents the data, the observations, or a measured probability distribution and distribution Q represents instead a theory, a model, a description, or another approximation of P. However, sometimes the true distribution P represents a model and the approximating distribution Q represents (simulated) data that are intended to match the true distribution. The Kullback–Leibler divergence D KL ( P ∥ Q ) {\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 and the goal is to minimize D KL ( P ∥ Q ) {\displaystyle D_{\text{KL}}(P\parallel Q)} , such as with the expectation–maximization algorithm (EM) and evidence lower bound (ELBO) computations. This role-reversal approach exploits that D KL ( P ∥ Q ) = 0 {\displaystyle D_{\text{KL}}(P\parallel Q)=0} if and only if D KL ( Q ∥ P ) = 0 {\displaystyle D_{\text{KL}}(Q\parallel P)=0} and that, in many cases, reducing one has the effect of reducing the other.
Etymology The relative entropy was introduced by Solomon Kullback and Richard Leibler in Kullback & Leibler (1951) as "the mean information for discrimination between H 1 {\displaystyle H_{1}} and H 2 {\displaystyle H_{2}} per observation from μ 1 {\displaystyle \mu _{1}} ", where one is comparing two probability measures μ 1 , μ 2 {\displaystyle \mu _{1},\mu _{2}} , and H 1 , H 2 {\displaystyle H_{1},H_{2}} are the hypotheses that one is selecting from measure μ 1 , μ 2 {\displaystyle \mu _{1},\mu _{2}} (respectively). They denoted this by I ( 1 : 2 ) {\displaystyle I(1:2)} , and defined the "'divergence' between μ 1 {\displaystyle \mu _{1}} and μ 2 {\displaystyle \mu _{2}} " as the symmetrized quantity J ( 1 , 2 ) = I ( 1 : 2 ) + I ( 2 : 1 ) {\displaystyle J(1,2)=I(1:2)+I(2:1)} , which had already been defined and used by Harold Jeffreys in 1948. 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; Kullback preferred the term discrimination information. The term "divergence" is in contrast to a distance (metric), since the symmetrized divergence does not satisfy the triangle inequality. Numerous references to earlier uses of the symmetrized divergence and to other statistical distances are given in Kullback (1959). 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, X {\displaystyle {\mathcal {X}}} , the relative entropy from Q to P is defined to be
D KL ( P ∥ Q ) = ∑ x ∈ X P ( x ) log P ( x ) Q ( x ) , {\displaystyle D_{\text{KL}}(P\parallel Q)=\sum _{x\in {\mathcal {X}}}P(x)\,\log {\frac {P(x)}{Q(x)}}{\text{,}}}
which is equivalent to
D KL ( P ∥ Q ) = ( − ∑ x ∈ X P ( x ) log Q ( x ) ) − ( − ∑ x ∈ X P ( x ) log P ( x ) ) . {\displaystyle D_{\text{KL}}(P\parallel Q)=\left(-\sum _{x\in {\mathcal {X}}}P(x)\,\log Q(x)\right)-\left(-\sum _{x\in {\mathcal {X}}}P(x)\,\log P(x)\right){\text{.}}}
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, Q ( x ) = 0 {\displaystyle Q(x)=0} implies P ( x ) = 0 {\displaystyle P(x)=0} (absolute continuity). Otherwise, it is often defined as + ∞ {\displaystyle +\infty } , but the value + ∞ {\displaystyle \ +\infty \ } is possible even if Q ( x ) ≠ 0 {\displaystyle Q(x)\neq 0} everywhere, provided that X {\displaystyle {\mathcal {X}}} is infinite in extent. Analogous comments apply to the continuous and general measure cases defined below. Whenever P ( x ) {\displaystyle P(x)} is zero the contribution of the corresponding term is interpreted as zero because
lim x → 0 + x log ( x ) = 0 . {\displaystyle \lim _{x\to 0^{+}}x\,\log(x)=0{\text{.}}}
For distributions P and Q of a continuous random variable, relative entropy is defined to be the integral
D KL ( P ∥ Q ) = ∫ − ∞ ∞ p ( x ) log p ( x ) q ( x ) d x . {\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{-\infty }^{\infty }p(x)\,\log {\frac {p(x)}{q(x)}}\,dx{\text{.}}}
where p and q denote the probability density functions of P and Q. More generally, if P and Q are probability measures on a measurable space X , {\displaystyle {\mathcal {X}}\,,} and P is absolutely continuous with respect to Q, then the relative entropy from Q to P is defined as
D KL ( P ∥ Q ) = ∫ x ∈ X log d P ( x ) d Q ( x ) d P ( x ) , {\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}\log {\frac {dP(x)}{dQ(x)}}\,dP(x){\text{,}}}
where d P ( x ) d Q ( x ) {\displaystyle {\frac {dP(x)}{dQ(x)}}} is the Radon–Nikodym derivative of P with respect to Q, i.e. the unique Q almost everywhere defined function r on X {\displaystyle {\mathcal {X}}} such that d P ( x ) = r ( x ) d Q ( x ) {\displaystyle dP(x)=r(x)dQ(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
D KL ( P ∥ Q ) = ∫ x ∈ X d P ( x ) d Q ( x ) log d P ( x ) d Q ( x ) d Q ( x ) , {\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}{\frac {dP(x)}{dQ(x)}}\ \log {\frac {dP(x)}{dQ(x)}}\ dQ(x){\text{,}}}
which is the entropy of P relative to Q. Continuing in this case, if μ {\displaystyle \mu } is any measure on X {\displaystyle {\mathcal {X}}} for which densities p and q with d P ( x ) = p ( x ) d μ ( x ) {\displaystyle dP(x)=p(x)\,d\mu (x)} and d Q ( x ) = q ( x ) d μ ( x ) {\displaystyle dQ(x)=q(x)\,d\mu (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
D KL ( P ∥ Q ) = ∫ x ∈ X p ( x ) log p ( x ) q ( x ) d μ ( x ) . {\displaystyle D_{\text{KL}}(P\parallel Q)=\int _{x\in {\mathcal {X}}}p(x)\,\log {\frac {p(x)}{q(x)}}\ d\mu (x){\text{.}}}
Note that such a measure μ {\displaystyle \mu } for which densities can be defined always exists, since one can take μ = 1 2 ( P + Q ) {\textstyle \mu ={\frac {1}{2}}\left(P+Q\right)} although in practice it will usually be one that applies in the context such as counting measure for discrete distributions, or Lebesgue measure or a convenient variant thereof such as 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 D KL ( P ∥ Q ) {\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 distribution Q and updates to the posterior P. Another common way to refer to D KL ( P ∥ Q ) {\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 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 N = 2 {\displaystyle N=2} and p = 0.4 {\displaystyle p=0.4} . Q is the distribution on the right side of the figure, a discrete uniform distribution with the three possible outcomes x = 0, 1, 2 (i.e. X = { 0 , 1 , 2 } {\displaystyle {\mathcal {X}}=\{0,1,2\}} ), each with probability p = 1 / 3 {\displaystyle p=1/3} .
Relative entropies D KL ( P ∥ Q ) {\displaystyle D_{\text{KL}}(P\parallel Q)} and D KL ( Q ∥ P ) {\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):
D KL ( P ∥ Q ) = ∑ x ∈ X P ( x ) ln P ( x ) Q ( x ) = 9 25 ln 9 / 25 1 / 3 + 12 25 ln 12 / 25 1 / 3 + 4 25 ln 4 / 25 1 / 3 = 1 25 ( 32 ln 2 + 55 ln 3 − 50 ln 5 ) ≈ 0.0852996 , {\displaystyle {\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\sum _{x\in {\mathcal {X}}}P(x)\,\ln {\frac {P(x)}{Q(x)}}\\&={\frac {9}{25}}\ln {\frac {9/25}{1/3}}+{\frac {12}{25}}\ln {\frac {12/25}{1/3}}+{\frac {4}{25}}\ln {\frac {4/25}{1/3}}\\&={\frac {1}{25}}\left(32\ln 2+55\ln 3-50\ln 5\right)\\&\approx 0.0852996{\text{,}}\end{aligned}}}
D KL ( Q ∥ P ) = ∑ x ∈ X Q ( x ) ln Q ( x ) P ( x ) = 1 3 ln 1 / 3 9 / 25 + 1 3 ln 1 / 3 12 / 25 + 1 3 ln 1 / 3 4 / 25 = 1 3 ( − 4 ln 2 − 6 ln 3 + 6 ln 5 ) ≈ 0.097455 . {\displaystyle {\begin{aligned}D_{\text{KL}}(Q\parallel P)&=\sum _{x\in {\mathcal {X}}}Q(x)\,\ln {\frac {Q(x)}{P(x)}}\\&={\frac {1}{3}}\,\ln {\frac {1/3}{9/25}}+{\frac {1}{3}}\,\ln {\frac {1/3}{12/25}}+{\frac {1}{3}}\,\ln {\frac {1/3}{4/25}}\\&={\frac {1}{3}}\left(-4\ln 2-6\ln 3+6\ln 5\right)\\&\approx 0.097455{\text{.}}\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: log P ( Y ) − log Q ( Y ) {\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.
Coding In the context of coding theory, D KL ( P ∥ Q ) {\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, D KL ( P ∥ Q ) {\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, D KL ( P ∥ Q ) {\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.
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. 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 D KL ( P ∥ Q ) {\displaystyle D_{\text{KL}}(P\parallel Q)} does not equal D KL ( Q ∥ P ) {\displaystyle D_{\text{KL}}(Q\parallel P)} , and the asymmetry is an important part of the geometry. The infinitesimal form of relative entropy, specifically its Hessian, gives a metric tensor that equals the Fisher information metric; see § Fisher information metric. Fisher information metric on the certain probability distribution let determine the natural gradient for information-geometric optimization algorithms. Its quantum version is Fubini-study 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. 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. The application of Bregman divergence can be found in mirror descent.
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. This is a special case of a much more general connection between financial returns and divergence measures. Financial risks are connected to D KL {\displaystyle D_{\text{KL}}} via information geometry. 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. Extending this concept, relative entropy can be hypothetically utilised to identify the behaviour of informed investors, if one takes this to be represented by the magnitude and deviations away from the prior expectations of fund flows, for example.
Motivation
In information theory, the Kraft–McMillan theorem establishes that any directly decodable coding scheme for coding a message to identify one value x i {\displaystyle x_{i}} out of a set of possibilities X can be seen as representing an implicit probability distribution q ( x i ) = 2 − ℓ i {\displaystyle q(x_{i})=2^{-\ell _{i}}} over X, where ℓ i {\displaystyle \ell _{i}} is the length of the code for x i {\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.
D KL ( P ∥ Q ) = ∑ x ∈ X p ( x ) log 1 q ( x ) − ∑ x ∈ X p ( x ) log 1 p ( x ) = H ( P , Q ) − H ( P ) {\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 H ( P , Q ) {\displaystyle \mathrm {H} (P,Q)} is the cross entropy of Q relative to P and H ( P ) {\displaystyle \mathrm {H} (P)} is the entropy of P (which is the same as the cross-entropy of P with itself). The relative entropy D KL ( P ∥ Q ) {\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 H ( P , Q ) {\displaystyle H(P,Q)} is itself such a measurement (formally a loss function), but it cannot be thought of as a distance, since H ( P , P ) =: H ( P ) {\displaystyle H(P,P)=:H(P)} is not zero. This can be fixed by subtracting H ( P ) {\displaystyle H(P)} to make D KL ( P ∥ Q ) {\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. 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. Consequently, mutual information is the only measure of mutual dependence that obeys certai