 Kullback–Leibler divergence

In probability theory and information theory, the Kullback–Leibler divergence^{[1]}^{[2]}^{[3]} (also information divergence, information gain, relative entropy, or KLIC) is a nonsymmetric measure of the difference between two probability distributions P and Q. KL measures the expected number of extra bits required to code samples from P when using a code based on Q, rather than using a code based on P. Typically P represents the "true" distribution of data, observations, or a precisely calculated theoretical distribution. The measure Q typically represents a theory, model, description, or approximation of P.
Although it is often intuited as a metric or distance, the KL divergence is not a true metric — for example, it is not symmetric: the KL from P to Q is generally not the same as the KL from Q to P.
KL divergence is a special case of a broader class of divergences called fdivergences. Originally introduced by Solomon Kullback and Richard Leibler in 1951 as the directed divergence between two distributions, it is not the same as a divergence in calculus. However, the KL divergence can be derived from the Bregman divergence.
Definition
For probability distributions P and Q of a discrete random variable their K–L divergence is defined to be
In words, it is the average of the logarithmic difference between the probabilities P and Q, where the average is taken using the probabilities P. The KL divergence is only defined if P and Q both sum to 1 and if Q(i) > 0 for any i such that P(i) > 0. If the quantity 0log 0 appears in the formula, it is interpreted as zero.
For distributions P and Q of a continuous random variable, KLdivergence is defined to be the integral:^{[4]}
where p and q denote the densities of P and Q.
More generally, if P and Q are probability measures over a set X, and Q is absolutely continuous with respect to P, then the Kullback–Leibler divergence from P to Q is defined as
where is the Radon–Nikodym derivative of Q with respect to P, and provided the expression on the righthand side exists. Likewise, if P is absolutely continuous with respect to Q, then
which we recognize as the entropy of P relative to Q. Continuing in this case, if μ is any measure on X for which and exist, then the Kullback–Leibler divergence from P to Q is given as
The logarithms in these formulae are 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 the KL divergence hold irrespective of log base.
In this article, this will be referred to as the divergence from P to Q, although some authors call it the divergence "from Q to P" and others call it the divergence "between P and Q" (though note it is not symmetric as this latter terminology implies). Care must be taken due to the lack of standardization in terminology.^{[citation needed]}
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} out of a set of possibilities X can be seen as representing an implicit probability distribution q(x_{i}) = 2^{−li} over X, where l_{i} is the length of the code for x_{i} in bits. Therefore, KL divergence can be interpreted as the expected extra messagelength 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.
where H(P,Q) is called the cross entropy of P and Q, and H(P) is the entropy of P.
Properties
The Kullback–Leibler divergence is always nonnegative,
a result known as Gibbs' inequality, with D_{KL}(PQ) zero if and only if P = Q. The entropy H(P) thus sets a minimum value for the crossentropy H(P,Q), the expected number of bits required when using a code based on Q rather than P; and the KL 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.
The Kullback–Leibler divergence remains welldefined for continuous distributions, and furthermore is invariant under parameter transformations. For example, if a transformation is made from variable x to variable y(x), then, since P(x)dx=P(y)dy and Q(x)dx=Q(y)dy the Kullback–Leibler divergence may be rewritten:
where y_{a} = y(x_{a}) and 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 Kullback–Leibler divergence produces a dimensionally consistent quantity, since if x is a dimensioned variable, P(x) and Q(x) are also dimensioned, since e.g. 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^{[5]} (such as selfinformation or Shannon entropy), which can become undefined or negative for nondiscrete probabilities.
The Kullback–Leibler divergence is additive for independent distributions in much the same way as Shannon entropy. If P_{1},P_{2} are independent distributions, with the joint distribution P(x,y) = P_{1}(x)P_{2}(y), and Q,Q_{1},Q_{2} likewise, then
 .
Relation to metrics
One might be tempted to call it a "distance metric" on the space of probability distributions, but this would not be correct as the Kullback–Leibler divergence is not symmetric – that is, , – nor does it satisfy the triangle inequality. Still, being a premetric, it generates a topology on the space of generalized probability distributions, of which probability distributions proper are a special case. More concretely, if is a sequence of distributions such that
then it is said that . Pinsker's inequality entails that , where the latter stands for the usual convergence in total variation.
Following Rényi (1970, 1961)^{[6]}^{[7]} the term is sometimes also called the information gain about X achieved if P can be used instead of Q. It is also called the relative entropy, for using Q instead of P.
Relation to other quantities of information theory
Many of the other quantities of information theory can be interpreted as applications of the KL divergence to specific cases.
The selfinformation,
is the KL divergence of the probability distribution P(i) from a Kronecker delta representing certainty that i=m — i.e. the number of extra bits that must be transmitted to identify i if only the probability distribution P(i) is available to the receiver, not the fact that i=m.
The mutual information,
is the KL divergence of the product P(X)P(Y) of the two marginal probability distributions from the joint probability distribution P(X,Y) — 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 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.
The Shannon entropy,
is the number of bits which would have to be transmitted to identify X from N equally likely possibilities, less the KL divergence of the uniform distribution P_{U}(X) from the true distribution 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 P_{U}(X) rather than the true distribution P(X).
The conditional entropy,
is the number of bits which would have to be transmitted to identify X from N equally likely possibilities, less the KL divergence of the product distribution P_{U}(X) P(Y) from the true joint distribution 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 P_{U}(X) rather than the conditional distribution P(XY) of X given Y.
The cross entropy between two probability distributions 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:
KL divergence and Bayesian updating
In Bayesian statistics the KL divergence can be used as a measure of the information gain in moving from a prior distribution to a posterior distribution. If some new fact Y = y is discovered, it can be used to update the probability distribution for X from p(xI) to a new posterior probability distribution p(xy,I) using Bayes' theorem:
This distribution has a new entropy
which may be less than or greater than the original entropy H(p(·I)). However, from the standpoint of the new probability distribution one can estimate that to have used the original code based on p(xI) instead of a new code based on p(xy,I) would have added an expected number of bits
to the message length. This therefore represents the amount of useful information, or information gain, about X, that we can estimate has been learned by discovering Y = y.
If a further piece of data, Y_{2} = y_{2}, subsequently comes in, the probability distribution for x can be updated further, to give a new best guess p(xy_{1},y_{2},I). If one reinvestigates the information gain for using p(xy_{1},I) rather than p(xI), it turns out that it may be either greater or less than previously estimated:
 may be ≤ or > than
and so the combined information gain does not obey the triangle inequality:
 may be <, = or > than
All one can say is that on average, averaging using p(y_{2}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 KL divergence between the prior and the posterior.^{[8]} When posteriors are approximated to be Gaussian distributions, a design maximising the expected KL divergence is called Bayes doptimal.
Discrimination information
The Kullback–Leibler divergence D_{KL}( p(xH_{1})  p(xH_{0}) ) can also be interpreted as the expected discrimination information for H_{1} over H_{0}: the mean information per sample for discriminating in favor of a hypothesis H_{1} against a hypothesis H_{0}, when hypothesis H_{1} is true.^{[9]} Another name for this quantity, given to it by I.J. Good, is the expected weight of evidence for H_{1} over H_{0} to be expected from each sample.
The expected weight of evidence for H_{1} over H_{0} is not the same as the information gain expected per sample about the probability distribution p(H) of the hypotheses,
 D_{KL}( p(xH_{1})  p(xH_{0}) ) IG = D_{KL}( p(Hx)  p(HI) ).
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 Kullback–Leibler divergence 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 f_{0} as possible; so that the new data produces as small an information gain D_{KL}( f  f_{0} ) as possible.
For example, if one had a prior distribution p(x,a) over x and a, and subsequently learnt the true distribution of a was u(a), the Kullback–Leibler divergence between the new joint distribution for x and a, q(xa) u(a), and the earlier prior distribution would be:
i.e. the sum of the KL divergence of p(a) the prior distribution for a from the updated distribution u(a), plus the expected value (using the probability distribution u(a)) of the KL divergence of the prior conditional distribution p(xa) from the new conditional distribution q(xa). (Note that often the later expected value is called the conditional KL divergence (or conditional relative entropy) and denoted by D_{KL}(q(xa)p(xa))^{[10]}) This is minimised if q(xa) = p(xa) over the whole support of u(a); and we note that this result incorporates Bayes' theorem, if the new distribution 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 KL divergence continues to be just as relevant.
In the engineering literature, MDI is sometimes called the Principle of Minimum CrossEntropy (MCE) or Minxent for short. This is not entirely helpful. Minimising the KL divergence of m from p with respect to m is equivalent to minimizing the crossentropy of p and m, since
which is appropriate if one is trying to choose a least 'braindamaged' 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 D_{KL}(pm) subject to some constraint. This has led to some ambiguity in the literature, with some authors attempting to resolve the inconsistency by redefining crossentropy to be D_{KL}(pm), rather than H(p,m).
Relationship to available work
Surprisals^{[11]} add where probabilities multiply. The surprisal for an event of probability p is defined as s ≡ k ln[1/p]. If k is {1,1/ln 2,1.38×10^{−23}} then surprisal is in {nats, bits, or J/K} so that, for instance, there are N bits of surprisal for landing all "heads" on a toss of N coins.
Bestguess states (e.g. for atoms in a gas) are inferred by maximizing the averagesurprisal S (entropy) for a given set of control parameters (like pressure P or volume V). This constrained entropy maximization, both classically^{[12]} and quantum mechanically,^{[13]} minimizes Gibbs availability in entropy units^{[14]} A ≡ −kln Z where Z is a constrained multiplicity or partition function.
When temperature T is fixed, freeenergy (T × A) is also minimized. Thus if T, V and number of molecules N are constant, the Helmholtz free energy F ≡ U − TS (where U is energy) is minimized as a system "equilibrates." If T and P are held constant (say during processes in your body), the Gibbs free energy G ≡ U + PV − TS is minimized instead. The change in free energy under these conditions is a measure of available work that might be done in the process. Thus available work for an ideal gas at constant temperature T_{o} and pressure P_{o} is W = ΔG = NkT_{o}Θ[V/V_{o}] where V_{o} = NkT_{o}/P_{o} and Θ[x] ≡ x − 1 − ln x ≥ 0 (see also Gibbs inequality).
More generally^{[15]} the work available relative to some ambient is obtained by multiplying ambient temperature T_{o} by KLdivergence or netsurprisal ΔI ≥ 0, defined as the average value of k ln[p/p_{o}] where p_{o} is the probability of a given state under ambient conditions. For instance, the work available in equilibrating a monatomic ideal gas to ambient values of V_{o} and T_{o} is thus W =T_{o}ΔI, where KLdivergence ΔI = Nk(Θ[V/V_{o}] + ^{3}⁄_{2}Θ[T/T_{o}]). The resulting contours of constant KLdivergence, at right for a mole of Argon at standard temperature and pressure, for example put limits on the conversion of hot to cold as in flamepowered airconditioning or in the unpowered device to convert boilingwater to icewater discussed here.^{[16]} Thus KLdivergence measures thermodynamic availability in bits.
Quantum information theory
For density matrices P and Q on a Hilbert space the K–L divergence (or relative entropy as it is often called in this case) from P to Q is defined to be
In quantum information science the minimum of over all separable states Q can also be used as a measure of entanglement in the state P.
Relationship between models and reality
Just as KLdivergence of "ambient from actual" measures thermodynamic availability, KLdivergence of "model from reality" is also useful even if the only clues we have about reality are some experimental measurements. In the former case KLdivergence describes distance to equilibrium or (when multiplied by ambient temperature) the amount of available work, while in the latter case it tells you about surprises that reality has up its sleeve or, in other words, how much the model has yet to learn.
Although this tool for evaluating models against systems that are accessible experimentally may be applied in any field, its application to models in ecology via Akaike information criterion are particularly well described in papers^{[17]} and a book^{[18]} by Burnham and Anderson. In a nutshell the KLdivergence of a model from reality may be estimated, to within a constant additive term, by a function (like the squares summed) of the deviations observed between data and the model's predictions. Estimates of such divergence for models that share the same additive term can in turn be used to choose between models.
When trying to fit parametrized models to data there are various estimators which attempt to minimize Kullback–Leibler divergence, such as maximum likelihood and maximum spacing estimators.
Symmetrised divergence
Kullback and Leibler themselves actually defined the divergence as:
which is symmetric and nonnegative. This quantity has sometimes been used for feature selection in classification problems, where P and Q are the conditional pdfs of a feature under two different classes.
An alternative is given via the λ divergence,
which can be interpreted as the expected information gain about X from discovering which probability distribution X is drawn from, P or Q, if they currently have probabilities λ and (1 − λ) respectively.
The value λ = 0.5 gives the Jensen–Shannon divergence, defined by
where M is the average of the two distributions,
D_{JS} can also be interpreted as the capacity of a noisy information channel with two inputs giving the output distributions p and q. The Jensen–Shannon divergence is the square of a metric that is equivalent to the Hellinger metric, and the Jensen–Shannon divergence is also equal to onehalf the socalled Jeffreys divergence (Rubner et al., 2000; Jeffreys 1946).
Relationship to Hellinger distance
If P and Q are two probability measures, then the squared Hellinger distance is the quantity given by
Noting that , so that in particular, , we see that
Taking expectations with respect to Q, we get
Hence
Other probabilitydistance measures
Other measures of probability distance are the histogram intersection, Chisquared statistic, quadratic form distance, match distance, Kolmogorov–Smirnov distance, and earth mover's distance.^{[19]}
Data differencing
Main article: Data differencingJust as absolute entropy serves as theoretical background for data compression, relative entropy serves as theoretical background for data differencing – the absolute entropy of a set of data in this sense being the data required to reconstruct it (minimum compressed size), while the relative entropy of a target set of data, given a source set of data, is the data required to reconstruct the target given the source (minimum size of a patch).
See also
 Bregman divergence
 Deviance information criterion
 Bayesian information criterion
 Quantum relative entropy
 Information gain in decision trees
 Solomon Kullback and Richard Leibler
 Information theory and measure theory
References
 ^ Kullback, S.; Leibler, R.A. (1951). "On Information and Sufficiency". Annals of Mathematical Statistics 22 (1): 79–86. doi:10.1214/aoms/1177729694. MR39968.
 ^ S. Kullback (1959) Information theory and statistics (John Wiley and Sons, NY).
 ^ Kullback, S.; Burnham, K. P.; Laubscher, N. F.; Dallal, G. E.; Wilkinson, L.; Morrison, D. F.; Loyer, M. W.; Eisenberg, B. et al. (1987). "Letter to the Editor: The Kullback–Leibler distance". The American Statistician 41 (4): 340–341. JSTOR 2684769.
 ^ C. Bishop (2006). Pattern Recognition and Machine Learning. p. 55.
 ^ See the section "differential entropy  4" in Relative Entropy video lecture by Sergio Verdú NIPS 2009
 ^ A. Rényi (1970). Probability Theory. New York: Elsevier. Appendix, Sec.4. ISBN 0486458679.
 ^ A. Rényi (1961). "On measures of information and entropy". Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960. pp. 547–561. http://digitalassets.lib.berkeley.edu/math/ucb/text/math_s4_v1_article27.pdf.
 ^ Chaloner K. and Verdinelli I. (1995) Bayesian Experimental Design: A Review. Statistical Science 10 (3): 273304. doi:10.1214/ss/1177009939
 ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 14.7.2. KullbackLeibler Distance", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 9780521880688, http://apps.nrbook.com/empanel/index.html#pg=756
 ^ Thomas M. Cover, Joy A. Thomas (1991) Elements of Information Theory (John Wiley and Sons, New York, NY), p.22
 ^ Myron Tribus (1961) Thermodynamics and thermostatics (D. Van Nostrand, New York)
 ^ E. T. Jaynes (1957) Information theory and statistical mechanics, Physical Review 106:620
 ^ E. T. Jaynes (1957) Information theory and statistical mechanics II, Physical Review 108:171
 ^ J.W. Gibbs (1873) A method of geometrical representation of thermodynamic properties of substances by means of surfaces, reprinted in The Collected Works of J. W. Gibbs, Volume I Thermodynamics, ed. W. R. Longley and R. G. Van Name (New York: Longmans, Green, 1931) footnote page 52.
 ^ M. Tribus and E. C. McIrvine (1971) Energy and information, Scientific American 224:179–186.
 ^ P. Fraundorf (2007) Thermal roots of correlationbased complexity, Complexity 13:3, 18–26
 ^ Kenneth P. Burnham and David R. Anderson (2001) Kullback–Leibler information as a basis for strong inference in ecological studies, Wildlife Research 28:111–119.
 ^ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical InformationTheoretic Approach, Second Edition (Springer Science, New York) ISBN 9780387953649.
 ^ Rubner, Y., Tomasi, C., and Guibas, L. J., 2000. The Earth Mover's distance as a metric for image retrieval. International Journal of Computer Vision, 40(2): 99–121.
External links
Categories: Statistical theory
 Entropy and information
 Fdivergences
 Thermodynamics
Wikimedia Foundation. 2010.
Look at other dictionaries:
Divergence De KullbackLeibler — En théorie des probabilités et en théorie de l information, la divergence de Kullback Leibler[1] [2] (ou divergence K L ou encore Entropie relative) est une mesure de dissimilarité entre deux distributions de probabilités P et Q. Elle doit son… … Wikipédia en Français
Divergence de kullbackleibler — En théorie des probabilités et en théorie de l information, la divergence de Kullback Leibler[1] [2] (ou divergence K L ou encore Entropie relative) est une mesure de dissimilarité entre deux distributions de probabilités P et Q. Elle doit son… … Wikipédia en Français
Divergence de KullbackLeibler — En théorie des probabilités et en théorie de l information, la divergence de Kullback Leibler[1], [2] (ou divergence K L ou encore entropie relative) est une mesure de dissimilarité entre deux distributions de probabilités P et Q. Elle doit son… … Wikipédia en Français
Divergence (disambiguation) — Divergence can refer to: In mathematics: Divergence, a function that associates a scalar with every point of a vector field Divergence (computer science), a computation which does not terminate (or terminates in an exceptional state) Divergence… … Wikipedia
Divergence (statistics) — In statistics and information geometry, divergence or a contrast function is a function which establishes the “distance” of one probability distribution to the other on a statistical manifold. The divergence is a weaker notion than that of the… … Wikipedia
Jensen–Shannon divergence — In probability theory and statistics, the Jensen Shannon divergence is a popular method of measuring the similarity between two probability distributions. It is also known as information radius (IRad) [cite book author=Hinrich Schütze;… … Wikipedia
Solomon Kullback — Dr Solomon Kullback (b. Birth date19070403 d. Death date19940805) was a US cryptanalyst and mathematician.Kullback was one of the first three employees hired by William F. Friedman at the US Army s Signal Intelligence Service (SIS) in the… … Wikipedia
Richard Leibler — (March 18, 1914–October 25, 2003) was an American mathematician and cryptanalyst. While working at the NSA, he and Solomon Kullback formulated the Kullback Leibler divergence, a measure of similarity between probability distributions which has… … Wikipedia
Bregman divergence — In mathematics Bregman divergence or Bregman distance is similar to a metric, but does not satisfy the triangle inequality nor symmetry. There are two ways in which Bregman divergences are important. Firstly, they generalize squared Euclidean… … Wikipedia
Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… … Wikipedia