Get Kullback%E2%80%93Leibler Divergence essential facts below. View Videos or join the Kullback%E2%80%93Leibler Divergence discussion. Add Kullback%E2%80%93Leibler Divergence to your PopFlock.com topic list for future reference or share this resource on social media.
Measurement of how one probability distribution is different from a second reference probability distribution
In mathematical statistics, the Kullback-Leibler divergence, (also called relative entropy), is a measure of how one probability distribution is different from a second, reference probability distribution. Applications include characterizing the relative (Shannon) entropy in information systems, randomness in continuous time-series, and information gain when comparing statistical models of inference. In contrast to variation of information, it is a distribution-wise asymmetric measure and thus does not qualify as a statistical metric of spread - it also does not satisfy the triangle inequality. In the simple case, a relative entropy of 0 indicates that the two distributions in question have identical quantities of information. In simplified terms, it is a measure of surprise, with diverse applications such as applied statistics, fluid mechanics, neuroscience and bioinformatics.
Introduction and context
Consider two probability distributions and . Usually, represents the data, the observations, or a measured probability distribution. Distribution represents instead a theory, a model, a description or an approximation of . The Kullback-Leibler divergence is then interpreted as the average difference of the number of bits required for encoding samples of using a code optimized for rather than one optimized for . Note that the roles of and can be reversed in some situations where that is easier to compute, such as with the Expectation-maximization (EM) algorithm and Evidence lower bound (ELBO) computations.
The relative entropy was introduced by Solomon Kullback and Richard Leibler in 1951 as the directed divergence between two distributions; Kullback preferred the term discrimination information. The divergence is discussed in Kullback's 1959 book, Information Theory and Statistics.
In other words, it is the expectation of the logarithmic difference between the probabilities and , where the expectation is taken using the probabilities . Relative entropy is defined only if for all , implies (absolute continuity). Whenever is zero the contribution of the corresponding term is interpreted as zero because
More generally, if and are probability measures over a set , and is absolutely continuous with respect to , then the relative entropy from to is defined as
where is the Radon-Nikodym derivative of with respect to , and provided the expression on the right-hand side exists. Equivalently (by the chain rule), this can be written as
which is the entropy of relative to . Continuing in this case, if is any measure on for which and exist (meaning that and are absolutely continuous with respect to ), then the relative entropy from to is given as
The logarithms in these formulae are taken to base 2 if information is measured in units of bits, or to base 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 in words. Often it is referred to as the divergence between and , but this fails to convey the fundamental asymmetry in the relation. Sometimes, as in this article, it may be described as the divergence of from or as the divergence fromto. This reflects the asymmetry in Bayesian inference, which starts from a prior and updates to the posterior. Another common way to refer to is as the relative entropy of with respect to.
Kullback gives the following example (Table 2.1, Example 2.1). Let and be the distributions shown in the table and figure. is the distribution on the left side of the figure, a binomial distribution with and . is the distribution on the right side of the figure, a discrete uniform distribution with the three possible outcomes , , or (i.e. ), each with probability .
In the context of machine learning, is often called the information gain achieved if would be used instead of which is currently used. By analogy with information theory, it is called the relative entropy of with respect to . In the context of coding theory, can be constructed by measuring the expected number of extra bits required to code samples from using a code optimized for rather than the code optimized for .
Expressed in the language of Bayesian inference, is a measure of the information gained by revising one's beliefs from the prior probability distribution to the posterior probability distribution. In other words, it is the amount of information lost when is used to approximate . In applications, typically represents the "true" distribution of data, observations, or a precisely calculated theoretical distribution, while typically represents a theory, model, description, or approximation of . In order to find a distribution that is closest to , we can minimize KL divergence and compute an information projection.
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 out of a set of possibilities can be seen as representing an implicit probability distribution over , where is the length of the code for 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 is used, compared to using a code based on the true distribution .
where is the cross entropy of and , and is the entropy of (which is the same as the cross-entropy of P with itself).
Relative entropy can be thought of as something like a measurement of how far the distribution Q is from the distribution P. The cross-entropy is itself such a measurement, but it has the defect that isn't zero, so we subtract to make agree more closely with our notion of distance. (Unfortunately it still isn't symmetric.)
Relative entropy relates to "rate function" in the theory of large deviations.
a result known as Gibbs' inequality, with equals zero if and only ifalmost everywhere. The entropy thus sets a minimum value for the cross-entropy , the expected number of bits required when using a code based on rather than ; and the Kullback-Leibler divergence therefore represents the expected number of extra bits that must be transmitted to identify a value drawn from , if a code is used corresponding to the probability distribution , rather than the "true" distribution .
no upper-bound exists for the general case. However, it is shown that if and are two discrete probability distributions built by distributing the same discrete quantity, then the maximum value of can be calculated.
Relative entropy remains well-defined for continuous distributions, and furthermore is invariant under parameter transformations. For example, if a transformation is made from variable to variable , then, since and the relative entropy may be rewritten:
where and . 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 is a dimensioned variable, and are also dimensioned, since e.g. 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 (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 are independent distributions, with the joint distribution , and likewise, then
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 yields the divergence in bits.
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):
Relative entropy is directly related to the Fisher information metric. This can be made explicit as follows. Assume that the probability distributions and are both parameterized by some (possibly multi-dimensional) parameter . Consider then two close by values of and so that the parameter differs by only a small amount from the parameter value . Specifically, up to first order one has (using the Einstein summation convention)
with a small change of in the direction, and the corresponding rate of change in the probability distribution. Since relative entropy has an absolute minimum 0 for , i.e. , it changes only to second order in the small parameters . More formally, as for any minimum, the first derivatives of the divergence vanish
is the relative entropy of the probability distribution from a Kronecker delta representing certainty that -- i.e. the number of extra bits that must be transmitted to identify if only the probability distribution is available to the receiver, not the fact that .
is the relative entropy of the product of the two marginal probability distributions from the joint probability distribution -- i.e. the expected number of extra bits that must be transmitted to identify and if they are coded using only their marginal distributions instead of the joint distribution. Equivalently, if the joint probability is known, it is the expected number of extra bits that must on average be sent to identify if the value of is not already known to the receiver.
is the number of bits which would have to be transmitted to identify from equally likely possibilities, less the relative entropy of the uniform distribution on the random variates of , , from the true distribution -- i.e. less the expected number of bits saved, which would have had to be sent if the value of were coded according to the uniform distribution rather than the true distribution .
is the number of bits which would have to be transmitted to identify from equally likely possibilities, less the relative entropy of the product distribution from the true joint distribution -- i.e. less the expected number of bits saved which would have had to be sent if the value of were coded according to the uniform distribution rather than the conditional distribution of given .
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 ). 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.
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 ) for encoding the events because of using q for constructing the encoding scheme instead of p.
which may be less than or greater than the original entropy . However, from the standpoint of the new probability distribution one can estimate that to have used the original code based on instead of a new code based on would have added an expected number of bits:
to the message length. This therefore represents the amount of useful information, or information gain, about , that has been learned by discovering .
If a further piece of data, , subsequently comes in, the probability distribution for can be updated further, to give a new best guess . If one reinvestigates the information gain for using rather than , it turns out that it may be either greater or less than previously estimated:
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 , 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. When posteriors are approximated to be Gaussian distributions, a design maximising the expected relative entropy is called Bayes d-optimal.
Relative entropy can also be interpreted as the expected discrimination information for over : the mean information per sample for discriminating in favor of a hypothesis against a hypothesis , when hypothesis is true. Another name for this quantity, given to it by I. J. Good, is the expected weight of evidence for over to be expected from each sample.
The expected weight of evidence for over is not the same as the information gain expected per sample about the probability distribution of the hypotheses,
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 should be chosen which is as hard to discriminate from the original distribution as possible; so that the new data produces as small an information gain as possible.
For example, if one had a prior distribution over and , and subsequently learnt the true distribution of was , then the relative entropy between the new joint distribution for and , , and the earlier prior distribution would be:
i.e. the sum of the relative entropy of the prior distribution for from the updated distribution , plus the expected value (using the probability distribution ) of the relative entropy of the prior conditional distribution from the new conditional distribution . (Note that often the later expected value is called the conditional relative entropy (or conditional Kullback-Leibler divergence) and denoted by ) This is minimized if over the whole support of ; and we note that this result incorporates Bayes' theorem, if the new distribution is in fact a ? function representing certainty that has one particular value.
In the engineering literature, MDI is sometimes called the Principle of Minimum Cross-Entropy (MCE) or Minxent for short. Minimising relative entropy from to with respect to is equivalent to minimizing the cross-entropy of and , since
which is appropriate if one is trying to choose an adequate approximation to . However, this is just as often not the task one is trying to achieve. Instead, just as often it is that is some fixed prior reference measure, and that one is attempting to optimise by minimising 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 , rather than .
Relationship to available work
Pressure versus volume plot of available work from a mole of argon gas relative to ambient, calculated as times the Kullback-Leibler divergence.
Surprisals add where probabilities multiply. The surprisal for an event of probability is defined as . If is then surprisal is in nats, bits, or so that, for instance, there are bits of surprisal for landing all "heads" on a toss of coins.
Best-guess states (e.g. for atoms in a gas) are inferred by maximizing the average surprisal (entropy) for a given set of control parameters (like pressure or volume ). This constrained entropy maximization, both classically and quantum mechanically, minimizes Gibbs availability in entropy units where is a constrained multiplicity or partition function.
When temperature is fixed, free energy () is also minimized. Thus if and number of molecules are constant, the Helmholtz free energy (where is energy and is entropy) is minimized as a system "equilibrates." If and are held constant (say during processes in your body), the Gibbs free energy 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 and pressure is where and (see also Gibbs inequality).
More generally the work available relative to some ambient is obtained by multiplying ambient temperature by relative entropy or net surprisal defined as the average value of where 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 and is thus , where relative entropy
The resulting contours of constant relative entropy, shown 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 flame-powered air-conditioning or in the unpowered device to convert boiling-water to ice-water discussed here. Thus relative entropy measures thermodynamic availability in bits.
Just as relative entropy of "actual from ambient" measures thermodynamic availability, relative entropy of "reality from a model" is also useful even if the only clues we have about reality are some experimental measurements. In the former case relative entropy 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 selecting a statistical model via Akaike information criterion are particularly well described in papers and a book by Burnham and Anderson. In a nutshell the relative entropy of reality from a model may be estimated, to within a constant additive term, by a function of the deviations observed between data and the model's predictions (like the mean squared deviation) . Estimates of such divergence for models that share the same additive term can in turn be used to select among models.
When trying to fit parametrized models to data there are various estimators which attempt to minimize relative entropy, such as maximum likelihood and maximum spacing estimators.
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 and are the conditional pdfs of a feature under two different classes. In the Banking and Finance industries, this quantity is referred to as Population Stability Index (PSI), and is used to assess distributional shifts in model features through time.
An alternative is given via the divergence,
which can be interpreted as the expected information gain about from discovering which probability distribution is drawn from, or , if they currently have probabilities and respectively.[clarification needed]
can also be interpreted as the capacity of a noisy information channel with two inputs giving the output distributions and . The Jensen-Shannon divergence, like all f-divergences, is locally proportional to the Fisher information metric. It is similar to the Hellinger metric (in the sense that it induces the same affine connection on a statistical manifold).
Furthermore, the Jensen-Shannon divergence can be generalized using abstract statistical M-mixtures relying on an abstract mean M.
Relationship to other probability-distance measures
There are many other important measures of probability distance. Some of these are particularly connected with relative entropy. For example:
Just 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).
^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.