↑ arvau

Wikipedia / Kullback–Leibler divergence

In mathematical statistics, the Kullback–Leibler (KL) divergence (also called relative entropy and I-divergence),, is a type of statistical distance: a measure of how much an approximating probability distribution is different from a true probability distribution . Mathematically, it is defined as

A simple interpretation of the KL divergence of from is the expected excess surprisal from using the approximation instead of when the actual is . 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 and an approximating . Often, represents the data, the observations, or a measured probability distribution and distribution represents instead a theory, a model, a description, or another approximation of . However, sometimes the true distribution represents a model and the approximating distribution 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 , such as with the expectation–maximization algorithm (EM) and evidence lower bound (ELBO) 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 ",, which had already been defined and used by Harold Jeffreys in 1948. In , 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 . 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 and defined on the same sample space, the relative entropy from to is defined to be

which is equivalent to

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 only defined in this way if, for all (absolute continuity). Otherwise, it is often defined as everywhere, is infinite in extent. Analogous comments apply to the continuous and general measure cases defined below.

is zero the contribution of the corresponding term is interpreted as zero because

For distributions and of a continuous random variable, relative entropy is defined to be the integral

where and denote the probability density functions of and .

More generally, if and are probability measuress on a measurable space and is absolutely continuous with respect to , then the relative entropy from to is defined as

is the Radon–Nikodym derivative of with respect to , i.e. the unique almost everywhere defined function which exists because is absolutely continuous with respect to . Also we assume 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 for which densities and exist (meaning that and are both absolutely continuous with respect to then the relative entropy from to is given as

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 if information is measured in natss. Most formulas involving relative entropy hold regardless of the base of the logarithm.

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 from to . This reflects the asymmetry in Bayesian inference, which starts from a prior distribution and updates to the posterior is as the relative entropy of with respect to or the information gain from over .

Basic example

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. is the distribution on the right side of the figure, a discrete uniform distribution with the three possible outcomes .

are calculated as follows. This example uses the natural log with base e, designated to get results in nats (see units of information):

Interpretations

Statistics

In the field of statistics, the Neyman–Pearson lemma states that the most powerful way to distinguish between the two distributions and based on an observation . The KL divergence is the expected value of this statistic if is actually drawn from . Kullback motivated the statistic as an expected log likelihood ratio.

Coding

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 .

Inference

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 .

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 .

Information geometry

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 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, 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 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.

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 out of a set of possibilities over 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 : it is the excess entropy.

is the cross entropy of relative to is the entropy of (which is the same as the cross-entropy of P with itself).

can be thought of geometrically as a statistical distance, a measure of how far the distribution is from the distribution . Geometrically it is a divergence is itself such a measurement (formally a loss function agree more closely with our notion of distance, as the excess loss. The resulting function is asymmetric, and while this can be symmetrized (see ), the asymmetric form is more useful. See 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 certain related conditions, since it can be defined in terms of Kullback–Leibler divergence.

Properties

-almost everywhere, 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 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 is the absolute value of the derivative or more generally of the Jacobian. 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 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

  • is convex in the pair of probability measures

  • almost surely.

, so the series diverges.

Duality formula for variational inference

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

Examples

Multivariate normal distributions

Suppose that we have two multivariate normal distributions and with (non-singular) covariance matrices If the two distributions have the same dimension, , then the relative entropy between the distributions is as follows:

The logarithm in the last term must be taken to base e since all terms apart from the last are base- logarithms of expressions that are either factors of the density function or otherwise arise naturally. The equation therefore gives a result measured in nats yields the divergence in bits.

. Then with and ,

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):

For two univariate normal distributions and the above simplifies to

, this simplifies to:

Uniform distributions

). Then the information gain is:

Intuitively, the information gain to a bits would be needed to identify one element of a long stream.

Exponential family

The exponential family of distribution is given by

is sufficient statistics is the log-partition function.

is given by

.

For example, for the Poisson distribution is

is

is

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. 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, and while this can be symmetrized (see ), the asymmetry is an important part of the geometry.

It generates a topology on the space of probability distributions 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.

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 and . Specifically, up to first order one has (using the Einstein summation convention

in the , it changes only to second. More formally, as for any minimum, the first derivatives of the divergence vanish

and by the Taylor expansion one has up to second order

where the Hessian matrix of the divergence

must be positive semi-definite defines a (possibly degenerate) Riemannian metric on the parameter space, called the Fisher information metric.

Fisher information metric theorem

There is an associated theorem. satisfies the following regularity conditions:

where is independent of

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.

MAUVE Metric

MAUVE is a measure of the statistical gap between two text distributions, such as the difference between text generated by a model and human-written text. This measure is computed using Kullback–Leibler divergences between the two distributions in a quantized embedding space of a foundation model.

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

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

from a Kronecker delta — i.e. the number of extra bits that must be transmitted to identify .

Mutual information

The mutual information,

is the relative entropy of the joint probability distribution of the two marginal probability distributions — 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.

Shannon entropy

The Shannon entropy,

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 — i.e. less the expected number of bits saved, which would have had to be sent if the value of . 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

Conditional entropy

The conditional entropy,

is the number of bits which would have to be transmitted to identify from equally likely possibilities, less from — i.e. less the expected number of bits saved which would have had to be sent if the value of of given .

Cross entropy

When we have a set of possible events, coming from the distribution , 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 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 ), which will be equal to Shannon's Entropy of ). However, if we use a different probability distribution () 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 and .

The cross entropy between two probability distributions ( and ) 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 , rather than the "true" distribution . The cross entropy for two distributions and over the same probability space is thus defined as follows.

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

) for encoding the events because of using for constructing the encoding scheme instead of .

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 is discovered, it can be used to update the posterior distribution for using Bayes' theorem:

This distribution has a new entropy:

would have added an expected number of bits:

to the message length. This therefore represents the amount of useful information, or information gain, about .

, subsequently comes in, the probability distribution for , 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:

All one can say is that on average, 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.

Discrimination information

can also be interpreted as the expected discrimination information is true. Another name for this quantity, given to it by I. J. Good to be expected from each sample.

is not 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 (MDI): given new facts, a new distribution as possible.

over and , and subsequently learnt the true distribution of , then the relative entropy between the new joint distribution for and , and the earlier prior distribution would be:

the prior distribution for . (Note that often the later expected value is called the conditional relative entropy (or conditional Kullback–Leibler divergence is in fact a δ function representing certainty that 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 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 .

Relationship to available work

Surprisals add where probabilities multiply. The surprisal for an event of probability . If 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 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 (see also Gibbs inequality).

More generally the work available by relative entropy or net surprisal, 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.

Quantum information theory

For density matrices and on a Hilbert space, the quantum relative entropy from to is defined to be

In quantum information science over all separable states can also be used as a measure of entanglement in the state .

Relationship between models and reality

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.

Symmetrised divergence

also considered the symmetrized function:

which they referred to as the "divergence", though today the "KL divergence" refers to the asymmetric function (see for the evolution of the term). This function is symmetric and nonnegative, and had already been defined and used by Harold Jeffreys in 1948; it is accordingly called the Jeffreys divergence.

This quantity has sometimes been used for feature selection in classification problems, where and are the conditional Probability density functions 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.

-divergence,

which can be interpreted as the expected information gain about from discovering which probability distribution is drawn from, or respectively.

gives the Jensen–Shannon divergence, defined by

where is the average of the two distributions,

as the capacity of a noisy information channel with two inputs giving the output distributions and . The Jensen–Shannon divergence, like all -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:

Other notable measures of distance include the Hellinger distance, histogram intersection, Chi-squared statistic, quadratic form distance, match distance, Kolmogorov–Smirnov distance, and earth mover's distance.

Data differencing

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).

See also

References